How to dynamically add new data to a 2D Array?

Question

I want to implement a simple hash table using chaining collision handling. main.c:

int main ()
{
    const int size = 20;
    const int key = 30;
    const int data = 40;

    htable ht;
    htable_init(&ht, size);
    htable_insert(&ht, key, data);
    htable_insert(&ht, key+1, 22);
    htable_insert(&ht, key+2, 23);
    htable_insert(&ht, key+2, 23);
    assert(htable_get(&ht, key) == data); // Expected: 40
    int d = htable_get(&ht, 415);
    assert(htable_delete(&ht, key) == data); // Expected: 40
    assert(htable_delete(&ht, key) == 0); // Expected: 0
    htable_destroy(&ht);

    // It is recommended to do further tests on your own

    return 0;
}

htable.h:

struct _ht_entry_ {
    int key;
    int data;
    struct _ht_entry_* next;
    struct _ht_entry_* prev;
};
typedef struct _ht_entry_ ht_entry;

struct _htable_ {
    ht_entry** entries;
    int size;
};

htable.c:

void htable_init(htable* ht, int initial_size)
{
    ht->entries = (ht_entry**) calloc(initial_size, sizeof(ht_entry*));
    if(ht->entries)
    {
        ht->size = initial_size;
    }
}

void htable_insert(htable* ht, int key, int data)
{
    ht_entry* newEntry = malloc(sizeof(ht_entry));
    if(!newEntry)
        return;

    newEntry->data = data;
    newEntry->key = key;
    newEntry->next = NULL;
    newEntry->prev = NULL;

    ht_entry** entries = ht->entries;
    *entries = newEntry;
    newEntry->data = 1;
    *(entries + 1) = newEntry;
    newEntry->data = 2;
    *(entries + 2) = newEntry;
    newEntry->data = 3;
    *(entries + 3) = newEntry;
    newEntry->data = 4;
    int i = 0;
    for ( i = 0; i < 3; i++ ) {
        ht_entry* entry = *(entries + i);
        printf("*(entries + %d) : %p\n",  i, *(entries + i) );
    }
}  

In the example above I tried several ways to store the new entry in the HashTable but none of them worked. I also don't understand why the addresses are identical.

output:

*(entries + 0) : data: 2  0x60003a410
*(entries + 1) : data: 2  0x60003a410
*(entries + 2) : data: 2  0x60003a410

I also tried entries[0][0] = newEntry; because I thought ht_entry** entries; is a 2D Array but that didn't work either.

So how can I fill my HashTable?

Answer 1

Let's take a look at htable_insert. First you create a new entry on the heap and keep a pointer to it (named newEntry). Then you set your key and your data.

So far so good.

Now you dereference entries and set it's value to newEntry. Since entries is an array of pointers to pointers (2D is just a fancy name for this), dereferencing it gives you a pointer to ht_entry. What that means is that you don't copy the struct newEntry points to into the array, but you just save it's pointer. Then you proceed to do this 3 more times, each at the next greater index. In the end, entries is filled with 4 pointers to the same struct. Thus, when you print it's addresses, you get always the same address.