неверное чтение размера 8 только при перефразировании хеш-таблицы в c - PullRequest
Новая
       30

неверное чтение размера 8 только при перефразировании хеш-таблицы в c

0 голосов

Недопустимое чтение происходит в моей функции HTSize в коде, но также происходит и в других функциях. Проблема возникает только тогда, когда хэш-таблица перефразируется. Вероятно, это связано с моей функцией HTCreate, но я не совсем уверен.

Я пытался использовать malloc и calloc, но ничего не получается. 

typedef char* KeyType;
typedef int HTItem;
typedef struct node{
    KeyType key;
    HTItem item;
    struct node *next;
}List;
typedef struct {
    List *head;
}TableEntry;
typedef TableEntry *HTHash;


int TABLESIZE = 10;

HTHash HTCreate(void)
{
//malloc
//      int i;
//      HTHash table = (HTHash)malloc(TABLESIZE*sizeof(TableEntry));
//      for(i=0;i<TABLESIZE;i++)
//          table[i].head = NULL;
//      return table;
//calloc    
        return calloc(TABLESIZE, sizeof(TableEntry));
}

int HTSize(HTHash hash)
{
    int i,count=0;
    List *temp; 
    for(i=0;i<TABLESIZE;i++)
    {
        if(hash[i].head != NULL)
        {
            count++;
            temp = hash[i].head->next;
            while(temp != NULL)
           {
                count++;
                temp = temp->next;
           }
        }   
    }
    return count;   
}

void HTInsert(HTHash hash, KeyType key, HTItem item)
{
    float a = 0.0;
    int index = h(key);
    int i;
    List *NewNode = (List*)malloc(sizeof(List));
    NewNode->key = key;
    NewNode->item = item;
    NewNode->next = NULL;
    if(hash[index].head == NULL)
        hash[index].head = NewNode;
    else
    {
        if(!strcmp(hash[index].head->key,key))
            hash[index].head->item = item;
        else
        {
            while(hash[index].head->next != NULL)
            {
                if(!strcmp(hash[index].head->next->key,key))
                {
                    hash[index].head->next->item = 
item;
                    break;
                }
                hash[index].head->next = hash[index].head- 
>next->next;
            }
            if(hash[index].head->next == NULL)
                hash[index].head->next = NewNode;
        }
    }
    a = (1.0 * HTSize(hash))/ TABLESIZE;
    if(a>=0.9)
    {
        printf("hash table is rehashing!\n");
        HTRehash(hash); 
    }
}

void HTRehash(HTHash hash)
{
    int i;
    HTHash temp = hash;
    int n = TABLESIZE;
    TABLESIZE = 2 * TABLESIZE;
    hash = HTCreate();
    for(i=0;i<n;i++)
    {
        List* list = temp[i].head;
        while(list!=NULL)
        {
            HTInsert(hash,list->key,list->item);
            list = list->next;
        }
    }
}

В HTSize, который запускается с valgrind, он дает мне 3 раза «неверное чтение размера 8».

1 Ответ

2 голосов
/ 02 июня 2019

Ваша проблема в том, что вы звоните HTRehash с одним указателем.Затем вы перераспределяете хеш-таблицу, но теперь вы не можете вернуть эту новую память.

Вы должны либо вызвать ее с двойным указателем, чтобы новая память была доступна вызывающей стороне, либо вы должны вернуть новый указатель,Последний более простой в общих чертах: 

HTHash HTRehash(HTHash hash)
{
    //...
    hash = HTCreate();
    //...
    return hash;
}

Я также отмечаю, что вы не освобождаете старую хеш-таблицу.

...