hashmap 的动态数组访问冲突

Question

我在尝试实现的小哈希图 table 方面遇到问题。

map.h

typedef struct Map Map;

Map *map_create();
int map_set(Map *map, char *key, void *val);

map.c

const int MAP_INITIAL_SIZE = 100;

typedef struct MapPair MapPair;
struct MapPair
{
    char *key;
    void *val;
};

struct Map
{
    MapPair **table;
    int count;
    int limit;
};

Map *map_create(void)
{
    Map *map = (Map*)malloc(sizeof(Map));
    if (!map) return NULL;

    map->table = (MapPair**)malloc(MAP_INITIAL_SIZE * sizeof(MapPair));
    if (!map->table)
    {
        free(map);
        return NULL;
    }

    map->count = 0;
    map->limit = MAP_INITIAL_SIZE;

    return map;
}

void add(MapPair **context, int start, MapPair *pair, int limit)
{
    int i = start;
    while (context[i] != NULL && strcmp(context[i]->key, pair->key) != 0) // crashing here
    {
        i++;
        if (i == limit) i = 0;
    }
    context[i] = pair;
}

int map_set(Map *map, char *key, void *val)
{
    if (map->count >= map->limit / 2)
    {
        if (!expand(map)) return 0;
    }

    MapPair *pair = (MapPair*)malloc(sizeof(MapPair));
    if (!pair) return 0;

    pair->key = key;
    pair->val = val;

    add(map->table, hash(key, map->limit), pair, map->limit);

    ++map->count;
    return 1;
}

我最初是在 pelles c 中开发的，但是当我遇到问题时为了调试器而转向了 vs2013。然后在 vs2013 中，程序会在 add 函数处崩溃，但在 pelles c 中不会。我假设它与我计划以后能够扩展的动态数组有关。

谁能告诉我为什么当我尝试访问动态数组的索引时程序似乎崩溃了？

Answer 1

在添加函数中，您正在检查 table，直到到达 NULL 指针：

while (context[i] != N ...

但是当您分配这个 table 时，您永远不会将这些指针中的任何一个设置为 NULL:

map->table = (MapPair**)malloc(MAP_INITIAL_SIZE * sizeof(MapPair));

您应该将它们设置为 NULL：

for( size_t i = 0 ; i < MAP_INITIAL_SIZE ; i++ )
    map->table[i] = NULL ;

否则你将越界。

Answer 2

我不知道 Visual 可以编译纯 C 项目！无论如何，你的崩溃是由一个神奇的字符串引起的：http://en.wikipedia.org/wiki/Magic_number_(programming)

* 0xABABABAB : Used by Microsoft's HeapAlloc() to mark "no man's land" guard bytes after allocated heap memory
* 0xABADCAFE : A startup to this value to initialize all free memory to catch errant pointers
* 0xBAADF00D : Used by Microsoft's LocalAlloc(LMEM_FIXED) to mark uninitialised allocated heap memory
* 0xBADCAB1E : Error Code returned to the Microsoft eVC debugger when connection is severed to the debugger
* 0xBEEFCACE : Used by Microsoft .NET as a magic number in resource files
* 0xCCCCCCCC : Used by Microsoft's C++ debugging runtime library to mark uninitialised stack memory
* 0xCDCDCDCD : Used by Microsoft's C++ debugging runtime library to mark uninitialised heap memory
* 0xDEADDEAD : A Microsoft Windows STOP Error code used when the user manually initiates the crash.
* 0xFDFDFDFD : Used by Microsoft's C++ debugging heap to mark "no man's land" guard bytes before and after allocated heap memory
* 0xFEEEFEEE : Used by Microsoft's HeapFree() to mark freed heap memory

（SO 来源：In Visual Studio C++, what are the memory allocation representations?）

与 GCC（或我想象的 pelles）不同，Visual Studio 将未初始化的堆数组指针设置为 0xCDCDCDCD，而不是 NULL。因此，即使上下文未初始化，您对 context[i] != NULL returns 的检查也是正确的。

...这就是为什么显式总是比隐式好。

hashmap 的动态数组访问冲突

Access violation of dynamic array for hashmap

c

arrays

dynamic

hashmap