diff options
| -rw-r--r-- | example.c | 15 | ||||
| -rwxr-xr-x | genheader.sh | 5 | ||||
| -rw-r--r-- | hashtable.h | 15 | ||||
| -rw-r--r-- | libhashtable.c | 130 |
4 files changed, 119 insertions, 46 deletions
@@ -7,18 +7,23 @@ int main(int argc,char *argv[]) { struct hashtable ht; int i; char *name; + char *tmp; char *value; - inittable(&ht,65535); + inittable(&ht,1000); for(i=0;environ[i];i++) { name=strdup(environ[i]); - if((value=strchr(name,'=') )){ - *value=0; - value++; + if((tmp=strchr(name,'=') )){ + *tmp=0; + tmp++; } + value=strdup(tmp); ht_setkey(&ht,name,value); free(name); } - printf("PATH='%s'\n",ht_getvalue(&ht,"PATH")); + printf("ht.size: %u\n",ht.size); + printf("before: PATH='%s'\n",ht_getvalue(&ht,"PATH")); + ht_delete(&ht,"PATH"); + printf("after: PATH='%s'\n",ht_getvalue(&ht,"PATH")); //if you want to get a whole entry struct use ht_getnode(); //getentry() just returns the first struct in the linked list in that bucket. return 0; diff --git a/genheader.sh b/genheader.sh index b3a28e6..8a253b7 100755 --- a/genheader.sh +++ b/genheader.sh @@ -1,3 +1,4 @@ #!/bin/sh -cat libhashtable.c | grep -A 100 _A_ | grep -B 100 _B_ | grep -v "_[AB]_" > hashtable.h -cat libhashtable.c | grep '(.*) *{' | egrep -v 'if|for|while' | sed 's/ {/;/' >> hashtable.h +L=$(wc -l libhashtable.c | tr -s ' ' | cut '-d ' -f2) +cat libhashtable.c | grep -A "$L" _A_ | grep -B "$L" _B_ | grep -v "_[AB]_" > hashtable.h +cat libhashtable.c | grep '(.*) *{' | egrep -v 'switch|if|for|while' | sed 's/ {/;/' >> hashtable.h diff --git a/hashtable.h b/hashtable.h index 60d1b50..0d6112b 100644 --- a/hashtable.h +++ b/hashtable.h @@ -1,7 +1,7 @@ -struct entry {//linked list node. +struct entry { char *original; void *target; - struct entry *prev;// doubly linked list. why? + struct entry *prev; struct entry *next; }; @@ -10,12 +10,14 @@ struct hitem { }; struct hashtable { - int kl;//number of keys in the table + unsigned int kl; + unsigned int size; struct hitem **bucket; - int *keys; + unsigned int *keys; }; -unsigned short hash(char *key);//maybe use a seeded rand()? :) Thanks FreeArtMan -void inittable(struct hashtable *ht,int tsize); +unsigned int murmur3_32(const char *key, unsigned int len, unsigned int seed); +unsigned int hash(char *key); +void inittable(struct hashtable *ht,unsigned int tsize); void ll_delete(struct entry *ll); void ll_destroy(struct entry *ll); void ht_destroy(struct hashtable *ht); @@ -25,4 +27,5 @@ struct entry *ll_getentry(struct entry *start,char *key); struct entry *ht_getentry(struct hashtable *ht,char *key); struct entry *ht_getnode(struct hashtable *ht,char *key); void *ht_getvalue(struct hashtable *ht,char *key); +struct hitem *ht_getbucket(struct hashtable *ht,char *key); void ht_delete(struct hashtable *ht,char *key); diff --git a/libhashtable.c b/libhashtable.c index e838433..7152f56 100644 --- a/libhashtable.c +++ b/libhashtable.c @@ -4,10 +4,10 @@ #include "hashtable.h" /* _A_ -struct entry {//linked list node. +struct entry { char *original; void *target; - struct entry *prev;// doubly linked list. why? + struct entry *prev; struct entry *next; }; @@ -16,23 +16,78 @@ struct hitem { }; struct hashtable { - int kl;//number of keys in the table + unsigned int kl; + unsigned int size; struct hitem **bucket; - int *keys; + unsigned int *keys; }; _B_ */ -unsigned short hash(char *key) {//maybe use a seeded rand()? :) Thanks FreeArtMan - return (strlen(key)<<8)+(key[0]<<4)+key[1]; +/*stolen from wikipedia!*/ +unsigned int murmur3_32(const char *key, unsigned int len, unsigned int seed) { + static const uint32_t c1 = 0xcc9e2d51; + static const uint32_t c2 = 0x1b873593; + static const uint32_t r1 = 15; + static const uint32_t r2 = 13; + static const uint32_t m = 5; + static const uint32_t n = 0xe6546b64; + + uint32_t hash = seed; + + const int nblocks = len / 4; + const uint32_t *blocks = (const uint32_t *) key; + const uint8_t *tail; + uint32_t k1; + int i; + for (i = 0; i < nblocks; i++) { + uint32_t k = blocks[i]; + k *= c1; + k = (k << r1) | (k >> (32 - r1)); + k *= c2; + + hash ^= k; + hash = ((hash << r2) | (hash >> (32 - r2))) * m + n; + } + + tail = (const uint8_t *) (key + nblocks * 4); + k1 = 0; + + switch (len & 3) { + case 3: + k1 ^= tail[2] << 16; + case 2: + k1 ^= tail[1] << 8; + case 1: + k1 ^= tail[0]; + k1 *= c1; + k1 = (k1 << r1) | (k1 >> (32 - r1)); + k1 *= c2; + hash ^= k1; + } + + hash ^= len; + hash ^= (hash >> 16); + hash *= 0x85ebca6b; + hash ^= (hash >> 13); + hash *= 0xc2b2ae35; + hash ^= (hash >> 16); + + return hash; } -void inittable(struct hashtable *ht,int tsize) { +unsigned int hash(char *key) { +// return 0;//use this like a linked list.*key*strlen(key); + return murmur3_32(key,strlen(key),0); +} + +void inittable(struct hashtable *ht,unsigned int tsize) { int i; ht->bucket=malloc(sizeof(char *)*tsize); ht->kl=0; ht->keys=malloc(sizeof(int *)*tsize); + ht->size=tsize; if(!ht) { - fprintf(stderr,"malloc error 6 in hash table.\n"); + fprintf(stderr,"malloc error 6 in hash table.\n");//dafuq? return; } for(i=0;i<tsize;i++) { @@ -41,19 +96,9 @@ void inittable(struct hashtable *ht,int tsize) { } void ll_delete(struct entry *ll) { - //do I have to free() any of this shit? - //keys are always allocated. strdup(). - //gotta free that. anything else isn't my fault. - if(ll->prev) { - ll->prev->next=ll->next; - } else { - //I am the first node. - } - if(ll->next) { - ll->next->prev=ll->prev; - } else { - //I am the last node. - } + if(!ll) return; + if(ll->prev) ll->prev->next=ll->next; + if(ll->next) ll->next->prev=ll->prev; free(ll);//all these nodes are malloc()d. } @@ -61,9 +106,6 @@ void ll_destroy(struct entry *ll) { if(ll->next) ll_destroy(ll->next); free(ll->original); free(ll); - //destroy_this_node. - //ll->original //malloc()d - //ll->target //I dunno where this comes from. } void ht_destroy(struct hashtable *ht) { @@ -86,13 +128,13 @@ void ht_freevalues(struct hashtable *ht) { } } -//this seems too complicated. int ht_setkey(struct hashtable *ht,char *key,void *value) { - unsigned short h; + unsigned int h; struct entry *tmp; int i; if(!key) key="(null)"; - h=hash(key); + h=hash(key)%(ht->size); + //printf("setkey: %s\nhash: %u\n",key,h); for(i=0;i<ht->kl;i++) { if(ht->keys[i]==h) break; } @@ -131,19 +173,19 @@ int ht_setkey(struct hashtable *ht,char *key,void *value) { struct entry *ll_getentry(struct entry *start,char *key) { struct entry *m; - if(!key) return NULL; - if(!start) return NULL; + if(!key) return 0; + if(!start) return 0; for(m=start;m;m=m->next) { - if(!strncmp(key,m->original,strlen(m->original)) && (key[strlen(m->original)]==' ' || key[strlen(m->original)] == 0)) {//this allows !c to get called when using !c2 if !c2 is defined after !c. >_> + if(!strcmp(key,m->original)) { return m; } } - return NULL; + return 0; } //returns the table entry (a linked list) at the key. struct entry *ht_getentry(struct hashtable *ht,char *key) { - unsigned short h=hash(key); + unsigned int h=hash(key)%(ht->size); if(!ht->bucket[h]) return NULL; return ht->bucket[h]->ll; } @@ -156,10 +198,32 @@ struct entry *ht_getnode(struct hashtable *ht,char *key) { //you'll probably want to use me. void *ht_getvalue(struct hashtable *ht,char *key) { struct entry *tmp=ll_getentry(ht_getentry(ht,key),key); + //printf("getvalue: %s\nhash: %u\n",key,hash(key)%(ht->size)); return tmp?tmp->target:0; } +struct hitem *ht_getbucket(struct hashtable *ht,char *key) { + return ht->bucket[hash(key)%ht->size]; +} + //delete the node in the linked list in the table entry that matches the key. void ht_delete(struct hashtable *ht,char *key) { - ll_delete(ht_getentry(ht,key)); + int i; + unsigned int h=hash(key)%(ht->size); + +//working on this stuff: + struct hitem *bucket=ht_getbucket(ht,key); + struct entry *first=ht_getentry(ht,key); + struct entry *tmp=ll_getentry(first,key); + + if(!(tmp->next || tmp->prev)) bucket->ll=0; + else ll_delete(tmp); + + for(i=0;i<ht->kl;i++) { + if(ht->keys[i]==h) break; + } + for(;i<ht->kl;i++) { + ht->keys[i]=ht->keys[i+1]; + } + ht->kl--; } |