c - 释放已用数据的内存会导致段错误

Question

我写了一个哈希表，它基本上由这两种结构组成:

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

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

dict.table 是一个多维数组，其中包含所有存储的键/值对，又是一个链表。

如果哈希表的一半已满，我会通过将大小加倍并重新哈希来扩展它:

dict *_dictRehash(dict *d) {
    int i;
    dict *_d;
    dictEntry *dit;

    _d = dictCreate(d->size * 2);

    for (i = 0; i < d->size; i++) {
        for (dit = d->table[i]; dit != NULL; dit = dit->next) {
            _dictAddRaw(_d, dit);
        }
    }

    /* FIXME memory leak because the old dict can never be freed */
    free(d); // seg fault

    return _d;
}

上面的函数使用旧哈希表中的指针并将其存储在新创建的哈希表中。释放旧的 dict d 时会发生段错误。

我如何才能释放旧的哈希表结构而不必再次为键/值对分配内存？

编辑，为了完整性:

dict *dictCreate(unsigned long size) {
    dict *d;

    d = malloc(sizeof(dict));
    d->size  = size;
    d->items = 0;
    d->table = calloc(size, sizeof(dictEntry*));

    return d;
}

void dictAdd(dict *d, void *key, void *value) {
    dictEntry *entry;

    entry = malloc(sizeof *entry);

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

    if ((((float)d->items) / d->size) > 0.5) d = _dictRehash(d);

    _dictAddRaw(d, entry);
}

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

    if (d->table[index]) {
        dictEntry *next, *prev;

        for (next = d->table[index]; next != NULL; next = next->next) {
            prev = next;

        }

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

Answer 1

1. 调试此问题的最佳方法是针对 valgrind 运行您的代码。

但是给你一些观点:

1. 当您free(d) 时，您期望更多的析构函数 调用您的struct dict，这将在内部释放分配给指向 dictEntry

的指针的内存

2. 为什么必须删除整个 has 表才能展开它？你有一个 next 指针，为什么不直接向它添加新的散列条目呢？

解决方案不是释放 d 而是通过分配更多 struct dictEntry 并将它们分配给适当的 next 来扩展 d 。

当收缩 d 时，您将必须遍历 next 以到达结尾，然后开始为内部的 struct dictEntry 释放内存你的 d。