1 /**
2 r_assoc.c
3
4
5 Copyright (C) 2002-2003, Network Resonance, Inc.
6 Copyright (C) 2006, Network Resonance, Inc.
7 All Rights Reserved
8
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions
11 are met:
12
13 1. Redistributions of source code must retain the above copyright
14 notice, this list of conditions and the following disclaimer.
15 2. Redistributions in binary form must reproduce the above copyright
16 notice, this list of conditions and the following disclaimer in the
17 documentation and/or other materials provided with the distribution.
18 3. Neither the name of Network Resonance, Inc. nor the name of any
19 contributors to this software may be used to endorse or promote
20 products derived from this software without specific prior written
21 permission.
22
23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
24 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
27 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 POSSIBILITY OF SUCH DAMAGE.
34
35
36 */
37
38 /**
39 r_assoc.c
40
41 This is an associative array implementation, using an open-chained
42 hash bucket technique.
43
44 Note that this implementation permits each data entry to have
45 separate copy constructors and destructors. This currently wastes
46 space, but could be implemented while saving space by using
47 the high order bit of the length value or somesuch.
48
49 The major problem with this code is it's not resizable, though it
50 could be made so.
51
52
53 Copyright (C) 1999-2000 RTFM, Inc.
54 All Rights Reserved
55
56 This package is a SSLv3/TLS protocol analyzer written by Eric Rescorla
57 <ekr@rtfm.com> and licensed by RTFM, Inc.
58
59 Redistribution and use in source and binary forms, with or without
60 modification, are permitted provided that the following conditions
61 are met:
62 1. Redistributions of source code must retain the above copyright
63 notice, this list of conditions and the following disclaimer.
64 2. Redistributions in binary form must reproduce the above copyright
65 notice, this list of conditions and the following disclaimer in the
66 documentation and/or other materials provided with the distribution.
67 3. All advertising materials mentioning features or use of this software
68 must display the following acknowledgement:
69
70 This product includes software developed by Eric Rescorla for
71 RTFM, Inc.
72
73 4. Neither the name of RTFM, Inc. nor the name of Eric Rescorla may be
74 used to endorse or promote products derived from this
75 software without specific prior written permission.
76
77 THIS SOFTWARE IS PROVIDED BY ERIC RESCORLA AND RTFM, INC. ``AS IS'' AND
78 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
79 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
80 ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
81 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
82 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
83 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
84 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
85 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
86 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY SUCH DAMAGE.
87
88 $Id: r_assoc.c,v 1.4 2007/06/08 17:41:49 adamcain Exp $
89
90 ekr@rtfm.com Sun Jan 17 17:57:15 1999
91 */
92
93 #include <r_common.h>
94 #include <string.h>
95 #include "r_assoc.h"
96
97 typedef struct r_assoc_el_ {
98 char *key;
99 int key_len;
100 void *data;
101 struct r_assoc_el_ *prev;
102 struct r_assoc_el_ *next;
103 int (*copy)(void **n,void *old);
104 int (*destroy)(void *ptr);
105 } r_assoc_el;
106
107 struct r_assoc_ {
108 int size;
109 int bits;
110 int (*hash_func)(char *key,int len,int size);
111 r_assoc_el **chains;
112 UINT4 num_elements;
113 };
114
115 #define DEFAULT_TABLE_BITS 5
116
117 static int destroy_assoc_chain(r_assoc_el *chain);
118 static int r_assoc_fetch_bucket(r_assoc *assoc,
119 char *key,int len,r_assoc_el **bucketp);
120 static int copy_assoc_chain(r_assoc_el **knewp, r_assoc_el *old);
121
r_assoc_create(assocp,hash_func,bits)122 int r_assoc_create(assocp,hash_func,bits)
123 r_assoc **assocp;
124 int (*hash_func)(char *key,int len,int size);
125 int bits;
126 {
127 r_assoc *assoc=0;
128 int _status;
129
130 if(!(assoc=(r_assoc *)RCALLOC(sizeof(r_assoc))))
131 ABORT(R_NO_MEMORY);
132 assoc->size=(1<<bits);
133 assoc->bits=bits;
134 assoc->hash_func=hash_func;
135
136 if(!(assoc->chains=(r_assoc_el **)RCALLOC(sizeof(r_assoc_el *)*
137 assoc->size)))
138 ABORT(R_NO_MEMORY);
139
140 *assocp=assoc;
141
142 _status=0;
143 abort:
144 if(_status){
145 r_assoc_destroy(&assoc);
146 }
147 return(_status);
148 }
149
r_assoc_destroy(assocp)150 int r_assoc_destroy(assocp)
151 r_assoc **assocp;
152 {
153 r_assoc *assoc;
154 int i;
155
156 if(!assocp || !*assocp)
157 return(0);
158
159 assoc=*assocp;
160 for(i=0;i<assoc->size;i++)
161 destroy_assoc_chain(assoc->chains[i]);
162
163 RFREE(assoc->chains);
164 RFREE(*assocp);
165
166 return(0);
167 }
168
destroy_assoc_chain(chain)169 static int destroy_assoc_chain(chain)
170 r_assoc_el *chain;
171 {
172 r_assoc_el *nxt;
173
174 while(chain){
175 nxt=chain->next;
176
177 if(chain->destroy)
178 chain->destroy(chain->data);
179
180 RFREE(chain->key);
181
182 RFREE(chain);
183 chain=nxt;
184 }
185
186 return(0);
187 }
188
copy_assoc_chain(knewp,old)189 static int copy_assoc_chain(knewp,old)
190 r_assoc_el **knewp;
191 r_assoc_el *old;
192 {
193 r_assoc_el *knew=0,*ptr,*tmp;
194 int r,_status;
195
196 ptr=0; /* Pacify GCC's uninitialized warning.
197 It's not correct */
198 if(!old) {
199 *knewp=0;
200 return(0);
201 }
202 for(;old;old=old->next){
203 if(!(tmp=(r_assoc_el *)RCALLOC(sizeof(r_assoc_el))))
204 ABORT(R_NO_MEMORY);
205
206 if(!knew){
207 knew=tmp;
208 ptr=knew;
209 }
210 else{
211 ptr->next=tmp;
212 tmp->prev=ptr;
213 ptr=tmp;
214 }
215
216 ptr->destroy=old->destroy;
217 ptr->copy=old->copy;
218
219 if(old->copy){
220 if(r=old->copy(&ptr->data,old->data))
221 ABORT(r);
222 }
223 else
224 ptr->data=old->data;
225
226 if(!(ptr->key=(char *)RMALLOC(old->key_len)))
227 ABORT(R_NO_MEMORY);
228 memcpy(ptr->key,old->key,ptr->key_len=old->key_len);
229 }
230
231 *knewp=knew;
232
233 _status=0;
234 abort:
235 if(_status){
236 destroy_assoc_chain(knew);
237 }
238 return(_status);
239 }
240
r_assoc_fetch_bucket(assoc,key,len,bucketp)241 static int r_assoc_fetch_bucket(assoc,key,len,bucketp)
242 r_assoc *assoc;
243 char *key;
244 int len;
245 r_assoc_el **bucketp;
246 {
247 UINT4 hash_value;
248 r_assoc_el *bucket;
249
250 hash_value=assoc->hash_func(key,len,assoc->bits);
251
252 for(bucket=assoc->chains[hash_value];bucket;bucket=bucket->next){
253 if(bucket->key_len == len && !memcmp(bucket->key,key,len)){
254 *bucketp=bucket;
255 return(0);
256 }
257 }
258
259 return(R_NOT_FOUND);
260 }
261
r_assoc_fetch(assoc,key,len,datap)262 int r_assoc_fetch(assoc,key,len,datap)
263 r_assoc *assoc;
264 char *key;
265 int len;
266 void **datap;
267 {
268 r_assoc_el *bucket;
269 int r;
270
271 if(r=r_assoc_fetch_bucket(assoc,key,len,&bucket)){
272 if(r!=R_NOT_FOUND)
273 ERETURN(r);
274 return(r);
275 }
276
277 *datap=bucket->data;
278 return(0);
279 }
280
r_assoc_insert(assoc,key,len,data,copy,destroy,how)281 int r_assoc_insert(assoc,key,len,data,copy,destroy,how)
282 r_assoc *assoc;
283 char *key;
284 int len;
285 void *data;
286 int (*copy)(void **knew,void *old);
287 int (*destroy)(void *ptr);
288 int how;
289 {
290 r_assoc_el *bucket,*new_bucket=0;
291 int r,_status;
292
293 if(r=r_assoc_fetch_bucket(assoc,key,len,&bucket)){
294 /*Note that we compute the hash value twice*/
295 UINT4 hash_value;
296
297 if(r!=R_NOT_FOUND)
298 ABORT(r);
299 hash_value=assoc->hash_func(key,len,assoc->bits);
300
301 if(!(new_bucket=(r_assoc_el *)RCALLOC(sizeof(r_assoc_el))))
302 ABORT(R_NO_MEMORY);
303 if(!(new_bucket->key=(char *)RMALLOC(len)))
304 ABORT(R_NO_MEMORY);
305 memcpy(new_bucket->key,key,len);
306 new_bucket->key_len=len;
307
308 /*Insert at the list head. Is FIFO a good algorithm?*/
309 if(assoc->chains[hash_value])
310 assoc->chains[hash_value]->prev=new_bucket;
311 new_bucket->next=assoc->chains[hash_value];
312 assoc->chains[hash_value]=new_bucket;
313 bucket=new_bucket;
314 }
315 else{
316 if(!(how&R_ASSOC_REPLACE))
317 ABORT(R_ALREADY);
318
319 if(bucket->destroy)
320 bucket->destroy(bucket->data);
321 }
322
323 bucket->data=data;
324 bucket->copy=copy;
325 bucket->destroy=destroy;
326 assoc->num_elements++;
327
328 _status=0;
329 abort:
330 if(_status && new_bucket){
331 RFREE(new_bucket->key);
332 RFREE(new_bucket);
333 }
334 return(_status);
335 }
336
r_assoc_delete(assoc,key,len)337 int r_assoc_delete(assoc,key,len)
338 r_assoc *assoc;
339 char *key;
340 int len;
341 {
342 int r;
343 r_assoc_el *bucket;
344 UINT4 hash_value;
345
346 if(r=r_assoc_fetch_bucket(assoc,key,len,&bucket)){
347 if(r!=R_NOT_FOUND)
348 ERETURN(r);
349 return(r);
350 }
351
352 /* Now remove the element from the hash chain */
353 if(bucket->prev){
354 bucket->prev->next=bucket->next;
355 }
356 else {
357 hash_value=assoc->hash_func(key,len,assoc->bits);
358 assoc->chains[hash_value]=bucket->next;
359 }
360
361 if(bucket->next)
362 bucket->next->prev=bucket->prev;
363
364 /* Remove the data */
365 if(bucket->destroy)
366 bucket->destroy(bucket->data);
367
368 RFREE(bucket->key);
369 RFREE(bucket);
370 assoc->num_elements--;
371
372 return(0);
373 }
374
r_assoc_copy(knewp,old)375 int r_assoc_copy(knewp,old)
376 r_assoc **knewp;
377 r_assoc *old;
378 {
379 int r,_status,i;
380 r_assoc *knew;
381
382 if(!(knew=(r_assoc *)RCALLOC(sizeof(r_assoc))))
383 ABORT(R_NO_MEMORY);
384 knew->size=old->size;
385 knew->bits=old->bits;
386 knew->hash_func=old->hash_func;
387
388 if(!(knew->chains=(r_assoc_el **)RCALLOC(sizeof(r_assoc_el)*old->size)))
389 ABORT(R_NO_MEMORY);
390 for(i=0;i<knew->size;i++){
391 if(r=copy_assoc_chain(knew->chains+i,old->chains[i]))
392 ABORT(r);
393 }
394 knew->num_elements=old->num_elements;
395
396 *knewp=knew;
397
398 _status=0;
399 abort:
400 if(_status){
401 r_assoc_destroy(&knew);
402 }
403 return(_status);
404 }
405
r_assoc_num_elements(r_assoc * assoc,int * sizep)406 int r_assoc_num_elements(r_assoc *assoc,int *sizep)
407 {
408 *sizep=assoc->num_elements;
409
410 return(0);
411 }
412
r_assoc_init_iter(assoc,iter)413 int r_assoc_init_iter(assoc,iter)
414 r_assoc *assoc;
415 r_assoc_iterator *iter;
416 {
417 int i;
418
419 iter->assoc=assoc;
420 iter->prev_chain=-1;
421 iter->prev=0;
422
423 iter->next_chain=assoc->size;
424 iter->next=0;
425
426 for(i=0;i<assoc->size;i++){
427 if(assoc->chains[i]!=0){
428 iter->next_chain=i;
429 iter->next=assoc->chains[i];
430 break;
431 }
432 }
433
434 return(0);
435 }
436
r_assoc_iter(iter,key,keyl,val)437 int r_assoc_iter(iter,key,keyl,val)
438 r_assoc_iterator *iter;
439 void **key;
440 int *keyl;
441 void **val;
442 {
443 int i;
444 r_assoc_el *ret;
445
446 if(!iter->next)
447 return(R_EOD);
448 ret=iter->next;
449
450 *key=ret->key;
451 *keyl=ret->key_len;
452 *val=ret->data;
453
454 /* Now increment */
455 iter->prev_chain=iter->next_chain;
456 iter->prev=iter->next;
457
458 /* More on this chain */
459 if(iter->next->next){
460 iter->next=iter->next->next;
461 }
462 else{
463 iter->next=0;
464
465 /* FInd the next occupied chain*/
466 for(i=iter->next_chain+1;i<iter->assoc->size;i++){
467 if(iter->assoc->chains[i]){
468 iter->next_chain=i;
469 iter->next=iter->assoc->chains[i];
470 break;
471 }
472 }
473 }
474
475 return(0);
476 }
477
478 /* Delete the last returned value*/
r_assoc_iter_delete(iter)479 int r_assoc_iter_delete(iter)
480 r_assoc_iterator *iter;
481 {
482 /* First unhook it from the list*/
483 if(!iter->prev->prev){
484 /* First element*/
485 iter->assoc->chains[iter->prev_chain]=iter->prev->next;
486 }
487 else{
488 iter->prev->prev->next=iter->prev->next;
489 }
490
491 if(iter->prev->next){
492 iter->prev->next->prev=iter->prev->prev;
493 }
494
495 if (iter->prev->destroy)
496 iter->prev->destroy(iter->prev->data);
497
498 iter->assoc->num_elements--;
499 RFREE(iter->prev->key);
500 RFREE(iter->prev);
501 return(0);
502 }
503
504
505 /*This is a hack from AMS. Supposedly, it's pretty good for strings, even
506 though it doesn't take into account all the data*/
r_assoc_simple_hash_compute(key,len,bits)507 int r_assoc_simple_hash_compute(key,len,bits)
508 char *key;
509 int len;
510 int bits;
511 {
512 UINT4 h=0;
513
514 h=key[0] +(key[len-1] * len);
515
516 h &= (1<<bits) - 1;
517
518 return(h);
519 }
520
521
522 int r_crc32(char *data,int len,UINT4 *crcval);
523
r_assoc_crc32_hash_compute(data,len,bits)524 int r_assoc_crc32_hash_compute(data,len,bits)
525 char *data;
526 int len;
527 int bits;
528 {
529 UINT4 res;
530 UINT4 mask;
531
532 /* First compute the CRC value */
533 if(r_crc32(data,len,&res))
534 ERETURN(R_INTERNAL);
535
536 mask=~(0xffffffff<<bits);
537
538 return(res & mask);
539 }
540