Line data Source code
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 : static char *RCSSTRING __UNUSED__ ="$Id: r_assoc.c,v 1.4 2007/06/08 17:41:49 adamcain Exp $";
94 :
95 : #include <r_common.h>
96 : #include <string.h>
97 : #include "r_assoc.h"
98 :
99 : typedef struct r_assoc_el_ {
100 : char *key;
101 : int key_len;
102 : void *data;
103 : struct r_assoc_el_ *prev;
104 : struct r_assoc_el_ *next;
105 : int (*copy)(void **n,void *old);
106 : int (*destroy)(void *ptr);
107 : } r_assoc_el;
108 :
109 : struct r_assoc_ {
110 : int size;
111 : int bits;
112 : int (*hash_func)(char *key,int len,int size);
113 : r_assoc_el **chains;
114 : UINT4 num_elements;
115 : };
116 :
117 : #define DEFAULT_TABLE_BITS 5
118 :
119 : static int destroy_assoc_chain(r_assoc_el *chain);
120 : static int r_assoc_fetch_bucket(r_assoc *assoc,
121 : char *key,int len,r_assoc_el **bucketp);
122 : static int copy_assoc_chain(r_assoc_el **knewp, r_assoc_el *old);
123 :
124 0 : int r_assoc_create(assocp,hash_func,bits)
125 : r_assoc **assocp;
126 : int (*hash_func)(char *key,int len,int size);
127 : int bits;
128 : {
129 0 : r_assoc *assoc=0;
130 : int _status;
131 :
132 0 : if(!(assoc=(r_assoc *)RCALLOC(sizeof(r_assoc))))
133 0 : ABORT(R_NO_MEMORY);
134 0 : assoc->size=(1<<bits);
135 0 : assoc->bits=bits;
136 0 : assoc->hash_func=hash_func;
137 :
138 0 : if(!(assoc->chains=(r_assoc_el **)RCALLOC(sizeof(r_assoc_el *)*
139 : assoc->size)))
140 0 : ABORT(R_NO_MEMORY);
141 :
142 0 : *assocp=assoc;
143 :
144 0 : _status=0;
145 : abort:
146 0 : if(_status){
147 0 : r_assoc_destroy(&assoc);
148 : }
149 0 : return(_status);
150 : }
151 :
152 0 : int r_assoc_destroy(assocp)
153 : r_assoc **assocp;
154 : {
155 : r_assoc *assoc;
156 : int i;
157 :
158 0 : if(!assocp || !*assocp)
159 0 : return(0);
160 :
161 0 : assoc=*assocp;
162 0 : for(i=0;i<assoc->size;i++)
163 0 : destroy_assoc_chain(assoc->chains[i]);
164 :
165 0 : RFREE(assoc->chains);
166 0 : RFREE(*assocp);
167 :
168 0 : return(0);
169 : }
170 :
171 0 : static int destroy_assoc_chain(chain)
172 : r_assoc_el *chain;
173 : {
174 : r_assoc_el *nxt;
175 :
176 0 : while(chain){
177 0 : nxt=chain->next;
178 :
179 0 : if(chain->destroy)
180 0 : chain->destroy(chain->data);
181 :
182 0 : RFREE(chain->key);
183 :
184 0 : RFREE(chain);
185 0 : chain=nxt;
186 : }
187 :
188 0 : return(0);
189 : }
190 :
191 0 : static int copy_assoc_chain(knewp,old)
192 : r_assoc_el **knewp;
193 : r_assoc_el *old;
194 : {
195 0 : r_assoc_el *knew=0,*ptr,*tmp;
196 : int r,_status;
197 :
198 0 : ptr=0; /* Pacify GCC's uninitialized warning.
199 : It's not correct */
200 0 : if(!old) {
201 0 : *knewp=0;
202 0 : return(0);
203 : }
204 0 : for(;old;old=old->next){
205 0 : if(!(tmp=(r_assoc_el *)RCALLOC(sizeof(r_assoc_el))))
206 0 : ABORT(R_NO_MEMORY);
207 :
208 0 : if(!knew){
209 0 : knew=tmp;
210 0 : ptr=knew;
211 : }
212 : else{
213 0 : ptr->next=tmp;
214 0 : tmp->prev=ptr;
215 0 : ptr=tmp;
216 : }
217 :
218 0 : ptr->destroy=old->destroy;
219 0 : ptr->copy=old->copy;
220 :
221 0 : if(old->copy){
222 0 : if(r=old->copy(&ptr->data,old->data))
223 0 : ABORT(r);
224 : }
225 : else
226 0 : ptr->data=old->data;
227 :
228 0 : if(!(ptr->key=(char *)RMALLOC(old->key_len)))
229 0 : ABORT(R_NO_MEMORY);
230 0 : memcpy(ptr->key,old->key,ptr->key_len=old->key_len);
231 : }
232 :
233 0 : *knewp=knew;
234 :
235 0 : _status=0;
236 : abort:
237 0 : if(_status){
238 0 : destroy_assoc_chain(knew);
239 : }
240 0 : return(_status);
241 : }
242 :
243 0 : static int r_assoc_fetch_bucket(assoc,key,len,bucketp)
244 : r_assoc *assoc;
245 : char *key;
246 : int len;
247 : r_assoc_el **bucketp;
248 : {
249 : UINT4 hash_value;
250 : r_assoc_el *bucket;
251 :
252 0 : hash_value=assoc->hash_func(key,len,assoc->bits);
253 :
254 0 : for(bucket=assoc->chains[hash_value];bucket;bucket=bucket->next){
255 0 : if(bucket->key_len == len && !memcmp(bucket->key,key,len)){
256 0 : *bucketp=bucket;
257 0 : return(0);
258 : }
259 : }
260 :
261 0 : return(R_NOT_FOUND);
262 : }
263 :
264 0 : int r_assoc_fetch(assoc,key,len,datap)
265 : r_assoc *assoc;
266 : char *key;
267 : int len;
268 : void **datap;
269 : {
270 : r_assoc_el *bucket;
271 : int r;
272 :
273 0 : if(r=r_assoc_fetch_bucket(assoc,key,len,&bucket)){
274 0 : if(r!=R_NOT_FOUND)
275 0 : ERETURN(r);
276 0 : return(r);
277 : }
278 :
279 0 : *datap=bucket->data;
280 0 : return(0);
281 : }
282 :
283 0 : int r_assoc_insert(assoc,key,len,data,copy,destroy,how)
284 : r_assoc *assoc;
285 : char *key;
286 : int len;
287 : void *data;
288 : int (*copy)(void **knew,void *old);
289 : int (*destroy)(void *ptr);
290 : int how;
291 : {
292 0 : r_assoc_el *bucket,*new_bucket=0;
293 : int r,_status;
294 :
295 0 : if(r=r_assoc_fetch_bucket(assoc,key,len,&bucket)){
296 : /*Note that we compute the hash value twice*/
297 : UINT4 hash_value;
298 :
299 0 : if(r!=R_NOT_FOUND)
300 0 : ABORT(r);
301 0 : hash_value=assoc->hash_func(key,len,assoc->bits);
302 :
303 0 : if(!(new_bucket=(r_assoc_el *)RCALLOC(sizeof(r_assoc_el))))
304 0 : ABORT(R_NO_MEMORY);
305 0 : if(!(new_bucket->key=(char *)RMALLOC(len)))
306 0 : ABORT(R_NO_MEMORY);
307 0 : memcpy(new_bucket->key,key,len);
308 0 : new_bucket->key_len=len;
309 :
310 : /*Insert at the list head. Is FIFO a good algorithm?*/
311 0 : if(assoc->chains[hash_value])
312 0 : assoc->chains[hash_value]->prev=new_bucket;
313 0 : new_bucket->next=assoc->chains[hash_value];
314 0 : assoc->chains[hash_value]=new_bucket;
315 0 : bucket=new_bucket;
316 : }
317 : else{
318 0 : if(!(how&R_ASSOC_REPLACE))
319 0 : ABORT(R_ALREADY);
320 :
321 0 : if(bucket->destroy)
322 0 : bucket->destroy(bucket->data);
323 : }
324 :
325 0 : bucket->data=data;
326 0 : bucket->copy=copy;
327 0 : bucket->destroy=destroy;
328 0 : assoc->num_elements++;
329 :
330 0 : _status=0;
331 : abort:
332 0 : if(_status && new_bucket){
333 0 : RFREE(new_bucket->key);
334 0 : RFREE(new_bucket);
335 : }
336 0 : return(_status);
337 : }
338 :
339 0 : int r_assoc_delete(assoc,key,len)
340 : r_assoc *assoc;
341 : char *key;
342 : int len;
343 : {
344 : int r;
345 : r_assoc_el *bucket;
346 : UINT4 hash_value;
347 :
348 0 : if(r=r_assoc_fetch_bucket(assoc,key,len,&bucket)){
349 0 : if(r!=R_NOT_FOUND)
350 0 : ERETURN(r);
351 0 : return(r);
352 : }
353 :
354 : /* Now remove the element from the hash chain */
355 0 : if(bucket->prev){
356 0 : bucket->prev->next=bucket->next;
357 : }
358 : else {
359 0 : hash_value=assoc->hash_func(key,len,assoc->bits);
360 0 : assoc->chains[hash_value]=bucket->next;
361 : }
362 :
363 0 : if(bucket->next)
364 0 : bucket->next->prev=bucket->prev;
365 :
366 : /* Remove the data */
367 0 : if(bucket->destroy)
368 0 : bucket->destroy(bucket->data);
369 :
370 0 : RFREE(bucket->key);
371 0 : RFREE(bucket);
372 0 : assoc->num_elements--;
373 :
374 0 : return(0);
375 : }
376 :
377 0 : int r_assoc_copy(knewp,old)
378 : r_assoc **knewp;
379 : r_assoc *old;
380 : {
381 : int r,_status,i;
382 : r_assoc *knew;
383 :
384 0 : if(!(knew=(r_assoc *)RCALLOC(sizeof(r_assoc))))
385 0 : ABORT(R_NO_MEMORY);
386 0 : knew->size=old->size;
387 0 : knew->bits=old->bits;
388 0 : knew->hash_func=old->hash_func;
389 :
390 0 : if(!(knew->chains=(r_assoc_el **)RCALLOC(sizeof(r_assoc_el)*old->size)))
391 0 : ABORT(R_NO_MEMORY);
392 0 : for(i=0;i<knew->size;i++){
393 0 : if(r=copy_assoc_chain(knew->chains+i,old->chains[i]))
394 0 : ABORT(r);
395 : }
396 0 : knew->num_elements=old->num_elements;
397 :
398 0 : *knewp=knew;
399 :
400 0 : _status=0;
401 : abort:
402 0 : if(_status){
403 0 : r_assoc_destroy(&knew);
404 : }
405 0 : return(_status);
406 : }
407 :
408 0 : int r_assoc_num_elements(r_assoc *assoc,int *sizep)
409 : {
410 0 : *sizep=assoc->num_elements;
411 :
412 0 : return(0);
413 : }
414 :
415 0 : int r_assoc_init_iter(assoc,iter)
416 : r_assoc *assoc;
417 : r_assoc_iterator *iter;
418 : {
419 : int i;
420 :
421 0 : iter->assoc=assoc;
422 0 : iter->prev_chain=-1;
423 0 : iter->prev=0;
424 :
425 0 : iter->next_chain=assoc->size;
426 0 : iter->next=0;
427 :
428 0 : for(i=0;i<assoc->size;i++){
429 0 : if(assoc->chains[i]!=0){
430 0 : iter->next_chain=i;
431 0 : iter->next=assoc->chains[i];
432 0 : break;
433 : }
434 : }
435 :
436 0 : return(0);
437 : }
438 :
439 0 : int r_assoc_iter(iter,key,keyl,val)
440 : r_assoc_iterator *iter;
441 : void **key;
442 : int *keyl;
443 : void **val;
444 : {
445 : int i;
446 : r_assoc_el *ret;
447 :
448 0 : if(!iter->next)
449 0 : return(R_EOD);
450 0 : ret=iter->next;
451 :
452 0 : *key=ret->key;
453 0 : *keyl=ret->key_len;
454 0 : *val=ret->data;
455 :
456 : /* Now increment */
457 0 : iter->prev_chain=iter->next_chain;
458 0 : iter->prev=iter->next;
459 :
460 : /* More on this chain */
461 0 : if(iter->next->next){
462 0 : iter->next=iter->next->next;
463 : }
464 : else{
465 0 : iter->next=0;
466 :
467 : /* FInd the next occupied chain*/
468 0 : for(i=iter->next_chain+1;i<iter->assoc->size;i++){
469 0 : if(iter->assoc->chains[i]){
470 0 : iter->next_chain=i;
471 0 : iter->next=iter->assoc->chains[i];
472 0 : break;
473 : }
474 : }
475 : }
476 :
477 0 : return(0);
478 : }
479 :
480 : /* Delete the last returned value*/
481 0 : int r_assoc_iter_delete(iter)
482 : r_assoc_iterator *iter;
483 : {
484 : /* First unhook it from the list*/
485 0 : if(!iter->prev->prev){
486 : /* First element*/
487 0 : iter->assoc->chains[iter->prev_chain]=iter->prev->next;
488 : }
489 : else{
490 0 : iter->prev->prev->next=iter->prev->next;
491 : }
492 :
493 0 : if(iter->prev->next){
494 0 : iter->prev->next->prev=iter->prev->prev;
495 : }
496 :
497 0 : if (iter->prev->destroy)
498 0 : iter->prev->destroy(iter->prev->data);
499 :
500 0 : iter->assoc->num_elements--;
501 0 : RFREE(iter->prev->key);
502 0 : RFREE(iter->prev);
503 0 : return(0);
504 : }
505 :
506 :
507 : /*This is a hack from AMS. Supposedly, it's pretty good for strings, even
508 : though it doesn't take into account all the data*/
509 0 : int r_assoc_simple_hash_compute(key,len,bits)
510 : char *key;
511 : int len;
512 : int bits;
513 : {
514 0 : UINT4 h=0;
515 :
516 0 : h=key[0] +(key[len-1] * len);
517 :
518 0 : h &= (1<<bits) - 1;
519 :
520 0 : return(h);
521 : }
522 :
523 :
524 : int r_crc32(char *data,int len,UINT4 *crcval);
525 :
526 0 : int r_assoc_crc32_hash_compute(data,len,bits)
527 : char *data;
528 : int len;
529 : int bits;
530 : {
531 : UINT4 res;
532 : UINT4 mask;
533 :
534 : /* First compute the CRC value */
535 0 : if(r_crc32(data,len,&res))
536 0 : ERETURN(R_INTERNAL);
537 :
538 0 : mask=~(0xffffffff<<bits);
539 :
540 0 : return(res & mask);
541 : }
|
