/* 
 * By George Peter Staplin AKA imaginator on ##C 
 * This file implements a 16-way trie.
 */
#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;
}

int trie_get (Trie *t, unsigned char *key) {
 int i;
 while ('\0' != *key) {
  i = (*key & 15);
  t = t->ar[i];
  i = (*key >> 4);
  t = t->ar[i];
  ++key;
 }
 return t->value.i;
}

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;

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

 return EXIT_SUCCESS;
}