summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile3
-rw-r--r--hashtable.h9
-rw-r--r--libhashtable.c115
3 files changed, 106 insertions, 21 deletions
diff --git a/Makefile b/Makefile
index 627a926..e6d30cd 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
### why the fuck is this here? LDFLAGS=-lhashtable -Llibhashtable
-CFLAGS=-fpic -shared -pedantic -Wall -g3
+CFLAGS=-pedantic -Wall -g3
PREFIX:=/usr/local
TARGET=libhashtable.so
@@ -10,6 +10,7 @@ all: $(TARGET)
libhashtable.h:
./genheader.sh
+$(TARGET): CFLAGS+=-fpic -shared
$(TARGET): libhashtable.o
ld -shared -o $(TARGET) libhashtable.o
diff --git a/hashtable.h b/hashtable.h
index 0d6112b..08cedda 100644
--- a/hashtable.h
+++ b/hashtable.h
@@ -1,6 +1,6 @@
-struct entry {
- char *original;
- void *target;
+struct entry {//wtf is with my stupid choice of names?
+ void *target;//value
+ char *original;//key
struct entry *prev;
struct entry *next;
};
@@ -17,6 +17,8 @@ struct hashtable {
};
unsigned int murmur3_32(const char *key, unsigned int len, unsigned int seed);
unsigned int hash(char *key);
+unsigned int ht_getkeycount(struct hashtable *ht);
+char **ht_getkeys(struct hashtable *ht,unsigned int *len);
void inittable(struct hashtable *ht,unsigned int tsize);
void ll_delete(struct entry *ll);
void ll_destroy(struct entry *ll);
@@ -28,4 +30,5 @@ 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_dump(struct hashtable *ht);
void ht_delete(struct hashtable *ht,char *key);
diff --git a/libhashtable.c b/libhashtable.c
index 0bdcd60..ddb7fb0 100644
--- a/libhashtable.c
+++ b/libhashtable.c
@@ -7,9 +7,9 @@
//#define DEBUG
/* _A_
-struct entry {
- char *original;
- void *target;
+struct entry {//wtf is with my stupid choice of names?
+ void *target;//value
+ char *original;//key
struct entry *prev;
struct entry *next;
};
@@ -80,9 +80,42 @@ unsigned int murmur3_32(const char *key, unsigned int len, unsigned int seed) {
unsigned int hash(char *key) {
// return 0;//use this like a linked list.*key*strlen(key);
+ if(!key) return fprintf(stderr,"piss.\n"),0;
return murmur3_32(key,strlen(key),0);
}
+unsigned int ht_getkeycount(struct hashtable *ht) {
+ struct entry *m;
+ int key_count=0,i;
+ for(i=0;i<ht->kl;i++) //who needs braces? not us. our teeth are straight. :|
+ if(ht->bucket[ht->keys[i]])
+ for(m=ht->bucket[ht->keys[i]]->ll;m;m=m->next)
+ key_count++;
+ return key_count;
+}
+
+//returns an array of pointers to the keys stored in the hashtable
+//free the pointer returned? or maybe we should just pass by reference?
+char **ht_getkeys(struct hashtable *ht,unsigned int *len) {
+ int i,j;
+ //need to count up how many entries are in the hash table?
+ //should the hashtable keep track of that info by itself?
+ char **a;
+ struct entry *m;
+ *len=ht_getkeycount(ht);
+ a=malloc(sizeof(char *) * *len);
+ j=0;
+ for(i=0;i<ht->kl;i++) {//for each key...
+ if(ht->bucket[ht->keys[i]]) {
+ for(m=ht->bucket[ht->keys[i]]->ll;m;m=m->next) {
+ a[j]=m->original;
+ j++;
+ }
+ }
+ }
+ return a;
+}
+
void inittable(struct hashtable *ht,unsigned int tsize) {
int i;
ht->bucket=malloc(sizeof(char *)*tsize);
@@ -181,8 +214,12 @@ struct entry *ll_getentry(struct entry *start,char *key) {
if(!key) return 0;
if(!start) return 0;
for(m=start;m;m=m->next) {
- if(!strcmp(key,m->original)) {
- return m;
+ if(m->original) {
+ if(!strcmp(key,m->original)) {
+ return m;
+ }
+ } else {
+ fprintf(stderr,"shit. %s this element in the linked list doesn't have a name. wtf?\n",key);
}
}
return 0;
@@ -190,6 +227,7 @@ struct entry *ll_getentry(struct entry *start,char *key) {
//returns the table entry (a linked list) at the key.
struct entry *ht_getentry(struct hashtable *ht,char *key) {
+ if(!ht) return NULL;
unsigned int h=hash(key)%(ht->size);
if(!ht->bucket[h]) return NULL;
return ht->bucket[h]->ll;
@@ -213,24 +251,67 @@ struct hitem *ht_getbucket(struct hashtable *ht,char *key) {
return ht->bucket[hash(key)%ht->size];
}
+void ht_dump(struct hashtable *ht) {
+ int i;
+ struct entry *m;
+
+ unsigned int key_count=0;
+ char **keys=ht_getkeys(ht,&key_count);
+ printf("amount of keys: %d\n",key_count);
+ for(i=0;i<key_count;i++) {
+ printf("key: %s hash: %d\n",keys[i],hash(keys[i]) % ht->size);
+ }
+
+ printf("kl: %d\n",ht->kl);
+ for(i=0;i<ht->kl;i++) {
+ printf("looking into hash: %d\n",ht->keys[i]);
+ if(ht->bucket[ht->keys[i]]) {
+ printf("bucket not empty!: %d\n",ht->keys[i]);
+ printf("printing its linked list:\n");
+ for(m=ht->bucket[ht->keys[i]]->ll;m;m=m->next) {
+ printf(" key: %s hash: %08x\n",m->original,ht->keys[i]);
+ }
+ printf("end of linked list\n");
+ } else {
+ printf("empty bucket: %d\n",ht->keys[i]);
+ }
+ }
+}
+
//delete the node in the linked list in the table entry that matches the key.
void ht_delete(struct hashtable *ht,char *key) {
int i;
unsigned int h=hash(key)%(ht->size);
+ struct entry *tmp;
-//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);
+ struct hitem *bucket=ht->bucket[h];
+ if(!bucket) { fprintf(stderr,"attempted to ht_delete key: %s which had a non-existing bucket.\n",key) ; return; }
+ if(!bucket->ll) { fprintf(stderr,"attempted to ht_delete key: %s which has a bucket with a null ll\n",key) ; return; }
+ for(tmp=bucket->ll;tmp;tmp=tmp->next) {
+ if(!strcmp(tmp->original,key)) break;//we found it
+ }
+ if(!tmp) { fprintf(stderr,"attempted to ht_delete key: %s which isn't in the linked list for its bucket\n",key); return; }
+ tmp->target=0;
+ if(tmp->next == 0 && tmp->prev == 0) {//only dump the bucket if it has only one thing
+ free(bucket->ll);//btw, bucket->ll == tmp
+ free(bucket);
+ ht->bucket[h % ht->size]=0;
- for(i=0;i<ht->kl;i++) {
- if(ht->keys[i]==h) break;
+ 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--;
+ }
+ else {
+ if(tmp->next) tmp->next->prev=tmp->prev;
+ if(tmp->prev) tmp->prev->next=tmp->next;
+ else bucket->ll=tmp->next;//we deleted the start of the linked list, we need to tell our bucket about it.
+ free(tmp);
}
- for(;i<ht->kl;i++) {
- ht->keys[i]=ht->keys[i+1];
+ if(ht->kl < 0) {
+ abort();
}
- ht->kl--;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-25 18:47:58 +0000