7 files changed, 238 insertions, 0 deletions

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 <stdio.h>
+#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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#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;i<tsize;i++) {
+  ht->bucket[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;i<ht->kl;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;i<ht->kl;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;i<ht->kl;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));
+}