#include <limits.h>
#include <assert.h>
#include <stdlib.h>

/* number of (integral) values of an object of type char in your
 * implementation.
 */
#if COME_ON__A_BYTE_IS_A_BYTE
#define NUM_OF_CHARS 256
#else
#define NUM_OF_CHARS (CHAR_MAX - CHAR_MIN + 1)
#endif

struct node {
    struct node * table[NUM_OF_CHARS];
};

struct node root;

static void node_init(struct node * n) {
   assert(n != 0);
   int i;
   for(i = 0; i < NUM_OF_CHARS; ++i)
       n->table[i] = 0;
}

void dictionary_init() {
    node_init(&root);
}

static void node_clear(struct node * n) {
    int i;
    assert(n != 0);
    for(i = 1; i < NUM_OF_CHARS; ++i)
	if (n->table[i] != 0)
	    node_clear(n->table[i]);
    free(n);
}

void dictionary_clear() {
    int i;
    for(i = 1; i < NUM_OF_CHARS; ++i)
	if (root.table[i] != 0) {
	    node_clear(root.table[i]);
	    root.table[i] = 0;
	}
}

static size_t char_to_index(char c) {
    /* as it turns out, these two variants of this function are
     * exactly equivalent, although the second one lets the compiler
     * do the conversion, probably more efficiently.
     */
#if 0
    if (c < 0)
	return NUM_OF_CHARS + c;
    return c;
#else
    return (unsigned char)c;
#endif
}

int dictionary_add(const char * word) {
    struct node * n = &root;
    while (*word != 0) {
	if (n->table[char_to_index(*word)] == 0) {
	    struct node * new_node = malloc(sizeof(struct node));
	    if (!new_node)
		return 0;
	    node_init(new_node);
	    n->table[char_to_index(*word)] = new_node;
	}
	n = n->table[char_to_index(*word)];
	++word;
    }
    n->table[0] = n;
    return 1;
}

int dictionary_search(const char * word) {
    struct node * n = &root;
    while (*word != 0) {
	if (n->table[char_to_index(*word)] == 0)
	    return 0;
	n = n->table[char_to_index(*word)];
	++word;
    }
    return (n->table[0] != 0);
}