c - 哈希表内存泄漏

Question

我有一个基本的哈希表实现，当我运行它时，一切都很好，但是valgrind 说我失去了一些内存。

==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

我认为这可能是由于我为键指针分配内存的方式所致。这是我的代码表:

#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]);
  }
}

emalloc 函数只是使用 malloc 并检查它是否正确分配内存。另外，在我的insert 函数，我 emalloc key 的大小。但是 key 是一个指针，所以不应该给我大小指针的不是单词的？

Answer 1

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

实际上，您正在正确分配键指针。它缺少 free() 似乎是你的垮台:

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

需要在某处free()ed。如:

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