1 /**********************************************************************
2 * Copyright (C) (2004) (Jack Louis) <jack@dyadsecurity.com> *
3 * *
4 * This program is free software; you can redistribute it and/or *
5 * modify it under the terms of the GNU General Public License *
6 * as published by the Free Software Foundation; either *
7 * version 2 of the License, or (at your option) any later *
8 * version. *
9 * *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
14 * *
15 * You should have received a copy of the GNU General Public License *
16 * along with this program; if not, write to the Free Software *
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
18 **********************************************************************/
19 #include <config.h>
20 #include <unistd.h>
21 #include <fcntl.h>
22
23 #include <xmalloc.h>
24 #include <chtbl.h>
25
26 #ifdef DEBUG
27 # define DBG(fmt, args...) \
28 fprintf(stderr, "DEBUG[%s at %s:%d]: ", __FUNCTION__, __FILE__, __LINE__);\
29 fprintf(stderr, fmt, ## args); \
30 fprintf(stderr, "\n");
31 #else
32 # define DBG(fmt, args...)
33 #endif
34
35 #define chead chtbl_head_t
36 #define cnode chtbl_node_t
37
38 #define CHTMAGIC (uint32_t)0xdefaced1
39
40 #define MALLOC(x) xmalloc(x)
41 #define FREE(x) _xfree(x)
42
43 typedef struct cnode {
44 void *data;
45 uint64_t key;
46 struct cnode *next;
47 } cnode;
48
49 typedef struct chead {
50 uint32_t magic;
51 uint32_t tsize;
52 uint32_t size;
53 cnode **table;
54 } chead;
55
56 /* exported */
chtinit(uint32_t exp_size)57 void *chtinit(uint32_t exp_size) {
58 union {
59 void *ptr;
60 chead *th;
61 } h_u;
62 uint32_t j=0;
63
64 h_u.ptr=MALLOC(sizeof(chead));
65 h_u.th->magic=CHTMAGIC;
66 h_u.th->tsize=0;
67 h_u.th->size=exp_size;
68 h_u.th->table=(cnode **)MALLOC(sizeof(cnode *) * exp_size);
69 for (j=0 ; j < exp_size ; j++) {
70 h_u.th->table[j]=(cnode *)NULL;
71 }
72
73 return h_u.ptr;
74 }
75
chtdestroy(void * lh)76 void chtdestroy(void *lh) {
77 union {
78 void *ptr;
79 chead *th;
80 } h_u;
81 uint32_t j=0;
82 cnode *n=NULL, *save=NULL;
83
84 assert(lh != NULL);
85 h_u.ptr=lh;
86 assert(h_u.th->magic == CHTMAGIC);
87
88 if (h_u.th->tsize == 0) {
89 return;
90 }
91
92 for (j=0 ; j < h_u.th->size ; j++) {
93 DBG("freeing bucket %u\n", j);
94 n=h_u.th->table[j];
95 if (n == NULL) continue; /* nothing to see here, please move along */
96 while (n->next != NULL) {
97 save=n;
98 n=n->next;
99 DBG("deleting node in chain");
100 FREE(save);
101 save=NULL;
102 }
103 DBG("deleting last node in chain");
104 FREE(n);
105 }
106
107 FREE(h_u.ptr);
108 h_u.ptr=NULL;
109
110 return;
111 }
112
chtgetsize(void * th)113 uint32_t chtgetsize(void *th) {
114 union {
115 void *ptr;
116 chead *th;
117 } h_u;
118 assert(th != NULL);
119 h_u.ptr=th;
120 assert(h_u.th->magic == CHTMAGIC);
121
122 return h_u.th->tsize;
123 }
124
chtinsert(void * th,uint64_t key,void * data)125 int chtinsert(void *th, uint64_t key, void *data) {
126 union {
127 void *ptr;
128 chead *th;
129 } h_u;
130 uint32_t offset=0;
131 cnode *bucket=NULL, *newn=NULL, *prev=NULL;
132
133 assert(data != NULL);
134 assert(th != NULL);
135 h_u.ptr=th;
136 assert(h_u.th->magic == CHTMAGIC);
137
138 offset=(key % h_u.th->size);
139
140 bucket=h_u.th->table[offset];
141
142 while (bucket != NULL && key != bucket->key) {
143 prev=bucket;
144 bucket=bucket->next;
145 }
146 if (bucket != NULL && bucket->key == key) {
147 return CHEXIT_KEYCOLLIDE;
148 }
149
150 newn=(cnode *)MALLOC(sizeof(cnode));
151 newn->key=key;
152 newn->data=data;
153
154 if (!(prev)) {
155 h_u.th->table[offset]=newn;
156 }
157 else {
158 prev->next=newn;
159 }
160 newn->next=NULL;
161 ++h_u.th->tsize;
162
163 return CHEXIT_SUCCESS;
164 }
165
chtdelete(void * th,uint64_t key)166 int chtdelete(void *th, uint64_t key) {
167 union {
168 void *ptr;
169 chead *th;
170 } h_u;
171 uint32_t offset=0;
172 cnode *bucket=NULL, *prev=NULL;
173
174 assert(th != NULL);
175 h_u.ptr=th;
176 assert(h_u.th->magic == CHTMAGIC);
177
178 offset=(key % h_u.th->size);
179 bucket=h_u.th->table[offset];
180
181 while (bucket != NULL && bucket->key != key) {
182 prev=bucket;
183 bucket=bucket->next;
184 }
185 if (bucket == NULL || bucket->key != key) {
186 return CHEXIT_FAILURE;
187 }
188 if (prev != NULL) {
189 prev->next=bucket->next;
190 }
191 else {
192 h_u.th->table[offset]=bucket->next;
193 }
194 FREE(bucket->data);
195 FREE(bucket);
196 --h_u.th->tsize;
197
198 return CHEXIT_SUCCESS;
199 }
200
chtfind(void * th,uint64_t key,void ** udata)201 int chtfind(void *th, uint64_t key, void **udata) {
202 union {
203 void *ptr;
204 chead *th;
205 } h_u;
206 uint32_t offset=0;
207 cnode *bucket=NULL, *prev=NULL;
208
209 assert(th != NULL);
210 h_u.ptr=th;
211 assert(h_u.th->magic == CHTMAGIC);
212
213 offset=(key % h_u.th->size);
214 bucket=h_u.th->table[offset];
215
216 while (bucket != NULL && bucket->key != key) {
217 prev=bucket;
218 bucket=bucket->next;
219 }
220
221 if (bucket == NULL || bucket->key != key) {
222 *udata=NULL;
223 return CHEXIT_FAILURE;
224 }
225
226 *udata=bucket->data;
227 return CHEXIT_SUCCESS;
228 }
229
230 #ifdef DEBUG
chtstats(void * th)231 void chtstats(void *th) {
232 union {
233 void *ptr;
234 chead *th;
235 } h_u;
236 uint32_t j=0;
237 uint32_t clen=0;
238 cnode *step=NULL;
239
240 assert(th != NULL);
241 h_u.ptr=th;
242 assert(h_u.th->magic == CHTMAGIC);
243
244 printf("Load Factor %f [%u items in %u slots]\n", (float)(h_u.th->tsize / h_u.th->size), h_u.th->tsize, h_u.th->size);
245
246 for (j=0 ; j < h_u.th->size ; j++) {
247 if (h_u.th->table[j]) {
248 step=h_u.th->table[j]; ++clen;
249 while (step->next != NULL) {
250 ++clen;
251 step=step->next;
252 }
253 printf("%u [%u] ", j, clen); clen=0;
254 }
255 }
256 }
257 #endif
258
259 #undef chead
260 #undef cnode
261