As a learning exercise, I'm trying to implement my own dictionary in C. My dictionary type definition is:

#define MAXCAP 24

static size_t primes[MAXCAP   2] = {
    1,
    101,       251,       509,         1021,      2039,     4093,     8191,
    16381,     32749,     65521,       131071,    262139,   524287,   1048573,
    2097143,   4194301,   8388593,     16777213,  33554393, 67108859, 134217689,
    268435399, 536870909, 10737441789, 2147483647};

typedef struct item_tag item;

struct item_tag {
    void *key;
    void *val;
    item *next;
};

typedef struct dict_tag {
    size_t cap; // capacity of the dict, which is used as an index for primes[]
    size_t size; // number of slots taken up out of the capacity of the dict 
    item **items;
    int (*eq) (const void *, const void *);
    int (*hash) (const void *, size_t n);
} dict;

My function for inserting a new entry to the dict is:

int dict_put(void *key, void *val, dict *d) {
    int i;
    item *kv;

    if (!dict_get(key, d)) {
        kv = malloc(sizeof(item));
        kv->key = key;
        kv->val = val;
        kv->next = d->items[(i = d->hash(key, primes[d->cap]))];
        d->items[i] = kv;
        if (!kv->next)
            d->size  ;
        if (d->size >= primes[d->cap] / 2)
            expand(d);
        return 1;
    }
    return 0;
}

Insertion works fine if I do not try to resize the dict using expand function which is defined as:

static void expand(dict *d) {
    int i;
    item *kv;
    dict *tmp;

    if (d->cap < MAXCAP) {
        tmp = malloc(sizeof(dict));
        init(d->cap   1, d->hash, d->eq, tmp);
        for (i = 0; i < d->cap; i  ) {
            for (kv = d->items[i]; kv; kv = kv->next)
                dict_put(kv->key, kv->val, tmp);
        }
        destroy_items(0, d);
        d->cap = tmp->cap;
        d->size = tmp->size;
        d->items = tmp->items; // looks like there are no items in dict after this step
        free(tmp);
    } else
        fprintf(stderr, "dict: max size reached.\n");
}

In the above function, I'm trying to create a new temporary larger dict and then copy the pointer to the new list of items to the old dict. The init function is:

static void init(size_t n, const int (*hash) (const void *, size_t n), const int (*eq) (const void *, const void *),
                 dict *d) {
    d->cap = n;
    d->size = 0;
    d->eq = eq;
    d->hash = hash;
    d->items = calloc(primes[d->cap], sizeof(item *));
}

CodePudding user response：

Your problem is on this line in the expand function

for (i = 0; i < d->cap; i  ) {

should be changed to

for (i = 0; i < primes[d->cap]; i  ) {