| 1 | /* hash.c - hash table lookup strings - |
| 2 | Copyright (C) 1987 Free Software Foundation, Inc. |
| 3 | |
| 4 | This file is part of GAS, the GNU Assembler. |
| 5 | |
| 6 | GAS is free software; you can redistribute it and/or modify |
| 7 | it under the terms of the GNU General Public License as published by |
| 8 | the Free Software Foundation; either version 1, or (at your option) |
| 9 | any later version. |
| 10 | |
| 11 | GAS is distributed in the hope that it will be useful, |
| 12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 | GNU General Public License for more details. |
| 15 | |
| 16 | You should have received a copy of the GNU General Public License |
| 17 | along with GAS; see the file COPYING. If not, write to |
| 18 | the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ |
| 19 | |
| 20 | /* |
| 21 | * BUGS, GRIPES, APOLOGIA etc. |
| 22 | * |
| 23 | * A typical user doesn't need ALL this: I intend to make a library out |
| 24 | * of it one day - Dean Elsner. |
| 25 | * Also, I want to change the definition of a symbol to (address,length) |
| 26 | * so I can put arbitrary binary in the names stored. [see hsh.c for that] |
| 27 | * |
| 28 | * This slime is common coupled inside the module. Com-coupling (and other |
| 29 | * vandalism) was done to speed running time. The interfaces at the |
| 30 | * module's edges are adequately clean. |
| 31 | * |
| 32 | * There is no way to (a) run a test script through this heap and (b) |
| 33 | * compare results with previous scripts, to see if we have broken any |
| 34 | * code. Use GNU (f)utilities to do this. A few commands assist test. |
| 35 | * The testing is awkward: it tries to be both batch & interactive. |
| 36 | * For now, interactive rules! |
| 37 | */ |
| 38 | \f |
| 39 | /* |
| 40 | * The idea is to implement a symbol table. A test jig is here. |
| 41 | * Symbols are arbitrary strings; they can't contain '\0'. |
| 42 | * [See hsh.c for a more general symbol flavour.] |
| 43 | * Each symbol is associated with a char*, which can point to anything |
| 44 | * you want, allowing an arbitrary property list for each symbol. |
| 45 | * |
| 46 | * The basic operations are: |
| 47 | * |
| 48 | * new creates symbol table, returns handle |
| 49 | * find (symbol) returns char* |
| 50 | * insert (symbol,char*) error if symbol already in table |
| 51 | * delete (symbol) returns char* if symbol was in table |
| 52 | * apply so you can delete all symbols before die() |
| 53 | * die destroy symbol table (free up memory) |
| 54 | * |
| 55 | * Supplementary functions include: |
| 56 | * |
| 57 | * say how big? what % full? |
| 58 | * replace (symbol,newval) report previous value |
| 59 | * jam (symbol,value) assert symbol:=value |
| 60 | * |
| 61 | * You, the caller, have control over errors: this just reports them. |
| 62 | * |
| 63 | * This package requires malloc(), free(). |
| 64 | * Malloc(size) returns NULL or address of char[size]. |
| 65 | * Free(address) frees same. |
| 66 | */ |
| 67 | \f |
| 68 | /* |
| 69 | * The code and its structures are re-enterent. |
| 70 | * Before you do anything else, you must call hash_new() which will |
| 71 | * return the address of a hash-table-control-block (or NULL if there |
| 72 | * is not enough memory). You then use this address as a handle of the |
| 73 | * symbol table by passing it to all the other hash_...() functions. |
| 74 | * The only approved way to recover the memory used by the symbol table |
| 75 | * is to call hash_die() with the handle of the symbol table. |
| 76 | * |
| 77 | * Before you call hash_die() you normally delete anything pointed to |
| 78 | * by individual symbols. After hash_die() you can't use that symbol |
| 79 | * table again. |
| 80 | * |
| 81 | * The char* you associate with a symbol may not be NULL (0) because |
| 82 | * NULL is returned whenever a symbol is not in the table. Any other |
| 83 | * value is OK, except DELETED, #defined below. |
| 84 | * |
| 85 | * When you supply a symbol string for insertion, YOU MUST PRESERVE THE |
| 86 | * STRING until that symbol is deleted from the table. The reason is that |
| 87 | * only the address you supply, NOT the symbol string itself, is stored |
| 88 | * in the symbol table. |
| 89 | * |
| 90 | * You may delete and add symbols arbitrarily. |
| 91 | * Any or all symbols may have the same 'value' (char *). In fact, these |
| 92 | * routines don't do anything with your symbol values. |
| 93 | * |
| 94 | * You have no right to know where the symbol:char* mapping is stored, |
| 95 | * because it moves around in memory; also because we may change how it |
| 96 | * works and we don't want to break your code do we? However the handle |
| 97 | * (address of struct hash_control) is never changed in |
| 98 | * the life of the symbol table. |
| 99 | * |
| 100 | * What you CAN find out about a symbol table is: |
| 101 | * how many slots are in the hash table? |
| 102 | * how many slots are filled with symbols? |
| 103 | * (total hashes,collisions) for (reads,writes) (*) |
| 104 | * All of the above values vary in time. |
| 105 | * (*) some of these numbers will not be meaningful if we change the |
| 106 | * internals. |
| 107 | */ |
| 108 | \f |
| 109 | /* |
| 110 | * I N T E R N A L |
| 111 | * |
| 112 | * Hash table is an array of hash_entries; each entry is a pointer to a |
| 113 | * a string and a user-supplied value 1 char* wide. |
| 114 | * |
| 115 | * The array always has 2 ** n elements, n>0, n integer. |
| 116 | * There is also a 'wall' entry after the array, which is always empty |
| 117 | * and acts as a sentinel to stop running off the end of the array. |
| 118 | * When the array gets too full, we create a new array twice as large |
| 119 | * and re-hash the symbols into the new array, then forget the old array. |
| 120 | * (Of course, we copy the values into the new array before we junk the |
| 121 | * old array!) |
| 122 | * |
| 123 | */ |
| 124 | |
| 125 | #include <stdio.h> |
| 126 | #define TRUE (1) |
| 127 | #define FALSE (0) |
| 128 | #include <ctype.h> |
| 129 | #define min(a, b) ((a) < (b) ? (a) : (b)) |
| 130 | |
| 131 | #include "hash.h" |
| 132 | char *xmalloc(); |
| 133 | |
| 134 | #define DELETED ((char *)1) /* guarenteed invalid address */ |
| 135 | #define START_POWER (11) /* power of two: size of new hash table *//* JF was 6 */ |
| 136 | /* JF These next two aren't used any more. */ |
| 137 | /* #define START_SIZE (64) / * 2 ** START_POWER */ |
| 138 | /* #define START_FULL (32) / * number of entries before table expands */ |
| 139 | #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED) |
| 140 | /* above TRUE if a symbol is in entry @ ptr */ |
| 141 | |
| 142 | #define STAT_SIZE (0) /* number of slots in hash table */ |
| 143 | /* the wall does not count here */ |
| 144 | /* we expect this is always a power of 2 */ |
| 145 | #define STAT_ACCESS (1) /* number of hash_ask()s */ |
| 146 | #define STAT__READ (0) /* reading */ |
| 147 | #define STAT__WRITE (1) /* writing */ |
| 148 | #define STAT_COLLIDE (3) /* number of collisions (total) */ |
| 149 | /* this may exceed STAT_ACCESS if we have */ |
| 150 | /* lots of collisions/access */ |
| 151 | #define STAT_USED (5) /* slots used right now */ |
| 152 | #define STATLENGTH (6) /* size of statistics block */ |
| 153 | #if STATLENGTH != HASH_STATLENGTH |
| 154 | Panic! Please make #include "stat.h" agree with previous definitions! |
| 155 | #endif |
| 156 | |
| 157 | /* #define SUSPECT to do runtime checks */ |
| 158 | /* #define TEST to be a test jig for hash...() */ |
| 159 | |
| 160 | #ifdef TEST /* TEST: use smaller hash table */ |
| 161 | #undef START_POWER |
| 162 | #define START_POWER (3) |
| 163 | #undef START_SIZE |
| 164 | #define START_SIZE (8) |
| 165 | #undef START_FULL |
| 166 | #define START_FULL (4) |
| 167 | #endif |
| 168 | \f |
| 169 | /*------------------ plan ---------------------------------- i = internal |
| 170 | |
| 171 | struct hash_control * c; |
| 172 | struct hash_entry * e; i |
| 173 | int b[z]; buffer for statistics |
| 174 | z size of b |
| 175 | char * s; symbol string (address) [ key ] |
| 176 | char * v; value string (address) [datum] |
| 177 | boolean f; TRUE if we found s in hash table i |
| 178 | char * t; error string; "" means OK |
| 179 | int a; access type [0...n) i |
| 180 | |
| 181 | c=hash_new () create new hash_control |
| 182 | |
| 183 | hash_die (c) destroy hash_control (and hash table) |
| 184 | table should be empty. |
| 185 | doesn't check if table is empty. |
| 186 | c has no meaning after this. |
| 187 | |
| 188 | hash_say (c,b,z) report statistics of hash_control. |
| 189 | also report number of available statistics. |
| 190 | |
| 191 | v=hash_delete (c,s) delete symbol, return old value if any. |
| 192 | ask() NULL means no old value. |
| 193 | f |
| 194 | |
| 195 | v=hash_replace (c,s,v) replace old value of s with v. |
| 196 | ask() NULL means no old value: no table change. |
| 197 | f |
| 198 | |
| 199 | t=hash_insert (c,s,v) insert (s,v) in c. |
| 200 | ask() return error string. |
| 201 | f it is an error to insert if s is already |
| 202 | in table. |
| 203 | if any error, c is unchanged. |
| 204 | |
| 205 | t=hash_jam (c,s,v) assert that new value of s will be v. i |
| 206 | ask() it may decide to GROW the table. i |
| 207 | f i |
| 208 | grow() i |
| 209 | t=hash_grow (c) grow the hash table. i |
| 210 | jam() will invoke JAM. i |
| 211 | |
| 212 | ?=hash_apply (c,y) apply y() to every symbol in c. |
| 213 | y evtries visited in 'unspecified' order. |
| 214 | |
| 215 | v=hash_find (c,s) return value of s, or NULL if s not in c. |
| 216 | ask() |
| 217 | f |
| 218 | |
| 219 | f,e=hash_ask() (c,s,a) return slot where s SHOULD live. i |
| 220 | code() maintain collision stats in c. i |
| 221 | |
| 222 | .=hash_code (c,s) compute hash-code for s, i |
| 223 | from parameters of c. i |
| 224 | |
| 225 | */ |
| 226 | \f |
| 227 | static char hash_found; /* returned by hash_ask() to stop extra */ |
| 228 | /* testing. hash_ask() wants to return both */ |
| 229 | /* a slot and a status. This is the status. */ |
| 230 | /* TRUE: found symbol */ |
| 231 | /* FALSE: absent: empty or deleted slot */ |
| 232 | /* Also returned by hash_jam(). */ |
| 233 | /* TRUE: we replaced a value */ |
| 234 | /* FALSE: we inserted a value */ |
| 235 | |
| 236 | static struct hash_entry * hash_ask(); |
| 237 | static int hash_code (); |
| 238 | static char * hash_grow(); |
| 239 | \f |
| 240 | /* |
| 241 | * h a s h _ n e w ( ) |
| 242 | * |
| 243 | */ |
| 244 | struct hash_control * |
| 245 | hash_new() /* create a new hash table */ |
| 246 | /* return NULL if failed */ |
| 247 | /* return handle (address of struct hash) */ |
| 248 | { |
| 249 | register struct hash_control * retval; |
| 250 | register struct hash_entry * room; /* points to hash table */ |
| 251 | register struct hash_entry * wall; |
| 252 | register struct hash_entry * entry; |
| 253 | char * malloc(); |
| 254 | register int * ip; /* scan stats block of struct hash_control */ |
| 255 | register int * nd; /* limit of stats block */ |
| 256 | |
| 257 | if ( room = (struct hash_entry *) malloc( sizeof(struct hash_entry)*((1<<START_POWER) + 1) ) ) |
| 258 | /* +1 for the wall entry */ |
| 259 | { |
| 260 | if ( retval = (struct hash_control *) malloc(sizeof(struct hash_control)) ) |
| 261 | { |
| 262 | nd = retval->hash_stat + STATLENGTH; |
| 263 | for (ip=retval->hash_stat; ip<nd; ip++) |
| 264 | { |
| 265 | *ip = 0; |
| 266 | } |
| 267 | |
| 268 | retval -> hash_stat[STAT_SIZE] = 1<<START_POWER; |
| 269 | retval -> hash_mask = (1<<START_POWER) - 1; |
| 270 | retval -> hash_sizelog = START_POWER; |
| 271 | /* works for 1's compl ok */ |
| 272 | retval -> hash_where = room; |
| 273 | retval -> hash_wall = |
| 274 | wall = room + (1<<START_POWER); |
| 275 | retval -> hash_full = (1<<START_POWER)/2; |
| 276 | for (entry=room; entry<=wall; entry++) |
| 277 | { |
| 278 | entry->hash_string = NULL; |
| 279 | } |
| 280 | } |
| 281 | } |
| 282 | else |
| 283 | { |
| 284 | retval = NULL; /* no room for table: fake a failure */ |
| 285 | } |
| 286 | return(retval); /* return NULL or set-up structs */ |
| 287 | } |
| 288 | |
| 289 | /* |
| 290 | * h a s h _ d i e ( ) |
| 291 | * |
| 292 | * Table should be empty, but this is not checked. |
| 293 | * To empty the table, try hash_apply()ing a symbol deleter. |
| 294 | * Return to free memory both the hash table and it's control |
| 295 | * block. |
| 296 | * 'handle' has no meaning after this function. |
| 297 | * No errors are recoverable. |
| 298 | */ |
| 299 | void |
| 300 | hash_die(handle) |
| 301 | struct hash_control * handle; |
| 302 | { |
| 303 | free((char *)handle->hash_where); |
| 304 | free((char *)handle); |
| 305 | } |
| 306 | \f |
| 307 | /* |
| 308 | * h a s h _ s a y ( ) |
| 309 | * |
| 310 | * Return the size of the statistics table, and as many statistics as |
| 311 | * we can until either (a) we have run out of statistics or (b) caller |
| 312 | * has run out of buffer. |
| 313 | * NOTE: hash_say treats all statistics alike. |
| 314 | * These numbers may change with time, due to insertions, deletions |
| 315 | * and expansions of the table. |
| 316 | * The first "statistic" returned is the length of hash_stat[]. |
| 317 | * Then contents of hash_stat[] are read out (in ascending order) |
| 318 | * until your buffer or hash_stat[] is exausted. |
| 319 | */ |
| 320 | void |
| 321 | hash_say(handle,buffer,bufsiz) |
| 322 | register struct hash_control * handle; |
| 323 | register int buffer[/*bufsiz*/]; |
| 324 | register int bufsiz; |
| 325 | { |
| 326 | register int * nd; /* limit of statistics block */ |
| 327 | register int * ip; /* scan statistics */ |
| 328 | |
| 329 | ip = handle -> hash_stat; |
| 330 | nd = ip + min(bufsiz-1,STATLENGTH); |
| 331 | if (bufsiz>0) /* trust nothing! bufsiz<=0 is dangerous */ |
| 332 | { |
| 333 | *buffer++ = STATLENGTH; |
| 334 | for (; ip<nd; ip++,buffer++) |
| 335 | { |
| 336 | *buffer = *ip; |
| 337 | } |
| 338 | } |
| 339 | } |
| 340 | \f |
| 341 | /* |
| 342 | * h a s h _ d e l e t e ( ) |
| 343 | * |
| 344 | * Try to delete a symbol from the table. |
| 345 | * If it was there, return its value (and adjust STAT_USED). |
| 346 | * Otherwise, return NULL. |
| 347 | * Anyway, the symbol is not present after this function. |
| 348 | * |
| 349 | */ |
| 350 | char * /* NULL if string not in table, else */ |
| 351 | /* returns value of deleted symbol */ |
| 352 | hash_delete(handle,string) |
| 353 | register struct hash_control * handle; |
| 354 | register char * string; |
| 355 | { |
| 356 | register char * retval; /* NULL if string not in table */ |
| 357 | register struct hash_entry * entry; /* NULL or entry of this symbol */ |
| 358 | |
| 359 | entry = hash_ask(handle,string,STAT__WRITE); |
| 360 | if (hash_found) |
| 361 | { |
| 362 | retval = entry -> hash_value; |
| 363 | entry -> hash_string = DELETED; /* mark as deleted */ |
| 364 | handle -> hash_stat[STAT_USED] -= 1; /* slots-in-use count */ |
| 365 | #ifdef SUSPECT |
| 366 | if (handle->hash_stat[STAT_USED]<0) |
| 367 | { |
| 368 | error("hash_delete"); |
| 369 | } |
| 370 | #endif /* def SUSPECT */ |
| 371 | } |
| 372 | else |
| 373 | { |
| 374 | retval = NULL; |
| 375 | } |
| 376 | return(retval); |
| 377 | } |
| 378 | \f |
| 379 | /* |
| 380 | * h a s h _ r e p l a c e ( ) |
| 381 | * |
| 382 | * Try to replace the old value of a symbol with a new value. |
| 383 | * Normally return the old value. |
| 384 | * Return NULL and don't change the table if the symbol is not already |
| 385 | * in the table. |
| 386 | */ |
| 387 | char * |
| 388 | hash_replace(handle,string,value) |
| 389 | register struct hash_control * handle; |
| 390 | register char * string; |
| 391 | register char * value; |
| 392 | { |
| 393 | register struct hash_entry * entry; |
| 394 | register char * retval; |
| 395 | |
| 396 | entry = hash_ask(handle,string,STAT__WRITE); |
| 397 | if (hash_found) |
| 398 | { |
| 399 | retval = entry -> hash_value; |
| 400 | entry -> hash_value = value; |
| 401 | } |
| 402 | else |
| 403 | { |
| 404 | retval = NULL; |
| 405 | } |
| 406 | ; |
| 407 | return (retval); |
| 408 | } |
| 409 | \f |
| 410 | /* |
| 411 | * h a s h _ i n s e r t ( ) |
| 412 | * |
| 413 | * Insert a (symbol-string, value) into the hash table. |
| 414 | * Return an error string, "" means OK. |
| 415 | * It is an 'error' to insert an existing symbol. |
| 416 | */ |
| 417 | |
| 418 | char * /* return error string */ |
| 419 | hash_insert(handle,string,value) |
| 420 | register struct hash_control * handle; |
| 421 | register char * string; |
| 422 | register char * value; |
| 423 | { |
| 424 | register struct hash_entry * entry; |
| 425 | register char * retval; |
| 426 | |
| 427 | retval = ""; |
| 428 | if (handle->hash_stat[STAT_USED] > handle->hash_full) |
| 429 | { |
| 430 | retval = hash_grow(handle); |
| 431 | } |
| 432 | if ( ! * retval) |
| 433 | { |
| 434 | entry = hash_ask(handle,string,STAT__WRITE); |
| 435 | if (hash_found) |
| 436 | { |
| 437 | retval = "exists"; |
| 438 | } |
| 439 | else |
| 440 | { |
| 441 | entry -> hash_value = value; |
| 442 | entry -> hash_string = string; |
| 443 | handle-> hash_stat[STAT_USED] += 1; |
| 444 | } |
| 445 | } |
| 446 | return(retval); |
| 447 | } |
| 448 | \f |
| 449 | /* |
| 450 | * h a s h _ j a m ( ) |
| 451 | * |
| 452 | * Regardless of what was in the symbol table before, after hash_jam() |
| 453 | * the named symbol has the given value. The symbol is either inserted or |
| 454 | * (its value is) relpaced. |
| 455 | * An error message string is returned, "" means OK. |
| 456 | * |
| 457 | * WARNING: this may decide to grow the hashed symbol table. |
| 458 | * To do this, we call hash_grow(), WHICH WILL recursively CALL US. |
| 459 | * |
| 460 | * We report status internally: hash_found is TRUE if we replaced, but |
| 461 | * false if we inserted. |
| 462 | */ |
| 463 | char * |
| 464 | hash_jam(handle,string,value) |
| 465 | register struct hash_control * handle; |
| 466 | register char * string; |
| 467 | register char * value; |
| 468 | { |
| 469 | register char * retval; |
| 470 | register struct hash_entry * entry; |
| 471 | |
| 472 | retval = ""; |
| 473 | if (handle->hash_stat[STAT_USED] > handle->hash_full) |
| 474 | { |
| 475 | retval = hash_grow(handle); |
| 476 | } |
| 477 | if (! * retval) |
| 478 | { |
| 479 | entry = hash_ask(handle,string,STAT__WRITE); |
| 480 | if ( ! hash_found) |
| 481 | { |
| 482 | entry -> hash_string = string; |
| 483 | handle->hash_stat[STAT_USED] += 1; |
| 484 | } |
| 485 | entry -> hash_value = value; |
| 486 | } |
| 487 | return(retval); |
| 488 | } |
| 489 | |
| 490 | /* |
| 491 | * h a s h _ g r o w ( ) |
| 492 | * |
| 493 | * Grow a new (bigger) hash table from the old one. |
| 494 | * We choose to double the hash table's size. |
| 495 | * Return a human-scrutible error string: "" if OK. |
| 496 | * Warning! This uses hash_jam(), which had better not recurse |
| 497 | * back here! Hash_jam() conditionally calls us, but we ALWAYS |
| 498 | * call hash_jam()! |
| 499 | * Internal. |
| 500 | */ |
| 501 | static char * |
| 502 | hash_grow(handle) /* make a hash table grow */ |
| 503 | struct hash_control * handle; |
| 504 | { |
| 505 | register struct hash_entry * newwall; |
| 506 | register struct hash_entry * newwhere; |
| 507 | struct hash_entry * newtrack; |
| 508 | register struct hash_entry * oldtrack; |
| 509 | register struct hash_entry * oldwhere; |
| 510 | register struct hash_entry * oldwall; |
| 511 | register int temp; |
| 512 | int newsize; |
| 513 | char * string; |
| 514 | char * retval; |
| 515 | #ifdef SUSPECT |
| 516 | int oldused; |
| 517 | #endif |
| 518 | |
| 519 | /* |
| 520 | * capture info about old hash table |
| 521 | */ |
| 522 | oldwhere = handle -> hash_where; |
| 523 | oldwall = handle -> hash_wall; |
| 524 | #ifdef SUSPECT |
| 525 | oldused = handle -> hash_stat[STAT_USED]; |
| 526 | #endif |
| 527 | /* |
| 528 | * attempt to get enough room for a hash table twice as big |
| 529 | */ |
| 530 | temp = handle->hash_stat[STAT_SIZE]; |
| 531 | if ( newwhere = (struct hash_entry *) xmalloc((long)((temp+temp+1)*sizeof(struct hash_entry)))) |
| 532 | /* +1 for wall slot */ |
| 533 | { |
| 534 | retval = ""; /* assume success until proven otherwise */ |
| 535 | /* |
| 536 | * have enough room: now we do all the work. |
| 537 | * double the size of everything in handle, |
| 538 | * note: hash_mask frob works for 1's & for 2's complement machines |
| 539 | */ |
| 540 | handle->hash_mask = handle->hash_mask + handle->hash_mask + 1; |
| 541 | handle->hash_stat[STAT_SIZE] <<= 1; |
| 542 | newsize = handle->hash_stat[STAT_SIZE]; |
| 543 | handle->hash_where = newwhere; |
| 544 | handle->hash_full <<= 1; |
| 545 | handle->hash_sizelog += 1; |
| 546 | handle->hash_stat[STAT_USED] = 0; |
| 547 | handle->hash_wall = |
| 548 | newwall = newwhere + newsize; |
| 549 | /* |
| 550 | * set all those pesky new slots to vacant. |
| 551 | */ |
| 552 | for (newtrack=newwhere; newtrack <= newwall; newtrack++) |
| 553 | { |
| 554 | newtrack -> hash_string = NULL; |
| 555 | } |
| 556 | /* |
| 557 | * we will do a scan of the old table, the hard way, using the |
| 558 | * new control block to re-insert the data into new hash table. |
| 559 | */ |
| 560 | handle -> hash_stat[STAT_USED] = 0; /* inserts will bump it up to correct */ |
| 561 | for (oldtrack=oldwhere; oldtrack < oldwall; oldtrack++) |
| 562 | { |
| 563 | if ( (string=oldtrack->hash_string) && string!=DELETED ) |
| 564 | { |
| 565 | if ( * (retval = hash_jam(handle,string,oldtrack->hash_value) ) ) |
| 566 | { |
| 567 | break; |
| 568 | } |
| 569 | } |
| 570 | } |
| 571 | #ifdef SUSPECT |
| 572 | if ( !*retval && handle->hash_stat[STAT_USED] != oldused) |
| 573 | { |
| 574 | retval = "hash_used"; |
| 575 | } |
| 576 | #endif |
| 577 | if (!*retval) |
| 578 | { |
| 579 | /* |
| 580 | * we have a completely faked up control block. |
| 581 | * return the old hash table. |
| 582 | */ |
| 583 | free((char *)oldwhere); |
| 584 | /* |
| 585 | * Here with success. retval is already "". |
| 586 | */ |
| 587 | } |
| 588 | } |
| 589 | else |
| 590 | { |
| 591 | retval = "no room"; |
| 592 | } |
| 593 | return(retval); |
| 594 | } |
| 595 | \f |
| 596 | /* |
| 597 | * h a s h _ a p p l y ( ) |
| 598 | * |
| 599 | * Use this to scan each entry in symbol table. |
| 600 | * For each symbol, this calls (applys) a nominated function supplying the |
| 601 | * symbol's value (and the symbol's name). |
| 602 | * The idea is you use this to destroy whatever is associted with |
| 603 | * any values in the table BEFORE you destroy the table with hash_die. |
| 604 | * Of course, you can use it for other jobs; whenever you need to |
| 605 | * visit all extant symbols in the table. |
| 606 | * |
| 607 | * We choose to have a call-you-back idea for two reasons: |
| 608 | * asthetic: it is a neater idea to use apply than an explicit loop |
| 609 | * sensible: if we ever had to grow the symbol table (due to insertions) |
| 610 | * then we would lose our place in the table when we re-hashed |
| 611 | * symbols into the new table in a different order. |
| 612 | * |
| 613 | * The order symbols are visited depends entirely on the hashing function. |
| 614 | * Whenever you insert a (symbol, value) you risk expanding the table. If |
| 615 | * you do expand the table, then the hashing function WILL change, so you |
| 616 | * MIGHT get a different order of symbols visited. In other words, if you |
| 617 | * want the same order of visiting symbols as the last time you used |
| 618 | * hash_apply() then you better not have done any hash_insert()s or |
| 619 | * hash_jam()s since the last time you used hash_apply(). |
| 620 | * |
| 621 | * In future we may use the value returned by your nominated function. |
| 622 | * One idea is to abort the scan if, after applying the function to a |
| 623 | * certain node, the function returns a certain code. |
| 624 | * To be safe, please make your functions of type char *. If you always |
| 625 | * return NULL, then the scan will complete, visiting every symbol in |
| 626 | * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet! |
| 627 | * Caveat Actor! |
| 628 | * |
| 629 | * The function you supply should be of the form: |
| 630 | * char * myfunct(string,value) |
| 631 | * char * string; |* the symbol's name *| |
| 632 | * char * value; |* the symbol's value *| |
| 633 | * { |
| 634 | * |* ... *| |
| 635 | * return(NULL); |
| 636 | * } |
| 637 | * |
| 638 | * The returned value of hash_apply() is (char*)NULL. In future it may return |
| 639 | * other values. NULL means "completed scan OK". Other values have no meaning |
| 640 | * yet. (The function has no graceful failures.) |
| 641 | */ |
| 642 | char * |
| 643 | hash_apply(handle,function) |
| 644 | struct hash_control * handle; |
| 645 | char* (*function)(); |
| 646 | { |
| 647 | register struct hash_entry * entry; |
| 648 | register struct hash_entry * wall; |
| 649 | |
| 650 | wall = handle->hash_wall; |
| 651 | for (entry = handle->hash_where; entry < wall; entry++) |
| 652 | { |
| 653 | if (islive(entry)) /* silly code: tests entry->string twice! */ |
| 654 | { |
| 655 | (*function)(entry->hash_string,entry->hash_value); |
| 656 | } |
| 657 | } |
| 658 | return (NULL); |
| 659 | } |
| 660 | \f |
| 661 | /* |
| 662 | * h a s h _ f i n d ( ) |
| 663 | * |
| 664 | * Given symbol string, find value (if any). |
| 665 | * Return found value or NULL. |
| 666 | */ |
| 667 | char * |
| 668 | hash_find(handle,string) /* return char* or NULL */ |
| 669 | struct hash_control * handle; |
| 670 | char * string; |
| 671 | { |
| 672 | register struct hash_entry * entry; |
| 673 | register char * retval; |
| 674 | |
| 675 | entry = hash_ask(handle,string,STAT__READ); |
| 676 | if (hash_found) |
| 677 | { |
| 678 | retval = entry->hash_value; |
| 679 | } |
| 680 | else |
| 681 | { |
| 682 | retval = NULL; |
| 683 | } |
| 684 | return(retval); |
| 685 | } |
| 686 | \f |
| 687 | /* |
| 688 | * h a s h _ a s k ( ) |
| 689 | * |
| 690 | * Searches for given symbol string. |
| 691 | * Return the slot where it OUGHT to live. It may be there. |
| 692 | * Return hash_found: TRUE only if symbol is in that slot. |
| 693 | * Access argument is to help keep statistics in control block. |
| 694 | * Internal. |
| 695 | */ |
| 696 | static struct hash_entry * /* string slot, may be empty or deleted */ |
| 697 | hash_ask(handle,string,access) |
| 698 | struct hash_control * handle; |
| 699 | char * string; |
| 700 | int access; /* access type */ |
| 701 | { |
| 702 | register char *string1; /* JF avoid strcmp calls */ |
| 703 | register char * s; |
| 704 | register int c; |
| 705 | register struct hash_entry * slot; |
| 706 | register int collision; /* count collisions */ |
| 707 | |
| 708 | slot = handle->hash_where + hash_code(handle,string); /* start looking here */ |
| 709 | handle->hash_stat[STAT_ACCESS+access] += 1; |
| 710 | collision = 0; |
| 711 | hash_found = FALSE; |
| 712 | while ( (s = slot->hash_string) && s!=DELETED ) |
| 713 | { |
| 714 | for(string1=string;;) { |
| 715 | if(!(c= *s++)) { |
| 716 | if(!*string1) |
| 717 | hash_found = TRUE; |
| 718 | break; |
| 719 | } |
| 720 | if(*string1++!=c) |
| 721 | break; |
| 722 | } |
| 723 | if(hash_found) |
| 724 | break; |
| 725 | collision++; |
| 726 | slot++; |
| 727 | } |
| 728 | /* |
| 729 | * slot: return: |
| 730 | * in use: we found string slot |
| 731 | * at empty: |
| 732 | * at wall: we fell off: wrap round ???? |
| 733 | * in table: dig here slot |
| 734 | * at DELETED: dig here slot |
| 735 | */ |
| 736 | if (slot==handle->hash_wall) |
| 737 | { |
| 738 | slot = handle->hash_where; /* now look again */ |
| 739 | while( (s = slot->hash_string) && s!=DELETED ) |
| 740 | { |
| 741 | for(string1=string;*s;string1++,s++) { |
| 742 | if(*string1!=*s) |
| 743 | break; |
| 744 | } |
| 745 | if(*s==*string1) { |
| 746 | hash_found = TRUE; |
| 747 | break; |
| 748 | } |
| 749 | collision++; |
| 750 | slot++; |
| 751 | } |
| 752 | /* |
| 753 | * slot: return: |
| 754 | * in use: we found it slot |
| 755 | * empty: wall: ERROR IMPOSSIBLE !!!! |
| 756 | * in table: dig here slot |
| 757 | * DELETED:dig here slot |
| 758 | */ |
| 759 | } |
| 760 | /* fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,string),collision); */ |
| 761 | handle -> hash_stat[STAT_COLLIDE+access] += collision; |
| 762 | return(slot); /* also return hash_found */ |
| 763 | } |
| 764 | \f |
| 765 | /* |
| 766 | * h a s h _ c o d e |
| 767 | * |
| 768 | * Does hashing of symbol string to hash number. |
| 769 | * Internal. |
| 770 | */ |
| 771 | static int |
| 772 | hash_code(handle,string) |
| 773 | struct hash_control * handle; |
| 774 | register char * string; |
| 775 | { |
| 776 | register long int h; /* hash code built here */ |
| 777 | register long int c; /* each character lands here */ |
| 778 | register int n; /* Amount to shift h by */ |
| 779 | |
| 780 | n = (handle->hash_sizelog - 3); |
| 781 | h = 0; |
| 782 | while (c = *string++) |
| 783 | { |
| 784 | h += c; |
| 785 | h = (h<<3) + (h>>n) + c; |
| 786 | } |
| 787 | return (h & handle->hash_mask); |
| 788 | } |
| 789 | \f |
| 790 | /* |
| 791 | * Here is a test program to exercise above. |
| 792 | */ |
| 793 | #ifdef TEST |
| 794 | |
| 795 | #define TABLES (6) /* number of hash tables to maintain */ |
| 796 | /* (at once) in any testing */ |
| 797 | #define STATBUFSIZE (12) /* we can have 12 statistics */ |
| 798 | |
| 799 | int statbuf[STATBUFSIZE]; /* display statistics here */ |
| 800 | char answer[100]; /* human farts here */ |
| 801 | char * hashtable[TABLES]; /* we test many hash tables at once */ |
| 802 | char * h; /* points to curent hash_control */ |
| 803 | char ** pp; |
| 804 | char * p; |
| 805 | char * name; |
| 806 | char * value; |
| 807 | int size; |
| 808 | int used; |
| 809 | char command; |
| 810 | int number; /* number 0:TABLES-1 of current hashed */ |
| 811 | /* symbol table */ |
| 812 | |
| 813 | main() |
| 814 | { |
| 815 | char (*applicatee()); |
| 816 | char * hash_find(); |
| 817 | char * destroy(); |
| 818 | char * what(); |
| 819 | struct hash_control * hash_new(); |
| 820 | char * hash_replace(); |
| 821 | int * ip; |
| 822 | |
| 823 | number = 0; |
| 824 | h = 0; |
| 825 | printf("type h <RETURN> for help\n"); |
| 826 | for(;;) |
| 827 | { |
| 828 | printf("hash_test command: "); |
| 829 | gets(answer); |
| 830 | command = answer[0]; |
| 831 | if (isupper(command)) command = tolower(command); /* ecch! */ |
| 832 | switch (command) |
| 833 | { |
| 834 | case '#': |
| 835 | printf("old hash table #=%d.\n",number); |
| 836 | whattable(); |
| 837 | break; |
| 838 | case '?': |
| 839 | for (pp=hashtable; pp<hashtable+TABLES; pp++) |
| 840 | { |
| 841 | printf("address of hash table #%d control block is %xx\n" |
| 842 | ,pp-hashtable,*pp); |
| 843 | } |
| 844 | break; |
| 845 | case 'a': |
| 846 | hash_apply(h,applicatee); |
| 847 | break; |
| 848 | case 'd': |
| 849 | hash_apply(h,destroy); |
| 850 | hash_die(h); |
| 851 | break; |
| 852 | case 'f': |
| 853 | p = hash_find(h,name=what("symbol")); |
| 854 | printf("value of \"%s\" is \"%s\"\n",name,p?p:"NOT-PRESENT"); |
| 855 | break; |
| 856 | case 'h': |
| 857 | printf("# show old, select new default hash table number\n"); |
| 858 | printf("? display all hashtable control block addresses\n"); |
| 859 | printf("a apply a simple display-er to each symbol in table\n"); |
| 860 | printf("d die: destroy hashtable\n"); |
| 861 | printf("f find value of nominated symbol\n"); |
| 862 | printf("h this help\n"); |
| 863 | printf("i insert value into symbol\n"); |
| 864 | printf("j jam value into symbol\n"); |
| 865 | printf("n new hashtable\n"); |
| 866 | printf("r replace a value with another\n"); |
| 867 | printf("s say what %% of table is used\n"); |
| 868 | printf("q exit this program\n"); |
| 869 | printf("x delete a symbol from table, report its value\n"); |
| 870 | break; |
| 871 | case 'i': |
| 872 | p = hash_insert(h,name=what("symbol"),value=what("value")); |
| 873 | if (*p) |
| 874 | { |
| 875 | printf("symbol=\"%s\" value=\"%s\" error=%s\n",name,value,p); |
| 876 | } |
| 877 | break; |
| 878 | case 'j': |
| 879 | p = hash_jam(h,name=what("symbol"),value=what("value")); |
| 880 | if (*p) |
| 881 | { |
| 882 | printf("symbol=\"%s\" value=\"%s\" error=%s\n",name,value,p); |
| 883 | } |
| 884 | break; |
| 885 | case 'n': |
| 886 | h = hashtable[number] = (char *) hash_new(); |
| 887 | break; |
| 888 | case 'q': |
| 889 | exit(); |
| 890 | case 'r': |
| 891 | p = hash_replace(h,name=what("symbol"),value=what("value")); |
| 892 | printf("old value was \"%s\"\n",p?p:"{}"); |
| 893 | break; |
| 894 | case 's': |
| 895 | hash_say(h,statbuf,STATBUFSIZE); |
| 896 | for (ip=statbuf; ip<statbuf+STATBUFSIZE; ip++) |
| 897 | { |
| 898 | printf("%d ",*ip); |
| 899 | } |
| 900 | printf("\n"); |
| 901 | break; |
| 902 | case 'x': |
| 903 | p = hash_delete(h,name=what("symbol")); |
| 904 | printf("old value was \"%s\"\n",p?p:"{}"); |
| 905 | break; |
| 906 | default: |
| 907 | printf("I can't understand command \"%c\"\n",command); |
| 908 | break; |
| 909 | } |
| 910 | } |
| 911 | } |
| 912 | |
| 913 | char * |
| 914 | what(description) |
| 915 | char * description; |
| 916 | { |
| 917 | char * retval; |
| 918 | char * malloc(); |
| 919 | |
| 920 | printf(" %s : ",description); |
| 921 | gets(answer); |
| 922 | /* will one day clean up answer here */ |
| 923 | retval = malloc(strlen(answer)+1); |
| 924 | if (!retval) |
| 925 | { |
| 926 | error("room"); |
| 927 | } |
| 928 | (void)strcpy(retval,answer); |
| 929 | return(retval); |
| 930 | } |
| 931 | |
| 932 | char * |
| 933 | destroy(string,value) |
| 934 | char * string; |
| 935 | char * value; |
| 936 | { |
| 937 | free(string); |
| 938 | free(value); |
| 939 | return(NULL); |
| 940 | } |
| 941 | |
| 942 | |
| 943 | char * |
| 944 | applicatee(string,value) |
| 945 | char * string; |
| 946 | char * value; |
| 947 | { |
| 948 | printf("%.20s-%.20s\n",string,value); |
| 949 | return(NULL); |
| 950 | } |
| 951 | |
| 952 | whattable() /* determine number: what hash table to use */ |
| 953 | /* also determine h: points to hash_control */ |
| 954 | { |
| 955 | |
| 956 | for (;;) |
| 957 | { |
| 958 | printf(" what hash table (%d:%d) ? ",0,TABLES-1); |
| 959 | gets(answer); |
| 960 | sscanf(answer,"%d",&number); |
| 961 | if (number>=0 && number<TABLES) |
| 962 | { |
| 963 | h = hashtable[number]; |
| 964 | if (!h) |
| 965 | { |
| 966 | printf("warning: current hash-table-#%d. has no hash-control\n",number); |
| 967 | } |
| 968 | return; |
| 969 | } |
| 970 | else |
| 971 | { |
| 972 | printf("invalid hash table number: %d\n",number); |
| 973 | } |
| 974 | } |
| 975 | } |
| 976 | |
| 977 | |
| 978 | |
| 979 | #endif /* #ifdef TEST */ |
| 980 | |
| 981 | /* end: hash.c */ |