Annotation of embedaddon/php/ext/mbstring/oniguruma/st.c, revision 1.1
1.1 ! misho 1: /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
! 2:
! 3: /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
! 4:
! 5: #include "config.h"
! 6: #include <stdio.h>
! 7: #include <stdlib.h>
! 8: #include <string.h>
! 9:
! 10: #ifdef _WIN32
! 11: #include <malloc.h>
! 12: #endif
! 13:
! 14: #ifdef NOT_RUBY
! 15: #include "regint.h"
! 16: #else
! 17: #ifdef RUBY_PLATFORM
! 18: #define xmalloc ruby_xmalloc
! 19: #define xcalloc ruby_xcalloc
! 20: #define xrealloc ruby_xrealloc
! 21: #define xfree ruby_xfree
! 22:
! 23: void *xmalloc(long);
! 24: void *xcalloc(long, long);
! 25: void *xrealloc(void *, long);
! 26: void xfree(void *);
! 27: #endif
! 28: #endif
! 29:
! 30: #include "st.h"
! 31:
! 32: typedef struct st_table_entry st_table_entry;
! 33:
! 34: struct st_table_entry {
! 35: unsigned int hash;
! 36: st_data_t key;
! 37: st_data_t record;
! 38: st_table_entry *next;
! 39: };
! 40:
! 41: #define ST_DEFAULT_MAX_DENSITY 5
! 42: #define ST_DEFAULT_INIT_TABLE_SIZE 11
! 43:
! 44: /*
! 45: * DEFAULT_MAX_DENSITY is the default for the largest we allow the
! 46: * average number of items per bin before increasing the number of
! 47: * bins
! 48: *
! 49: * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
! 50: * allocated initially
! 51: *
! 52: */
! 53:
! 54: static int numcmp(long, long);
! 55: static int numhash(long);
! 56: static struct st_hash_type type_numhash = {
! 57: numcmp,
! 58: numhash,
! 59: };
! 60:
! 61: /* extern int strcmp(const char *, const char *); */
! 62: static int strhash(const char *);
! 63: static struct st_hash_type type_strhash = {
! 64: strcmp,
! 65: strhash,
! 66: };
! 67:
! 68: static void rehash(st_table *);
! 69:
! 70: #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
! 71: #define Calloc(n,s) (char*)xcalloc((n),(s))
! 72:
! 73: #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
! 74:
! 75: #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
! 76: #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
! 77:
! 78: /*
! 79: * MINSIZE is the minimum size of a dictionary.
! 80: */
! 81:
! 82: #define MINSIZE 8
! 83:
! 84: /*
! 85: Table of prime numbers 2^n+a, 2<=n<=30.
! 86: */
! 87: static const long primes[] = {
! 88: 8 + 3,
! 89: 16 + 3,
! 90: 32 + 5,
! 91: 64 + 3,
! 92: 128 + 3,
! 93: 256 + 27,
! 94: 512 + 9,
! 95: 1024 + 9,
! 96: 2048 + 5,
! 97: 4096 + 3,
! 98: 8192 + 27,
! 99: 16384 + 43,
! 100: 32768 + 3,
! 101: 65536 + 45,
! 102: 131072 + 29,
! 103: 262144 + 3,
! 104: 524288 + 21,
! 105: 1048576 + 7,
! 106: 2097152 + 17,
! 107: 4194304 + 15,
! 108: 8388608 + 9,
! 109: 16777216 + 43,
! 110: 33554432 + 35,
! 111: 67108864 + 15,
! 112: 134217728 + 29,
! 113: 268435456 + 3,
! 114: 536870912 + 11,
! 115: 1073741824 + 85,
! 116: 0
! 117: };
! 118:
! 119: static int
! 120: new_size(size)
! 121: int size;
! 122: {
! 123: int i;
! 124:
! 125: #if 0
! 126: for (i=3; i<31; i++) {
! 127: if ((1<<i) > size) return 1<<i;
! 128: }
! 129: return -1;
! 130: #else
! 131: int newsize;
! 132:
! 133: for (i = 0, newsize = MINSIZE;
! 134: i < (int )(sizeof(primes)/sizeof(primes[0]));
! 135: i++, newsize <<= 1)
! 136: {
! 137: if (newsize > size) return primes[i];
! 138: }
! 139: /* Ran out of polynomials */
! 140: return -1; /* should raise exception */
! 141: #endif
! 142: }
! 143:
! 144: #ifdef HASH_LOG
! 145: static int collision = 0;
! 146: static int init_st = 0;
! 147:
! 148: static void
! 149: stat_col()
! 150: {
! 151: FILE *f = fopen("/tmp/col", "w");
! 152: fprintf(f, "collision: %d\n", collision);
! 153: fclose(f);
! 154: }
! 155: #endif
! 156:
! 157: st_table*
! 158: st_init_table_with_size(type, size)
! 159: struct st_hash_type *type;
! 160: int size;
! 161: {
! 162: st_table *tbl;
! 163:
! 164: #ifdef HASH_LOG
! 165: if (init_st == 0) {
! 166: init_st = 1;
! 167: atexit(stat_col);
! 168: }
! 169: #endif
! 170:
! 171: size = new_size(size); /* round up to prime number */
! 172:
! 173: tbl = alloc(st_table);
! 174: tbl->type = type;
! 175: tbl->num_entries = 0;
! 176: tbl->num_bins = size;
! 177: tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
! 178:
! 179: return tbl;
! 180: }
! 181:
! 182: st_table*
! 183: st_init_table(type)
! 184: struct st_hash_type *type;
! 185: {
! 186: return st_init_table_with_size(type, 0);
! 187: }
! 188:
! 189: st_table*
! 190: st_init_numtable(void)
! 191: {
! 192: return st_init_table(&type_numhash);
! 193: }
! 194:
! 195: st_table*
! 196: st_init_numtable_with_size(size)
! 197: int size;
! 198: {
! 199: return st_init_table_with_size(&type_numhash, size);
! 200: }
! 201:
! 202: st_table*
! 203: st_init_strtable(void)
! 204: {
! 205: return st_init_table(&type_strhash);
! 206: }
! 207:
! 208: st_table*
! 209: st_init_strtable_with_size(size)
! 210: int size;
! 211: {
! 212: return st_init_table_with_size(&type_strhash, size);
! 213: }
! 214:
! 215: void
! 216: st_free_table(table)
! 217: st_table *table;
! 218: {
! 219: register st_table_entry *ptr, *next;
! 220: int i;
! 221:
! 222: for(i = 0; i < table->num_bins; i++) {
! 223: ptr = table->bins[i];
! 224: while (ptr != 0) {
! 225: next = ptr->next;
! 226: free(ptr);
! 227: ptr = next;
! 228: }
! 229: }
! 230: free(table->bins);
! 231: free(table);
! 232: }
! 233:
! 234: #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
! 235: ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
! 236:
! 237: #ifdef HASH_LOG
! 238: #define COLLISION collision++
! 239: #else
! 240: #define COLLISION
! 241: #endif
! 242:
! 243: #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
! 244: bin_pos = hash_val%(table)->num_bins;\
! 245: ptr = (table)->bins[bin_pos];\
! 246: if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
! 247: COLLISION;\
! 248: while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
! 249: ptr = ptr->next;\
! 250: }\
! 251: ptr = ptr->next;\
! 252: }\
! 253: } while (0)
! 254:
! 255: int
! 256: st_lookup(table, key, value)
! 257: st_table *table;
! 258: register st_data_t key;
! 259: st_data_t *value;
! 260: {
! 261: unsigned int hash_val, bin_pos;
! 262: register st_table_entry *ptr;
! 263:
! 264: hash_val = do_hash(key, table);
! 265: FIND_ENTRY(table, ptr, hash_val, bin_pos);
! 266:
! 267: if (ptr == 0) {
! 268: return 0;
! 269: }
! 270: else {
! 271: if (value != 0) *value = ptr->record;
! 272: return 1;
! 273: }
! 274: }
! 275:
! 276: #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
! 277: do {\
! 278: st_table_entry *entry;\
! 279: if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
! 280: rehash(table);\
! 281: bin_pos = hash_val % table->num_bins;\
! 282: }\
! 283: \
! 284: entry = alloc(st_table_entry);\
! 285: \
! 286: entry->hash = hash_val;\
! 287: entry->key = key;\
! 288: entry->record = value;\
! 289: entry->next = table->bins[bin_pos];\
! 290: table->bins[bin_pos] = entry;\
! 291: table->num_entries++;\
! 292: } while (0)
! 293:
! 294: int
! 295: st_insert(table, key, value)
! 296: register st_table *table;
! 297: register st_data_t key;
! 298: st_data_t value;
! 299: {
! 300: unsigned int hash_val, bin_pos;
! 301: register st_table_entry *ptr;
! 302:
! 303: hash_val = do_hash(key, table);
! 304: FIND_ENTRY(table, ptr, hash_val, bin_pos);
! 305:
! 306: if (ptr == 0) {
! 307: ADD_DIRECT(table, key, value, hash_val, bin_pos);
! 308: return 0;
! 309: }
! 310: else {
! 311: ptr->record = value;
! 312: return 1;
! 313: }
! 314: }
! 315:
! 316: void
! 317: st_add_direct(table, key, value)
! 318: st_table *table;
! 319: st_data_t key;
! 320: st_data_t value;
! 321: {
! 322: unsigned int hash_val, bin_pos;
! 323:
! 324: hash_val = do_hash(key, table);
! 325: bin_pos = hash_val % table->num_bins;
! 326: ADD_DIRECT(table, key, value, hash_val, bin_pos);
! 327: }
! 328:
! 329: static void
! 330: rehash(table)
! 331: register st_table *table;
! 332: {
! 333: register st_table_entry *ptr, *next, **new_bins;
! 334: int i, old_num_bins = table->num_bins, new_num_bins;
! 335: unsigned int hash_val;
! 336:
! 337: new_num_bins = new_size(old_num_bins+1);
! 338: new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
! 339:
! 340: for(i = 0; i < old_num_bins; i++) {
! 341: ptr = table->bins[i];
! 342: while (ptr != 0) {
! 343: next = ptr->next;
! 344: hash_val = ptr->hash % new_num_bins;
! 345: ptr->next = new_bins[hash_val];
! 346: new_bins[hash_val] = ptr;
! 347: ptr = next;
! 348: }
! 349: }
! 350: free(table->bins);
! 351: table->num_bins = new_num_bins;
! 352: table->bins = new_bins;
! 353: }
! 354:
! 355: st_table*
! 356: st_copy(old_table)
! 357: st_table *old_table;
! 358: {
! 359: st_table *new_table;
! 360: st_table_entry *ptr, *entry;
! 361: int i, num_bins = old_table->num_bins;
! 362:
! 363: new_table = alloc(st_table);
! 364: if (new_table == 0) {
! 365: return 0;
! 366: }
! 367:
! 368: *new_table = *old_table;
! 369: new_table->bins = (st_table_entry**)
! 370: Calloc((unsigned)num_bins, sizeof(st_table_entry*));
! 371:
! 372: if (new_table->bins == 0) {
! 373: free(new_table);
! 374: return 0;
! 375: }
! 376:
! 377: for(i = 0; i < num_bins; i++) {
! 378: new_table->bins[i] = 0;
! 379: ptr = old_table->bins[i];
! 380: while (ptr != 0) {
! 381: entry = alloc(st_table_entry);
! 382: if (entry == 0) {
! 383: free(new_table->bins);
! 384: free(new_table);
! 385: return 0;
! 386: }
! 387: *entry = *ptr;
! 388: entry->next = new_table->bins[i];
! 389: new_table->bins[i] = entry;
! 390: ptr = ptr->next;
! 391: }
! 392: }
! 393: return new_table;
! 394: }
! 395:
! 396: int
! 397: st_delete(table, key, value)
! 398: register st_table *table;
! 399: register st_data_t *key;
! 400: st_data_t *value;
! 401: {
! 402: unsigned int hash_val;
! 403: st_table_entry *tmp;
! 404: register st_table_entry *ptr;
! 405:
! 406: hash_val = do_hash_bin(*key, table);
! 407: ptr = table->bins[hash_val];
! 408:
! 409: if (ptr == 0) {
! 410: if (value != 0) *value = 0;
! 411: return 0;
! 412: }
! 413:
! 414: if (EQUAL(table, *key, ptr->key)) {
! 415: table->bins[hash_val] = ptr->next;
! 416: table->num_entries--;
! 417: if (value != 0) *value = ptr->record;
! 418: *key = ptr->key;
! 419: free(ptr);
! 420: return 1;
! 421: }
! 422:
! 423: for(; ptr->next != 0; ptr = ptr->next) {
! 424: if (EQUAL(table, ptr->next->key, *key)) {
! 425: tmp = ptr->next;
! 426: ptr->next = ptr->next->next;
! 427: table->num_entries--;
! 428: if (value != 0) *value = tmp->record;
! 429: *key = tmp->key;
! 430: free(tmp);
! 431: return 1;
! 432: }
! 433: }
! 434:
! 435: return 0;
! 436: }
! 437:
! 438: int
! 439: st_delete_safe(table, key, value, never)
! 440: register st_table *table;
! 441: register st_data_t *key;
! 442: st_data_t *value;
! 443: st_data_t never;
! 444: {
! 445: unsigned int hash_val;
! 446: register st_table_entry *ptr;
! 447:
! 448: hash_val = do_hash_bin(*key, table);
! 449: ptr = table->bins[hash_val];
! 450:
! 451: if (ptr == 0) {
! 452: if (value != 0) *value = 0;
! 453: return 0;
! 454: }
! 455:
! 456: for(; ptr != 0; ptr = ptr->next) {
! 457: if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
! 458: table->num_entries--;
! 459: *key = ptr->key;
! 460: if (value != 0) *value = ptr->record;
! 461: ptr->key = ptr->record = never;
! 462: return 1;
! 463: }
! 464: }
! 465:
! 466: return 0;
! 467: }
! 468:
! 469: static int
! 470: delete_never(key, value, never)
! 471: st_data_t key, value, never;
! 472: {
! 473: if (value == never) return ST_DELETE;
! 474: return ST_CONTINUE;
! 475: }
! 476:
! 477: void
! 478: st_cleanup_safe(table, never)
! 479: st_table *table;
! 480: st_data_t never;
! 481: {
! 482: int num_entries = table->num_entries;
! 483:
! 484: st_foreach(table, delete_never, never);
! 485: table->num_entries = num_entries;
! 486: }
! 487:
! 488: int
! 489: st_foreach(table, func, arg)
! 490: st_table *table;
! 491: int (*func)();
! 492: st_data_t arg;
! 493: {
! 494: st_table_entry *ptr, *last, *tmp;
! 495: enum st_retval retval;
! 496: int i;
! 497:
! 498: for(i = 0; i < table->num_bins; i++) {
! 499: last = 0;
! 500: for(ptr = table->bins[i]; ptr != 0;) {
! 501: retval = (*func)(ptr->key, ptr->record, arg);
! 502: switch (retval) {
! 503: case ST_CHECK: /* check if hash is modified during iteration */
! 504: tmp = 0;
! 505: if (i < table->num_bins) {
! 506: for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
! 507: if (tmp == ptr) break;
! 508: }
! 509: }
! 510: if (!tmp) {
! 511: /* call func with error notice */
! 512: return 1;
! 513: }
! 514: /* fall through */
! 515: case ST_CONTINUE:
! 516: last = ptr;
! 517: ptr = ptr->next;
! 518: break;
! 519: case ST_STOP:
! 520: return 0;
! 521: case ST_DELETE:
! 522: tmp = ptr;
! 523: if (last == 0) {
! 524: table->bins[i] = ptr->next;
! 525: }
! 526: else {
! 527: last->next = ptr->next;
! 528: }
! 529: ptr = ptr->next;
! 530: free(tmp);
! 531: table->num_entries--;
! 532: }
! 533: }
! 534: }
! 535: return 0;
! 536: }
! 537:
! 538: static int
! 539: strhash(string)
! 540: register const char *string;
! 541: {
! 542: register int c;
! 543:
! 544: #ifdef HASH_ELFHASH
! 545: register unsigned int h = 0, g;
! 546:
! 547: while ((c = *string++) != '\0') {
! 548: h = ( h << 4 ) + c;
! 549: if ( g = h & 0xF0000000 )
! 550: h ^= g >> 24;
! 551: h &= ~g;
! 552: }
! 553: return h;
! 554: #elif HASH_PERL
! 555: register int val = 0;
! 556:
! 557: while ((c = *string++) != '\0') {
! 558: val += c;
! 559: val += (val << 10);
! 560: val ^= (val >> 6);
! 561: }
! 562: val += (val << 3);
! 563: val ^= (val >> 11);
! 564:
! 565: return val + (val << 15);
! 566: #else
! 567: register int val = 0;
! 568:
! 569: while ((c = *string++) != '\0') {
! 570: val = val*997 + c;
! 571: }
! 572:
! 573: return val + (val>>5);
! 574: #endif
! 575: }
! 576:
! 577: static int
! 578: numcmp(x, y)
! 579: long x, y;
! 580: {
! 581: return x != y;
! 582: }
! 583:
! 584: static int
! 585: numhash(n)
! 586: long n;
! 587: {
! 588: return n;
! 589: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to st.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / mbstring / oniguruma