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