#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>

typedef struct tnode { 
    char splitchar; 
    struct tnode *low;
    struct tnode *equal;
    struct tnode *high; 
    void *value;
} tnode; 

void *search(tnode *root, char *s) 
{
    tnode *p = root;
    while (p) { 
        if (*s < p->splitchar) {
            p = p->low; 
        } else if (*s == p->splitchar) {
            if (*s == '\0') {
                return p->value;
            } else {
                s++;
                p = p->equal; 
            }
        } else {
            p = p->high; 
        }
    } 
    return NULL; 
}

tnode *insert(tnode *p, char *s, char *value)
{
    if (p == NULL) { 
        p = (tnode *) calloc(1,sizeof(tnode)); 
        p->splitchar = *s; 
    } 
    if (*s < p->splitchar) {
        p->low = insert(p->low, s, value); 
    } else if (*s == p->splitchar) { 
        if (*s != '\0') {
            p->equal = insert(p->equal, ++s, value); 
        } else {
            p->value = value;
        }
    } else 
        p->high = insert(p->high, s, value); 
    return p; 
}

void traverse(tnode *p) 
{
    if (!p) return; 
    traverse(p->low); 
    if (p->splitchar) 
        traverse(p->equal); 
    else {
        //printf("%s\n", p->value); 
    }
    traverse(p->high); 
}

int main(int argc, char **argv)
{
    int i;
    tnode *root = NULL;
    FILE *samples = NULL;
    int fd = 0;
    struct stat stats;
    char *data = NULL;
    char *key = NULL;
    char *val = NULL;
    unsigned int expected_modulo = (32*2+2);
    unsigned int record_count = 0;

    assert(!stat("samples.txt", &stats) && "Failed to stat.");
    // double check the size
    assert(stats.st_size % expected_modulo == 0 && "File isn't right size.");
    record_count = stats.st_size / expected_modulo;
    assert(record_count > 0 && "No records in the file.");

    // open it to work with
    fd = open("samples.txt", O_RDONLY);
    assert(fd && "Couldn't open samples.txt.");

    // mmap it into ram
    data = (char *)mmap(NULL, stats.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    assert(data && "Failed to mmap the file.");

    // now to carve out our huge list from this file
    printf("processing %u records\n", record_count);
    root = insert(NULL, "/", "");
    for(i = 0; i < record_count; i++) {
        key = data + (expected_modulo * i);
        val = key + expected_modulo / 2;
        // printf("key: %s, val: %s\r", key, val);
        insert(root, key, val);
    }

    // now zip through every key in order to test find
    for(i = 0; i < record_count; i++) {
        key = data + (expected_modulo * i);
        val = search(root, key);
        assert(val && "Couldn't find the val for the key.");
        // not find keys by trying to find each
        assert(!search(root, val) && "Found a val but should not.");
    }

    // now traverse all the keys
    //traverse(root);
}