CODEWITHSUNDEEP
cpointerslinked-listhashtable
pori
pori

Reputation: 83

Implementing a hash table in C

I'm having trouble to implement a simple list in C, the problem is the connection of the items via pointers.
The following piece of code is a snippet from a hashtable, which is supposed to store items with the same index in a list to avoid collisions.

typedef struct dictEntry {
    void *key;
    void *value;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictEntry **table;
    unsigned long size;
    unsigned long used;
} dict;

void dictAdd(dict *d, void *key, void *value) {
    int index = hash(key) & d->size;
    dictEntry *entry;

    entry = malloc(sizeof(entry));

    entry->key   = key;
    entry->value = value;
    entry->next  = 0;

    if (d->table[index]) {
        /* this is does not work */
        dictEntry *next;
        next = d->table[index];

        while (next) {
            next = next->next;
        }

        next = entry;
    } else {
        d->table[index] = entry;
        d->used++;
    }
}

My thinking was to iterate through every element of the list (next->next) and assign the pointer of entry to the last element (next = entry;).
After a few days of rewriting and moving parts of the code around, I still can't seem to find a solution.

Upvotes: 0

Views: 2414

Answers (3)

wildplasser
wildplasser

Reputation: 44250

entry = malloc(sizeof(entry));

should be:

entry = malloc(sizeof *entry);

Also dictAdd is overly complex. Using a pointer-to-pointer will help in this case:

void dictAdd(dict *d, void *key, void *value) {
    unsigned index;
    dictEntry **pp;

    index = hash(key) % d->size;
    if (!d->table[index]) d->used++;

    for (pp = &d->table[index]; *pp; pp = &(*pp)->next) {;}

    *pp = malloc(sizeof **pp);
     /* Omitted : handle ((*pp) == NULL) malloc failure here */
    (*pp)->key   = key;
    (*pp)->value = value;
    (*pp)->next  = NULL;
}

Upvotes: 1

Francis Upton IV
Francis Upton IV

Reputation: 19443

Have a look at your while loop. You are going until next becomes zero, but you really want the last entry that has the next pointer being zero. Fix that and it should be closer.

Upvotes: 0

Viktor Latypov
Viktor Latypov

Reputation: 14467

You should try to implement the linked list first.

Here's how I would implement the addition to the end (I've modified your code where you just overwrite the temporary "next" variable without modifying the list itself):

if (d->table[index]) {
    /* this should work*/
    dictEntry *next;
    dictEntry *prev = NULL;
    next = d->table[index];

    while (next) {
        prev = next;
        next = next->next;
    }

    // yes, add new entry as the "next" pointer to the "last" item
    prev->next = entry;
} else {

....

Upvotes: 5

Related Questions