CODEWITHSUNDEEP
cmemory-leakshashtable
Paldan
Paldan

Reputation: 435

Hash table memory leak

I have a basic hash table implementation and when I run it, all is fine but valgrind says that I have lost some memory.

==11454== HEAP SUMMARY:
==11454==     in use at exit: 136 bytes in 1 blocks
==11454==   total heap usage: 10 allocs, 9 frees, 224 bytes allocated
==11454== 
==11454== LEAK SUMMARY:
==11454==    definitely lost: 136 bytes in 1 blocks
==11454==    indirectly lost: 0 bytes in 0 blocks
==11454==      possibly lost: 0 bytes in 0 blocks
==11454==    still reachable: 0 bytes in 0 blocks
==11454==         suppressed: 0 bytes in 0 blocks

I think it may be due to the way I'm allocating memory to my keys pointer. Here is my code for the table:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "htable.h"
#include "mylib.h"

struct htablerec {

  int capacity;
  int num_keys;
  char **keys;

};

static unsigned int htable_word_to_int(char *word) {
  unsigned int result = 0;
  while (*word != '\0') {
    result = (*word++ + 31 * result);
  }
  return result;
}

static unsigned int htable_hash(htable h, unsigned int i_key) {
  return i_key % h->capacity;
}

htable htable_new(int capacity) {

  int i;
  htable result = emalloc(sizeof *result);
  result->capacity = capacity;
  result->num_keys = 0;
  result->keys = emalloc(capacity * sizeof result->keys[0]);

  for (i = 0; i < capacity; i++) {

    result->keys[i] = NULL;
  }

  return result;
}

void htable_free(htable h) {

  int i;
l

  for (i = 0; i < h->capacity; i++) {

    free(h->keys[i]);
  }

  free(h);
}

int htable_insert(htable h, char *key) {

  unsigned int index = htable_word_to_int(key) % h->capacity;

  if (h->num_keys == h->capacity) {
    return 0;
  }
  for (;;) {

    if (NULL == h->keys[index]) {

      h->keys[index] = emalloc(sizeof(key));
      strcpy(h->keys[index], key);
      h->num_keys++;

      return 1;
    }
    if (strcmp(h->keys[index], key) == 0) {

      return 1;
    }
    index = htable_hash(h, index + 1);
  }
}

void htable_print(htable h, FILE *stream) {

  int i;

  for (i = 0; i < h->capacity; i++) {
    fprintf(stream, "%2d %s\n", i, h->keys[i] == NULL ? "" : h->keys[i]);
  }
}

The emalloc function just uses malloc and checks whether it allocated memory properly. Also, in my insert function, I emalloc the size of key. But key is a pointer, so shouldn't that give me the size of the pointer not of the word?

Upvotes: 1

Views: 1233

Answers (1)

WhozCraig
WhozCraig

Reputation: 66224

"I think it may be due to the way I'm allocating memory to my keys pointer."

Actually, you're allocating the keys pointer correctly. Its the lack of free()ing it that seems to be your downfall:

result->keys = emalloc(capacity * sizeof result->keys[0]);

needs to be free()ed somewhere. Such as:

void htable_free(htable h) 
{
   int i;
   for (i = 0; i < h->capacity; i++)
   {
       free(h->keys[i]);
   }
   free(h->keys); // NOTE: h->keys freed here.
   free(h);
}

Upvotes: 1

Related Questions