|
Ruby
1.9.3p448(2013-06-27revision41675)
|
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 st_index_t 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 int 00699 st_shift(register st_table *table, register st_data_t *key, st_data_t *value) 00700 { 00701 st_index_t hash_val; 00702 st_table_entry **prev; 00703 register st_table_entry *ptr; 00704 00705 if (table->num_entries == 0) { 00706 if (value != 0) *value = 0; 00707 return 0; 00708 } 00709 00710 if (table->entries_packed) { 00711 if (value != 0) *value = (st_data_t)table->bins[1]; 00712 *key = (st_data_t)table->bins[0]; 00713 table->num_entries--; 00714 memmove(&table->bins[0], &table->bins[2], 00715 sizeof(struct st_table_entry*) * 2*table->num_entries); 00716 return 1; 00717 } 00718 00719 hash_val = do_hash_bin(table->head->key, table); 00720 prev = &table->bins[hash_val]; 00721 for (;(ptr = *prev) != 0; prev = &ptr->next) { 00722 if (ptr == table->head) { 00723 *prev = ptr->next; 00724 REMOVE_ENTRY(table, ptr); 00725 if (value != 0) *value = ptr->record; 00726 *key = ptr->key; 00727 free(ptr); 00728 return 1; 00729 } 00730 } 00731 00732 /* if hash is not consistent and need to be rehashed */ 00733 if (value != 0) *value = 0; 00734 return 0; 00735 } 00736 00737 void 00738 st_cleanup_safe(st_table *table, st_data_t never) 00739 { 00740 st_table_entry *ptr, **last, *tmp; 00741 st_index_t i; 00742 00743 if (table->entries_packed) { 00744 st_index_t i = 0, j = 0; 00745 while ((st_data_t)table->bins[i*2] != never) { 00746 if (i++ == table->num_entries) return; 00747 } 00748 for (j = i; ++i < table->num_entries;) { 00749 if ((st_data_t)table->bins[i*2] == never) continue; 00750 table->bins[j*2] = table->bins[i*2]; 00751 table->bins[j*2+1] = table->bins[i*2+1]; 00752 j++; 00753 } 00754 table->num_entries = j; 00755 return; 00756 } 00757 00758 for (i = 0; i < table->num_bins; i++) { 00759 ptr = *(last = &table->bins[i]); 00760 while (ptr != 0) { 00761 if (ptr->key == never) { 00762 tmp = ptr; 00763 *last = ptr = ptr->next; 00764 free(tmp); 00765 } 00766 else { 00767 ptr = *(last = &ptr->next); 00768 } 00769 } 00770 } 00771 } 00772 00773 int 00774 st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) 00775 { 00776 st_table_entry *ptr, **last, *tmp; 00777 enum st_retval retval; 00778 st_index_t i; 00779 00780 if (table->entries_packed) { 00781 for (i = 0; i < table->num_entries; i++) { 00782 st_index_t j; 00783 st_data_t key, val; 00784 key = (st_data_t)table->bins[i*2]; 00785 val = (st_data_t)table->bins[i*2+1]; 00786 retval = (*func)(key, val, arg); 00787 if (!table->entries_packed) { 00788 FIND_ENTRY(table, ptr, key, i); 00789 if (retval == ST_CHECK) { 00790 if (!ptr) goto deleted; 00791 goto unpacked_continue; 00792 } 00793 goto unpacked; 00794 } 00795 switch (retval) { 00796 case ST_CHECK: /* check if hash is modified during iteration */ 00797 for (j = 0; j < table->num_entries; j++) { 00798 if ((st_data_t)table->bins[j*2] == key) 00799 break; 00800 } 00801 if (j == table->num_entries) { 00802 goto deleted; 00803 } 00804 /* fall through */ 00805 case ST_CONTINUE: 00806 break; 00807 case ST_STOP: 00808 return 0; 00809 case ST_DELETE: 00810 table->num_entries--; 00811 memmove(&table->bins[i*2], &table->bins[(i+1)*2], 00812 sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); 00813 i--; 00814 break; 00815 } 00816 } 00817 return 0; 00818 } 00819 else { 00820 ptr = table->head; 00821 } 00822 00823 if (ptr != 0) { 00824 do { 00825 i = ptr->hash % table->num_bins; 00826 retval = (*func)(ptr->key, ptr->record, arg); 00827 unpacked: 00828 switch (retval) { 00829 case ST_CHECK: /* check if hash is modified during iteration */ 00830 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { 00831 if (!tmp) { 00832 deleted: 00833 /* call func with error notice */ 00834 retval = (*func)(0, 0, arg, 1); 00835 return 1; 00836 } 00837 } 00838 /* fall through */ 00839 case ST_CONTINUE: 00840 unpacked_continue: 00841 ptr = ptr->fore; 00842 break; 00843 case ST_STOP: 00844 return 0; 00845 case ST_DELETE: 00846 last = &table->bins[ptr->hash % table->num_bins]; 00847 for (; (tmp = *last) != 0; last = &tmp->next) { 00848 if (ptr == tmp) { 00849 tmp = ptr->fore; 00850 *last = ptr->next; 00851 REMOVE_ENTRY(table, ptr); 00852 free(ptr); 00853 if (ptr == tmp) return 0; 00854 ptr = tmp; 00855 break; 00856 } 00857 } 00858 } 00859 } while (ptr && table->head); 00860 } 00861 return 0; 00862 } 00863 00864 #if 0 /* unused right now */ 00865 int 00866 st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) 00867 { 00868 st_table_entry *ptr, **last, *tmp; 00869 enum st_retval retval; 00870 int i; 00871 00872 if (table->entries_packed) { 00873 for (i = table->num_entries-1; 0 <= i; i--) { 00874 int j; 00875 st_data_t key, val; 00876 key = (st_data_t)table->bins[i*2]; 00877 val = (st_data_t)table->bins[i*2+1]; 00878 retval = (*func)(key, val, arg); 00879 switch (retval) { 00880 case ST_CHECK: /* check if hash is modified during iteration */ 00881 for (j = 0; j < table->num_entries; j++) { 00882 if ((st_data_t)table->bins[j*2] == key) 00883 break; 00884 } 00885 if (j == table->num_entries) { 00886 /* call func with error notice */ 00887 retval = (*func)(0, 0, arg, 1); 00888 return 1; 00889 } 00890 /* fall through */ 00891 case ST_CONTINUE: 00892 break; 00893 case ST_STOP: 00894 return 0; 00895 case ST_DELETE: 00896 table->num_entries--; 00897 memmove(&table->bins[i*2], &table->bins[(i+1)*2], 00898 sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); 00899 break; 00900 } 00901 } 00902 return 0; 00903 } 00904 00905 if ((ptr = table->head) != 0) { 00906 ptr = ptr->back; 00907 do { 00908 retval = (*func)(ptr->key, ptr->record, arg, 0); 00909 switch (retval) { 00910 case ST_CHECK: /* check if hash is modified during iteration */ 00911 i = ptr->hash % table->num_bins; 00912 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { 00913 if (!tmp) { 00914 /* call func with error notice */ 00915 retval = (*func)(0, 0, arg, 1); 00916 return 1; 00917 } 00918 } 00919 /* fall through */ 00920 case ST_CONTINUE: 00921 ptr = ptr->back; 00922 break; 00923 case ST_STOP: 00924 return 0; 00925 case ST_DELETE: 00926 last = &table->bins[ptr->hash % table->num_bins]; 00927 for (; (tmp = *last) != 0; last = &tmp->next) { 00928 if (ptr == tmp) { 00929 tmp = ptr->back; 00930 *last = ptr->next; 00931 REMOVE_ENTRY(table, ptr); 00932 free(ptr); 00933 ptr = tmp; 00934 break; 00935 } 00936 } 00937 ptr = ptr->next; 00938 free(tmp); 00939 table->num_entries--; 00940 } 00941 } while (ptr && table->head); 00942 } 00943 return 0; 00944 } 00945 #endif 00946 00947 /* 00948 * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code 00949 * 00950 * @(#) $Hash32: Revision: 1.1 $ 00951 * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $ 00952 * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $ 00953 * 00954 *** 00955 * 00956 * Fowler/Noll/Vo hash 00957 * 00958 * The basis of this hash algorithm was taken from an idea sent 00959 * as reviewer comments to the IEEE POSIX P1003.2 committee by: 00960 * 00961 * Phong Vo (http://www.research.att.com/info/kpv/) 00962 * Glenn Fowler (http://www.research.att.com/~gsf/) 00963 * 00964 * In a subsequent ballot round: 00965 * 00966 * Landon Curt Noll (http://www.isthe.com/chongo/) 00967 * 00968 * improved on their algorithm. Some people tried this hash 00969 * and found that it worked rather well. In an EMail message 00970 * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. 00971 * 00972 * FNV hashes are designed to be fast while maintaining a low 00973 * collision rate. The FNV speed allows one to quickly hash lots 00974 * of data while maintaining a reasonable collision rate. See: 00975 * 00976 * http://www.isthe.com/chongo/tech/comp/fnv/index.html 00977 * 00978 * for more details as well as other forms of the FNV hash. 00979 *** 00980 * 00981 * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the 00982 * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str(). 00983 * 00984 *** 00985 * 00986 * Please do not copyright this code. This code is in the public domain. 00987 * 00988 * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 00989 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO 00990 * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR 00991 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF 00992 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR 00993 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 00994 * PERFORMANCE OF THIS SOFTWARE. 00995 * 00996 * By: 00997 * chongo <Landon Curt Noll> /\oo/\ 00998 * http://www.isthe.com/chongo/ 00999 * 01000 * Share and Enjoy! :-) 01001 */ 01002 01003 /* 01004 * 32 bit FNV-1 and FNV-1a non-zero initial basis 01005 * 01006 * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets: 01007 * 01008 * chongo <Landon Curt Noll> /\../\ 01009 * 01010 * NOTE: The \'s above are not back-slashing escape characters. 01011 * They are literal ASCII backslash 0x5c characters. 01012 * 01013 * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition. 01014 */ 01015 #define FNV1_32A_INIT 0x811c9dc5 01016 01017 /* 01018 * 32 bit magic FNV-1a prime 01019 */ 01020 #define FNV_32_PRIME 0x01000193 01021 01022 #ifdef ST_USE_FNV1 01023 static st_index_t 01024 strhash(st_data_t arg) 01025 { 01026 register const char *string = (const char *)arg; 01027 register st_index_t hval = FNV1_32A_INIT; 01028 01029 /* 01030 * FNV-1a hash each octet in the buffer 01031 */ 01032 while (*string) { 01033 /* xor the bottom with the current octet */ 01034 hval ^= (unsigned int)*string++; 01035 01036 /* multiply by the 32 bit FNV magic prime mod 2^32 */ 01037 hval *= FNV_32_PRIME; 01038 } 01039 return hval; 01040 } 01041 #else 01042 01043 #ifndef UNALIGNED_WORD_ACCESS 01044 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \ 01045 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \ 01046 defined(__mc68020__) 01047 # define UNALIGNED_WORD_ACCESS 1 01048 # endif 01049 #endif 01050 #ifndef UNALIGNED_WORD_ACCESS 01051 # define UNALIGNED_WORD_ACCESS 0 01052 #endif 01053 01054 /* MurmurHash described in http://murmurhash.googlepages.com/ */ 01055 #ifndef MURMUR 01056 #define MURMUR 2 01057 #endif 01058 01059 #define MurmurMagic_1 (st_index_t)0xc6a4a793 01060 #define MurmurMagic_2 (st_index_t)0x5bd1e995 01061 #if MURMUR == 1 01062 #define MurmurMagic MurmurMagic_1 01063 #elif MURMUR == 2 01064 #if SIZEOF_ST_INDEX_T > 4 01065 #define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2) 01066 #else 01067 #define MurmurMagic MurmurMagic_2 01068 #endif 01069 #endif 01070 01071 static inline st_index_t 01072 murmur(st_index_t h, st_index_t k, int r) 01073 { 01074 const st_index_t m = MurmurMagic; 01075 #if MURMUR == 1 01076 h += k; 01077 h *= m; 01078 h ^= h >> r; 01079 #elif MURMUR == 2 01080 k *= m; 01081 k ^= k >> r; 01082 k *= m; 01083 01084 h *= m; 01085 h ^= k; 01086 #endif 01087 return h; 01088 } 01089 01090 static inline st_index_t 01091 murmur_finish(st_index_t h) 01092 { 01093 #if MURMUR == 1 01094 h = murmur(h, 0, 10); 01095 h = murmur(h, 0, 17); 01096 #elif MURMUR == 2 01097 h ^= h >> 13; 01098 h *= MurmurMagic; 01099 h ^= h >> 15; 01100 #endif 01101 return h; 01102 } 01103 01104 #define murmur_step(h, k) murmur((h), (k), 16) 01105 01106 #if MURMUR == 1 01107 #define murmur1(h) murmur_step((h), 16) 01108 #else 01109 #define murmur1(h) murmur_step((h), 24) 01110 #endif 01111 01112 st_index_t 01113 st_hash(const void *ptr, size_t len, st_index_t h) 01114 { 01115 const char *data = ptr; 01116 st_index_t t = 0; 01117 01118 h += 0xdeadbeef; 01119 01120 #define data_at(n) (st_index_t)((unsigned char)data[(n)]) 01121 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0) 01122 #if SIZEOF_ST_INDEX_T > 4 01123 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4 01124 #if SIZEOF_ST_INDEX_T > 8 01125 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \ 01126 UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8 01127 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16 01128 #endif 01129 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8 01130 #else 01131 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4 01132 #endif 01133 if (len >= sizeof(st_index_t)) { 01134 #if !UNALIGNED_WORD_ACCESS 01135 int align = (int)((st_data_t)data % sizeof(st_index_t)); 01136 if (align) { 01137 st_index_t d = 0; 01138 int sl, sr, pack; 01139 01140 switch (align) { 01141 #ifdef WORDS_BIGENDIAN 01142 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \ 01143 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2) 01144 #else 01145 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \ 01146 t |= data_at(n) << CHAR_BIT*(n) 01147 #endif 01148 UNALIGNED_ADD_ALL; 01149 #undef UNALIGNED_ADD 01150 } 01151 01152 #ifdef WORDS_BIGENDIAN 01153 t >>= (CHAR_BIT * align) - CHAR_BIT; 01154 #else 01155 t <<= (CHAR_BIT * align); 01156 #endif 01157 01158 data += sizeof(st_index_t)-align; 01159 len -= sizeof(st_index_t)-align; 01160 01161 sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align); 01162 sr = CHAR_BIT * align; 01163 01164 while (len >= sizeof(st_index_t)) { 01165 d = *(st_index_t *)data; 01166 #ifdef WORDS_BIGENDIAN 01167 t = (t << sr) | (d >> sl); 01168 #else 01169 t = (t >> sr) | (d << sl); 01170 #endif 01171 h = murmur_step(h, t); 01172 t = d; 01173 data += sizeof(st_index_t); 01174 len -= sizeof(st_index_t); 01175 } 01176 01177 pack = len < (size_t)align ? (int)len : align; 01178 d = 0; 01179 switch (pack) { 01180 #ifdef WORDS_BIGENDIAN 01181 # define UNALIGNED_ADD(n) case (n) + 1: \ 01182 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1) 01183 #else 01184 # define UNALIGNED_ADD(n) case (n) + 1: \ 01185 d |= data_at(n) << CHAR_BIT*(n) 01186 #endif 01187 UNALIGNED_ADD_ALL; 01188 #undef UNALIGNED_ADD 01189 } 01190 #ifdef WORDS_BIGENDIAN 01191 t = (t << sr) | (d >> sl); 01192 #else 01193 t = (t >> sr) | (d << sl); 01194 #endif 01195 01196 #if MURMUR == 2 01197 if (len < (size_t)align) goto skip_tail; 01198 #endif 01199 h = murmur_step(h, t); 01200 data += pack; 01201 len -= pack; 01202 } 01203 else 01204 #endif 01205 { 01206 do { 01207 h = murmur_step(h, *(st_index_t *)data); 01208 data += sizeof(st_index_t); 01209 len -= sizeof(st_index_t); 01210 } while (len >= sizeof(st_index_t)); 01211 } 01212 } 01213 01214 t = 0; 01215 switch (len) { 01216 #ifdef WORDS_BIGENDIAN 01217 # define UNALIGNED_ADD(n) case (n) + 1: \ 01218 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1) 01219 #else 01220 # define UNALIGNED_ADD(n) case (n) + 1: \ 01221 t |= data_at(n) << CHAR_BIT*(n) 01222 #endif 01223 UNALIGNED_ADD_ALL; 01224 #undef UNALIGNED_ADD 01225 #if MURMUR == 1 01226 h = murmur_step(h, t); 01227 #elif MURMUR == 2 01228 # if !UNALIGNED_WORD_ACCESS 01229 skip_tail: 01230 # endif 01231 h ^= t; 01232 h *= MurmurMagic; 01233 #endif 01234 } 01235 01236 return murmur_finish(h); 01237 } 01238 01239 st_index_t 01240 st_hash_uint32(st_index_t h, uint32_t i) 01241 { 01242 return murmur_step(h + i, 16); 01243 } 01244 01245 st_index_t 01246 st_hash_uint(st_index_t h, st_index_t i) 01247 { 01248 st_index_t v = 0; 01249 h += i; 01250 #ifdef WORDS_BIGENDIAN 01251 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 01252 v = murmur1(v + (h >> 12*8)); 01253 #endif 01254 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 01255 v = murmur1(v + (h >> 8*8)); 01256 #endif 01257 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 01258 v = murmur1(v + (h >> 4*8)); 01259 #endif 01260 #endif 01261 v = murmur1(v + h); 01262 #ifndef WORDS_BIGENDIAN 01263 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 01264 v = murmur1(v + (h >> 4*8)); 01265 #endif 01266 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 01267 v = murmur1(v + (h >> 8*8)); 01268 #endif 01269 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 01270 v = murmur1(v + (h >> 12*8)); 01271 #endif 01272 #endif 01273 return v; 01274 } 01275 01276 st_index_t 01277 st_hash_end(st_index_t h) 01278 { 01279 h = murmur_step(h, 10); 01280 h = murmur_step(h, 17); 01281 return h; 01282 } 01283 01284 #undef st_hash_start 01285 st_index_t 01286 st_hash_start(st_index_t h) 01287 { 01288 return h; 01289 } 01290 01291 static st_index_t 01292 strhash(st_data_t arg) 01293 { 01294 register const char *string = (const char *)arg; 01295 return st_hash(string, strlen(string), FNV1_32A_INIT); 01296 } 01297 #endif 01298 01299 int 01300 st_strcasecmp(const char *s1, const char *s2) 01301 { 01302 unsigned int c1, c2; 01303 01304 while (1) { 01305 c1 = (unsigned char)*s1++; 01306 c2 = (unsigned char)*s2++; 01307 if (c1 == '\0' || c2 == '\0') { 01308 if (c1 != '\0') return 1; 01309 if (c2 != '\0') return -1; 01310 return 0; 01311 } 01312 if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A'; 01313 if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A'; 01314 if (c1 != c2) { 01315 if (c1 > c2) 01316 return 1; 01317 else 01318 return -1; 01319 } 01320 } 01321 } 01322 01323 int 01324 st_strncasecmp(const char *s1, const char *s2, size_t n) 01325 { 01326 unsigned int c1, c2; 01327 01328 while (n--) { 01329 c1 = (unsigned char)*s1++; 01330 c2 = (unsigned char)*s2++; 01331 if (c1 == '\0' || c2 == '\0') { 01332 if (c1 != '\0') return 1; 01333 if (c2 != '\0') return -1; 01334 return 0; 01335 } 01336 if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A'; 01337 if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A'; 01338 if (c1 != c2) { 01339 if (c1 > c2) 01340 return 1; 01341 else 01342 return -1; 01343 } 01344 } 01345 return 0; 01346 } 01347 01348 static st_index_t 01349 strcasehash(st_data_t arg) 01350 { 01351 register const char *string = (const char *)arg; 01352 register st_index_t hval = FNV1_32A_INIT; 01353 01354 /* 01355 * FNV-1a hash each octet in the buffer 01356 */ 01357 while (*string) { 01358 unsigned int c = (unsigned char)*string++; 01359 if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A'; 01360 hval ^= c; 01361 01362 /* multiply by the 32 bit FNV magic prime mod 2^32 */ 01363 hval *= FNV_32_PRIME; 01364 } 01365 return hval; 01366 } 01367 01368 int 01369 st_numcmp(st_data_t x, st_data_t y) 01370 { 01371 return x != y; 01372 } 01373 01374 st_index_t 01375 st_numhash(st_data_t n) 01376 { 01377 return (st_index_t)n; 01378 } 01379
1.7.6.1