#define BUCKETS 100
struct s_stringMap;
typedef struct s_stringMap {
const char *key;
const char *value;
struct s_stringMap *next;
} stringMap;
unsigned int hashmap( const char *s );
void hash_init( stringMap *map );
void hash_add( stringMap *map, const char *k, const char *v );
const char * hash_find(stringMap *map, const char *k);
unsigned int hashmap( const char *s )
{
unsigned int hash = 0;
if(!s || !*s) return 0;
do {
hash += *s;
hash *= 13;
s++;
} while (*s);
return hash % BUCKETS;
}
void hash_init( stringMap *map )
{
int i;
for(i = 0; i < BUCKETS; i++)
{
map[i].key = NULL;
map[i].value = NULL;
map[i].next = NULL;
}
}
void hash_add( stringMap *map, const char *k, const char *v )
{
unsigned int hashcode;
stringMap *p;
hashcode = hashmap(k);
p = &map[hashcode];
while(p->key && strcmp(p->key, k) && p->next)
p = p->next;
if(!p->key) {
/* First node? */
p->key = (const char *)strdup(k);
p->value = (const char *)strdup(v);
p->next = NULL;
} else if(!strcmp(p->key, k)) {
/* Found our match! */
if(p->value)
free((void *)p->value);
p->value = (const char *)strdup(v);
} else {
/* New key */
p->next = (stringMap *)calloc(1, sizeof(stringMap));
p = p->next;
p->key = (const char *)strdup(k);
p->value = (const char *)strdup(v);
p->next = NULL;
}
}
const char * hash_find(stringMap *map, const char *k)
{
unsigned int hashcode;
stringMap *p;
hashcode = hashmap(k);
p = &map[hashcode];
while(p->key && strcmp(p->key, k) && p->next)
p = p->next;
if(!p->key)
return NULL;
if(!strcmp(p->key, k))
return p->value;
return NULL;
}
Long story short. I see TONS of info on how to handle trees with data already in them. I have yet to come across an example that shows how to start a tree from root or they start from the bottom which makes my brain bleed. Every time I run my code, I end up with a worst-case (linked list) tree. I haven't tried randomizing the key for my data structure, but that's because I don't want to end up with a collision (at least 1K monsters, 4K rooms, areas, players, etc). Can anyone point me in the direction of a dummies guide to self-balancing binary trees?
</rant>
Thanx for listening!