Generic HashMap, unwanted output (C)

Question

I was writing a generic Hashtable library but I keep getting problems while I use functions like the lookup(). The expected output should be:

result = thirteen
result = thirteen
result = thirteen

but I get:

result = thirteen

and then it crashes. This problem seems to appear when I call the lookup() function more then one time, in fact if I call lookup() one time the code runs without any problem.

Each time I call the lookup() function, it creates a new HashMap, but I can't see any correlation between having more HashMaps and the problem. I tried to solve the problem using a free() method between each lookup() function, but the problem kept on appearing.

This is a portion of the original code:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

  typedef struct _Association Association;
  typedef struct _HashMap HashMap;
  typedef int (*HashMapCmp)(void*, void*);
  /*
    Hash Map
  */
  struct _HashMap{
    Association** array;
    int number_of_rows;
    int number_of_elements;
    HashMapCmp cmp_key;
  };

  /*
    element of the linked Hash Map
  */
  struct _Association{
    void* key;
    void* value;
    struct _Association* next;
  };

  /*
    hash function
  */
  unsigned int hash(HashMap* map, void* key){
      unsigned int hash_value = 0;
      hash_value = (*(int*)key * 1500) % map->number_of_rows;
      return hash_value;
  }

  /*
    inits a new Hash Map
  */
  HashMap* HashMap_new(int table_size, HashMapCmp cmp_key){
    HashMap* result = (HashMap*) malloc(sizeof(HashMap));
    result->number_of_rows = table_size;
    result->array = (Association**) malloc(sizeof(Association*) * result->number_of_rows);
    result->number_of_elements = 0;
    result->cmp_key = cmp_key;

    for(int i = 0; i < result->number_of_rows; i++){
      result->array[i] = malloc(sizeof(Association*));
      result->array[i] = NULL;
    }
    return result;
  }

  /*
    inserts a new association in my Hash Map
  */
  bool HashMap_insert(HashMap* map, void* key, void* value){
    if(map == NULL)
      return false;
    else{
      int index = hash(map, key);
      Association* as = malloc(sizeof(Association*));

      as->key = key;
      as->value = value;
      as->next = map->array[index];

      map->array[index] = as;
      map->number_of_elements++;

      return true;
    }
  }

  /*
    returns the value of the key passed by parameter
  */
  void* HashMap_lookup(HashMap* map, void* key){
    int index = hash(map, key);
    Association* tmp = map->array[index];

    while(tmp != NULL && map->cmp_key(tmp->key,key) != 0){
        tmp = tmp->next;
    }
    return tmp->value;
  }

  /*
    **************************************
    tests methods
  */

  /*
    int pointer (key)
  */
  int* int_new(int n) {
      int* result = (int*) malloc(sizeof(int));
      *result = n;
      return result;
  }

  /*
    char* pointer (value)
  */
  char** string_new(char* s) {
      char** result = (char**) malloc(sizeof(char*)*20);
      *result = s;
      return result;
  }

  /*
    Integers comparator -> obj1>obj2 = 1, obj1<obj2 = -1, obj1=obj2 = 0
  */

  static int compare_ints(int* obj1, int* obj2) {
      return *obj1 - *obj2;
  }

  /*
    creation of a 5 elements, high 4, HashMap
  */
  HashMap* create_five_elements_hash_map(){
    HashMap* map = HashMap_new(4, (HashMapCmp) compare_ints);

    HashMap_insert(map, int_new(0), string_new("zero"));
    HashMap_insert(map, int_new(13), string_new("thirteen"));
    HashMap_insert(map, int_new(22), string_new("twentytwo"));
    HashMap_insert(map, int_new(34), string_new("thirtyfour"));
    HashMap_insert(map, int_new(41), string_new("fortyone"));

    return map;
  }
  /*
    looking inside the Hashmap for the element
  */
  void test_lookup(){
    HashMap* map = create_five_elements_hash_map();
    char** str = (char**)HashMap_lookup(map,int_new(13));
    printf("result = %s\n", *str);
  }

  int main(){

    test_lookup();
    test_lookup();
    test_lookup();

    return 0;
  }

Answer 1

In HashMap_insert that line is erroned :

Association* as = malloc(sizeof(Association*));

and must be

Association* as = malloc(sizeof(Association));

or

Association* as = malloc(sizeof(*as));

else you allocate memory just for 1 pointer while Association needs enough space for 3 pointers, and just after when you set as fields you write out of the allocated block with an undefined behavior.

---

If you can install valgrind I highly encourage you to use it, for instance if I do on your definition under my PI4 here are a lot of messages :

pi@raspberrypi:/tmp $ gcc -g -Wall c.c
pi@raspberrypi:/tmp $ valgrind ./a.out
==6708== Memcheck, a memory error detector
==6708== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6708== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==6708== Command: ./a.out
==6708== 
==6708== Invalid write of size 4
==6708==    at 0x10628: HashMap_insert (c.c:64)
==6708==    by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708==    by 0x108F3: test_lookup (c.c:136)
==6708==    by 0x10943: main (c.c:143)
==6708==  Address 0x49e2244 is 0 bytes after a block of size 4 alloc'd
==6708==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6708==    by 0x1060B: HashMap_insert (c.c:61)
==6708==    by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708==    by 0x108F3: test_lookup (c.c:136)
==6708==    by 0x10943: main (c.c:143)
==6708== 
==6708== Invalid write of size 4
==6708==    at 0x10648: HashMap_insert (c.c:65)
==6708==    by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708==    by 0x108F3: test_lookup (c.c:136)
==6708==    by 0x10943: main (c.c:143)
==6708==  Address 0x49e2248 is 4 bytes after a block of size 4 alloc'd
==6708==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6708==    by 0x1060B: HashMap_insert (c.c:61)
==6708==    by 0x1081B: create_five_elements_hash_map (c.c:124)
==6708==    by 0x108F3: test_lookup (c.c:136)
==6708==    by 0x10943: main (c.c:143)
==6708== 
==6708== Invalid write of size 4
==6708==    at 0x10628: HashMap_insert (c.c:64)
==6708==    by 0x10843: create_five_elements_hash_map (c.c:125)
==6708==    by 0x108F3: test_lookup (c.c:136)
==6708==    by 0x10943: main (c.c:143)
==6708==  Address 0x49e2334 is 0 bytes after a block of size 4 alloc'd
==6708==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6708==    by 0x1060B: HashMap_insert (c.c:61)
==6708==    by 0x10843: create_five_elements_hash_map (c.c:125)
==6708==    by 0x108F3: test_lookup (c.c:136)
==6708==    by 0x10943: main (c.c:143)
...

