Name: Anonymous 2011-11-30 23:57
What does prog think of my hashtable?
(1) unixs1 $ cat hashtable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "void.h"
#define HASHTABLE_DEFAULT_LOAD_FACTOR 0.75
struct entry;
struct hashtable {
u32 size;
u32 cap;
u32 thr;
f32 lfac;
struct entry **slots;
};
struct hashtable *hashtable_create(u32,f32);
void *hashtable_put(struct hashtable *,u8*,void*);
void *hashtable_get(struct hashtable *,u8*);
void *hashtable_remove(struct hashtable *,u8*);
void **hashtable_array(struct hashtable *);
#endif
(2) unixs1 $ cat hashtable.c
#include "hashtable.h"
struct entry {
struct entry *next;
s64 key;
void *v;
};
void hashtable_rehash(struct hashtable *);
void hashtable_add(struct hashtable *,s64,void*,u32);
s64 hashtable_hash(u8*);
struct hashtable *hashtable_create(u32 s,f32 l)
{
struct hashtable *h = malloc(sizeof(struct hashtable));
if(!h){
printf("Failed to create the hashtable\n");
exit(EXIT_FAILURE);
}
h->cap = s;
h->size = 0;
h->lfac = l;
h->thr = s * l;
h->slots = malloc(sizeof(struct entry *) * s);
for(s=0;s<h->cap;++s)
h->slots[s] = NULL;
if(!h->slots){
printf("Failed to create the hashtable\n");
exit(EXIT_FAILURE);
}
return h;
}
void *hashtable_put(struct hashtable *h,u8 *key,void *v)
{
s64 k = hashtable_hash(key);
u32 id = k % h->cap;
struct entry *e = h->slots[id];
while(e != NULL){
if(e->key == k){
void *r = e->v;
e->v = v;
return r;
}
e = e->next;
}
h->size++;
if(h->size > h->thr){
hashtable_rehash(h);
id = k % h->cap;
}
hashtable_add(h,k,v,id);
return NULL;
}
void hashtable_add(struct hashtable *h,s64 k,void *v,u32 id)
{
struct entry *e = malloc(sizeof(struct entry));
e->key = k;
e->v = v;
e->next = h->slots[id];
h->slots[id] = e;
}
void hashtable_rehash(struct hashtable *h)
{
u32 id;
s32 i = h->cap-1;
struct entry *e;
struct entry *next;
struct entry **old = h->slots;
h->cap = h->cap * 2 + 1;
h->thr = h->cap * h->lfac;
h->slots = malloc(sizeof(struct entry *)*h->cap);
for(id=0;id<h->cap;++id)
h->slots[id] = NULL;
for(;i>=0;--i){
e = old[i];
while(e != NULL){
id = e->key % h->cap;
next = e->next;
e->next = h->slots[id];
h->slots[id] = e;
e = next;
}
}
free(old);
}
void *hashtable_get(struct hashtable *h,u8 *key)
{
s64 k = hashtable_hash(key);
u32 id = k % h->cap;
struct entry *e = h->slots[id];
while(e != NULL){
if(e->key == k)
return e->v;
e = e->next;
}
return NULL;
}
void *hashtable_remove(struct hashtable *h,u8 *key)
{
s64 k = hashtable_hash(key);
u32 id = k % h->cap;
struct entry *e = h->slots[id];
struct entry *l = NULL;
while(e != NULL){
if(e->key == k){
if(l == NULL)
h->slots[id] = e->next;
else
l->next = e->next;
--h->size;
return e->v;
}
l = e;
e = e->next;
}
return NULL;
}
void **hashtable_array(struct hashtable *h)
{
struct entry *e;
void **vals = malloc(sizeof(void *) * h->size);
s32 s = 0;
s32 i = h->cap-1;
for(;i>=0;--i){
e = h->slots[i];
while(e != NULL){
vals[s] = e->v;
s++;
e = e->next;
}
}
return vals;
}
s64 hashtable_hash(u8 *k)
{
s32 s = strlen(k);
s64 h = 0;
for(;s>=0;--s){
h = k[s] + h << 5;
}
h ^= (h >> 20) ^ (h >> 12);
return h ^ (h >> 7) ^ (h >> 4);
}
int main()
{
s32 i;
void **t;
struct hashtable *h = hashtable_create(4,HASHTABLE_DEFAULT_LOAD_FACTOR);
printf("HT SIZE [%d] | CAP [%d] | THR [%d]\n",h->size,h->cap,h->thr);
hashtable_put(h,"anus","equates to /prog/");
hashtable_put(h,"`faggot'","needs to gtfo");
hashtable_put(h,"Frozenvoid","is a `faggot'");
hashtable_put(h,"anusify","me captain");
printf("HT SIZE [%d] | CAP [%d] | THR [%d]\n",h->size,h->cap,h->thr);
printf("HT GET `faggot' : [%s]\n",hashtable_get(h,"`faggot'"));
printf("HT REM cockfag : [%s]\n",hashtable_remove(h,"cockfag"));
printf("HT REM anus : [%s]\n",hashtable_remove(h,"anus"));
printf("HT SIZE [%d] | CAP [%d] | THR [%d]\n",h->size,h->cap,h->thr);
t = hashtable_array(h);
for(i=0;i<h->size;++i){
printf("HT %d => [%s]\n",i,(char *)t[i]);
}
}
(3) unixs1 $ tcc hashtable.c
(4) unixs1 $ hashtable.exe
HT SIZE [0] | CAP [4] | THR [3]
HT SIZE [4] | CAP [9] | THR [6]
HT GET `faggot' : [needs to gtfo]
HT REM cockfag : [(null)]
HT REM anus : [equates to /prog/]
HT SIZE [3] | CAP [9] | THR [6]
HT 0 => [me captain]
HT 1 => [is a `faggot']
HT 2 => [needs to gtfo]