Simple trie implementation in C

linkedlist.c

#include <stdlib.h>

struct LinkedList
{
  void *value;
  struct LinkedList *next;
};

struct LinkedList *linked_list_new()
{
  struct LinkedList *new = calloc(sizeof(struct LinkedList), 1);
  return new;
}

void linked_list_append(struct LinkedList *list, void *value)
{
  if (list->next)
    return linked_list_append(list->next, value);
  struct LinkedList *next = linked_list_new();
  list->value = value;
  list->next = next;
}

void *linked_list_get(struct LinkedList *list, int index)
{
  if (index == 0)
    return list->value;
  if (list->next)
    return linked_list_get(list->next, index - 1);
  return NULL;
}

void linked_list_free(struct LinkedList *list)
{
  if (list->next)
    linked_list_free(list->next);
  free(list);
}

trie.c

#include "linkedlist.c"
#include <stdio.h>
#include <string.h>
#include <profileapi.h>

struct String
{
  char *data;
  int length;
};

struct Span
{
  struct String *string;
  int from;
  int to;
};

struct String *string_to_string(int length, char *data)
{
  struct String *string = malloc(sizeof(struct String));
  string->data = malloc(length);
  memcpy(string->data, data, length);
  string->length = length;
  return string;
};

int string_length(struct String *string)
{
  return string->length;
}

char string_char_at(struct String *string, int index)
{
  if (string->length < index)
    return 0;
  return string->data[index];
}

void string_free(struct String string)
{
  if (string.data)
    free(string.data);
}

struct Span span_from_string(struct String *string, int from, int to)
{
  struct Span span = {0, 0, 0};
  span.string = string;
  span.from = from;
  span.to = to;
  return span;
}

int span_length(struct Span span)
{
  return span.to - span.from;
}

char span_char_at(struct Span span, int index)
{
  return string_char_at(span.string, span.from + index);
}

struct Span span_sub_span(struct Span span, int from, int to)
{
  return span_from_string(span.string, span.from + from, span.to + to);
}

struct SearchTree
{
  char c;
  struct String *terminates;
  struct LinkedList *subTree;
};

struct SearchTree *search_tree_new()
{
  struct SearchTree *tree = malloc(sizeof(struct SearchTree));
  tree->subTree = 0;
  tree->terminates = 0;
  return tree;
}

struct SearchTree *search_tree_get_sub(struct SearchTree *tree, char v)
{
  if (!tree->subTree)
    tree->subTree = linked_list_new();

  struct SearchTree *sub = NULL;
  struct LinkedList *n = tree->subTree;
  while (n)
  {
    sub = n->value;
    if (!sub || sub->c == v)
      break;
    n = n->next;
  }
  if (!sub || sub->c != v)
  {
    struct SearchTree *new = search_tree_new();
    new->c = v;
    linked_list_append(tree->subTree, new);
    sub = new;
  }
  return sub;
}

void search_tree_insert(struct SearchTree *tree, struct Span span)
{
  if (span_length(span) == 0)
    return;

  if (span_length(span) == 1)
  {
    tree->terminates = span.string;
    return;
  }
  char v = span_char_at(span, 0);
  search_tree_insert(search_tree_get_sub(tree, v), span_sub_span(span, 1, 0));
}

void search_tree_get(struct SearchTree *tree, struct LinkedList *list, int limit, int *current)
{
  if (limit <= *current)
    return;
  if (tree->terminates)
  {
    linked_list_append(list, tree->terminates);
    *current += 1;
  }
  if (!tree->subTree)
    return;
  struct LinkedList *n = tree->subTree;
  while (n->next)
  {
    search_tree_get(n->value, list, limit, current);
    n = n->next;
  }
}

void search_tree_suggest(struct SearchTree *tree, struct LinkedList *list, struct Span span)
{
  if (!tree->subTree)
    return;
  if (span_length(span) == 0)
  {
    int a = 0;
    search_tree_get(tree, list, 20, &a);
    return;
  }
  char v = span_char_at(span, 0);
  search_tree_suggest(search_tree_get_sub(tree, v), list, span_sub_span(span, 1, 0));
}

void string_print(struct String *string)
{
  for (int i = 0; i < string->length; i++)
  {
    printf("%c", string->data[i]);
  }
}

const int ITEM_COUNT = 14000000;

void populate(struct SearchTree *tree)
{
  FILE *fp;
  char *line = malloc(50);
  int i = 1;

  fp = fopen("./test2.txt", "r");
  if (fp == NULL)
    exit(EXIT_FAILURE);

  while ((fgets(line, 50, fp)) != NULL)
  {
    int len = strlen(line) - 1;
    struct String *str = string_to_string(len, line);
    struct Span span = span_from_string(str, 0, len);
    search_tree_insert(tree, span);
    memset(line, 0, 50);
    i++;
  }

  fclose(fp);
  if (line)
    free(line);
}

int main()
{
  struct SearchTree *tree = search_tree_new();
  LARGE_INTEGER start, end;
  QueryPerformanceCounter(&start);
  populate(tree);
  QueryPerformanceCounter(&end);
  float ms = (float)(end.QuadPart - start.QuadPart) / 10000;
  printf("Populated in %0.2fms meaning %d/ms\n", ms, (int)(ITEM_COUNT / ms));
  while (1)
  {
    char *b = malloc(30);
    scanf("%s", b);
    int len = strlen(b);
    printf("Len: %d\n", len);
    struct String *str = string_to_string(len, b);
    struct Span span = span_from_string(str, 0, strlen(b));
    struct LinkedList *list = linked_list_new(span);
    QueryPerformanceCounter(&start);
    search_tree_suggest(tree, list, span);
    QueryPerformanceCounter(&end);
    float ms = (float)(end.QuadPart - start.QuadPart) / 10000;
    printf("Suggestion in %fms meaning %f/ms\n", ms, 1 / ms);
    int i = 0;
    while (linked_list_get(list, i))
    {
      string_print(linked_list_get(list, i));
      printf("\n");
      i++;
    }
    linked_list_free(list);
  }
  return 0;
}