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