C Trie

trie.c

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

typedef struct Node {
  struct Node *children;
  size_t child_count;
  char value;
} Node;

Node *add_letter(Node *node, char letter) {
  for (size_t i = 0; i < node->child_count; i++) {
    if (node->children[i].value == letter) {
      return &node->children[i];
    }
  }
  node->child_count++;
  Node *next = malloc(sizeof(Node) * node->child_count);
  memcpy(next, node->children, sizeof(Node) * (node->child_count - 1));
  next[node->child_count - 1].value = letter;
  node->children = next;
  node->children[node->child_count - 1].child_count = 0;
  return &node->children[node->child_count - 1];
}

void add_string(Node *node, char *str) {
  for (int i = 0; i < strlen(str); i++) {
    node = add_letter(node, str[i]);
  }
}

int trie_size(Node *node, int sum) {
  sum += node->child_count;
  for (size_t i = 0; i < node->child_count; i++) {
    sum += trie_size(&node->children[i], 0);
  }
  return sum;
}

void clear_tree(Node *node) {
  for (size_t i = 0; i < node->child_count; i++) {
    if (node->child_count == 0) {
      free(node->children);
      node->value = 0;
      free(node);
    } else {
      clear_tree(&node->children[i]);
    }
  }
}

void print_trie(Node *node, char *p) {
  for (size_t i = 0; i < node->child_count; i++) {
    Node *n = &node->children[i];
    if (n->child_count == 0) {
      printf("%s%c\n", p, n->value);
    } else {
      char *np = malloc(sizeof(char) * (strlen(p) + 1));
      memset(np, 0, sizeof(char) * (strlen(p) + 1));
      strcat(np, p);
      strncat(np, &n->value, sizeof(char));
      print_trie(n, np);
      free(np);
    }
  }
}

int trie_contains(Node *node, char *str) {
  if (*str == '\0')
    return 1;
  for (size_t i = 0; i < node->child_count; i++) {
    if (node->children[i].value == *str)
      return trie_contains(&node->children[i], ++str);
  }
  return 0;
}

void parse_file(char *fname) {
  Node trie = {NULL, 0};
  FILE *fp = fopen(fname, "rb");
  if (fp == NULL) {
    printf("unable to read file\n");
    return;
  }
  char line[1024];
  size_t orig_sum = 0;
  while (!feof(fp) && fscanf(fp, "%s\n", line)) {
    orig_sum += strlen(line);
    add_string(&trie, line);
  }
  char *buf = (char*) malloc(sizeof(char) * (1 << 16));
  print_trie(&trie, buf);
  printf("%d\n", orig_sum);
  printf("%d\n", trie_size(&trie, 0));
  printf("%d\n", trie_contains(&trie, "blah"));
  clear_tree(&trie);
}

int main(int argc, char **argv) {
  if (argc == 2) {
    parse_file(argv[1]);
  } else {
    printf("Usage: ./trie wordlist.txt\n");
  }
  return 0;
}