1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
#include "hashtable.h"
htable_t* ht_init(int num_buckets, int(*hashcode)(void *obj),
int(*compare)(void *obj1, void *obj2)){
int i;
htable_t *ht = (htable_t*)malloc(sizeof(htable_t));
ht->table=(ht_list_t**)malloc(sizeof(ht_list_t*)*num_buckets);
memset(ht->table, 0, sizeof(ht_list_t*)*num_buckets);
ht->num_buckets=num_buckets;
ht->size=0;
ht->hashcode = hashcode;
ht->compare = compare;
return ht;
}
void ht_reset(htable_t *ht){
int i;
ht_list_t *cur,*next;
if(ht){
for(i=0;i<ht->num_buckets;i++){
cur=ht->table[i];
if(cur){
next=cur->lptr;
free(cur);
cur=next;
}
}
free(ht->table);
}
ht->table=(ht_list_t**)malloc(sizeof(ht_list_t*)*ht->num_buckets);
memset(ht->table, 0, sizeof(ht_list_t*)*ht->num_buckets);
ht->size=0;
}
void *ht_find(void *obj, htable_t *ht){
ht_list_t *chain=ht->table[(ht->hashcode(obj)%ht->num_buckets)];
void *info_to_return=NULL;
while(chain) {
if(ht->compare(obj, chain->info)==0){
info_to_return=chain->info;
break;
} else chain = chain->lptr;
}
return info_to_return;
}
void ht_insert(void *obj, htable_t *ht){
int hc=(ht->hashcode(obj)%ht->num_buckets);
ht_list_t *new_entry=NULL,*old_chain=ht->table[hc];
if(!ht_find(obj, ht)){
new_entry=(ht_list_t*)malloc(sizeof(ht_list_t));
new_entry->info=obj;
new_entry->lptr=old_chain;
ht->table[hc]=new_entry;
ht->size++;
}
return;
}
void ht_remove(void *obj, htable_t *ht){
int hc=(ht->hashcode(obj)%ht->num_buckets);
ht_list_t *chain=ht->table[hc];
ht_list_t *oldchain=chain;
while(chain){
if(ht->compare(obj, chain->info)==0){
if(oldchain==chain){ // i.e first list entry
ht->table[hc]=chain->lptr;
free(chain);
} else {
oldchain->lptr=chain->lptr;
free(chain);
}
ht->size--;
break;
}
oldchain=chain;
chain=chain->lptr;
}
}
ht_list_t *ht_iter(htable_t *ht){
int i;
ht_list_t *prev=NULL, *cur=NULL, *next=NULL;
if(!ht || !ht->table) return NULL;
for(i=0;i<ht->num_buckets;i++){
next=ht->table[i];
while(next){
cur=(ht_list_t*)malloc(sizeof(ht_list_t));
cur->info=next->info;
cur->lptr=prev;
prev=cur;
next=next->lptr;
}
}
return cur;
}
void ht_free_iter(ht_list_t *l){
ht_list_t *next;
while(l){
next=l->lptr;
free(l);
l=next;
}
}
|
