12159047fSniklas /* hash.c - hash table lookup strings - 22159047fSniklas Copyright (C) 1987, 1990, 1991, 1992 Free Software Foundation, Inc. 32159047fSniklas 42159047fSniklas This file is part of GAS, the GNU Assembler. 52159047fSniklas 62159047fSniklas GAS is free software; you can redistribute it and/or modify 72159047fSniklas it under the terms of the GNU General Public License as published by 82159047fSniklas the Free Software Foundation; either version 2, or (at your option) 92159047fSniklas any later version. 102159047fSniklas 112159047fSniklas GAS is distributed in the hope that it will be useful, 122159047fSniklas but WITHOUT ANY WARRANTY; without even the implied warranty of 132159047fSniklas MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 142159047fSniklas GNU General Public License for more details. 152159047fSniklas 162159047fSniklas You should have received a copy of the GNU General Public License 172159047fSniklas along with GAS; see the file COPYING. If not, write to 182159047fSniklas the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 192159047fSniklas 202159047fSniklas /* 212159047fSniklas * BUGS, GRIPES, APOLOGIA etc. 222159047fSniklas * 232159047fSniklas * A typical user doesn't need ALL this: I intend to make a library out 242159047fSniklas * of it one day - Dean Elsner. 252159047fSniklas * Also, I want to change the definition of a symbol to (address,length) 262159047fSniklas * so I can put arbitrary binary in the names stored. [see hsh.c for that] 272159047fSniklas * 282159047fSniklas * This slime is common coupled inside the module. Com-coupling (and other 292159047fSniklas * vandalism) was done to speed running time. The interfaces at the 302159047fSniklas * module's edges are adequately clean. 312159047fSniklas * 322159047fSniklas * There is no way to (a) run a test script through this heap and (b) 332159047fSniklas * compare results with previous scripts, to see if we have broken any 342159047fSniklas * code. Use GNU (f)utilities to do this. A few commands assist test. 352159047fSniklas * The testing is awkward: it tries to be both batch & interactive. 362159047fSniklas * For now, interactive rules! 372159047fSniklas */ 382159047fSniklas 392159047fSniklas /* 402159047fSniklas * The idea is to implement a symbol table. A test jig is here. 412159047fSniklas * Symbols are arbitrary strings; they can't contain '\0'. 422159047fSniklas * [See hsh.c for a more general symbol flavour.] 432159047fSniklas * Each symbol is associated with a char*, which can point to anything 442159047fSniklas * you want, allowing an arbitrary property list for each symbol. 452159047fSniklas * 462159047fSniklas * The basic operations are: 472159047fSniklas * 482159047fSniklas * new creates symbol table, returns handle 492159047fSniklas * find (symbol) returns char* 502159047fSniklas * insert (symbol,char*) error if symbol already in table 512159047fSniklas * delete (symbol) returns char* if symbol was in table 522159047fSniklas * apply so you can delete all symbols before die() 532159047fSniklas * die destroy symbol table (free up memory) 542159047fSniklas * 552159047fSniklas * Supplementary functions include: 562159047fSniklas * 572159047fSniklas * say how big? what % full? 582159047fSniklas * replace (symbol,newval) report previous value 592159047fSniklas * jam (symbol,value) assert symbol:=value 602159047fSniklas * 612159047fSniklas * You, the caller, have control over errors: this just reports them. 622159047fSniklas * 632159047fSniklas * This package requires malloc(), free(). 642159047fSniklas * Malloc(size) returns NULL or address of char[size]. 652159047fSniklas * Free(address) frees same. 662159047fSniklas */ 672159047fSniklas 682159047fSniklas /* 692159047fSniklas * The code and its structures are re-enterent. 702159047fSniklas * 712159047fSniklas * Before you do anything else, you must call hash_new() which will 722159047fSniklas * return the address of a hash-table-control-block. You then use 732159047fSniklas * this address as a handle of the symbol table by passing it to all 742159047fSniklas * the other hash_...() functions. The only approved way to recover 752159047fSniklas * the memory used by the symbol table is to call hash_die() with the 762159047fSniklas * handle of the symbol table. 772159047fSniklas * 782159047fSniklas * Before you call hash_die() you normally delete anything pointed to 792159047fSniklas * by individual symbols. After hash_die() you can't use that symbol 802159047fSniklas * table again. 812159047fSniklas * 822159047fSniklas * The char* you associate with a symbol may not be NULL (0) because 832159047fSniklas * NULL is returned whenever a symbol is not in the table. Any other 842159047fSniklas * value is OK, except DELETED, #defined below. 852159047fSniklas * 862159047fSniklas * When you supply a symbol string for insertion, YOU MUST PRESERVE THE 872159047fSniklas * STRING until that symbol is deleted from the table. The reason is that 882159047fSniklas * only the address you supply, NOT the symbol string itself, is stored 892159047fSniklas * in the symbol table. 902159047fSniklas * 912159047fSniklas * You may delete and add symbols arbitrarily. 922159047fSniklas * Any or all symbols may have the same 'value' (char *). In fact, these 932159047fSniklas * routines don't do anything with your symbol values. 942159047fSniklas * 952159047fSniklas * You have no right to know where the symbol:char* mapping is stored, 962159047fSniklas * because it moves around in memory; also because we may change how it 972159047fSniklas * works and we don't want to break your code do we? However the handle 982159047fSniklas * (address of struct hash_control) is never changed in 992159047fSniklas * the life of the symbol table. 1002159047fSniklas * 1012159047fSniklas * What you CAN find out about a symbol table is: 1022159047fSniklas * how many slots are in the hash table? 1032159047fSniklas * how many slots are filled with symbols? 1042159047fSniklas * (total hashes,collisions) for (reads,writes) (*) 1052159047fSniklas * All of the above values vary in time. 1062159047fSniklas * (*) some of these numbers will not be meaningful if we change the 1072159047fSniklas * internals. */ 1082159047fSniklas 1092159047fSniklas /* 1102159047fSniklas * I N T E R N A L 1112159047fSniklas * 1122159047fSniklas * Hash table is an array of hash_entries; each entry is a pointer to a 1132159047fSniklas * a string and a user-supplied value 1 char* wide. 1142159047fSniklas * 1152159047fSniklas * The array always has 2 ** n elements, n>0, n integer. 1162159047fSniklas * There is also a 'wall' entry after the array, which is always empty 1172159047fSniklas * and acts as a sentinel to stop running off the end of the array. 1182159047fSniklas * When the array gets too full, we create a new array twice as large 1192159047fSniklas * and re-hash the symbols into the new array, then forget the old array. 1202159047fSniklas * (Of course, we copy the values into the new array before we junk the 1212159047fSniklas * old array!) 1222159047fSniklas * 1232159047fSniklas */ 1242159047fSniklas 1252159047fSniklas #include <stdio.h> 1262159047fSniklas 1272159047fSniklas #ifndef FALSE 1282159047fSniklas #define FALSE (0) 1292159047fSniklas #define TRUE (!FALSE) 1302159047fSniklas #endif /* no FALSE yet */ 1312159047fSniklas 1322159047fSniklas #include <ctype.h> 1332159047fSniklas #define min(a, b) ((a) < (b) ? (a) : (b)) 1342159047fSniklas 1352159047fSniklas #include "as.h" 1362159047fSniklas 1372159047fSniklas #define error as_fatal 1382159047fSniklas 139*191aa565Sniklas static char _deleted_[1]; 140*191aa565Sniklas #define DELETED ((PTR)_deleted_) /* guarenteed unique address */ 141*191aa565Sniklas #define START_POWER (10) /* power of two: size of new hash table */ 1422159047fSniklas 1432159047fSniklas /* TRUE if a symbol is in entry @ ptr. */ 1442159047fSniklas #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED) 1452159047fSniklas 146*191aa565Sniklas enum stat_enum { 1472159047fSniklas /* Number of slots in hash table. The wall does not count here. 1482159047fSniklas We expect this is always a power of 2. */ 149*191aa565Sniklas STAT_SIZE = 0, 150*191aa565Sniklas /* Number of hash_ask calls. */ 151*191aa565Sniklas STAT_ACCESS, 152*191aa565Sniklas STAT_ACCESS_w, 1532159047fSniklas /* Number of collisions (total). This may exceed STAT_ACCESS if we 1542159047fSniklas have lots of collisions/access. */ 155*191aa565Sniklas STAT_COLLIDE, 156*191aa565Sniklas STAT_COLLIDE_w, 157*191aa565Sniklas /* Slots used right now. */ 158*191aa565Sniklas STAT_USED, 159*191aa565Sniklas /* How many string compares? */ 160*191aa565Sniklas STAT_STRCMP, 161*191aa565Sniklas STAT_STRCMP_w, 162*191aa565Sniklas /* Size of statistics block... this must be last. */ 163*191aa565Sniklas STATLENGTH 164*191aa565Sniklas }; 165*191aa565Sniklas #define STAT__READ (0) /* reading */ 166*191aa565Sniklas #define STAT__WRITE (1) /* writing */ 167*191aa565Sniklas 168*191aa565Sniklas /* When we grow a hash table, by what power of two do we increase it? */ 169*191aa565Sniklas #define GROW_FACTOR 1 170*191aa565Sniklas /* When should we grow it? */ 171*191aa565Sniklas #define FULL_VALUE(N) ((N) / 2) 1722159047fSniklas 1732159047fSniklas /* #define SUSPECT to do runtime checks */ 1742159047fSniklas /* #define TEST to be a test jig for hash...() */ 1752159047fSniklas 1762159047fSniklas #ifdef TEST 1772159047fSniklas /* TEST: use smaller hash table */ 1782159047fSniklas #undef START_POWER 1792159047fSniklas #define START_POWER (3) 1802159047fSniklas #undef START_SIZE 1812159047fSniklas #define START_SIZE (8) 1822159047fSniklas #undef START_FULL 1832159047fSniklas #define START_FULL (4) 1842159047fSniklas #endif 1852159047fSniklas 186*191aa565Sniklas struct hash_entry 187*191aa565Sniklas { 188*191aa565Sniklas const char *hash_string; /* points to where the symbol string is */ 189*191aa565Sniklas /* NULL means slot is not used */ 190*191aa565Sniklas /* DELETED means slot was deleted */ 191*191aa565Sniklas PTR hash_value; /* user's datum, associated with symbol */ 192*191aa565Sniklas unsigned long h; 193*191aa565Sniklas }; 194*191aa565Sniklas 195*191aa565Sniklas struct hash_control { 196*191aa565Sniklas struct hash_entry *hash_where;/* address of hash table */ 197*191aa565Sniklas int hash_sizelog; /* Log of ( hash_mask + 1 ) */ 198*191aa565Sniklas int hash_mask; /* masks a hash into index into table */ 199*191aa565Sniklas int hash_full; /* when hash_stat[STAT_USED] exceeds this, */ 200*191aa565Sniklas /* grow table */ 201*191aa565Sniklas struct hash_entry *hash_wall; /* point just after last (usable) entry */ 202*191aa565Sniklas /* here we have some statistics */ 203*191aa565Sniklas int hash_stat[STATLENGTH]; /* lies & statistics */ 204*191aa565Sniklas }; 205*191aa565Sniklas 2062159047fSniklas /*------------------ plan ---------------------------------- i = internal 2072159047fSniklas 2082159047fSniklas struct hash_control * c; 2092159047fSniklas struct hash_entry * e; i 2102159047fSniklas int b[z]; buffer for statistics 2112159047fSniklas z size of b 2122159047fSniklas char * s; symbol string (address) [ key ] 2132159047fSniklas char * v; value string (address) [datum] 2142159047fSniklas boolean f; TRUE if we found s in hash table i 2152159047fSniklas char * t; error string; 0 means OK 2162159047fSniklas int a; access type [0...n) i 2172159047fSniklas 2182159047fSniklas c=hash_new () create new hash_control 2192159047fSniklas 2202159047fSniklas hash_die (c) destroy hash_control (and hash table) 2212159047fSniklas table should be empty. 2222159047fSniklas doesn't check if table is empty. 2232159047fSniklas c has no meaning after this. 2242159047fSniklas 2252159047fSniklas hash_say (c,b,z) report statistics of hash_control. 2262159047fSniklas also report number of available statistics. 2272159047fSniklas 2282159047fSniklas v=hash_delete (c,s) delete symbol, return old value if any. 2292159047fSniklas ask() NULL means no old value. 2302159047fSniklas f 2312159047fSniklas 2322159047fSniklas v=hash_replace (c,s,v) replace old value of s with v. 2332159047fSniklas ask() NULL means no old value: no table change. 2342159047fSniklas f 2352159047fSniklas 2362159047fSniklas t=hash_insert (c,s,v) insert (s,v) in c. 2372159047fSniklas ask() return error string. 2382159047fSniklas f it is an error to insert if s is already 2392159047fSniklas in table. 2402159047fSniklas if any error, c is unchanged. 2412159047fSniklas 2422159047fSniklas t=hash_jam (c,s,v) assert that new value of s will be v. i 2432159047fSniklas ask() it may decide to GROW the table. i 2442159047fSniklas f i 2452159047fSniklas grow() i 2462159047fSniklas t=hash_grow (c) grow the hash table. i 2472159047fSniklas jam() will invoke JAM. i 2482159047fSniklas 2492159047fSniklas ?=hash_apply (c,y) apply y() to every symbol in c. 2502159047fSniklas y evtries visited in 'unspecified' order. 2512159047fSniklas 2522159047fSniklas v=hash_find (c,s) return value of s, or NULL if s not in c. 2532159047fSniklas ask() 2542159047fSniklas f 2552159047fSniklas 2562159047fSniklas f,e=hash_ask() (c,s,a) return slot where s SHOULD live. i 2572159047fSniklas code() maintain collision stats in c. i 2582159047fSniklas 2592159047fSniklas .=hash_code (c,s) compute hash-code for s, i 2602159047fSniklas from parameters of c. i 2612159047fSniklas 2622159047fSniklas */ 2632159047fSniklas 2642159047fSniklas /* Returned by hash_ask() to stop extra testing. hash_ask() wants to 2652159047fSniklas return both a slot and a status. This is the status. TRUE: found 2662159047fSniklas symbol FALSE: absent: empty or deleted slot Also returned by 2672159047fSniklas hash_jam(). TRUE: we replaced a value FALSE: we inserted a value. */ 2682159047fSniklas static char hash_found; 2692159047fSniklas 2702159047fSniklas static struct hash_entry *hash_ask PARAMS ((struct hash_control *, 2712159047fSniklas const char *, int)); 2722159047fSniklas static int hash_code PARAMS ((struct hash_control *, const char *)); 2732159047fSniklas static const char *hash_grow PARAMS ((struct hash_control *)); 2742159047fSniklas 2752159047fSniklas /* Create a new hash table. Return NULL if failed; otherwise return handle 2762159047fSniklas (address of struct hash). */ 2772159047fSniklas struct hash_control * 2782159047fSniklas hash_new () 2792159047fSniklas { 2802159047fSniklas struct hash_control *retval; 2812159047fSniklas struct hash_entry *room; /* points to hash table */ 2822159047fSniklas struct hash_entry *wall; 2832159047fSniklas struct hash_entry *entry; 2842159047fSniklas int *ip; /* scan stats block of struct hash_control */ 2852159047fSniklas int *nd; /* limit of stats block */ 2862159047fSniklas 2872159047fSniklas room = (struct hash_entry *) xmalloc (sizeof (struct hash_entry) 2882159047fSniklas /* +1 for the wall entry */ 2892159047fSniklas * ((1 << START_POWER) + 1)); 2902159047fSniklas retval = (struct hash_control *) xmalloc (sizeof (struct hash_control)); 2912159047fSniklas 2922159047fSniklas nd = retval->hash_stat + STATLENGTH; 2932159047fSniklas for (ip = retval->hash_stat; ip < nd; ip++) 2942159047fSniklas *ip = 0; 2952159047fSniklas 2962159047fSniklas retval->hash_stat[STAT_SIZE] = 1 << START_POWER; 2972159047fSniklas retval->hash_mask = (1 << START_POWER) - 1; 2982159047fSniklas retval->hash_sizelog = START_POWER; 2992159047fSniklas /* works for 1's compl ok */ 3002159047fSniklas retval->hash_where = room; 3012159047fSniklas retval->hash_wall = 3022159047fSniklas wall = room + (1 << START_POWER); 303*191aa565Sniklas retval->hash_full = FULL_VALUE (1 << START_POWER); 3042159047fSniklas for (entry = room; entry <= wall; entry++) 3052159047fSniklas entry->hash_string = NULL; 3062159047fSniklas return retval; 3072159047fSniklas } 3082159047fSniklas 3092159047fSniklas /* 3102159047fSniklas * h a s h _ d i e ( ) 3112159047fSniklas * 3122159047fSniklas * Table should be empty, but this is not checked. 3132159047fSniklas * To empty the table, try hash_apply()ing a symbol deleter. 3142159047fSniklas * Return to free memory both the hash table and it's control 3152159047fSniklas * block. 3162159047fSniklas * 'handle' has no meaning after this function. 3172159047fSniklas * No errors are recoverable. 3182159047fSniklas */ 3192159047fSniklas void 3202159047fSniklas hash_die (handle) 3212159047fSniklas struct hash_control *handle; 3222159047fSniklas { 3232159047fSniklas free ((char *) handle->hash_where); 3242159047fSniklas free ((char *) handle); 3252159047fSniklas } 3262159047fSniklas 327*191aa565Sniklas #ifdef TEST 3282159047fSniklas /* 3292159047fSniklas * h a s h _ s a y ( ) 3302159047fSniklas * 3312159047fSniklas * Return the size of the statistics table, and as many statistics as 3322159047fSniklas * we can until either (a) we have run out of statistics or (b) caller 3332159047fSniklas * has run out of buffer. 3342159047fSniklas * NOTE: hash_say treats all statistics alike. 3352159047fSniklas * These numbers may change with time, due to insertions, deletions 3362159047fSniklas * and expansions of the table. 3372159047fSniklas * The first "statistic" returned is the length of hash_stat[]. 3382159047fSniklas * Then contents of hash_stat[] are read out (in ascending order) 3392159047fSniklas * until your buffer or hash_stat[] is exausted. 3402159047fSniklas */ 341*191aa565Sniklas static void 3422159047fSniklas hash_say (handle, buffer, bufsiz) 3432159047fSniklas struct hash_control *handle; 3442159047fSniklas int buffer[ /*bufsiz*/ ]; 3452159047fSniklas int bufsiz; 3462159047fSniklas { 3472159047fSniklas int *nd; /* limit of statistics block */ 3482159047fSniklas int *ip; /* scan statistics */ 3492159047fSniklas 3502159047fSniklas ip = handle->hash_stat; 3512159047fSniklas nd = ip + min (bufsiz - 1, STATLENGTH); 3522159047fSniklas if (bufsiz > 0) /* trust nothing! bufsiz<=0 is dangerous */ 3532159047fSniklas { 3542159047fSniklas *buffer++ = STATLENGTH; 3552159047fSniklas for (; ip < nd; ip++, buffer++) 3562159047fSniklas { 3572159047fSniklas *buffer = *ip; 3582159047fSniklas } 3592159047fSniklas } 3602159047fSniklas } 361*191aa565Sniklas #endif 3622159047fSniklas 3632159047fSniklas /* 3642159047fSniklas * h a s h _ d e l e t e ( ) 3652159047fSniklas * 3662159047fSniklas * Try to delete a symbol from the table. 3672159047fSniklas * If it was there, return its value (and adjust STAT_USED). 3682159047fSniklas * Otherwise, return NULL. 3692159047fSniklas * Anyway, the symbol is not present after this function. 3702159047fSniklas * 3712159047fSniklas */ 3722159047fSniklas PTR /* NULL if string not in table, else */ 3732159047fSniklas /* returns value of deleted symbol */ 3742159047fSniklas hash_delete (handle, string) 3752159047fSniklas struct hash_control *handle; 3762159047fSniklas const char *string; 3772159047fSniklas { 3782159047fSniklas PTR retval; 3792159047fSniklas struct hash_entry *entry; 3802159047fSniklas 3812159047fSniklas entry = hash_ask (handle, string, STAT__WRITE); 3822159047fSniklas if (hash_found) 3832159047fSniklas { 3842159047fSniklas retval = entry->hash_value; 3852159047fSniklas entry->hash_string = DELETED; 3862159047fSniklas handle->hash_stat[STAT_USED] -= 1; 3872159047fSniklas #ifdef SUSPECT 3882159047fSniklas if (handle->hash_stat[STAT_USED] < 0) 3892159047fSniklas { 3902159047fSniklas error ("hash_delete"); 3912159047fSniklas } 3922159047fSniklas #endif /* def SUSPECT */ 3932159047fSniklas } 3942159047fSniklas else 3952159047fSniklas { 3962159047fSniklas retval = NULL; 3972159047fSniklas } 3982159047fSniklas return (retval); 3992159047fSniklas } 4002159047fSniklas 4012159047fSniklas /* 4022159047fSniklas * h a s h _ r e p l a c e ( ) 4032159047fSniklas * 4042159047fSniklas * Try to replace the old value of a symbol with a new value. 4052159047fSniklas * Normally return the old value. 4062159047fSniklas * Return NULL and don't change the table if the symbol is not already 4072159047fSniklas * in the table. 4082159047fSniklas */ 4092159047fSniklas PTR 4102159047fSniklas hash_replace (handle, string, value) 4112159047fSniklas struct hash_control *handle; 4122159047fSniklas const char *string; 4132159047fSniklas PTR value; 4142159047fSniklas { 4152159047fSniklas struct hash_entry *entry; 4162159047fSniklas char *retval; 4172159047fSniklas 4182159047fSniklas entry = hash_ask (handle, string, STAT__WRITE); 4192159047fSniklas if (hash_found) 4202159047fSniklas { 4212159047fSniklas retval = entry->hash_value; 4222159047fSniklas entry->hash_value = value; 4232159047fSniklas } 4242159047fSniklas else 4252159047fSniklas { 4262159047fSniklas retval = NULL; 4272159047fSniklas } 4282159047fSniklas ; 4292159047fSniklas return retval; 4302159047fSniklas } 4312159047fSniklas 4322159047fSniklas /* 4332159047fSniklas * h a s h _ i n s e r t ( ) 4342159047fSniklas * 4352159047fSniklas * Insert a (symbol-string, value) into the hash table. 4362159047fSniklas * Return an error string, 0 means OK. 4372159047fSniklas * It is an 'error' to insert an existing symbol. 4382159047fSniklas */ 4392159047fSniklas 4402159047fSniklas const char * /* return error string */ 4412159047fSniklas hash_insert (handle, string, value) 4422159047fSniklas struct hash_control *handle; 4432159047fSniklas const char *string; 4442159047fSniklas PTR value; 4452159047fSniklas { 4462159047fSniklas struct hash_entry *entry; 4472159047fSniklas const char *retval; 4482159047fSniklas 4492159047fSniklas retval = 0; 4502159047fSniklas if (handle->hash_stat[STAT_USED] > handle->hash_full) 4512159047fSniklas { 4522159047fSniklas retval = hash_grow (handle); 4532159047fSniklas } 4542159047fSniklas if (!retval) 4552159047fSniklas { 4562159047fSniklas entry = hash_ask (handle, string, STAT__WRITE); 4572159047fSniklas if (hash_found) 4582159047fSniklas { 4592159047fSniklas retval = "exists"; 4602159047fSniklas } 4612159047fSniklas else 4622159047fSniklas { 4632159047fSniklas entry->hash_value = value; 4642159047fSniklas entry->hash_string = string; 4652159047fSniklas handle->hash_stat[STAT_USED] += 1; 4662159047fSniklas } 4672159047fSniklas } 4682159047fSniklas return retval; 4692159047fSniklas } 4702159047fSniklas 4712159047fSniklas /* 4722159047fSniklas * h a s h _ j a m ( ) 4732159047fSniklas * 4742159047fSniklas * Regardless of what was in the symbol table before, after hash_jam() 4752159047fSniklas * the named symbol has the given value. The symbol is either inserted or 476*191aa565Sniklas * (its value is) replaced. 4772159047fSniklas * An error message string is returned, 0 means OK. 4782159047fSniklas * 4792159047fSniklas * WARNING: this may decide to grow the hashed symbol table. 4802159047fSniklas * To do this, we call hash_grow(), WHICH WILL recursively CALL US. 4812159047fSniklas * 4822159047fSniklas * We report status internally: hash_found is TRUE if we replaced, but 4832159047fSniklas * false if we inserted. 4842159047fSniklas */ 4852159047fSniklas const char * 4862159047fSniklas hash_jam (handle, string, value) 4872159047fSniklas struct hash_control *handle; 4882159047fSniklas const char *string; 4892159047fSniklas PTR value; 4902159047fSniklas { 4912159047fSniklas const char *retval; 4922159047fSniklas struct hash_entry *entry; 4932159047fSniklas 4942159047fSniklas retval = 0; 4952159047fSniklas if (handle->hash_stat[STAT_USED] > handle->hash_full) 4962159047fSniklas { 4972159047fSniklas retval = hash_grow (handle); 4982159047fSniklas } 4992159047fSniklas if (!retval) 5002159047fSniklas { 5012159047fSniklas entry = hash_ask (handle, string, STAT__WRITE); 5022159047fSniklas if (!hash_found) 5032159047fSniklas { 5042159047fSniklas entry->hash_string = string; 5052159047fSniklas handle->hash_stat[STAT_USED] += 1; 5062159047fSniklas } 5072159047fSniklas entry->hash_value = value; 5082159047fSniklas } 5092159047fSniklas return retval; 5102159047fSniklas } 5112159047fSniklas 5122159047fSniklas /* 5132159047fSniklas * h a s h _ g r o w ( ) 5142159047fSniklas * 5152159047fSniklas * Grow a new (bigger) hash table from the old one. 5162159047fSniklas * We choose to double the hash table's size. 5172159047fSniklas * Return a human-scrutible error string: 0 if OK. 5182159047fSniklas * Warning! This uses hash_jam(), which had better not recurse 5192159047fSniklas * back here! Hash_jam() conditionally calls us, but we ALWAYS 5202159047fSniklas * call hash_jam()! 5212159047fSniklas * Internal. 5222159047fSniklas */ 5232159047fSniklas static const char * 5242159047fSniklas hash_grow (handle) /* make a hash table grow */ 5252159047fSniklas struct hash_control *handle; 5262159047fSniklas { 5272159047fSniklas struct hash_entry *newwall; 5282159047fSniklas struct hash_entry *newwhere; 5292159047fSniklas struct hash_entry *newtrack; 5302159047fSniklas struct hash_entry *oldtrack; 5312159047fSniklas struct hash_entry *oldwhere; 5322159047fSniklas struct hash_entry *oldwall; 5332159047fSniklas int temp; 5342159047fSniklas int newsize; 5352159047fSniklas const char *string; 5362159047fSniklas const char *retval; 5372159047fSniklas #ifdef SUSPECT 5382159047fSniklas int oldused; 5392159047fSniklas #endif 5402159047fSniklas 5412159047fSniklas /* 5422159047fSniklas * capture info about old hash table 5432159047fSniklas */ 5442159047fSniklas oldwhere = handle->hash_where; 5452159047fSniklas oldwall = handle->hash_wall; 5462159047fSniklas #ifdef SUSPECT 5472159047fSniklas oldused = handle->hash_stat[STAT_USED]; 5482159047fSniklas #endif 5492159047fSniklas /* 5502159047fSniklas * attempt to get enough room for a hash table twice as big 5512159047fSniklas */ 5522159047fSniklas temp = handle->hash_stat[STAT_SIZE]; 553*191aa565Sniklas newwhere = ((struct hash_entry *) 554*191aa565Sniklas xmalloc ((unsigned long) ((temp << GROW_FACTOR + 1) 5552159047fSniklas /* +1 for wall slot */ 556*191aa565Sniklas * sizeof (struct hash_entry)))); 557*191aa565Sniklas if (newwhere == NULL) 558*191aa565Sniklas return "no_room"; 559*191aa565Sniklas 5602159047fSniklas /* 5612159047fSniklas * have enough room: now we do all the work. 562*191aa565Sniklas * double the size of everything in handle. 5632159047fSniklas */ 564*191aa565Sniklas handle->hash_mask = ((handle->hash_mask + 1) << GROW_FACTOR) - 1; 565*191aa565Sniklas handle->hash_stat[STAT_SIZE] <<= GROW_FACTOR; 5662159047fSniklas newsize = handle->hash_stat[STAT_SIZE]; 5672159047fSniklas handle->hash_where = newwhere; 568*191aa565Sniklas handle->hash_full <<= GROW_FACTOR; 569*191aa565Sniklas handle->hash_sizelog += GROW_FACTOR; 570*191aa565Sniklas handle->hash_wall = newwall = newwhere + newsize; 571*191aa565Sniklas /* Set all those pesky new slots to vacant. */ 5722159047fSniklas for (newtrack = newwhere; newtrack <= newwall; newtrack++) 5732159047fSniklas newtrack->hash_string = NULL; 574*191aa565Sniklas /* We will do a scan of the old table, the hard way, using the 575*191aa565Sniklas * new control block to re-insert the data into new hash table. */ 576*191aa565Sniklas handle->hash_stat[STAT_USED] = 0; 5772159047fSniklas for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++) 5782159047fSniklas if (((string = oldtrack->hash_string) != NULL) && string != DELETED) 5792159047fSniklas if ((retval = hash_jam (handle, string, oldtrack->hash_value))) 580*191aa565Sniklas return retval; 5812159047fSniklas 5822159047fSniklas #ifdef SUSPECT 583*191aa565Sniklas if (handle->hash_stat[STAT_USED] != oldused) 584*191aa565Sniklas return "hash_used"; 5852159047fSniklas #endif 586*191aa565Sniklas 587*191aa565Sniklas /* We have a completely faked up control block. 588*191aa565Sniklas Return the old hash table. */ 5892159047fSniklas free ((char *) oldwhere); 590*191aa565Sniklas 591*191aa565Sniklas return 0; 5922159047fSniklas } 5932159047fSniklas 594*191aa565Sniklas #ifdef TEST 5952159047fSniklas /* 5962159047fSniklas * h a s h _ a p p l y ( ) 5972159047fSniklas * 5982159047fSniklas * Use this to scan each entry in symbol table. 5992159047fSniklas * For each symbol, this calls (applys) a nominated function supplying the 6002159047fSniklas * symbol's value (and the symbol's name). 6012159047fSniklas * The idea is you use this to destroy whatever is associted with 6022159047fSniklas * any values in the table BEFORE you destroy the table with hash_die. 6032159047fSniklas * Of course, you can use it for other jobs; whenever you need to 6042159047fSniklas * visit all extant symbols in the table. 6052159047fSniklas * 6062159047fSniklas * We choose to have a call-you-back idea for two reasons: 6072159047fSniklas * asthetic: it is a neater idea to use apply than an explicit loop 6082159047fSniklas * sensible: if we ever had to grow the symbol table (due to insertions) 6092159047fSniklas * then we would lose our place in the table when we re-hashed 6102159047fSniklas * symbols into the new table in a different order. 6112159047fSniklas * 6122159047fSniklas * The order symbols are visited depends entirely on the hashing function. 6132159047fSniklas * Whenever you insert a (symbol, value) you risk expanding the table. If 6142159047fSniklas * you do expand the table, then the hashing function WILL change, so you 6152159047fSniklas * MIGHT get a different order of symbols visited. In other words, if you 6162159047fSniklas * want the same order of visiting symbols as the last time you used 6172159047fSniklas * hash_apply() then you better not have done any hash_insert()s or 6182159047fSniklas * hash_jam()s since the last time you used hash_apply(). 6192159047fSniklas * 6202159047fSniklas * In future we may use the value returned by your nominated function. 6212159047fSniklas * One idea is to abort the scan if, after applying the function to a 6222159047fSniklas * certain node, the function returns a certain code. 6232159047fSniklas * 6242159047fSniklas * The function you supply should be of the form: 625*191aa565Sniklas * void myfunct(string,value) 6262159047fSniklas * char * string; |* the symbol's name *| 6272159047fSniklas * char * value; |* the symbol's value *| 6282159047fSniklas * { 6292159047fSniklas * |* ... *| 6302159047fSniklas * } 6312159047fSniklas * 6322159047fSniklas */ 633*191aa565Sniklas void 6342159047fSniklas hash_apply (handle, function) 6352159047fSniklas struct hash_control *handle; 636*191aa565Sniklas void (*function) (); 6372159047fSniklas { 6382159047fSniklas struct hash_entry *entry; 6392159047fSniklas struct hash_entry *wall; 6402159047fSniklas 6412159047fSniklas wall = handle->hash_wall; 6422159047fSniklas for (entry = handle->hash_where; entry < wall; entry++) 6432159047fSniklas { 6442159047fSniklas if (islive (entry)) /* silly code: tests entry->string twice! */ 6452159047fSniklas { 6462159047fSniklas (*function) (entry->hash_string, entry->hash_value); 6472159047fSniklas } 6482159047fSniklas } 6492159047fSniklas } 650*191aa565Sniklas #endif 6512159047fSniklas 6522159047fSniklas /* 6532159047fSniklas * h a s h _ f i n d ( ) 6542159047fSniklas * 6552159047fSniklas * Given symbol string, find value (if any). 6562159047fSniklas * Return found value or NULL. 6572159047fSniklas */ 6582159047fSniklas PTR 6592159047fSniklas hash_find (handle, string) 6602159047fSniklas struct hash_control *handle; 6612159047fSniklas const char *string; 6622159047fSniklas { 6632159047fSniklas struct hash_entry *entry; 6642159047fSniklas 6652159047fSniklas entry = hash_ask (handle, string, STAT__READ); 6662159047fSniklas if (hash_found) 6672159047fSniklas return entry->hash_value; 6682159047fSniklas else 6692159047fSniklas return NULL; 6702159047fSniklas } 6712159047fSniklas 6722159047fSniklas /* 6732159047fSniklas * h a s h _ a s k ( ) 6742159047fSniklas * 6752159047fSniklas * Searches for given symbol string. 6762159047fSniklas * Return the slot where it OUGHT to live. It may be there. 6772159047fSniklas * Return hash_found: TRUE only if symbol is in that slot. 6782159047fSniklas * Access argument is to help keep statistics in control block. 6792159047fSniklas * Internal. 6802159047fSniklas */ 6812159047fSniklas static struct hash_entry * /* string slot, may be empty or deleted */ 6822159047fSniklas hash_ask (handle, string, access_type) 6832159047fSniklas struct hash_control *handle; 6842159047fSniklas const char *string; 6852159047fSniklas int access_type; 6862159047fSniklas { 6872159047fSniklas const char *s; 6882159047fSniklas struct hash_entry *slot; 6892159047fSniklas int collision; /* count collisions */ 690*191aa565Sniklas int strcmps; 691*191aa565Sniklas int hcode; 6922159047fSniklas 6932159047fSniklas /* start looking here */ 694*191aa565Sniklas hcode = hash_code (handle, string); 695*191aa565Sniklas slot = handle->hash_where + (hcode & handle->hash_mask); 6962159047fSniklas 6972159047fSniklas handle->hash_stat[STAT_ACCESS + access_type] += 1; 698*191aa565Sniklas collision = strcmps = 0; 6992159047fSniklas hash_found = FALSE; 7002159047fSniklas while (((s = slot->hash_string) != NULL) && s != DELETED) 7012159047fSniklas { 702*191aa565Sniklas if (string == s) 703*191aa565Sniklas { 7042159047fSniklas hash_found = TRUE; 7052159047fSniklas break; 706*191aa565Sniklas } 707*191aa565Sniklas if (slot->h == hcode) 708*191aa565Sniklas { 709*191aa565Sniklas if (!strcmp (string, s)) 710*191aa565Sniklas { 711*191aa565Sniklas hash_found = TRUE; 712*191aa565Sniklas break; 713*191aa565Sniklas } 714*191aa565Sniklas strcmps++; 715*191aa565Sniklas } 7162159047fSniklas collision++; 7172159047fSniklas slot++; 7182159047fSniklas } 7192159047fSniklas /* 7202159047fSniklas * slot: return: 7212159047fSniklas * in use: we found string slot 7222159047fSniklas * at empty: 7232159047fSniklas * at wall: we fell off: wrap round ???? 7242159047fSniklas * in table: dig here slot 7252159047fSniklas * at DELETED: dig here slot 7262159047fSniklas */ 7272159047fSniklas if (slot == handle->hash_wall) 7282159047fSniklas { 7292159047fSniklas slot = handle->hash_where;/* now look again */ 7302159047fSniklas while (((s = slot->hash_string) != NULL) && s != DELETED) 7312159047fSniklas { 732*191aa565Sniklas if (string == s) 7332159047fSniklas { 7342159047fSniklas hash_found = TRUE; 7352159047fSniklas break; 7362159047fSniklas } 737*191aa565Sniklas if (slot->h == hcode) 738*191aa565Sniklas { 739*191aa565Sniklas if (!strcmp (string, s)) 740*191aa565Sniklas { 741*191aa565Sniklas hash_found = TRUE; 742*191aa565Sniklas break; 743*191aa565Sniklas } 744*191aa565Sniklas strcmps++; 745*191aa565Sniklas } 7462159047fSniklas collision++; 7472159047fSniklas slot++; 7482159047fSniklas } 7492159047fSniklas /* 7502159047fSniklas * slot: return: 7512159047fSniklas * in use: we found it slot 7522159047fSniklas * empty: wall: ERROR IMPOSSIBLE !!!! 7532159047fSniklas * in table: dig here slot 7542159047fSniklas * DELETED:dig here slot 7552159047fSniklas */ 7562159047fSniklas } 7572159047fSniklas handle->hash_stat[STAT_COLLIDE + access_type] += collision; 758*191aa565Sniklas handle->hash_stat[STAT_STRCMP + access_type] += strcmps; 759*191aa565Sniklas if (!hash_found) 760*191aa565Sniklas slot->h = hcode; 761*191aa565Sniklas return slot; /* also return hash_found */ 7622159047fSniklas } 7632159047fSniklas 7642159047fSniklas /* 7652159047fSniklas * h a s h _ c o d e 7662159047fSniklas * 7672159047fSniklas * Does hashing of symbol string to hash number. 7682159047fSniklas * Internal. 7692159047fSniklas */ 7702159047fSniklas static int 7712159047fSniklas hash_code (handle, string) 7722159047fSniklas struct hash_control *handle; 7732159047fSniklas const char *string; 7742159047fSniklas { 7752159047fSniklas #if 1 /* There seems to be some interesting property of this function 7762159047fSniklas that prevents the bfd version below from being an adequate 7772159047fSniklas substitute. @@ Figure out what this property is! */ 7782159047fSniklas long h; /* hash code built here */ 7792159047fSniklas long c; /* each character lands here */ 7802159047fSniklas int n; /* Amount to shift h by */ 7812159047fSniklas 7822159047fSniklas n = (handle->hash_sizelog - 3); 7832159047fSniklas h = 0; 7842159047fSniklas while ((c = *string++) != 0) 7852159047fSniklas { 7862159047fSniklas h += c; 7872159047fSniklas h = (h << 3) + (h >> n) + c; 7882159047fSniklas } 789*191aa565Sniklas return h; 7902159047fSniklas #else 7912159047fSniklas /* from bfd */ 7922159047fSniklas unsigned long h = 0; 7932159047fSniklas unsigned int len = 0; 7942159047fSniklas unsigned int c; 7952159047fSniklas 7962159047fSniklas while ((c = *string++) != 0) 7972159047fSniklas { 7982159047fSniklas h += c + (c << 17); 7992159047fSniklas h ^= h >> 2; 8002159047fSniklas ++len; 8012159047fSniklas } 8022159047fSniklas h += len + (len << 17); 8032159047fSniklas h ^= h >> 2; 804*191aa565Sniklas return h; 8052159047fSniklas #endif 8062159047fSniklas } 8072159047fSniklas 808*191aa565Sniklas void 809*191aa565Sniklas hash_print_statistics (file, name, h) 810*191aa565Sniklas FILE *file; 811*191aa565Sniklas const char *name; 812*191aa565Sniklas struct hash_control *h; 813*191aa565Sniklas { 814*191aa565Sniklas unsigned long sz, used, pct; 815*191aa565Sniklas 816*191aa565Sniklas if (h == 0) 817*191aa565Sniklas return; 818*191aa565Sniklas 819*191aa565Sniklas sz = h->hash_stat[STAT_SIZE]; 820*191aa565Sniklas used = h->hash_stat[STAT_USED]; 821*191aa565Sniklas pct = (used * 100 + sz / 2) / sz; 822*191aa565Sniklas 823*191aa565Sniklas fprintf (file, "%s hash statistics:\n\t%d/%d slots used (%d%%)\n", 824*191aa565Sniklas name, used, sz, pct); 825*191aa565Sniklas 826*191aa565Sniklas #define P(name, off) \ 827*191aa565Sniklas fprintf (file, "\t%-16s %6dr + %6dw = %7d\n", name, \ 828*191aa565Sniklas h->hash_stat[off+STAT__READ], \ 829*191aa565Sniklas h->hash_stat[off+STAT__WRITE], \ 830*191aa565Sniklas h->hash_stat[off+STAT__READ] + h->hash_stat[off+STAT__WRITE]) 831*191aa565Sniklas 832*191aa565Sniklas P ("accesses:", STAT_ACCESS); 833*191aa565Sniklas P ("collisions:", STAT_COLLIDE); 834*191aa565Sniklas P ("string compares:", STAT_STRCMP); 835*191aa565Sniklas 836*191aa565Sniklas #undef P 837*191aa565Sniklas } 838*191aa565Sniklas 8392159047fSniklas /* 8402159047fSniklas * Here is a test program to exercise above. 8412159047fSniklas */ 8422159047fSniklas #ifdef TEST 8432159047fSniklas 8442159047fSniklas #define TABLES (6) /* number of hash tables to maintain */ 8452159047fSniklas /* (at once) in any testing */ 8462159047fSniklas #define STATBUFSIZE (12) /* we can have 12 statistics */ 8472159047fSniklas 8482159047fSniklas int statbuf[STATBUFSIZE]; /* display statistics here */ 8492159047fSniklas char answer[100]; /* human farts here */ 8502159047fSniklas char *hashtable[TABLES]; /* we test many hash tables at once */ 8512159047fSniklas char *h; /* points to curent hash_control */ 8522159047fSniklas char **pp; 8532159047fSniklas char *p; 8542159047fSniklas char *name; 8552159047fSniklas char *value; 8562159047fSniklas int size; 8572159047fSniklas int used; 8582159047fSniklas char command; 8592159047fSniklas int number; /* number 0:TABLES-1 of current hashed */ 8602159047fSniklas /* symbol table */ 8612159047fSniklas 8622159047fSniklas main () 8632159047fSniklas { 864*191aa565Sniklas void applicatee (); 865*191aa565Sniklas void destroy (); 8662159047fSniklas char *what (); 8672159047fSniklas int *ip; 8682159047fSniklas 8692159047fSniklas number = 0; 8702159047fSniklas h = 0; 8712159047fSniklas printf ("type h <RETURN> for help\n"); 8722159047fSniklas for (;;) 8732159047fSniklas { 8742159047fSniklas printf ("hash_test command: "); 8752159047fSniklas gets (answer); 8762159047fSniklas command = answer[0]; 8772159047fSniklas if (isupper (command)) 8782159047fSniklas command = tolower (command); /* ecch! */ 8792159047fSniklas switch (command) 8802159047fSniklas { 8812159047fSniklas case '#': 8822159047fSniklas printf ("old hash table #=%d.\n", number); 8832159047fSniklas whattable (); 8842159047fSniklas break; 8852159047fSniklas case '?': 8862159047fSniklas for (pp = hashtable; pp < hashtable + TABLES; pp++) 8872159047fSniklas { 8882159047fSniklas printf ("address of hash table #%d control block is %xx\n" 8892159047fSniklas ,pp - hashtable, *pp); 8902159047fSniklas } 8912159047fSniklas break; 8922159047fSniklas case 'a': 8932159047fSniklas hash_apply (h, applicatee); 8942159047fSniklas break; 8952159047fSniklas case 'd': 8962159047fSniklas hash_apply (h, destroy); 8972159047fSniklas hash_die (h); 8982159047fSniklas break; 8992159047fSniklas case 'f': 9002159047fSniklas p = hash_find (h, name = what ("symbol")); 9012159047fSniklas printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); 9022159047fSniklas break; 9032159047fSniklas case 'h': 9042159047fSniklas printf ("# show old, select new default hash table number\n"); 9052159047fSniklas printf ("? display all hashtable control block addresses\n"); 9062159047fSniklas printf ("a apply a simple display-er to each symbol in table\n"); 9072159047fSniklas printf ("d die: destroy hashtable\n"); 9082159047fSniklas printf ("f find value of nominated symbol\n"); 9092159047fSniklas printf ("h this help\n"); 9102159047fSniklas printf ("i insert value into symbol\n"); 9112159047fSniklas printf ("j jam value into symbol\n"); 9122159047fSniklas printf ("n new hashtable\n"); 9132159047fSniklas printf ("r replace a value with another\n"); 9142159047fSniklas printf ("s say what %% of table is used\n"); 9152159047fSniklas printf ("q exit this program\n"); 9162159047fSniklas printf ("x delete a symbol from table, report its value\n"); 9172159047fSniklas break; 9182159047fSniklas case 'i': 9192159047fSniklas p = hash_insert (h, name = what ("symbol"), value = what ("value")); 9202159047fSniklas if (p) 9212159047fSniklas { 9222159047fSniklas printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, 9232159047fSniklas p); 9242159047fSniklas } 9252159047fSniklas break; 9262159047fSniklas case 'j': 9272159047fSniklas p = hash_jam (h, name = what ("symbol"), value = what ("value")); 9282159047fSniklas if (p) 9292159047fSniklas { 9302159047fSniklas printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); 9312159047fSniklas } 9322159047fSniklas break; 9332159047fSniklas case 'n': 9342159047fSniklas h = hashtable[number] = (char *) hash_new (); 9352159047fSniklas break; 9362159047fSniklas case 'q': 9372159047fSniklas exit (EXIT_SUCCESS); 9382159047fSniklas case 'r': 9392159047fSniklas p = hash_replace (h, name = what ("symbol"), value = what ("value")); 9402159047fSniklas printf ("old value was \"%s\"\n", p ? p : "{}"); 9412159047fSniklas break; 9422159047fSniklas case 's': 9432159047fSniklas hash_say (h, statbuf, STATBUFSIZE); 9442159047fSniklas for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) 9452159047fSniklas { 9462159047fSniklas printf ("%d ", *ip); 9472159047fSniklas } 9482159047fSniklas printf ("\n"); 9492159047fSniklas break; 9502159047fSniklas case 'x': 9512159047fSniklas p = hash_delete (h, name = what ("symbol")); 9522159047fSniklas printf ("old value was \"%s\"\n", p ? p : "{}"); 9532159047fSniklas break; 9542159047fSniklas default: 9552159047fSniklas printf ("I can't understand command \"%c\"\n", command); 9562159047fSniklas break; 9572159047fSniklas } 9582159047fSniklas } 9592159047fSniklas } 9602159047fSniklas 9612159047fSniklas char * 9622159047fSniklas what (description) 9632159047fSniklas char *description; 9642159047fSniklas { 9652159047fSniklas char *retval; 9662159047fSniklas char *malloc (); 9672159047fSniklas 9682159047fSniklas printf (" %s : ", description); 9692159047fSniklas gets (answer); 9702159047fSniklas /* will one day clean up answer here */ 9712159047fSniklas retval = malloc (strlen (answer) + 1); 9722159047fSniklas if (!retval) 9732159047fSniklas { 9742159047fSniklas error ("room"); 9752159047fSniklas } 9762159047fSniklas (void) strcpy (retval, answer); 9772159047fSniklas return (retval); 9782159047fSniklas } 9792159047fSniklas 980*191aa565Sniklas void 9812159047fSniklas destroy (string, value) 9822159047fSniklas char *string; 9832159047fSniklas char *value; 9842159047fSniklas { 9852159047fSniklas free (string); 9862159047fSniklas free (value); 9872159047fSniklas } 9882159047fSniklas 9892159047fSniklas 990*191aa565Sniklas void 9912159047fSniklas applicatee (string, value) 9922159047fSniklas char *string; 9932159047fSniklas char *value; 9942159047fSniklas { 9952159047fSniklas printf ("%.20s-%.20s\n", string, value); 9962159047fSniklas } 9972159047fSniklas 9982159047fSniklas whattable () /* determine number: what hash table to use */ 9992159047fSniklas /* also determine h: points to hash_control */ 10002159047fSniklas { 10012159047fSniklas 10022159047fSniklas for (;;) 10032159047fSniklas { 10042159047fSniklas printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); 10052159047fSniklas gets (answer); 10062159047fSniklas sscanf (answer, "%d", &number); 10072159047fSniklas if (number >= 0 && number < TABLES) 10082159047fSniklas { 10092159047fSniklas h = hashtable[number]; 10102159047fSniklas if (!h) 10112159047fSniklas { 10122159047fSniklas printf ("warning: current hash-table-#%d. has no hash-control\n", number); 10132159047fSniklas } 10142159047fSniklas return; 10152159047fSniklas } 10162159047fSniklas else 10172159047fSniklas { 10182159047fSniklas printf ("invalid hash table number: %d\n", number); 10192159047fSniklas } 10202159047fSniklas } 10212159047fSniklas } 10222159047fSniklas 10232159047fSniklas 10242159047fSniklas 10252159047fSniklas #endif /* #ifdef TEST */ 10262159047fSniklas 10272159047fSniklas /* end of hash.c */ 1028