syck_st.c

filter: Statementstmt 54.3% 94 / 173 Branchbran 51.8% 57 / 110 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 53.3% 151 / 283 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/YAML/Loader/Syck.pm ↑ Summary gram.c »
1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
2  
3 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
4  
5 #include "config.h"
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9 #include "syck_st.h"
10  
11 #ifdef NT
12 #include <malloc.h>
13 #endif
14  
15 #define SIZE32 4
16 #if SIZEOF_LONG == SIZE32
17 typedef long I32;
18 typedef unsigned long U32;
19 #define NUM2I32(x) NUM2LONG(x)
20 #define NUM2U32(x) NUM2ULONG(x)
21 #elif SIZEOF_INT == SIZE32
22 typedef int I32;
23 typedef unsigned int U32;
24 #define NUM2I32(x) NUM2INT(x)
25 #define NUM2U32(x) NUM2UINT(x)
26 #endif
27  
28 typedef struct st_table_entry st_table_entry;
29  
30 struct st_table_entry {
31 unsigned int hash;
32 st_data_t key;
33 st_data_t record;
34 st_table_entry *next;
35 };
36  
37 #define ST_DEFAULT_MAX_DENSITY 5
38 #define ST_DEFAULT_INIT_TABLE_SIZE 11
39  
40 /*
41 * DEFAULT_MAX_DENSITY is the default for the largest we allow the
42 * average number of items per bin before increasing the number of
43 * bins
44 *
45 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
46 * allocated initially
47 *
48 */
49 static int numcmp(st_data_t, st_data_t);
50 static int numhash(st_data_t);
51 static struct st_hash_type type_numhash = {
52 numcmp,
53 numhash,
54 };
55  
56 static int strhash(st_data_t);
57 static int st_strcmp(st_data_t, st_data_t);
58 static struct st_hash_type type_strhash = {
59 st_strcmp,
60 strhash,
61 };
62  
63 static void rehash(st_table *);
64  
65 #define alloc(type) (type*)malloc((unsigned)sizeof(type))
66 #define Calloc(n,s) (char*)calloc((n),(s))
67  
68 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
69  
70 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
71 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
72  
73 /*
74 * MINSIZE is the minimum size of a dictionary.
75 */
76  
77 #define MINSIZE 8
78  
79 /*
80 Table of prime numbers 2^n+a, 2<=n<=30.
81 */
82 static long primes[] = {
83 8 + 3,
84 16 + 3,
85 32 + 5,
86 64 + 3,
87 128 + 3,
88 256 + 27,
89 512 + 9,
90 1024 + 9,
91 2048 + 5,
92 4096 + 3,
93 8192 + 27,
94 16384 + 43,
95 32768 + 3,
96 65536 + 45,
97 131072 + 29,
98 262144 + 3,
99 524288 + 21,
100 1048576 + 7,
101 2097152 + 17,
102 4194304 + 15,
103 8388608 + 9,
104 16777216 + 43,
105 33554432 + 35,
106 67108864 + 15,
107 134217728 + 29,
108 268435456 + 3,
109 536870912 + 11,
110 1073741824 + 85,
111 0
112 };
113  
114 static int
115 9202 new_size(int size)
116 {
117 int i;
118  
119 #if 0
120 for (i=3; i<31; i++) {
121 if ((1<<i) > size) return 1<<i;
122 }
123 return -1;
124 #else
125 int newsize;
126  
127 9202 for (i = 0, newsize = MINSIZE;
128 36827 ▶ i < sizeof(primes)/sizeof(primes[0]);
Branch: 1 branch
BranchTrueFalseTotal
i < sizeof(primes)/sizeof(primes[0]); 36827 0 36827
129 27625 i++, newsize <<= 1)
130 {
131 36827 ▶ if (newsize > size) return primes[i];
Branch: 1 branch
BranchTrueFalseTotal
if (newsize > size) return primes[i]; 9202 27625 36827
132 }
133 /* Ran out of polynomials, return last known prime */
134 0 return primes[i > 1 ? i - 2 : 0];
135 #endif
136 }
137  
138 #ifdef HASH_LOG
139 static int collision = 0;
140 static int init_st = 0;
141  
142 static void
143 stat_col()
144 {
145 FILE *f = fopen("/tmp/col", "w");
146 fprintf(f, "collision: %d\n", collision);
147 fclose(f);
148 }
149 #endif
150  
151 st_table*
152 4153 st_init_table_with_size(struct st_hash_type *type, int size)
153 {
154 st_table *tbl;
155  
156 #ifdef HASH_LOG
157 if (init_st == 0) {
158 init_st = 1;
159 atexit(stat_col);
160 }
161 #endif
162  
163 4153 size = new_size(size); /* round up to prime number */
164 4153 ▶ if (size <= 0) size = MINSIZE;
Branch: 1 branch
BranchTrueFalseTotal
if (size <= 0) size = MINSIZE; 0 4153 4153
165  
166 4153 tbl = alloc(st_table);
167 4153 tbl->type = type;
168 4153 tbl->num_entries = 0;
169 4153 tbl->num_bins = size;
170 4153 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
171  
172 4153 return tbl;
173 }
174  
175 st_table*
176 4153 st_init_table(struct st_hash_type *type)
177 {
178 4153 return st_init_table_with_size(type, 0);
179 }
180  
181 st_table*
182 4123 st_init_numtable(void)
183 {
184 4123 return st_init_table(&type_numhash);
185 }
186  
187 st_table*
188 0 st_init_numtable_with_size(int size)
189 {
190 0 return st_init_table_with_size(&type_numhash, size);
191 }
192  
193 st_table*
194 30 st_init_strtable(void)
195 {
196 30 return st_init_table(&type_strhash);
197 }
198  
199 st_table*
200 0 st_init_strtable_with_size(int size)
201 {
202 0 return st_init_table_with_size(&type_strhash, size);
203 }
204  
205 void
206 4153 st_free_table(st_table *table)
207 {
208 register st_table_entry *ptr, *next;
209 int i;
210  
211 4155660 ▶ for(i = 0; i < table->num_bins; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < table->num_bins; i++) { 4151507 4153 4155660
212 4151507 ptr = table->bins[i];
213 22889509 ▶ while (ptr != 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (ptr != 0) { 18738002 4151507 22889509
214 18738002 next = ptr->next;
215 18738002 free(ptr);
216 18738002 ptr = next;
217 }
218 }
219 4153 free(table->bins);
220 4153 free(table);
221 4153 }
222  
223 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
224 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
225  
226 #ifdef HASH_LOG
227 #define COLLISION collision++
228 #else
229 #define COLLISION
230 #endif
231  
232 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
233 bin_pos = hash_val%(table)->num_bins;\
234 ptr = (table)->bins[bin_pos];\
235 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
236 COLLISION;\
237 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
238 ptr = ptr->next;\
239 }\
240 ptr = ptr->next;\
241 }\
242 } while (0)
243  
244 int
245 18784448 st_lookup(st_table *table, st_data_t key, st_data_t *value)
246 {
247 unsigned int hash_val, bin_pos;
248 register st_table_entry *ptr;
249  
250 18784448 hash_val = do_hash(key, table);
251 37976123 ▶ FIND_ENTRY(table, ptr, hash_val, bin_pos);
Branch: 8 branches
BranchTrueFalseTotal
FIND_ENTRY(table, ptr, hash_val, bin_pos); 18779892 4556 18784448
FIND_ENTRY(table, ptr, hash_val, bin_pos); 4159383 14620509 18779892
FIND_ENTRY(table, ptr, hash_val, bin_pos); 107 4159276 4159383
FIND_ENTRY(table, ptr, hash_val, bin_pos); 0 107 107
FIND_ENTRY(table, ptr, hash_val, bin_pos); 33805261 6923 33812184
FIND_ENTRY(table, ptr, hash_val, bin_pos); 19191675 14613586 33805261
FIND_ENTRY(table, ptr, hash_val, bin_pos); 0 14613586 14613586
FIND_ENTRY(table, ptr, hash_val, bin_pos); 0 0 0
252  
253 18784448 ▶ if (ptr == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ptr == 0) { 11479 18772969 18784448
254 11479 return 0;
255 }
256 else {
257 18772969 ▶ if (value != 0) *value = ptr->record;
Branch: 1 branch
BranchTrueFalseTotal
if (value != 0) *value = ptr->record; 18772779 190 18772969
258 18772969 return 1;
259 }
260 }
261  
262 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
263 do {\
264 st_table_entry *entry;\
265 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
266 rehash(table);\
267 bin_pos = hash_val % table->num_bins;\
268 }\
269 \
270 entry = alloc(st_table_entry);\
271 \
272 entry->hash = hash_val;\
273 entry->key = key;\
274 entry->record = value;\
275 entry->next = table->bins[bin_pos];\
276 table->bins[bin_pos] = entry;\
277 table->num_entries++;\
278 } while (0)
279  
280 int
281 18740134 st_insert(st_table *table, st_data_t key, st_data_t value)
282 {
283 unsigned int hash_val, bin_pos;
284 register st_table_entry *ptr;
285  
286 18740134 hash_val = do_hash(key, table);
287 70796010 ▶ FIND_ENTRY(table, ptr, hash_val, bin_pos);
Branch: 8 branches
BranchTrueFalseTotal
FIND_ENTRY(table, ptr, hash_val, bin_pos); 18726765 13369 18740134
FIND_ENTRY(table, ptr, hash_val, bin_pos); 834 18725931 18726765
FIND_ENTRY(table, ptr, hash_val, bin_pos); 32 802 834
FIND_ENTRY(table, ptr, hash_val, bin_pos); 0 32 32
FIND_ENTRY(table, ptr, hash_val, bin_pos); 52057172 18724635 70781807
FIND_ENTRY(table, ptr, hash_val, bin_pos); 52055876 1296 52057172
FIND_ENTRY(table, ptr, hash_val, bin_pos); 0 1296 1296
FIND_ENTRY(table, ptr, hash_val, bin_pos); 0 0 0
288  
289 18740134 ▶ if (ptr == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ptr == 0) { 18738004 2130 18740134
290 18738004 ▶ ADD_DIRECT(table, key, value, hash_val, bin_pos);
Branch: 1 branch
BranchTrueFalseTotal
ADD_DIRECT(table, key, value, hash_val, bin_pos); 5049 18732955 18738004
291 18738004 return 0;
292 }
293 else {
294 2130 ptr->record = value;
295 2130 return 1;
296 }
297 }
298  
299 void
300 0 st_add_direct(st_table *table, st_data_t key, st_data_t value)
301 {
302 unsigned int hash_val, bin_pos;
303  
304 0 hash_val = do_hash(key, table);
305 0 bin_pos = hash_val % table->num_bins;
306 0 ▶ ADD_DIRECT(table, key, value, hash_val, bin_pos);
Branch: 1 branch
BranchTrueFalseTotal
ADD_DIRECT(table, key, value, hash_val, bin_pos); 0 0 0
307 0 }
308  
309 static void
310 5049 rehash(st_table *table)
311 {
312 register st_table_entry *ptr, *next, **new_bins;
313 5049 int i, old_num_bins = table->num_bins, new_num_bins;
314 unsigned int hash_val;
315  
316 5049 new_num_bins = new_size(old_num_bins+1);
317 5049 ▶ if (new_num_bins <= 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (new_num_bins <= 0) return; 0 5049 5049
318 5049 new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
319  
320 4133946 ▶ for(i = 0; i < old_num_bins; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < old_num_bins; i++) { 4128897 5049 4133946
321 4128897 ptr = table->bins[i];
322 28902279 ▶ while (ptr != 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (ptr != 0) { 24773382 4128897 28902279
323 24773382 next = ptr->next;
324 24773382 hash_val = ptr->hash % new_num_bins;
325 24773382 ptr->next = new_bins[hash_val];
326 24773382 new_bins[hash_val] = ptr;
327 24773382 ptr = next;
328 }
329 }
330 5049 free(table->bins);
331 5049 table->num_bins = new_num_bins;
332 5049 table->bins = new_bins;
333 }
334  
335 st_table*
336 0 st_copy(st_table *old_table)
337 {
338 st_table *new_table;
339 st_table_entry *ptr, *entry;
340 0 int i, num_bins = old_table->num_bins;
341  
342 0 new_table = alloc(st_table);
343 0 ▶ if (new_table == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (new_table == 0) { 0 0 0
344 0 return 0;
345 }
346  
347 0 *new_table = *old_table;
348 0 new_table->bins = (st_table_entry**)
349 0 Calloc((unsigned)num_bins, sizeof(st_table_entry*));
350  
351 0 ▶ if (new_table->bins == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (new_table->bins == 0) { 0 0 0
352 0 free(new_table);
353 0 return 0;
354 }
355  
356 0 ▶ for(i = 0; i < num_bins; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < num_bins; i++) { 0 0 0
357 0 new_table->bins[i] = 0;
358 0 ptr = old_table->bins[i];
359 0 ▶ while (ptr != 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (ptr != 0) { 0 0 0
360 0 entry = alloc(st_table_entry);
361 0 ▶ if (entry == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (entry == 0) { 0 0 0
362 0 free(new_table->bins);
363 0 free(new_table);
364 0 return 0;
365 }
366 0 *entry = *ptr;
367 0 entry->next = new_table->bins[i];
368 0 new_table->bins[i] = entry;
369 0 ptr = ptr->next;
370 }
371 }
372 0 return new_table;
373 }
374  
375 int
376 35 st_delete(st_table *table, st_data_t *key, st_data_t *value)
377 {
378 unsigned int hash_val;
379 st_table_entry *tmp;
380 register st_table_entry *ptr;
381  
382 35 hash_val = do_hash_bin(*key, table);
383 35 ptr = table->bins[hash_val];
384  
385 35 ▶ if (ptr == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ptr == 0) { 33 2 35
386 33 ▶ if (value != 0) *value = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (value != 0) *value = 0; 33 0 33
387 33 return 0;
388 }
389  
390 2 ▶ if (EQUAL(table, *key, ptr->key)) {
Branch: 2 branches
BranchTrueFalseTotal
if (EQUAL(table, *key, ptr->key)) { 2 0 2
if (EQUAL(table, *key, ptr->key)) { 2 0 2
391 2 table->bins[hash_val] = ptr->next;
392 2 table->num_entries--;
393 2 ▶ if (value != 0) *value = ptr->record;
Branch: 1 branch
BranchTrueFalseTotal
if (value != 0) *value = ptr->record; 2 0 2
394 2 *key = ptr->key;
395 2 free(ptr);
396 2 return 1;
397 }
398  
399 0 ▶ for(; ptr->next != 0; ptr = ptr->next) {
Branch: 1 branch
BranchTrueFalseTotal
for(; ptr->next != 0; ptr = ptr->next) { 0 0 0
400 0 ▶ if (EQUAL(table, ptr->next->key, *key)) {
Branch: 2 branches
BranchTrueFalseTotal
if (EQUAL(table, ptr->next->key, *key)) { 0 0 0
if (EQUAL(table, ptr->next->key, *key)) { 0 0 0
401 0 tmp = ptr->next;
402 0 ptr->next = ptr->next->next;
403 0 table->num_entries--;
404 0 ▶ if (value != 0) *value = tmp->record;
Branch: 1 branch
BranchTrueFalseTotal
if (value != 0) *value = tmp->record; 0 0 0
405 0 *key = tmp->key;
406 0 free(tmp);
407 0 return 1;
408 }
409 }
410  
411 0 return 0;
412 }
413  
414 int
415 0 st_delete_safe(st_table *table, st_data_t *key, st_data_t *value, st_data_t never)
416 {
417 unsigned int hash_val;
418 register st_table_entry *ptr;
419  
420 0 hash_val = do_hash_bin(*key, table);
421 0 ptr = table->bins[hash_val];
422  
423 0 ▶ if (ptr == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ptr == 0) { 0 0 0
424 0 ▶ if (value != 0) *value = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (value != 0) *value = 0; 0 0 0
425 0 return 0;
426 }
427  
428 0 ▶ for(; ptr != 0; ptr = ptr->next) {
Branch: 1 branch
BranchTrueFalseTotal
for(; ptr != 0; ptr = ptr->next) { 0 0 0
429 0 ▶ if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
Branch: 3 branches
BranchTrueFalseTotal
if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 0 0 0
if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 0 0 0
if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 0 0 0
430 0 table->num_entries--;
431 0 *key = ptr->key;
432 0 ▶ if (value != 0) *value = ptr->record;
Branch: 1 branch
BranchTrueFalseTotal
if (value != 0) *value = ptr->record; 0 0 0
433 0 ptr->key = ptr->record = never;
434 0 return 1;
435 }
436 }
437  
438 0 return 0;
439 }
440  
441 static enum st_retval
442 0 delete_never(st_data_t key, st_data_t value, st_data_t never)
443 {
444 0 ▶ if (value == never) return ST_DELETE;
Branch: 1 branch
BranchTrueFalseTotal
if (value == never) return ST_DELETE; 0 0 0
445 0 return ST_CONTINUE;
446 }
447  
448 void
449 0 st_cleanup_safe(st_table *table, st_data_t never)
450 {
451 0 int num_entries = table->num_entries;
452  
453 0 st_foreach(table, delete_never, never);
454 0 table->num_entries = num_entries;
455 0 }
456  
457 void
458 117 st_foreach(st_table *table, st_foreach_func func, st_data_t arg)
459 {
460 st_table_entry *ptr, *last, *tmp;
461 enum st_retval retval;
462 int i;
463  
464 1404 ▶ for(i = 0; i < table->num_bins; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < table->num_bins; i++) { 1287 117 1404
465 1287 last = 0;
466 1517 ▶ for(ptr = table->bins[i]; ptr != 0;) {
Branch: 1 branch
BranchTrueFalseTotal
for(ptr = table->bins[i]; ptr != 0;) { 230 1287 1517
467 230 retval = (*func)(ptr->key, ptr->record, arg);
468 230 switch (retval) {
469 230 case ST_CONTINUE:
470 230 last = ptr;
471 230 ptr = ptr->next;
472 230 break;
473 0 case ST_STOP:
474 0 return;
475 0 case ST_DELETE:
476 0 tmp = ptr;
477 0 ▶ if (last == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (last == 0) { 0 0 0
478 0 table->bins[i] = ptr->next;
479 }
480 else {
481 0 last->next = ptr->next;
482 }
483 0 ptr = ptr->next;
484 0 free(tmp);
485 0 table->num_entries--;
486 }
487 }
488 }
489 }
490  
491 static int
492 224 strhash(st_data_t key)
493 {
494 224 register char *string = (char *)key;
495 register int c;
496  
497 #ifdef HASH_ELFHASH
498 register unsigned int h = 0, g;
499  
500 while ((c = *string++) != '\0') {
501 h = ( h << 4 ) + c;
502 if ( g = h & 0xF0000000 )
503 h ^= g >> 24;
504 h &= ~g;
505 }
506 return h;
507 #elif HASH_PERL
508 register int val = 0;
509  
510 while ((c = *string++) != '\0') {
511 val = val*33 + c;
512 }
513  
514 return val + (val>>5);
515 #elif HASH_JENKINS
516 register const unsigned char *s_PeRlHaSh = (const unsigned char *)string;
517 register U32 hash_PeRlHaSh = 0;
518 while ((c = *s_PeRlHaSh++) != '\0') {
519 hash_PeRlHaSh += c;
520 hash_PeRlHaSh += (hash_PeRlHaSh << 10);
521 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6);
522 }
523 hash_PeRlHaSh += (hash_PeRlHaSh << 3);
524 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11);
525 return (hash_PeRlHaSh + (hash_PeRlHaSh << 15));
526 #else
527 224 register int val = 0;
528  
529 735 ▶ while ((c = *string++) != '\0') {
Branch: 1 branch
BranchTrueFalseTotal
while ((c = *string++) != '\0') { 511 224 735
530 511 val = val*997 + c;
531 }
532  
533 224 return val + (val>>5);
534 #endif
535 }
536  
537 static int
538 141 st_strcmp(st_data_t x, st_data_t y)
539 {
540 141 return strcmp((const char *)x, (const char *)y);
541 }
542  
543 static int
544 0 numcmp(st_data_t x, st_data_t y)
545 {
546 0 return x != y;
547 }
548  
549 static int
550 37524393 numhash(st_data_t n)
551 {
552 37524393 return (int)n;
553 }
« blib/lib/YAML/Loader/Syck.pm ↑ Summary gram.c »