How do I allocate memory for a hash table int C?

Question

i'm very new to C and very confused about memory allocation. I'm trying to create a hash table but don't know what to do in regards to memory, especially for the keys parameter which is an array of strings.

I'm trying to set the code up to scan in words from a text file and print their frequencies. I've read around a bit and found that I might need to use the realloc function but i'm not completely sure.

Any help is appreciated, thanks!

struct htablerec {
int capacity;
int num_keys;
int *frequencies;
char **keys;
};

htable htable_new(int capacity2){
  int i;
  htable result = malloc(sizeof *result);
  result->capacity = capacity2;
  result->num_keys = 0;

  result->frequencies = malloc(result->capacity * sizeof
            result->frequencies[0]);

  result->keys = malloc(result->capacity * sizeof(char *));

  for(i=0;i<result->capacity;i++){
    result->frequencies[i] = 0;
    result->keys[i] = malloc(1); 
    result->keys[i][0] = 0; 
  }
  return result;
}

int htable_insert(htable h, char *str){
  int i;
  int number = htable_word_to_int(str) % h->capacity;

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

    if(number == h->capacity){
      number = 0;
    }

    if(strlen(h->keys[number]) == 0){
      h->keys[number] = str;
      h->frequencies[number]++;

      h->num_keys++;
      return h->frequencies[number];

    }
    if(h->keys[number] == str){
      h->frequencies[number]++;
      return h->frequencies[number];
    }
    number++;
  }
  return 0;
}

Answer 1

You have several issues, but the main one is handling str, first of all, if you initialize the keys with empty strings - you need to free them when you assign to them, second - when you compare a cell, don't use ==, since that checks that the pointer is identical, use something like strcmp, and last - when you assign, depending on your implementation of the program - you may need to use something like strdup to copy str, otherwise you are pointing to same space as the pointer you got. e.g:

int htable_insert(htable h, char *str){
int i;
int number = htable_word_to_int(str) % h->capacity;

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

if(number == h->capacity){
  number = 0;
}

if(strlen(h->keys[number]) == 0){
  free(h->keys[number]);
  h->keys[number] = strdup(str);
  h->frequencies[number]++;

  h->num_keys++;
  return h->frequencies[number];

}
if(!strcmp(h->keys[number], str)){
  h->frequencies[number]++;
  return h->frequencies[number];
}
number++;
}
return 0;
}

This isn't perfect, it doeesn't handle memory allocation failures, or null pointers in the parameters, a better way would be to initialize the keys to NULL values - but it illustrates the main issues

Also - It isn't clear if the size needs to remain constant, if not you need logic to expand the hash table when it is full (detecting the condition, realloc'ing the frequencies and keys, redistributing the keys and frequencies according to the new capacity, handling realloc failures, etc.)