but after the correction :

pi@raspberrypi:/tmp $ valgrind ./a.out
==6844== Memcheck, a memory error detector
==6844== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6844== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==6844== Command: ./a.out
==6844== 
result = thirteen
result = thirteen
result = thirteen
==6844== 
==6844== HEAP SUMMARY:
==6844==     in use at exit: 1,596 bytes in 66 blocks
==6844==   total heap usage: 67 allocs, 1 frees, 2,620 bytes allocated
==6844== 
==6844== LEAK SUMMARY:
==6844==    definitely lost: 108 bytes in 18 blocks
==6844==    indirectly lost: 1,488 bytes in 48 blocks
==6844==      possibly lost: 0 bytes in 0 blocks
==6844==    still reachable: 0 bytes in 0 blocks
==6844==         suppressed: 0 bytes in 0 blocks
==6844== Rerun with --leak-check=full to see details of leaked memory
==6844== 
==6844== For lists of detected and suppressed errors, rerun with: -s
==6844== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $ 

so you do not have undefined behavior anymore, but that does not means now the program does what you want, and but as you can see you have memory leaks, I encourage you to solve them, and to have more about them :

pi@raspberrypi:/tmp $ valgrind --leak-check=full --show-leak-kinds=definite ./a.out
==6967== Memcheck, a memory error detector
==6967== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6967== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==6967== Command: ./a.out
==6967== 
result = thirteen
result = thirteen
result = thirteen
==6967== 
==6967== HEAP SUMMARY:
==6967==     in use at exit: 1,596 bytes in 66 blocks
==6967==   total heap usage: 67 allocs, 1 frees, 2,620 bytes allocated
==6967== 
==6967== 4 bytes in 1 blocks are definitely lost in loss record 16 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x1073F: int_new (c.c:96)
==6967==    by 0x108FF: test_lookup (c.c:137)
==6967==    by 0x10943: main (c.c:143)
==6967== 
==6967== 4 bytes in 1 blocks are definitely lost in loss record 17 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x1073F: int_new (c.c:96)
==6967==    by 0x108FF: test_lookup (c.c:137)
==6967==    by 0x10947: main (c.c:144)
==6967== 
==6967== 4 bytes in 1 blocks are definitely lost in loss record 18 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x1073F: int_new (c.c:96)
==6967==    by 0x108FF: test_lookup (c.c:137)
==6967==    by 0x1094B: main (c.c:145)
==6967== 
==6967== 16 bytes in 4 blocks are definitely lost in loss record 37 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x1056F: HashMap_new (c.c:47)
==6967==    by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967==    by 0x108F3: test_lookup (c.c:136)
==6967==    by 0x10943: main (c.c:143)
==6967== 
==6967== 16 bytes in 4 blocks are definitely lost in loss record 38 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x1056F: HashMap_new (c.c:47)
==6967==    by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967==    by 0x108F3: test_lookup (c.c:136)
==6967==    by 0x10947: main (c.c:144)
==6967== 
==6967== 16 bytes in 4 blocks are definitely lost in loss record 39 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x1056F: HashMap_new (c.c:47)
==6967==    by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967==    by 0x108F3: test_lookup (c.c:136)
==6967==    by 0x1094B: main (c.c:145)
==6967== 
==6967== 512 (16 direct, 496 indirect) bytes in 1 blocks are definitely lost in loss record 55 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x104F7: HashMap_new (c.c:40)
==6967==    by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967==    by 0x108F3: test_lookup (c.c:136)
==6967==    by 0x10943: main (c.c:143)
==6967== 
==6967== 512 (16 direct, 496 indirect) bytes in 1 blocks are definitely lost in loss record 56 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x104F7: HashMap_new (c.c:40)
==6967==    by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967==    by 0x108F3: test_lookup (c.c:136)
==6967==    by 0x10947: main (c.c:144)
==6967== 
==6967== 512 (16 direct, 496 indirect) bytes in 1 blocks are definitely lost in loss record 57 of 57
==6967==    at 0x4847690: malloc (vg_replace_malloc.c:309)
==6967==    by 0x104F7: HashMap_new (c.c:40)
==6967==    by 0x107EF: create_five_elements_hash_map (c.c:122)
==6967==    by 0x108F3: test_lookup (c.c:136)
==6967==    by 0x1094B: main (c.c:145)
==6967== 
==6967== LEAK SUMMARY:
==6967==    definitely lost: 108 bytes in 18 blocks
==6967==    indirectly lost: 1,488 bytes in 48 blocks
==6967==      possibly lost: 0 bytes in 0 blocks
==6967==    still reachable: 0 bytes in 0 blocks
==6967==         suppressed: 0 bytes in 0 blocks
==6967== 
==6967== For lists of detected and suppressed errors, rerun with: -s
==6967== ERROR SUMMARY: 9 errors from 9 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $