From 5fc8d2a2fbbe55fb3f92c4edd216f9e96d21a288 Mon Sep 17 00:00:00 2001 From: epochqwert Date: Tue, 31 Mar 2015 12:54:01 -0500 Subject: init commit after splitting from segfault --- .gitignore | 1 + Makefile | 15 ++++++ README.md | 2 + example.c | 25 +++++++++ genheader.sh | 3 ++ hashtable.h | 27 ++++++++++ libhashtable.c | 165 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 238 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 README.md create mode 100644 example.c create mode 100755 genheader.sh create mode 100644 hashtable.h create mode 100644 libhashtable.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..a8a2858 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +libhashtable.so diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..6649739 --- /dev/null +++ b/Makefile @@ -0,0 +1,15 @@ +LDFLAGS=-lhashtable -Llibhashtable +CFLAGS=-fpic -shared -pedantic -Wall +TARGET=libhashtable.so + +all: $(TARGET) + +$(TARGET): + $(CC) $(CFLAGS) -o $(TARGET) libhashtable.c + +clean: + rm -f libhashtable.so + +install: + cp $(TARGET) /usr/local/lib/$(TARGET) + cp hashtable.h /usr/local/include/hashtable.h diff --git a/README.md b/README.md new file mode 100644 index 0000000..ba0967b --- /dev/null +++ b/README.md @@ -0,0 +1,2 @@ +C implementation of hashtables. +Uses linked lists in each node to manage hash collisions. diff --git a/example.c b/example.c new file mode 100644 index 0000000..919d75c --- /dev/null +++ b/example.c @@ -0,0 +1,25 @@ +#include +#include "hashtable.h" + +extern char **environ; + +int main(int argc,char *argv[]) { + struct hashtable ht; + int i; + char *name; + char *value; + inittable(&ht,65535); + for(i=0;environ[i];i++) { + name=strdup(environ[i]); + if((value=strchr(name,'=') )){ + *value=0; + value++; + } + ht_setkey(&ht,name,value); + free(name); + } + printf("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 new file mode 100755 index 0000000..3995579 --- /dev/null +++ b/genheader.sh @@ -0,0 +1,3 @@ +#!/bin/sh +cat libhashtable.c | head -n 22 | tail -n 16 > hashtable.h +cat libhashtable.c | grep '(.*) *{' | egrep -v 'if|for|while' | sed 's/ {/;/' >> hashtable.h diff --git a/hashtable.h b/hashtable.h new file mode 100644 index 0000000..a58a392 --- /dev/null +++ b/hashtable.h @@ -0,0 +1,27 @@ +struct entry {//linked list node. + char *original; + void *target; + struct entry *prev;// doubly linked list. why? + struct entry *next; +}; + +struct hitem { + struct entry *ll; +}; + +struct hashtable { + int kl;//number of keys in the table + struct hitem **bucket; + int *keys; +}; +unsigned short hash(char *key);//maybe use a seeded rand()? :) Thanks FreeArtMan +void inittable(struct hashtable *ht,int tsize); +void ll_delete(struct entry *ll); +void ll_destroy(struct entry *ll); +void ht_destroy(struct hashtable *ht); +void ht_freevalues(struct hashtable *ht); +int ht_setkey(struct hashtable *ht,char *key,void *value); +struct entry *ll_getentry(struct entry *start,char *msg); +struct entry *ht_getentry(struct hashtable *ht,char *key); +struct entry *ht_getnode(struct hashtable *ht,char *msg); +void *ht_getvalue(struct hashtable *ht,char *msg); diff --git a/libhashtable.c b/libhashtable.c new file mode 100644 index 0000000..496a3ee --- /dev/null +++ b/libhashtable.c @@ -0,0 +1,165 @@ +#include +#include +#include +#include "hashtable.h" + +/* +struct entry {//linked list node. + char *original; + void *target; + struct entry *prev;// doubly linked list. why? + struct entry *next; +}; + +struct hitem { + struct entry *ll; +}; + +struct hashtable { + int kl;//number of keys in the table + struct hitem **bucket; + int *keys; +}; +*/ + +unsigned short hash(char *key) {//maybe use a seeded rand()? :) Thanks FreeArtMan + return (strlen(key)<<8)+(key[0]<<4)+key[1]; +} + +void inittable(struct hashtable *ht,int tsize) { + int i; + ht->bucket=malloc(sizeof(char *)*tsize); + ht->kl=0; + ht->keys=malloc(sizeof(int *)*tsize); + if(!ht) { + fprintf(stderr,"malloc error 6 in hash table.\n"); + return; + } + for(i=0;ibucket[i]=0; + } +} + +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. + } + free(ll);//all these nodes are malloc()d. +} + +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) { + int i=0; + for(i=0;ikl;i++) { + ll_destroy(ht->bucket[ht->keys[i]]->ll); + } + free(ht->bucket); +} + +void ll_freevalues(struct entry *ll) {//only use if you malloc your table. + if(ll->next) ll_destroy(ll->next); + free(ll->target); +} + +void ht_freevalues(struct hashtable *ht) { + int i; + for(i=0;ikl;i++) { + ll_freevalues(ht->bucket[ht->keys[i]]->ll); + } +} + +//this seems too complicated. +int ht_setkey(struct hashtable *ht,char *key,void *value) { + unsigned short h; + struct entry *tmp; + int i; + if(!key) key="(null)"; + h=hash(key); + for(i=0;ikl;i++) { + if(ht->keys[i]==h) break; + } + ht->keys[i]=h; + ht->kl=(ht->kl)>i+1?ht->kl:i+1; + if(!ht->bucket[h]) { //empty bucket! + //add this to the list of used buckets so we can easily + //use that list later for stuff. + if(!(ht->bucket[h]=malloc(sizeof(struct hitem)))) return 1; + ht->bucket[h]->ll=0; + //we now have a valid hashtable entry and a NULL ll in it. + //don't bother with the new ll entry yet... + } + if((tmp=ll_getentry(ht->bucket[h]->ll,key)) != NULL) { + tmp->target=value; + return 0; + } + if(ht->bucket[h]->ll == NULL) { + if(!(ht->bucket[h]->ll=malloc(sizeof(struct entry)))) return 3; + ht->bucket[h]->ll->next=0; + ht->bucket[h]->ll->prev=0; + if(!(ht->bucket[h]->ll->original=strdup(key))) return 4; + ht->bucket[h]->ll->target=value; + } else { + //go to the end and add another entry to the ll. + for(tmp=ht->bucket[h]->ll;tmp->next;tmp=tmp->next); + if(!(tmp->next=malloc(sizeof(struct entry)))) return 6; + tmp->next->prev=tmp; + tmp=tmp->next; + if(!(tmp->original=strdup(key))) return 7; + tmp->target=value; + tmp->next=0; + } + return 0; +} + +struct entry *ll_getentry(struct entry *start,char *key) { + struct entry *m; + if(!key) return NULL; + if(!start) return NULL; + 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. >_> + return m; + } + } + return NULL; +} + +//returns the table entry (a linked list) at the key. +struct entry *ht_getentry(struct hashtable *ht,char *key) { + unsigned short h=hash(key); + if(!ht->bucket[h]) return NULL; + return ht->bucket[h]->ll; +} + +//returns the node in the linked list in the table entry that matches the key. +struct entry *ht_getnode(struct hashtable *ht,char *key) { + return ll_getentry(ht_getentry(ht,key),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); + return tmp?tmp->target:0; +} + +//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)); +} -- cgit v1.2.3