Access violation of dynamic array for hashmap

Question

I am having an issue with the table of a little hashmap I am trying to implement.

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;
}

I was originally developing in pelles c but moved to vs2013 for the debugger when I was experiencing problems. Then in vs2013 the program would crash at the add function but not in pelles c. I am assuming it has something to do with my dynamic array that I plan to be able to expand later.

Can anybody tell me why the program seems to crash when I try to access an index of the dynamic array?

in what header file are the functions expand() and hash() defined? — Ganesh Kamath - 'Code Frenzy', Jan 29 '15 at 14:01
It seems that you have one level of indirection too many. Your `Map` should contain a `MapPair *` and you should access the fields with `context[i].key`. (Your allocation for `map->table` reflects this pattern. You could also store pointers to pairs in the hash map, but that would introduce additional memory house-keeping.) — M Oehm, Jan 29 '15 at 14:07
@codefrenzy The same header, I omitted them to minimize the amount of code. I never even get to the expand part. — Carson, Jan 29 '15 at 14:07
You don't initialise the `map->table` to all `NULL`s and thus dereference garbage pointers. Not initialising makes the (principally useful) check for `NULL` useless. — M Oehm, Jan 29 '15 at 14:09
@MOehm How do I mark cells as empty if I use MapPair *. You can't assign NULL to them. — Carson, Jan 29 '15 at 14:47
@CarsonEvans: true, but you could make them have a `NULL` key, for example. — M Oehm, Jan 29 '15 at 14:58
@CarsonEvans: It's really a question of design. You can store pointers to pairs, which you then would have to allocate memory for. But then your allocation should be `map->table = malloc(n * sizeof(MapPair *));`, or maybe `map->table = malloc(n * sizeof(*map->table));` -- you need pointers to pairs. Or you can store the pairs directly in dynamic memory held by a `MapPair *`. — M Oehm, Jan 29 '15 at 15:03
@MOehm I like the idea of NULL keys. It makes some other things I am doing simpler. THANK YOU! — Carson, Jan 29 '15 at 15:47

score 2 · Accepted Answer · answered Jan 29 '15 at 14:12

In add function you are checking the table, until you reach the NULL pointer:

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

But when you allocate this table you never set any of those pointers to NULL:

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

You should set them to NULL:

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

Otherwise you will go out of bounds of that array.

score 1 · Answer 2 · edited May 23 '17 at 12:20

I didn't know Visual could compile pure C projects ! Anyway, your crash is caused by a magic string : 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 source : In Visual Studio C++, what are the memory allocation representations?)

Unlike GCC (or pelles I imagine), Visual Studio set uninitialized heap array pointers as 0xCDCDCDCD, not NULL. So your check of context[i] != NULL returns true even though context is not initialized.

... And that's why explicit is always better than implicit.

Access violation of dynamic array for hashmap

2 Answers2