Anagram groups in C

gistfile1.txt

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

struct hash_struct {
  struct hash_struct **pprev;
  struct hash_struct *next;
};

#define HASH_TABLE_SIZE 2017 // use a prime number for the Kernie and Ritchie hash

static struct hash_struct *table[HASH_TABLE_SIZE];

static __inline__ void hash_add(struct hash_struct *entry, unsigned int key) {
  unsigned int h = key;
  struct hash_struct **head = &table[h];
  if( (entry->next = *head ) ) {
    entry->next->pprev = &entry->next;
  }
  *(entry->pprev = head) = entry;
}

static __inline__ void hash_del(struct hash_struct *entry) {
  if(entry->next) {
    entry->next->pprev = entry->pprev;
  }
  *entry->pprev = entry->next;
  entry->next = NULL; //just reset the entry
}

#define hash_entry(element, cast, field) \
  (cast*) ( (unsigned char*)element - (unsigned long) &((cast*)0)->field)

struct anagram_group {
  struct hash_struct hash;
  char **words;
  int num_words;
  char *key;
};

static unsigned int hash_key(char *key) {
  unsigned int h = 0;
  char *p = key;
  while(*p) {
    h = h*31 + *p;
    p++;
  }
  return h % HASH_TABLE_SIZE;
}

static char *frequency_hash(char *word) {
  int frequencyTable[26] = { [ 0 ... 25] = 0 };
  char *p = word;
  while(*p) {
    if(isupper(*p)) {
      frequencyTable[*p-'A']++;
    } else {
      frequencyTable[*p-'a']++;
    }
    p++;
  }
  // 4 bytes or counts for each (999)
  int space = sizeof(frequencyTable)/sizeof(frequencyTable[0]) * 4;
  char *res = calloc(sizeof(char), space);
  int i;
  int nbytes = 0;
  for(i = 0; i < sizeof(frequencyTable)/sizeof(frequencyTable[0]); i++) {
    nbytes += snprintf(res + nbytes, space - nbytes, "%s%d", i > 0 ? "-" : "", frequencyTable[i]);
  }

  return res;
}

static struct anagram_group *hash_find(char *key) {
  struct hash_struct *iter;
  unsigned int hash = hash_key(key);
  for(iter = table[hash]; iter; iter = iter->next) {
    struct anagram_group *group = hash_entry(iter, struct anagram_group, hash);
    if(!strcmp(group->key, key)) {
      return group;
    }
  }
  return NULL;
}

static void anagram_group_add(char *word, struct anagram_group ***groups, int *num_groups) {
  char *key = frequency_hash(word);
  struct anagram_group *group = hash_find(key);
  int new_group = 0;
  if(group == NULL) {
    group = calloc(1, sizeof(*group));
    group->key = strdup(key);
    new_group = 1;
  }
  group->words = realloc(group->words, sizeof(*group->words) * (group->num_words+1));
  group->words[group->num_words] = word;
  group->num_words++;
  if(new_group) {
    int cur_groups = *num_groups;
    *groups = realloc(*groups, sizeof(*groups) * (cur_groups+1));
    (*groups)[cur_groups] = group;
    *num_groups = cur_groups+1;
    hash_add(&group->hash, hash_key(key));
  }
  free(key);
}

static void anagram_groups(char **words, int num_words, struct anagram_group ***res, int *num_res) {
  int i;
  struct anagram_group **groups = NULL;
  int num_groups = 0;
  for(i = 0; i < num_words; i++) {
    anagram_group_add(words[i], &groups, &num_groups);
  }
  if(res && num_res) {
    *res = groups;
    *num_res = num_groups;
  }
}

int main() {
  char *words[] = {"eat", "tea", "tan", "ate", "bak", "ant"};
  struct anagram_group **groups = NULL;
  int num_groups = 0;
  anagram_groups(words, sizeof(words)/sizeof(words[0]), &groups, &num_groups);

  printf("[");
  for(int i = 0; i < num_groups; i++) {
    struct anagram_group *group = groups[i];
    printf("[");
    for(int j = 0; j < group->num_words; j++) {
      printf("%s%s", j > 0 ? "," : "", group->words[j]);
    }
    printf("]");
    free(group);
  }
  printf("]");
  free(groups);

  return 0;
}