Ruby 1.9.3p327(2012-11-10revision37606)
|
00001 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */ 00002 00003 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */ 00004 00005 #ifdef NOT_RUBY 00006 #include "regint.h" 00007 #include "st.h" 00008 #else 00009 #include "ruby/ruby.h" 00010 #endif 00011 00012 #include <stdio.h> 00013 #ifdef HAVE_STDLIB_H 00014 #include <stdlib.h> 00015 #endif 00016 #include <string.h> 00017 00018 typedef struct st_table_entry st_table_entry; 00019 00020 struct st_table_entry { 00021 st_index_t hash; 00022 st_data_t key; 00023 st_data_t record; 00024 st_table_entry *next; 00025 st_table_entry *fore, *back; 00026 }; 00027 00028 #define ST_DEFAULT_MAX_DENSITY 5 00029 #define ST_DEFAULT_INIT_TABLE_SIZE 11 00030 00031 /* 00032 * DEFAULT_MAX_DENSITY is the default for the largest we allow the 00033 * average number of items per bin before increasing the number of 00034 * bins 00035 * 00036 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 00037 * allocated initially 00038 * 00039 */ 00040 00041 static const struct st_hash_type type_numhash = { 00042 st_numcmp, 00043 st_numhash, 00044 }; 00045 00046 /* extern int strcmp(const char *, const char *); */ 00047 static st_index_t strhash(st_data_t); 00048 static const struct st_hash_type type_strhash = { 00049 strcmp, 00050 strhash, 00051 }; 00052 00053 static st_index_t strcasehash(st_data_t); 00054 static const struct st_hash_type type_strcasehash = { 00055 st_strcasecmp, 00056 strcasehash, 00057 }; 00058 00059 static void rehash(st_table *); 00060 00061 #ifdef RUBY 00062 #define malloc xmalloc 00063 #define calloc xcalloc 00064 #define free(x) xfree(x) 00065 #endif 00066 00067 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0])) 00068 00069 #define alloc(type) (type*)malloc((size_t)sizeof(type)) 00070 #define Calloc(n,s) (char*)calloc((n),(s)) 00071 00072 #define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0) 00073 00074 /* remove cast to unsigned int in the future */ 00075 #define do_hash(key,table) (unsigned int)(st_index_t)(*(table)->type->hash)((key)) 00076 #define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins) 00077 00078 /* 00079 * MINSIZE is the minimum size of a dictionary. 00080 */ 00081 00082 #define MINSIZE 8 00083 00084 /* 00085 Table of prime numbers 2^n+a, 2<=n<=30. 00086 */ 00087 static const unsigned int primes[] = { 00088 8 + 3, 00089 16 + 3, 00090 32 + 5, 00091 64 + 3, 00092 128 + 3, 00093 256 + 27, 00094 512 + 9, 00095 1024 + 9, 00096 2048 + 5, 00097 4096 + 3, 00098 8192 + 27, 00099 16384 + 43, 00100 32768 + 3, 00101 65536 + 45, 00102 131072 + 29, 00103 262144 + 3, 00104 524288 + 21, 00105 1048576 + 7, 00106 2097152 + 17, 00107 4194304 + 15, 00108 8388608 + 9, 00109 16777216 + 43, 00110 33554432 + 35, 00111 67108864 + 15, 00112 134217728 + 29, 00113 268435456 + 3, 00114 536870912 + 11, 00115 1073741824 + 85, 00116 0 00117 }; 00118 00119 static st_index_t 00120 new_size(st_index_t size) 00121 { 00122 int i; 00123 00124 #if 0 00125 for (i=3; i<31; i++) { 00126 if ((1<<i) > size) return 1<<i; 00127 } 00128 return -1; 00129 #else 00130 st_index_t newsize; 00131 00132 for (i = 0, newsize = MINSIZE; i < numberof(primes); i++, newsize <<= 1) { 00133 if (newsize > size) return primes[i]; 00134 } 00135 /* Ran out of polynomials */ 00136 #ifndef NOT_RUBY 00137 rb_raise(rb_eRuntimeError, "st_table too big"); 00138 #endif 00139 return -1; /* should raise exception */ 00140 #endif 00141 } 00142 00143 #ifdef HASH_LOG 00144 #ifdef HAVE_UNISTD_H 00145 #include <unistd.h> 00146 #endif 00147 static struct { 00148 int all, total, num, str, strcase; 00149 } collision; 00150 static int init_st = 0; 00151 00152 static void 00153 stat_col(void) 00154 { 00155 char fname[10+sizeof(long)*3]; 00156 FILE *f = fopen((snprintf(fname, sizeof(fname), "/tmp/col%ld", (long)getpid()), fname), "w"); 00157 fprintf(f, "collision: %d / %d (%6.2f)\n", collision.all, collision.total, 00158 ((double)collision.all / (collision.total)) * 100); 00159 fprintf(f, "num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase); 00160 fclose(f); 00161 } 00162 #endif 00163 00164 #define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2) 00165 00166 st_table* 00167 st_init_table_with_size(const struct st_hash_type *type, st_index_t size) 00168 { 00169 st_table *tbl; 00170 00171 #ifdef HASH_LOG 00172 # if HASH_LOG+0 < 0 00173 { 00174 const char *e = getenv("ST_HASH_LOG"); 00175 if (!e || !*e) init_st = 1; 00176 } 00177 # endif 00178 if (init_st == 0) { 00179 init_st = 1; 00180 atexit(stat_col); 00181 } 00182 #endif 00183 00184 size = new_size(size); /* round up to prime number */ 00185 00186 tbl = alloc(st_table); 00187 tbl->type = type; 00188 tbl->num_entries = 0; 00189 tbl->entries_packed = type == &type_numhash && size/2 <= MAX_PACKED_NUMHASH; 00190 tbl->num_bins = size; 00191 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); 00192 tbl->head = 0; 00193 tbl->tail = 0; 00194 00195 return tbl; 00196 } 00197 00198 st_table* 00199 st_init_table(const struct st_hash_type *type) 00200 { 00201 return st_init_table_with_size(type, 0); 00202 } 00203 00204 st_table* 00205 st_init_numtable(void) 00206 { 00207 return st_init_table(&type_numhash); 00208 } 00209 00210 st_table* 00211 st_init_numtable_with_size(st_index_t size) 00212 { 00213 return st_init_table_with_size(&type_numhash, size); 00214 } 00215 00216 st_table* 00217 st_init_strtable(void) 00218 { 00219 return st_init_table(&type_strhash); 00220 } 00221 00222 st_table* 00223 st_init_strtable_with_size(st_index_t size) 00224 { 00225 return st_init_table_with_size(&type_strhash, size); 00226 } 00227 00228 st_table* 00229 st_init_strcasetable(void) 00230 { 00231 return st_init_table(&type_strcasehash); 00232 } 00233 00234 st_table* 00235 st_init_strcasetable_with_size(st_index_t size) 00236 { 00237 return st_init_table_with_size(&type_strcasehash, size); 00238 } 00239 00240 void 00241 st_clear(st_table *table) 00242 { 00243 register st_table_entry *ptr, *next; 00244 st_index_t i; 00245 00246 if (table->entries_packed) { 00247 table->num_entries = 0; 00248 return; 00249 } 00250 00251 for(i = 0; i < table->num_bins; i++) { 00252 ptr = table->bins[i]; 00253 table->bins[i] = 0; 00254 while (ptr != 0) { 00255 next = ptr->next; 00256 free(ptr); 00257 ptr = next; 00258 } 00259 } 00260 table->num_entries = 0; 00261 table->head = 0; 00262 table->tail = 0; 00263 } 00264 00265 void 00266 st_free_table(st_table *table) 00267 { 00268 st_clear(table); 00269 free(table->bins); 00270 free(table); 00271 } 00272 00273 size_t 00274 st_memsize(const st_table *table) 00275 { 00276 if (table->entries_packed) { 00277 return table->num_bins * sizeof (void *) + sizeof(st_table); 00278 } 00279 else { 00280 return table->num_entries * sizeof(struct st_table_entry) + table->num_bins * sizeof (void *) + sizeof(st_table); 00281 } 00282 } 00283 00284 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 00285 ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 00286 00287 #ifdef HASH_LOG 00288 static void 00289 count_collision(const struct st_hash_type *type) 00290 { 00291 collision.all++; 00292 if (type == &type_numhash) { 00293 collision.num++; 00294 } 00295 else if (type == &type_strhash) { 00296 collision.strcase++; 00297 } 00298 else if (type == &type_strcasehash) { 00299 collision.str++; 00300 } 00301 } 00302 #define COLLISION (collision_check ? count_collision(table->type) : (void)0) 00303 #define FOUND_ENTRY (collision_check ? collision.total++ : (void)0) 00304 #else 00305 #define COLLISION 00306 #define FOUND_ENTRY 00307 #endif 00308 00309 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 00310 (bin_pos) = (hash_val)%(table)->num_bins;\ 00311 (ptr) = (table)->bins[(bin_pos)];\ 00312 FOUND_ENTRY;\ 00313 if (PTR_NOT_EQUAL((table), (ptr), (hash_val), key)) {\ 00314 COLLISION;\ 00315 while (PTR_NOT_EQUAL((table), (ptr)->next, (hash_val), key)) {\ 00316 (ptr) = (ptr)->next;\ 00317 }\ 00318 (ptr) = (ptr)->next;\ 00319 }\ 00320 } while (0) 00321 00322 #define collision_check 0 00323 00324 int 00325 st_lookup(st_table *table, register st_data_t key, st_data_t *value) 00326 { 00327 st_index_t hash_val, bin_pos; 00328 register st_table_entry *ptr; 00329 00330 if (table->entries_packed) { 00331 st_index_t i; 00332 for (i = 0; i < table->num_entries; i++) { 00333 if ((st_data_t)table->bins[i*2] == key) { 00334 if (value !=0) *value = (st_data_t)table->bins[i*2+1]; 00335 return 1; 00336 } 00337 } 00338 return 0; 00339 } 00340 00341 hash_val = do_hash(key, table); 00342 FIND_ENTRY(table, ptr, hash_val, bin_pos); 00343 00344 if (ptr == 0) { 00345 return 0; 00346 } 00347 else { 00348 if (value != 0) *value = ptr->record; 00349 return 1; 00350 } 00351 } 00352 00353 int 00354 st_get_key(st_table *table, register st_data_t key, st_data_t *result) 00355 { 00356 st_index_t hash_val, bin_pos; 00357 register st_table_entry *ptr; 00358 00359 if (table->entries_packed) { 00360 st_index_t i; 00361 for (i = 0; i < table->num_entries; i++) { 00362 if ((st_data_t)table->bins[i*2] == key) { 00363 if (result !=0) *result = (st_data_t)table->bins[i*2]; 00364 return 1; 00365 } 00366 } 00367 return 0; 00368 } 00369 00370 hash_val = do_hash(key, table); 00371 FIND_ENTRY(table, ptr, hash_val, bin_pos); 00372 00373 if (ptr == 0) { 00374 return 0; 00375 } 00376 else { 00377 if (result != 0) *result = ptr->key; 00378 return 1; 00379 } 00380 } 00381 00382 #undef collision_check 00383 #define collision_check 1 00384 00385 #define MORE_PACKABLE_P(table) \ 00386 ((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \ 00387 (table)->num_entries+1 <= MAX_PACKED_NUMHASH) 00388 00389 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ 00390 do {\ 00391 st_table_entry *entry;\ 00392 if ((table)->num_entries > ST_DEFAULT_MAX_DENSITY * (table)->num_bins) {\ 00393 rehash(table);\ 00394 (bin_pos) = (hash_val) % (table)->num_bins;\ 00395 }\ 00396 \ 00397 entry = alloc(st_table_entry);\ 00398 \ 00399 entry->hash = (hash_val);\ 00400 entry->key = (key);\ 00401 entry->record = (value);\ 00402 entry->next = (table)->bins[(bin_pos)];\ 00403 if ((table)->head != 0) {\ 00404 entry->fore = 0;\ 00405 (entry->back = (table)->tail)->fore = entry;\ 00406 (table)->tail = entry;\ 00407 }\ 00408 else {\ 00409 (table)->head = (table)->tail = entry;\ 00410 entry->fore = entry->back = 0;\ 00411 }\ 00412 (table)->bins[(bin_pos)] = entry;\ 00413 (table)->num_entries++;\ 00414 } while (0) 00415 00416 static void 00417 unpack_entries(register st_table *table) 00418 { 00419 st_index_t i; 00420 struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2]; 00421 st_table tmp_table = *table; 00422 00423 memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * table->num_entries*2); 00424 table->bins = packed_bins; 00425 tmp_table.entries_packed = 0; 00426 tmp_table.num_entries = 0; 00427 memset(tmp_table.bins, 0, sizeof(struct st_table_entry *) * tmp_table.num_bins); 00428 for (i = 0; i < table->num_entries; i++) { 00429 st_insert(&tmp_table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]); 00430 } 00431 *table = tmp_table; 00432 } 00433 00434 int 00435 st_insert(register st_table *table, register st_data_t key, st_data_t value) 00436 { 00437 st_index_t hash_val, bin_pos; 00438 register st_table_entry *ptr; 00439 00440 if (table->entries_packed) { 00441 st_index_t i; 00442 for (i = 0; i < table->num_entries; i++) { 00443 if ((st_data_t)table->bins[i*2] == key) { 00444 table->bins[i*2+1] = (struct st_table_entry*)value; 00445 return 1; 00446 } 00447 } 00448 if (MORE_PACKABLE_P(table)) { 00449 i = table->num_entries++; 00450 table->bins[i*2] = (struct st_table_entry*)key; 00451 table->bins[i*2+1] = (struct st_table_entry*)value; 00452 return 0; 00453 } 00454 else { 00455 unpack_entries(table); 00456 } 00457 } 00458 00459 hash_val = do_hash(key, table); 00460 FIND_ENTRY(table, ptr, hash_val, bin_pos); 00461 00462 if (ptr == 0) { 00463 ADD_DIRECT(table, key, value, hash_val, bin_pos); 00464 return 0; 00465 } 00466 else { 00467 ptr->record = value; 00468 return 1; 00469 } 00470 } 00471 00472 int 00473 st_insert2(register st_table *table, register st_data_t key, st_data_t value, 00474 st_data_t (*func)(st_data_t)) 00475 { 00476 st_index_t hash_val, bin_pos; 00477 register st_table_entry *ptr; 00478 00479 if (table->entries_packed) { 00480 st_index_t i; 00481 for (i = 0; i < table->num_entries; i++) { 00482 if ((st_data_t)table->bins[i*2] == key) { 00483 table->bins[i*2+1] = (struct st_table_entry*)value; 00484 return 1; 00485 } 00486 } 00487 if (MORE_PACKABLE_P(table)) { 00488 i = table->num_entries++; 00489 table->bins[i*2] = (struct st_table_entry*)key; 00490 table->bins[i*2+1] = (struct st_table_entry*)value; 00491 return 0; 00492 } 00493 else { 00494 unpack_entries(table); 00495 } 00496 } 00497 00498 hash_val = do_hash(key, table); 00499 FIND_ENTRY(table, ptr, hash_val, bin_pos); 00500 00501 if (ptr == 0) { 00502 key = (*func)(key); 00503 ADD_DIRECT(table, key, value, hash_val, bin_pos); 00504 return 0; 00505 } 00506 else { 00507 ptr->record = value; 00508 return 1; 00509 } 00510 } 00511 00512 void 00513 st_add_direct(st_table *table, st_data_t key, st_data_t value) 00514 { 00515 st_index_t hash_val, bin_pos; 00516 00517 if (table->entries_packed) { 00518 int i; 00519 if (MORE_PACKABLE_P(table)) { 00520 i = table->num_entries++; 00521 table->bins[i*2] = (struct st_table_entry*)key; 00522 table->bins[i*2+1] = (struct st_table_entry*)value; 00523 return; 00524 } 00525 else { 00526 unpack_entries(table); 00527 } 00528 } 00529 00530 hash_val = do_hash(key, table); 00531 bin_pos = hash_val % table->num_bins; 00532 ADD_DIRECT(table, key, value, hash_val, bin_pos); 00533 } 00534 00535 static void 00536 rehash(register st_table *table) 00537 { 00538 register st_table_entry *ptr, **new_bins; 00539 st_index_t i, new_num_bins, hash_val; 00540 00541 new_num_bins = new_size(table->num_bins+1); 00542 new_bins = (st_table_entry**) 00543 xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*)); 00544 for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0; 00545 table->num_bins = new_num_bins; 00546 table->bins = new_bins; 00547 00548 if ((ptr = table->head) != 0) { 00549 do { 00550 hash_val = ptr->hash % new_num_bins; 00551 ptr->next = new_bins[hash_val]; 00552 new_bins[hash_val] = ptr; 00553 } while ((ptr = ptr->fore) != 0); 00554 } 00555 } 00556 00557 st_table* 00558 st_copy(st_table *old_table) 00559 { 00560 st_table *new_table; 00561 st_table_entry *ptr, *entry, *prev, **tail; 00562 st_index_t num_bins = old_table->num_bins; 00563 st_index_t hash_val; 00564 00565 new_table = alloc(st_table); 00566 if (new_table == 0) { 00567 return 0; 00568 } 00569 00570 *new_table = *old_table; 00571 new_table->bins = (st_table_entry**) 00572 Calloc((unsigned)num_bins, sizeof(st_table_entry*)); 00573 00574 if (new_table->bins == 0) { 00575 free(new_table); 00576 return 0; 00577 } 00578 00579 if (old_table->entries_packed) { 00580 memcpy(new_table->bins, old_table->bins, sizeof(struct st_table_entry *) * old_table->num_bins); 00581 return new_table; 00582 } 00583 00584 if ((ptr = old_table->head) != 0) { 00585 prev = 0; 00586 tail = &new_table->head; 00587 do { 00588 entry = alloc(st_table_entry); 00589 if (entry == 0) { 00590 st_free_table(new_table); 00591 return 0; 00592 } 00593 *entry = *ptr; 00594 hash_val = entry->hash % num_bins; 00595 entry->next = new_table->bins[hash_val]; 00596 new_table->bins[hash_val] = entry; 00597 entry->back = prev; 00598 *tail = prev = entry; 00599 tail = &entry->fore; 00600 } while ((ptr = ptr->fore) != 0); 00601 new_table->tail = prev; 00602 } 00603 00604 return new_table; 00605 } 00606 00607 #define REMOVE_ENTRY(table, ptr) do \ 00608 { \ 00609 if ((ptr)->fore == 0 && (ptr)->back == 0) { \ 00610 (table)->head = 0; \ 00611 (table)->tail = 0; \ 00612 } \ 00613 else { \ 00614 st_table_entry *fore = (ptr)->fore, *back = (ptr)->back; \ 00615 if (fore) fore->back = back; \ 00616 if (back) back->fore = fore; \ 00617 if ((ptr) == (table)->head) (table)->head = fore; \ 00618 if ((ptr) == (table)->tail) (table)->tail = back; \ 00619 } \ 00620 (table)->num_entries--; \ 00621 } while (0) 00622 00623 int 00624 st_delete(register st_table *table, register st_data_t *key, st_data_t *value) 00625 { 00626 st_index_t hash_val; 00627 st_table_entry **prev; 00628 register st_table_entry *ptr; 00629 00630 if (table->entries_packed) { 00631 st_index_t i; 00632 for (i = 0; i < table->num_entries; i++) { 00633 if ((st_data_t)table->bins[i*2] == *key) { 00634 if (value != 0) *value = (st_data_t)table->bins[i*2+1]; 00635 table->num_entries--; 00636 memmove(&table->bins[i*2], &table->bins[(i+1)*2], 00637 sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); 00638 return 1; 00639 } 00640 } 00641 if (value != 0) *value = 0; 00642 return 0; 00643 } 00644 00645 hash_val = do_hash_bin(*key, table); 00646 00647 for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) { 00648 if (EQUAL(table, *key, ptr->key)) { 00649 *prev = ptr->next; 00650 REMOVE_ENTRY(table, ptr); 00651 if (value != 0) *value = ptr->record; 00652 *key = ptr->key; 00653 free(ptr); 00654 return 1; 00655 } 00656 } 00657 00658 if (value != 0) *value = 0; 00659 return 0; 00660 } 00661 00662 int 00663 st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never) 00664 { 00665 st_index_t hash_val; 00666 register st_table_entry *ptr; 00667 00668 if (table->entries_packed) { 00669 st_index_t i; 00670 for (i = 0; i < table->num_entries; i++) { 00671 if ((st_data_t)table->bins[i*2] == *key) { 00672 if (value != 0) *value = (st_data_t)table->bins[i*2+1]; 00673 table->bins[i*2] = (void *)never; 00674 return 1; 00675 } 00676 } 00677 if (value != 0) *value = 0; 00678 return 0; 00679 } 00680 00681 hash_val = do_hash_bin(*key, table); 00682 ptr = table->bins[hash_val]; 00683 00684 for (; ptr != 0; ptr = ptr->next) { 00685 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 00686 REMOVE_ENTRY(table, ptr); 00687 *key = ptr->key; 00688 if (value != 0) *value = ptr->record; 00689 ptr->key = ptr->record = never; 00690 return 1; 00691 } 00692 } 00693 00694 if (value != 0) *value = 0; 00695 return 0; 00696 } 00697 00698 void 00699 st_cleanup_safe(st_table *table, st_data_t never) 00700 { 00701 st_table_entry *ptr, **last, *tmp; 00702 st_index_t i; 00703 00704 if (table->entries_packed) { 00705 st_index_t i = 0, j = 0; 00706 while ((st_data_t)table->bins[i*2] != never) { 00707 if (i++ == table->num_entries) return; 00708 } 00709 for (j = i; ++i < table->num_entries;) { 00710 if ((st_data_t)table->bins[i*2] == never) continue; 00711 table->bins[j*2] = table->bins[i*2]; 00712 table->bins[j*2+1] = table->bins[i*2+1]; 00713 j++; 00714 } 00715 table->num_entries = j; 00716 return; 00717 } 00718 00719 for (i = 0; i < table->num_bins; i++) { 00720 ptr = *(last = &table->bins[i]); 00721 while (ptr != 0) { 00722 if (ptr->key == never) { 00723 tmp = ptr; 00724 *last = ptr = ptr->next; 00725 free(tmp); 00726 } 00727 else { 00728 ptr = *(last = &ptr->next); 00729 } 00730 } 00731 } 00732 } 00733 00734 int 00735 st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) 00736 { 00737 st_table_entry *ptr, **last, *tmp; 00738 enum st_retval retval; 00739 st_index_t i; 00740 00741 if (table->entries_packed) { 00742 for (i = 0; i < table->num_entries; i++) { 00743 st_index_t j; 00744 st_data_t key, val; 00745 key = (st_data_t)table->bins[i*2]; 00746 val = (st_data_t)table->bins[i*2+1]; 00747 retval = (*func)(key, val, arg); 00748 if (!table->entries_packed) { 00749 FIND_ENTRY(table, ptr, key, i); 00750 if (retval == ST_CHECK) { 00751 if (!ptr) goto deleted; 00752 goto unpacked_continue; 00753 } 00754 goto unpacked; 00755 } 00756 switch (retval) { 00757 case ST_CHECK: /* check if hash is modified during iteration */ 00758 for (j = 0; j < table->num_entries; j++) { 00759 if ((st_data_t)table->bins[j*2] == key) 00760 break; 00761 } 00762 if (j == table->num_entries) { 00763 goto deleted; 00764 } 00765 /* fall through */ 00766 case ST_CONTINUE: 00767 break; 00768 case ST_STOP: 00769 return 0; 00770 case ST_DELETE: 00771 table->num_entries--; 00772 memmove(&table->bins[i*2], &table->bins[(i+1)*2], 00773 sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); 00774 i--; 00775 break; 00776 } 00777 } 00778 return 0; 00779 } 00780 else { 00781 ptr = table->head; 00782 } 00783 00784 if (ptr != 0) { 00785 do { 00786 i = ptr->hash % table->num_bins; 00787 retval = (*func)(ptr->key, ptr->record, arg); 00788 unpacked: 00789 switch (retval) { 00790 case ST_CHECK: /* check if hash is modified during iteration */ 00791 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { 00792 if (!tmp) { 00793 deleted: 00794 /* call func with error notice */ 00795 retval = (*func)(0, 0, arg, 1); 00796 return 1; 00797 } 00798 } 00799 /* fall through */ 00800 case ST_CONTINUE: 00801 unpacked_continue: 00802 ptr = ptr->fore; 00803 break; 00804 case ST_STOP: 00805 return 0; 00806 case ST_DELETE: 00807 last = &table->bins[ptr->hash % table->num_bins]; 00808 for (; (tmp = *last) != 0; last = &tmp->next) { 00809 if (ptr == tmp) { 00810 tmp = ptr->fore; 00811 *last = ptr->next; 00812 REMOVE_ENTRY(table, ptr); 00813 free(ptr); 00814 if (ptr == tmp) return 0; 00815 ptr = tmp; 00816 break; 00817 } 00818 } 00819 } 00820 } while (ptr && table->head); 00821 } 00822 return 0; 00823 } 00824 00825 #if 0 /* unused right now */ 00826 int 00827 st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) 00828 { 00829 st_table_entry *ptr, **last, *tmp; 00830 enum st_retval retval; 00831 int i; 00832 00833 if (table->entries_packed) { 00834 for (i = table->num_entries-1; 0 <= i; i--) { 00835 int j; 00836 st_data_t key, val; 00837 key = (st_data_t)table->bins[i*2]; 00838 val = (st_data_t)table->bins[i*2+1]; 00839 retval = (*func)(key, val, arg); 00840 switch (retval) { 00841 case ST_CHECK: /* check if hash is modified during iteration */ 00842 for (j = 0; j < table->num_entries; j++) { 00843 if ((st_data_t)table->bins[j*2] == key) 00844 break; 00845 } 00846 if (j == table->num_entries) { 00847 /* call func with error notice */ 00848 retval = (*func)(0, 0, arg, 1); 00849 return 1; 00850 } 00851 /* fall through */ 00852 case ST_CONTINUE: 00853 break; 00854 case ST_STOP: 00855 return 0; 00856 case ST_DELETE: 00857 table->num_entries--; 00858 memmove(&table->bins[i*2], &table->bins[(i+1)*2], 00859 sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); 00860 break; 00861 } 00862 } 00863 return 0; 00864 } 00865 00866 if ((ptr = table->head) != 0) { 00867 ptr = ptr->back; 00868 do { 00869 retval = (*func)(ptr->key, ptr->record, arg, 0); 00870 switch (retval) { 00871 case ST_CHECK: /* check if hash is modified during iteration */ 00872 i = ptr->hash % table->num_bins; 00873 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { 00874 if (!tmp) { 00875 /* call func with error notice */ 00876 retval = (*func)(0, 0, arg, 1); 00877 return 1; 00878 } 00879 } 00880 /* fall through */ 00881 case ST_CONTINUE: 00882 ptr = ptr->back; 00883 break; 00884 case ST_STOP: 00885 return 0; 00886 case ST_DELETE: 00887 last = &table->bins[ptr->hash % table->num_bins]; 00888 for (; (tmp = *last) != 0; last = &tmp->next) { 00889 if (ptr == tmp) { 00890 tmp = ptr->back; 00891 *last = ptr->next; 00892 REMOVE_ENTRY(table, ptr); 00893 free(ptr); 00894 ptr = tmp; 00895 break; 00896 } 00897 } 00898 ptr = ptr->next; 00899 free(tmp); 00900 table->num_entries--; 00901 } 00902 } while (ptr && table->head); 00903 } 00904 return 0; 00905 } 00906 #endif 00907 00908 /* 00909 * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code 00910 * 00911 * @(#) $Hash32: Revision: 1.1 $ 00912 * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $ 00913 * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $ 00914 * 00915 *** 00916 * 00917 * Fowler/Noll/Vo hash 00918 * 00919 * The basis of this hash algorithm was taken from an idea sent 00920 * as reviewer comments to the IEEE POSIX P1003.2 committee by: 00921 * 00922 * Phong Vo (http://www.research.att.com/info/kpv/) 00923 * Glenn Fowler (http://www.research.att.com/~gsf/) 00924 * 00925 * In a subsequent ballot round: 00926 * 00927 * Landon Curt Noll (http://www.isthe.com/chongo/) 00928 * 00929 * improved on their algorithm. Some people tried this hash 00930 * and found that it worked rather well. In an EMail message 00931 * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. 00932 * 00933 * FNV hashes are designed to be fast while maintaining a low 00934 * collision rate. The FNV speed allows one to quickly hash lots 00935 * of data while maintaining a reasonable collision rate. See: 00936 * 00937 * http://www.isthe.com/chongo/tech/comp/fnv/index.html 00938 * 00939 * for more details as well as other forms of the FNV hash. 00940 *** 00941 * 00942 * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the 00943 * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str(). 00944 * 00945 *** 00946 * 00947 * Please do not copyright this code. This code is in the public domain. 00948 * 00949 * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 00950 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO 00951 * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR 00952 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF 00953 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR 00954 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 00955 * PERFORMANCE OF THIS SOFTWARE. 00956 * 00957 * By: 00958 * chongo <Landon Curt Noll> /\oo/\ 00959 * http://www.isthe.com/chongo/ 00960 * 00961 * Share and Enjoy! :-) 00962 */ 00963 00964 /* 00965 * 32 bit FNV-1 and FNV-1a non-zero initial basis 00966 * 00967 * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets: 00968 * 00969 * chongo <Landon Curt Noll> /\../\ 00970 * 00971 * NOTE: The \'s above are not back-slashing escape characters. 00972 * They are literal ASCII backslash 0x5c characters. 00973 * 00974 * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition. 00975 */ 00976 #define FNV1_32A_INIT 0x811c9dc5 00977 00978 /* 00979 * 32 bit magic FNV-1a prime 00980 */ 00981 #define FNV_32_PRIME 0x01000193 00982 00983 #ifdef ST_USE_FNV1 00984 static st_index_t 00985 strhash(st_data_t arg) 00986 { 00987 register const char *string = (const char *)arg; 00988 register st_index_t hval = FNV1_32A_INIT; 00989 00990 /* 00991 * FNV-1a hash each octet in the buffer 00992 */ 00993 while (*string) { 00994 /* xor the bottom with the current octet */ 00995 hval ^= (unsigned int)*string++; 00996 00997 /* multiply by the 32 bit FNV magic prime mod 2^32 */ 00998 hval *= FNV_32_PRIME; 00999 } 01000 return hval; 01001 } 01002 #else 01003 01004 #ifndef UNALIGNED_WORD_ACCESS 01005 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \ 01006 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \ 01007 defined(__mc68020__) 01008 # define UNALIGNED_WORD_ACCESS 1 01009 # endif 01010 #endif 01011 #ifndef UNALIGNED_WORD_ACCESS 01012 # define UNALIGNED_WORD_ACCESS 0 01013 #endif 01014 01015 /* MurmurHash described in http://murmurhash.googlepages.com/ */ 01016 #ifndef MURMUR 01017 #define MURMUR 2 01018 #endif 01019 01020 #define MurmurMagic_1 (st_index_t)0xc6a4a793 01021 #define MurmurMagic_2 (st_index_t)0x5bd1e995 01022 #if MURMUR == 1 01023 #define MurmurMagic MurmurMagic_1 01024 #elif MURMUR == 2 01025 #if SIZEOF_ST_INDEX_T > 4 01026 #define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2) 01027 #else 01028 #define MurmurMagic MurmurMagic_2 01029 #endif 01030 #endif 01031 01032 static inline st_index_t 01033 murmur(st_index_t h, st_index_t k, int r) 01034 { 01035 const st_index_t m = MurmurMagic; 01036 #if MURMUR == 1 01037 h += k; 01038 h *= m; 01039 h ^= h >> r; 01040 #elif MURMUR == 2 01041 k *= m; 01042 k ^= k >> r; 01043 k *= m; 01044 01045 h *= m; 01046 h ^= k; 01047 #endif 01048 return h; 01049 } 01050 01051 static inline st_index_t 01052 murmur_finish(st_index_t h) 01053 { 01054 #if MURMUR == 1 01055 h = murmur(h, 0, 10); 01056 h = murmur(h, 0, 17); 01057 #elif MURMUR == 2 01058 h ^= h >> 13; 01059 h *= MurmurMagic; 01060 h ^= h >> 15; 01061 #endif 01062 return h; 01063 } 01064 01065 #define murmur_step(h, k) murmur((h), (k), 16) 01066 01067 #if MURMUR == 1 01068 #define murmur1(h) murmur_step((h), 16) 01069 #else 01070 #define murmur1(h) murmur_step((h), 24) 01071 #endif 01072 01073 st_index_t 01074 st_hash(const void *ptr, size_t len, st_index_t h) 01075 { 01076 const char *data = ptr; 01077 st_index_t t = 0; 01078 01079 h += 0xdeadbeef; 01080 01081 #define data_at(n) (st_index_t)((unsigned char)data[(n)]) 01082 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0) 01083 #if SIZEOF_ST_INDEX_T > 4 01084 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4 01085 #if SIZEOF_ST_INDEX_T > 8 01086 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \ 01087 UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8 01088 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16 01089 #endif 01090 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8 01091 #else 01092 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4 01093 #endif 01094 if (len >= sizeof(st_index_t)) { 01095 #if !UNALIGNED_WORD_ACCESS 01096 int align = (int)((st_data_t)data % sizeof(st_index_t)); 01097 if (align) { 01098 st_index_t d = 0; 01099 int sl, sr, pack; 01100 01101 switch (align) { 01102 #ifdef WORDS_BIGENDIAN 01103 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \ 01104 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2) 01105 #else 01106 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \ 01107 t |= data_at(n) << CHAR_BIT*(n) 01108 #endif 01109 UNALIGNED_ADD_ALL; 01110 #undef UNALIGNED_ADD 01111 } 01112 01113 #ifdef WORDS_BIGENDIAN 01114 t >>= (CHAR_BIT * align) - CHAR_BIT; 01115 #else 01116 t <<= (CHAR_BIT * align); 01117 #endif 01118 01119 data += sizeof(st_index_t)-align; 01120 len -= sizeof(st_index_t)-align; 01121 01122 sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align); 01123 sr = CHAR_BIT * align; 01124 01125 while (len >= sizeof(st_index_t)) { 01126 d = *(st_index_t *)data; 01127 #ifdef WORDS_BIGENDIAN 01128 t = (t << sr) | (d >> sl); 01129 #else 01130 t = (t >> sr) | (d << sl); 01131 #endif 01132 h = murmur_step(h, t); 01133 t = d; 01134 data += sizeof(st_index_t); 01135 len -= sizeof(st_index_t); 01136 } 01137 01138 pack = len < (size_t)align ? (int)len : align; 01139 d = 0; 01140 switch (pack) { 01141 #ifdef WORDS_BIGENDIAN 01142 # define UNALIGNED_ADD(n) case (n) + 1: \ 01143 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1) 01144 #else 01145 # define UNALIGNED_ADD(n) case (n) + 1: \ 01146 d |= data_at(n) << CHAR_BIT*(n) 01147 #endif 01148 UNALIGNED_ADD_ALL; 01149 #undef UNALIGNED_ADD 01150 } 01151 #ifdef WORDS_BIGENDIAN 01152 t = (t << sr) | (d >> sl); 01153 #else 01154 t = (t >> sr) | (d << sl); 01155 #endif 01156 01157 #if MURMUR == 2 01158 if (len < (size_t)align) goto skip_tail; 01159 #endif 01160 h = murmur_step(h, t); 01161 data += pack; 01162 len -= pack; 01163 } 01164 else 01165 #endif 01166 { 01167 do { 01168 h = murmur_step(h, *(st_index_t *)data); 01169 data += sizeof(st_index_t); 01170 len -= sizeof(st_index_t); 01171 } while (len >= sizeof(st_index_t)); 01172 } 01173 } 01174 01175 t = 0; 01176 switch (len) { 01177 #ifdef WORDS_BIGENDIAN 01178 # define UNALIGNED_ADD(n) case (n) + 1: \ 01179 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1) 01180 #else 01181 # define UNALIGNED_ADD(n) case (n) + 1: \ 01182 t |= data_at(n) << CHAR_BIT*(n) 01183 #endif 01184 UNALIGNED_ADD_ALL; 01185 #undef UNALIGNED_ADD 01186 #if MURMUR == 1 01187 h = murmur_step(h, t); 01188 #elif MURMUR == 2 01189 # if !UNALIGNED_WORD_ACCESS 01190 skip_tail: 01191 # endif 01192 h ^= t; 01193 h *= MurmurMagic; 01194 #endif 01195 } 01196 01197 return murmur_finish(h); 01198 } 01199 01200 st_index_t 01201 st_hash_uint32(st_index_t h, uint32_t i) 01202 { 01203 return murmur_step(h + i, 16); 01204 } 01205 01206 st_index_t 01207 st_hash_uint(st_index_t h, st_index_t i) 01208 { 01209 st_index_t v = 0; 01210 h += i; 01211 #ifdef WORDS_BIGENDIAN 01212 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 01213 v = murmur1(v + (h >> 12*8)); 01214 #endif 01215 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 01216 v = murmur1(v + (h >> 8*8)); 01217 #endif 01218 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 01219 v = murmur1(v + (h >> 4*8)); 01220 #endif 01221 #endif 01222 v = murmur1(v + h); 01223 #ifndef WORDS_BIGENDIAN 01224 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 01225 v = murmur1(v + (h >> 4*8)); 01226 #endif 01227 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 01228 v = murmur1(v + (h >> 8*8)); 01229 #endif 01230 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 01231 v = murmur1(v + (h >> 12*8)); 01232 #endif 01233 #endif 01234 return v; 01235 } 01236 01237 st_index_t 01238 st_hash_end(st_index_t h) 01239 { 01240 h = murmur_step(h, 10); 01241 h = murmur_step(h, 17); 01242 return h; 01243 } 01244 01245 #undef st_hash_start 01246 st_index_t 01247 st_hash_start(st_index_t h) 01248 { 01249 return h; 01250 } 01251 01252 static st_index_t 01253 strhash(st_data_t arg) 01254 { 01255 register const char *string = (const char *)arg; 01256 return st_hash(string, strlen(string), FNV1_32A_INIT); 01257 } 01258 #endif 01259 01260 int 01261 st_strcasecmp(const char *s1, const char *s2) 01262 { 01263 unsigned int c1, c2; 01264 01265 while (1) { 01266 c1 = (unsigned char)*s1++; 01267 c2 = (unsigned char)*s2++; 01268 if (c1 == '\0' || c2 == '\0') { 01269 if (c1 != '\0') return 1; 01270 if (c2 != '\0') return -1; 01271 return 0; 01272 } 01273 if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A'; 01274 if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A'; 01275 if (c1 != c2) { 01276 if (c1 > c2) 01277 return 1; 01278 else 01279 return -1; 01280 } 01281 } 01282 } 01283 01284 int 01285 st_strncasecmp(const char *s1, const char *s2, size_t n) 01286 { 01287 unsigned int c1, c2; 01288 01289 while (n--) { 01290 c1 = (unsigned char)*s1++; 01291 c2 = (unsigned char)*s2++; 01292 if (c1 == '\0' || c2 == '\0') { 01293 if (c1 != '\0') return 1; 01294 if (c2 != '\0') return -1; 01295 return 0; 01296 } 01297 if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A'; 01298 if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A'; 01299 if (c1 != c2) { 01300 if (c1 > c2) 01301 return 1; 01302 else 01303 return -1; 01304 } 01305 } 01306 return 0; 01307 } 01308 01309 static st_index_t 01310 strcasehash(st_data_t arg) 01311 { 01312 register const char *string = (const char *)arg; 01313 register st_index_t hval = FNV1_32A_INIT; 01314 01315 /* 01316 * FNV-1a hash each octet in the buffer 01317 */ 01318 while (*string) { 01319 unsigned int c = (unsigned char)*string++; 01320 if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A'; 01321 hval ^= c; 01322 01323 /* multiply by the 32 bit FNV magic prime mod 2^32 */ 01324 hval *= FNV_32_PRIME; 01325 } 01326 return hval; 01327 } 01328 01329 int 01330 st_numcmp(st_data_t x, st_data_t y) 01331 { 01332 return x != y; 01333 } 01334 01335 st_index_t 01336 st_numhash(st_data_t n) 01337 { 01338 return (st_index_t)n; 01339 } 01340