/* 
 * By George Peter Staplin AKA imaginator on ##C 
 * This file implements a 16-way trie.
 * This is just a simple example.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

inline void *check_malloc (size_t s) {
 void *r = malloc(s);

 if (NULL == r) {
  perror ("check_malloc"); 
  exit (EXIT_FAILURE);
 }
 return r;
}

typedef struct trie_s {
 struct trie_s *ar[16];
 union {
  int i;
  void *ptr;
 } value;
} Trie;

inline Trie *create_trie () {
 Trie *t = check_malloc (sizeof (Trie));
 memset (t, 0, sizeof (Trie));
 return t;
}

/*
 * This returns 0 when the key is invalid, and 1 when it's valid,
 * and the result is set.
 */
int trie_get (Trie *t, unsigned char *key, int *result) {
 int i;
 while ('\0' != *key) {
  i = (*key & 15);
  t = t->ar[i];

  if (NULL == t) {
   return 0;
  }

  i = (*key >> 4);
  t = t->ar[i];

  if (NULL == t) {
   return 0;
  }

  ++key;
 }

 *result = t->value.i;
 return 1;
}

void trie_insert (Trie *t, unsigned char *key, int val) {
 int i;
 while ('\0' != *key) {
  i = (*key & 15);
  if (NULL == t->ar[i]) {
   t->ar[i] = create_trie ();
  }
  t = t->ar[i];
  i = (*key >> 4);
  if (NULL == t->ar[i]) {
   t->ar[i] = create_trie ();
  }
  t = t->ar[i];
  ++key;
 }
 t->value.i = val;
}

int main () {
 Trie *t;
 int a, b, c;

 t = create_trie ();
 trie_insert (t, "abc", 123);
 trie_insert (t, "abcdef", 456);
 trie_insert (t, "foobar", 789);
#if 1
 trie_get (t, "abc", &a);
 trie_get (t, "abcdef", &b);
 trie_get (t, "foobar", &c);
 printf ("abc %d abcdef %d foobar %d\n", a, b, c); 
#endif

 return EXIT_SUCCESS;
}