An old boggle project's trie

Controller.m

#import "Controller.h"

#define ENABLE_INLINE
#ifdef ENABLE_INLINE
#define INLINE static inline
#else
#define INLINE
#endif

static inline int INDEX(char letter) {
    return letter - 'a';
}

typedef struct node {
    struct node *children[26];
    unsigned childrenSet:26;
    BOOL endOfWord;
} Node;

static Node *root;

INLINE void setIsEndOfWord(Node *node) {
    node->endOfWord = YES;
}

INLINE BOOL isEndOfWord(Node *node) {
    return node->endOfWord;
}

INLINE BOOL hasChild(Node *node, char letter) {
    return (node->childrenSet & (1 << INDEX(letter))) > 0;
}

INLINE void setHasChild(Node *node, char letter) {
    node->childrenSet |= (1 << INDEX(letter));
}

INLINE Node *child(Node *node, char child) {
    return node->children[INDEX(child)];
}

NSString *nodeDescription(Node *node) {
    NSMutableString *buffer = [NSMutableString string];
    if (isEndOfWord(node)) {
        [buffer appendFormat:@"End of word: "];
    }
    for (int i = 0; i < 26; ++i) {
        char letter = i + 'a';
        if (hasChild(node, letter)) {
            [buffer appendString:[NSString stringWithCString:&letter encoding:NSASCIIStringEncoding]];
        }
    }
    return buffer;
}

static const int poolSize = 131072;

typedef struct pool {
    int lastIdx;
    struct pool *previous;
    Node *buffer;
} Pool;

static Pool *currentPool;

INLINE void freePools() {
    while (currentPool) {
        Pool *p = currentPool;
        currentPool = currentPool->previous;
        free(p->buffer);
        free(p);
    }
    currentPool = NULL;
}

INLINE void createPool() {
    Pool *oldPool = currentPool;
    currentPool = malloc(sizeof(Pool));
    currentPool->buffer = malloc(poolSize * sizeof(Node));
    currentPool->previous = oldPool;
    currentPool->lastIdx = 0;
}

INLINE void *createNode() {
    currentPool->lastIdx++;
    if (currentPool->lastIdx == poolSize) {
        createPool();
    }
    Node *n = &(currentPool->buffer[currentPool->lastIdx]);
    n->endOfWord = NO;
    n->childrenSet = 0;
    return n;
}

INLINE Node *insertNode(Node *parent, char character)
{
    if (!hasChild(parent, character)) {
        Node *n = createNode();
        parent->children[INDEX(character)] = n;
        setHasChild(parent, character);
        return n;
    } else {
        return child(parent, character);
    }
}

@interface Controller (Haxxors)
- (void)buildWordTreeOfAwesomeness;
- (BOOL)wordInDictionary:(NSString *)word;
@end

@implementation Controller
- (void)awakeFromNib
{
    [textField setDelegate:self];
    [self buildWordTreeOfAwesomeness];
}

- (void)controlTextDidChange:(NSNotification *)aNotification
{
    if ([aNotification object] == textField) {
        [colorWell setColor:([self wordInDictionary:[textField stringValue]] ? [NSColor greenColor] : [NSColor redColor])];
    }
}

- (BOOL) testTree
{
    int mistakeCounter = 0;
    
    NSArray *words = [[NSString stringWithContentsOfURL:[[NSBundle mainBundle] URLForResource:@"dict" withExtension:@"txt"]
                                               encoding:NSUTF8StringEncoding
                                                  error:NULL]
                      componentsSeparatedByString:@"\n"];
    for (NSString *word in words)
    {
        if(![self wordInDictionary:word]) {
            NSLog(@"WRONG: %@", word);
            mistakeCounter++;
        }
    }
    NSLog(@"%d mistakes", mistakeCounter);
    return (mistakeCounter > 0) ? NO : YES;
}

- (BOOL)wordInDictionary:(NSString *)word
{
    NSUInteger len = [word length];
    if (len == 0) return NO;
    
    const char *c_word = [[word lowercaseString] UTF8String];
    Node *cur = root;
    
    for (NSUInteger idx = 0; idx < len; ++idx) {
        char character = c_word[idx];
        if (!hasChild(cur, character)) return NO;
        cur = child(cur, character);
    }
    
    return isEndOfWord(cur);
}

- (void)buildWordTreeOfAwesomeness
{
    createPool();
    root = createNode();
    NSTimeInterval start = [NSDate timeIntervalSinceReferenceDate];
    
    NSData *dictData = [[NSData alloc] initWithContentsOfURL:[[NSBundle mainBundle] URLForResource:@"dict" withExtension:@"txt"]
                                                     options:NSDataReadingMapped
                                                       error:NULL];
    const char *bytes = [dictData bytes];
    NSUInteger len = [dictData length];
    Node *currentNode = root;
    for (NSUInteger charIdx = 0; charIdx < len; ++charIdx) {
        char letter = bytes[charIdx];
        if (letter == '\n') {
            setIsEndOfWord(currentNode);
            currentNode = root;
        } else {
            currentNode = insertNode(currentNode, letter);
        }
    }
    setIsEndOfWord(currentNode); //clean up the last word
    [dictData release];
    NSTimeInterval end = [NSDate timeIntervalSinceReferenceDate];
    [self testTree];
    NSLog(@"Time %f total", end - start);
    //exit(0);
}
@end