Anagram hashtable...

anagram.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "qsort.h"
#include "hash.h"

int main()
{
        HashTable h;
        char *in = "antler";
        char *str = (char*)malloc(8192);
        FILE *fp = fopen("/usr/share/dict/cracklib-small", "r");
        while(str = fgets(str, 8191, fp))
        {
                str[strlen(str)-1]='\0';
                h.add(str);
        }
        StringList *t = h.getList(in);
        if(t == NULL)
        {
                printf("No anagrams found for \"%s\"\n", in);
        }
        else
        {
                printf("Anagrams for \"%s\":\n", in);
                t->dump();
        }
        return 0;
}

hash.cpp

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "hash.h"
#include "qsort.h"

unsigned short HashTable::crc16(const char *buf, int len)
{
        unsigned short crc = 0, i;
        while(len--)
        {
                crc ^= (*buf++)<<8;
                for(i=0; i<8; i++)
                {
                        if(crc & 0x8000) crc = (crc<<1)^0x1021;
                        else crc <<= 1;
                }
        }
        return crc;
}

HashTable::HashTable()
{
        table = (StringList***)malloc(256 * sizeof(StringList***));
        for(int i=0; i<256; i++) table[i] = NULL;
}

HashTable::~HashTable()
{
        for(int i=0; i<256; i++)
        {
                delete[] table[i];
        }
        delete table;
}

void HashTable::add(const char* str)
{
        char *temp = (char*)malloc(strlen(str)+1);
        strcpy(temp, str);
        qsort(temp, strlen(temp));

        unsigned short crc = crc16(temp, strlen(temp));
        if(table[crc>>8] == NULL)
        {
                table[crc>>8] = (StringList**)malloc(256*sizeof(StringList**));
                for(int i=0; i<256; i++) table[crc>>8][i] = NULL;
        }
        if(table[crc>>8][crc&255] == NULL)
        {
                table[crc>>8][crc&255] = new StringList();
        }
        table[crc>>8][crc&255]->append(str);
        free(temp);
}

StringList *HashTable::getList(const char *str)
{
        char *temp = (char*)malloc(strlen(str)+1);
        strcpy(temp, str);
        qsort(temp, strlen(temp));

        unsigned short crc = crc16(temp, strlen(temp));
        free(temp);
        if(table[crc>>8] == NULL) return NULL;
        return table[crc>>8][crc&255];
}

hash.h

#ifndef __HASH_H_
#define __HASH_H_

#include "strlist.h"

class HashTable
{
        private:
                StringList ***table;
                unsigned short crc16(const char*, int);
        public:
                HashTable();
                ~HashTable();
                void add(const char*);
                StringList *getList(const char*);
};

#endif//__HASH_H_

Makefile

CC = g++ -c
LD = g++

anagram: anagram.o hash.o qsort.o strlist.o
        $(LD) -o $@ $^

%.o: %.cpp %.c %.h
        $(CC) -o $@ $<

clean:
        rm *.o anagram

qsort.cpp

#include <stdlib.h>

void qsort(char *arr, int len)
{
        if(len > 1)
        {
                int pivot = len>>1;
                char *temp = (char*)malloc(len);
                int i, left=0, right=len-1;

                for(i=0; i<len; i++)
                {
                        if(i!=pivot)
                        {
                                if(arr[i] <= arr[pivot]) temp[left++] = arr[i];
                                else temp[right--] = arr[i];
                        }
                }
                temp[left] = arr[pivot];
                for(i=0; i<len; i++) arr[i]=temp[i];
                free(temp);

                qsort(arr, left);
                qsort(arr+right, len-right);
        }
}

qsort.h

#ifndef __QSORT_H_
#define __QSORT_H_

void qsort(char*, int);

#endif//__QSORT_H_

strlist.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "strlist.h"

StringList::StringList()
{
        head = NULL;
        tail = NULL;
}

StringList::~StringList()
{
        StringListEntry *n = tail;
        do
        {
                n = n->prev;
                free(n->next->data);
                free(n->next);
        } while(n != head);
        free(head->data);
        free(head);
}

void StringList::append(const char *str)
{
        if(!head && !tail)
        {
                head = (StringListEntry*)malloc(sizeof(StringListEntry));
                head->prev = NULL;
                head->next = NULL;
                head->data = (char*)malloc(strlen(str)+1);
                strcpy(head->data, str);
                tail = head;
        }
        else
        {
                StringListEntry *a = (StringListEntry*)malloc(sizeof(StringListEntry));
                a->next = NULL;
                a->prev = tail;
                a->data = (char*)malloc(strlen(str)+1);
                strcpy(a->data, str);

                tail->next = a;
                tail = a;
        }
}

void StringList::dump()
{
        StringListEntry *n = head;
        do
        {
                printf("(%08X) [%08X] %s [%08X]\n", n, n->prev,  n->data, n->next);
                n = n->next;
        } while(n != NULL);
}

strlist.h

#ifndef __STRLIST_H_
#define __STLIST_H_

struct StringListEntry
{
        char *data;
        StringListEntry *next;
        StringListEntry *prev;
};

class StringList
{
        private:
                StringListEntry *head, *tail;
        public:
                StringList();
                ~StringList();
                void append(const char*);
                void dump();
};

#endif//__STRLIST_H_