1 /*
2 Copyright (c) 1994 - 2010, Lawrence Livermore National Security, LLC.
3 LLNL-CODE-425250.
4 All rights reserved.
5
6 This file is part of Silo. For details, see silo.llnl.gov.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions
10 are met:
11
12 * Redistributions of source code must retain the above copyright
13 notice, this list of conditions and the disclaimer below.
14 * Redistributions in binary form must reproduce the above copyright
15 notice, this list of conditions and the disclaimer (as noted
16 below) in the documentation and/or other materials provided with
17 the distribution.
18 * Neither the name of the LLNS/LLNL nor the names of its
19 contributors may be used to endorse or promote products derived
20 from this software without specific prior written permission.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LAWRENCE
26 LIVERMORE NATIONAL SECURITY, LLC, THE U.S. DEPARTMENT OF ENERGY OR
27 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34
35 This work was produced at Lawrence Livermore National Laboratory under
36 Contract No. DE-AC52-07NA27344 with the DOE.
37
38 Neither the United States Government nor Lawrence Livermore National
39 Security, LLC nor any of their employees, makes any warranty, express
40 or implied, or assumes any liability or responsibility for the
41 accuracy, completeness, or usefulness of any information, apparatus,
42 product, or process disclosed, or represents that its use would not
43 infringe privately-owned rights.
44
45 Any reference herein to any specific commercial products, process, or
46 services by trade name, trademark, manufacturer or otherwise does not
47 necessarily constitute or imply its endorsement, recommendation, or
48 favoring by the United States Government or Lawrence Livermore
49 National Security, LLC. The views and opinions of authors expressed
50 herein do not necessarily state or reflect those of the United States
51 Government or Lawrence Livermore National Security, LLC, and shall not
52 be used for advertising or product endorsement purposes.
53 */
54 #include "config.h" /* For HAVE_MEMMOVE test. */
55 /*
56 * SCHASH.C - routines to manipulate hash tables
57 * - intended to be a complete module that
58 * - can be used with any application by defining
59 * - the struct, hashel, in SCORE.H suitably
60 *
61 * Source Version: 2.0
62 * Software Release #92-0043
63 *
64 */
65 #include "score.h"
66
67 /*-------------------------------------------------------------------------
68 Function: bjhash
69
70 Purpose: Hash a variable length stream of bytes into a 32-bit value.
71
72 Programmer: By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net.
73
74 You may use this code any way you wish, private, educational, or
75 commercial. It's free. However, do NOT use for cryptographic purposes.
76
77 See http://burtleburtle.net/bob/hash/evahash.html
78 *-------------------------------------------------------------------------*/
79
80 #define bjhash_mix(a,b,c) \
81 { \
82 a -= b; a -= c; a ^= (c>>13); \
83 b -= c; b -= a; b ^= (a<<8); \
84 c -= a; c -= b; c ^= (b>>13); \
85 a -= b; a -= c; a ^= (c>>12); \
86 b -= c; b -= a; b ^= (a<<16); \
87 c -= a; c -= b; c ^= (b>>5); \
88 a -= b; a -= c; a ^= (c>>3); \
89 b -= c; b -= a; b ^= (a<<10); \
90 c -= a; c -= b; c ^= (b>>15); \
91 }
92
93 #define K(I,L) (((unsigned int)((unsigned char)k[I]))<<L)
bjhash(register const char * k,register unsigned int length,register unsigned int initval)94 static unsigned int bjhash(register const char *k,
95 register unsigned int length, register unsigned int initval)
96 {
97 register unsigned int a,b,c,len;
98
99 len = length;
100 a = b = 0x9e3779b9;
101 c = initval;
102
103 while (len >= 12)
104 {
105 a += (K(0,0) + K(1,8) + K(2,16) + K(3,24));
106 b += (K(4,0) + K(5,8) + K(6,16) + K(7,24));
107 c += (K(8,0) + K(9,8) + K(10,16) + K(11,24));
108 bjhash_mix(a,b,c);
109 k += 12; len -= 12;
110 }
111
112 c += length;
113
114 switch(len)
115 {
116 case 11: c+=K(10,24);
117 case 10: c+=K(9,16);
118 case 9 : c+=K(8,8);
119 case 8 : b+=K(7,24);
120 case 7 : b+=K(6,16);
121 case 6 : b+=K(5,8);
122 case 5 : b+=K(4,0);
123 case 4 : a+=K(3,24);
124 case 3 : a+=K(2,16);
125 case 2 : a+=K(1,8);
126 case 1 : a+=K(0,0);
127 }
128
129 bjhash_mix(a,b,c);
130
131 return c;
132 }
133 #undef K
134 #undef bjhash_mix
135
136
137 /*-------------------------------------------------------------------------
138 * Function: lite_SC_hash
139 *
140 * Purpose: Compute hash value for string S in a table of SIZE
141 *
142 * Return: Success:
143 *
144 * Failure:
145 *
146 * Programmer: Adapted from PACT SCORE
147 * Mar 12, 1996
148 *
149 * Modifications:
150 *
151 * Mark C. Miller, Fri Apr 13 22:43:19 PDT 2012
152 * Use "BJ Hash"
153 *-------------------------------------------------------------------------
154 */
155 int
lite_SC_hash(char * s,int size)156 lite_SC_hash (char *s, int size) {
157
158 int len = strlen(s);
159 unsigned int hashval = bjhash(s, len, 0xDeadBeef);
160 if (hashval > INT_MAX) hashval -= INT_MAX;
161 return hashval % size;
162 }
163
164
165 /*-------------------------------------------------------------------------
166 * Function: lite_SC_lookup
167 *
168 * Purpose: Lookup S in hash table TABLE.
169 *
170 * Return: Success: Ptr to object
171 *
172 * Failure: NULL
173 *
174 * Programmer: Adapted from PACT SCORE
175 * Mar 12, 1996
176 *
177 * Modifications:
178 *
179 *-------------------------------------------------------------------------
180 */
181 hashel *
lite_SC_lookup(char * s,HASHTAB * tab)182 lite_SC_lookup (char *s, HASHTAB *tab) {
183
184 hashel *np, **tb;
185 int sz;
186
187 if (tab == NULL) return(NULL);
188
189 sz = tab->size;
190 tb = tab->table;
191 for (np = tb[lite_SC_hash(s, sz)]; np != NULL; np = np->next) {
192 if (strcmp(s, np->name) == 0) return(np); /* found it */
193 }
194
195 return(NULL); /* not found */
196 }
197
198
199 /*-------------------------------------------------------------------------
200 * Function: lite_SC_def_lookup
201 *
202 * Purpose: Return a ptr to the object version of LOOKUP.
203 *
204 * Return: Success: ptr to the object version of LOOKUP.
205 *
206 * Failure: NULL
207 *
208 * Programmer: Adapted from PACT SCORE
209 * Mar 12, 1996
210 *
211 * Modifications:
212 *
213 *-------------------------------------------------------------------------
214 */
215 lite_SC_byte *
lite_SC_def_lookup(char * s,HASHTAB * tab)216 lite_SC_def_lookup (char *s, HASHTAB *tab) {
217
218 hashel *np;
219
220 if (tab == NULL) return(NULL);
221
222 np = lite_SC_lookup(s, tab);
223 if (np != NULL) return(np->def);
224 else return(NULL);
225 }
226
227
228 /*-------------------------------------------------------------------------
229 * Function: lite_SC_install
230 *
231 * Purpose:
232 *
233 * Return: Success:
234 *
235 * Failure:
236 *
237 * Programmer: Adapted from PACT SCORE
238 * Mar 12, 1996
239 *
240 * Modifications:
241 *
242 *-------------------------------------------------------------------------
243 */
244 hashel *
lite_SC_install(char * name,lite_SC_byte * obj,char * type,HASHTAB * tab)245 lite_SC_install (char *name, lite_SC_byte *obj, char *type, HASHTAB *tab) {
246
247 return _lite_SC_install (name, obj, type, tab);
248 }
249
250
251 /*-------------------------------------------------------------------------
252 * Function: _lite_SC_install
253 *
254 * Purpose: Install an object in the hash table. The object type is
255 * defined in hash.h and is generic to enhance the
256 * portability of this code. WARNING: do NOT use litereals
257 * or volatiles for the type--for efficiency they are
258 * not strsave'd!!!
259 *
260 * Return: Success:
261 *
262 * Failure:
263 *
264 * Programmer: Adapted from PACT SCORE
265 * Mar 12, 1996
266 *
267 * Modifications:
268 * Eric Brugger, Tue Dec 8 16:57:20 PST 1998
269 * Remove unnecessary calls to lite_SC_mark, since reference count now
270 * set when allocated. The mark flag is now rendered useless since
271 * the memory will always be marked when it is allocated.
272 *
273 * Eric Brugger, Thu Sep 23 10:16:30 PDT 1999
274 * Remove the mark flag from the argument list.
275 *
276 *-------------------------------------------------------------------------
277 */
278 hashel *
_lite_SC_install(char * name,lite_SC_byte * obj,char * type,HASHTAB * tab)279 _lite_SC_install (char *name, lite_SC_byte *obj, char *type, HASHTAB *tab) {
280
281 hashel *np, **tb;
282 int hashval, sz;
283
284 sz = tab->size;
285 tb = tab->table;
286 np = lite_SC_lookup(name, tab);
287
288 /*
289 * If not found install it.
290 */
291 if (np == NULL) {
292 np = FMAKE(hashel, "SC_INSTALL:np");
293 if (np == NULL) return(NULL);
294
295 np->name = lite_SC_strsavef(name, "char*:SC_INSTALL:name");
296 if (np->name == NULL) return(NULL);
297
298 hashval = lite_SC_hash(np->name, sz);
299 np->next = tb[hashval];
300 tb[hashval] = np;
301 (tab->nelements)++;
302 }
303
304 np->type = type;
305 np->def = obj;
306
307 return(np);
308 }
309
310
311 /*-------------------------------------------------------------------------
312 * Function: lite_SC_hash_rem
313 *
314 * Purpose: Remove the specified entry from the given hash table.
315 *
316 * Return: Success: TRUE
317 *
318 * Failure: FALSE
319 *
320 * Programmer: Adapted from PACT SCORE
321 * Mar 12, 1996
322 *
323 * Modifications:
324 *
325 *-------------------------------------------------------------------------
326 */
327 int
lite_SC_hash_rem(char * name,HASHTAB * tab)328 lite_SC_hash_rem (char *name, HASHTAB *tab) {
329
330 hashel *np, *nxt, **tb;
331 int sz, i;
332
333 sz = tab->size;
334 tb = tab->table;
335 i = lite_SC_hash(name, sz);
336 np = tb[i];
337
338 /*
339 * If not found nothing else to do.
340 */
341 if (np == NULL) {
342 return(FALSE);
343 } else {
344 if (strcmp(name, np->name) == 0) {
345 tb[i] = np->next;
346
347 /*
348 * Undo the MARK in SC_install.
349 */
350 SFREE(np->def);
351 SFREE(np->name);
352 SFREE(np);
353 (tab->nelements)--;
354 return(TRUE);
355
356 } else {
357 /*
358 * Otherwise search for it.
359 */
360 for (; np->next != NULL; np = np->next) {
361 nxt = np->next;
362 if (strcmp(name, nxt->name) == 0) {
363 np->next = nxt->next;
364 SFREE(nxt->def);
365 SFREE(nxt->name);
366 SFREE(nxt);
367 (tab->nelements)--;
368 return(TRUE);
369 }
370 }
371 }
372 }
373 return(FALSE);
374 }
375
376
377 /*-------------------------------------------------------------------------
378 * Function: lite_SC_hash_clr
379 *
380 * Purpose: Clear the specified hash table.
381 *
382 * Return: void
383 *
384 * Programmer: Adapted from PACT SCORE
385 * Mar 12, 1996
386 *
387 * Modifications:
388 *
389 *-------------------------------------------------------------------------
390 */
391 void
lite_SC_hash_clr(HASHTAB * tab)392 lite_SC_hash_clr (HASHTAB *tab) {
393
394 int i, sz;
395 hashel **tb, *np, *nxt;
396
397 sz = tab->size;
398 tb = tab->table;
399 for (i = 0; i < sz; i++) {
400 for (np = tb[i]; np != NULL; np = nxt) {
401 nxt = np->next;
402
403 /*
404 * Undo the MARK in SC_install.
405 */
406 SFREE(np->def);
407 SFREE(np->name);
408 SFREE(np);
409 }
410 tb[i] = NULL;
411 }
412 }
413
414
415 /*-------------------------------------------------------------------------
416 * Function: lite_SC_make_hash_table
417 *
418 * Purpose: Allocate and initialize a hash table of size SZ.
419 *
420 * Return: Success: HASHTAB pointer
421 *
422 * Failure: NULL
423 *
424 * Programmer: Adapted from PACT SCORE
425 * Mar 12, 1996
426 *
427 * Modifications:
428 *
429 *-------------------------------------------------------------------------
430 */
431 HASHTAB *
lite_SC_make_hash_table(int sz,int docflag)432 lite_SC_make_hash_table (int sz, int docflag) {
433
434 HASHTAB *tab;
435 hashel **tb;
436 int i;
437
438 /*
439 * Allocate a new hash table.
440 */
441 tab = FMAKE(HASHTAB, "SC_MAKE_HASH_TABLE:tab");
442
443 if (tab == NULL) {
444 printf("\nCannot allocate a new hash table of size %d\n", sz);
445 return(NULL);
446 }
447
448 tb = FMAKE_N(hashel *, sz, "SC_MAKE_HASH_TABLE:tb");
449 if (tb == NULL) return(NULL);
450
451 tab->size = sz;
452 tab->docp = docflag;
453 tab->nelements = 0;
454 tab->table = tb;
455
456 /*
457 * Explicitly NULL the pointers.
458 */
459 for (i = 0; i < sz; i++) tb[i] = NULL;
460
461 return(tab);
462 }
463
464
465 /*-------------------------------------------------------------------------
466 * Function: lite_SC_rl_hash_table
467 *
468 * Purpose: Release a hash table. Call SC_HASH_CLR first to
469 * release the contents of the table.
470 *
471 * Return: void
472 *
473 * Programmer: Adapted from PACT SCORE
474 * Mar 12, 1996
475 *
476 * Modifications:
477 *
478 *-------------------------------------------------------------------------
479 */
480 void
lite_SC_rl_hash_table(HASHTAB * tab)481 lite_SC_rl_hash_table (HASHTAB *tab) {
482
483 lite_SC_hash_clr(tab);
484
485 SFREE(tab->table);
486 SFREE(tab);
487 }
488
489
490 /*-------------------------------------------------------------------------
491 * Function: lite_SC_hash_dump
492 *
493 * Purpose: Return a array of pointers whose entries point to the
494 * installed names in the given hash table and are alphabetically
495 * ordered by strcmp().
496 *
497 * Return: Success:
498 *
499 * Failure:
500 *
501 * Programmer: Adapted from PACT SCORE
502 * Mar 12, 1996
503 *
504 * Modifications:
505 *
506 *-------------------------------------------------------------------------
507 */
508 char **
lite_SC_hash_dump(HASHTAB * tab,char * patt)509 lite_SC_hash_dump (HASHTAB *tab, char *patt) {
510
511 return lite_SC_dump_hash (tab, patt, TRUE);
512 }
513
514
515 /*-------------------------------------------------------------------------
516 * Function: lite_SC_dump_hash
517 *
518 * Purpose: Return an array of pointers whose entries point to the
519 * installed names in the given hash table.
520 *
521 * Return: Success: Array of ptrs to entries.
522 *
523 * Failure: NULL
524 *
525 * Programmer: Adapted from PACT SCORE
526 * Mar 12, 1996
527 *
528 * Modifications:
529 *
530 *-------------------------------------------------------------------------
531 */
532 char **
lite_SC_dump_hash(HASHTAB * tab,char * patt,int sort)533 lite_SC_dump_hash (HASHTAB *tab, char *patt, int sort) {
534
535 hashel *np, **tb;
536 char **lineptr, *name;
537 int i, sz, nlines;
538
539 if (tab == NULL) return(NULL);
540
541 /*
542 * Allocate a list of pointers to the names in the hash table.
543 */
544 lineptr = FMAKE_N(char *, tab->nelements, "SC_HASH_DUMP:lineptr");
545 if (lineptr == NULL) return(NULL);
546
547 /*
548 * Fill in the list of pointers to names in the hash table.
549 */
550 sz = tab->size;
551 tb = tab->table;
552 nlines = 0;
553 for (i = 0; i < sz; i++) {
554 for (np = tb[i]; np != NULL; np = np->next) {
555 name = np->name;
556 if (patt == NULL) lineptr[nlines++] = name;
557 else if (lite_SC_regx_match(name, patt)) lineptr[nlines++] = name;
558 }
559 }
560
561 /*
562 * Check that the number of names found is what is expected.
563 */
564 if (nlines > tab->nelements) return(NULL);
565
566 REMAKE_N(lineptr, char *, nlines + 1);
567 lineptr[nlines] = NULL;
568
569 /*
570 * Sort the names.
571 */
572 if (sort) lite_SC_string_sort(lineptr, nlines);
573
574 /*
575 * Return the list of names.
576 */
577 return(lineptr);
578 }
579