hash.c revision 130561
160484Sobrien/* hash.c -- gas hash table code 278828Sobrien Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999, 3104834Sobrien 2000, 2001, 2002 433965Sjdp Free Software Foundation, Inc. 533965Sjdp 633965Sjdp This file is part of GAS, the GNU Assembler. 733965Sjdp 833965Sjdp GAS is free software; you can redistribute it and/or modify 933965Sjdp it under the terms of the GNU General Public License as published by 1033965Sjdp the Free Software Foundation; either version 2, or (at your option) 1133965Sjdp any later version. 1233965Sjdp 1333965Sjdp GAS is distributed in the hope that it will be useful, 1433965Sjdp but WITHOUT ANY WARRANTY; without even the implied warranty of 1533965Sjdp MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1633965Sjdp GNU General Public License for more details. 1733965Sjdp 1833965Sjdp You should have received a copy of the GNU General Public License 1960484Sobrien along with GAS; see the file COPYING. If not, write to the Free 2060484Sobrien Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2160484Sobrien 02111-1307, USA. */ 2233965Sjdp 2360484Sobrien/* This version of the hash table code is a wholescale replacement of 2460484Sobrien the old hash table code, which was fairly bad. This is based on 2560484Sobrien the hash table code in BFD, but optimized slightly for the 26130561Sobrien assembler. The assembler does not need to derive structures that 2760484Sobrien are stored in the hash table. Instead, it always stores a pointer. 2860484Sobrien The assembler uses the hash table mostly to store symbols, and we 2960484Sobrien don't need to confuse the symbol structure with a hash table 3060484Sobrien structure. */ 3133965Sjdp 3233965Sjdp#include "as.h" 3389857Sobrien#include "safe-ctype.h" 3460484Sobrien#include "obstack.h" 3533965Sjdp 3660484Sobrien/* The default number of entries to use when creating a hash table. */ 3733965Sjdp 3860484Sobrien#define DEFAULT_SIZE (4051) 3933965Sjdp 4060484Sobrien/* An entry in a hash table. */ 4133965Sjdp 4277298Sobrienstruct hash_entry { 4360484Sobrien /* Next entry for this hash code. */ 4460484Sobrien struct hash_entry *next; 4560484Sobrien /* String being hashed. */ 4660484Sobrien const char *string; 4760484Sobrien /* Hash code. This is the full hash code, not the index into the 4860484Sobrien table. */ 4960484Sobrien unsigned long hash; 5060484Sobrien /* Pointer being stored in the hash table. */ 5160484Sobrien PTR data; 5233965Sjdp}; 5333965Sjdp 5460484Sobrien/* A hash table. */ 5533965Sjdp 5677298Sobrienstruct hash_control { 5760484Sobrien /* The hash array. */ 5860484Sobrien struct hash_entry **table; 5960484Sobrien /* The number of slots in the hash table. */ 6060484Sobrien unsigned int size; 6160484Sobrien /* An obstack for this hash table. */ 6260484Sobrien struct obstack memory; 6333965Sjdp 6460484Sobrien#ifdef HASH_STATISTICS 6560484Sobrien /* Statistics. */ 6660484Sobrien unsigned long lookups; 6760484Sobrien unsigned long hash_compares; 6860484Sobrien unsigned long string_compares; 6960484Sobrien unsigned long insertions; 7060484Sobrien unsigned long replacements; 7160484Sobrien unsigned long deletions; 7260484Sobrien#endif /* HASH_STATISTICS */ 7333965Sjdp}; 7433965Sjdp 7560484Sobrien/* Create a hash table. This return a control block. */ 7633965Sjdp 7760484Sobrienstruct hash_control * 78130561Sobrienhash_new (void) 7960484Sobrien{ 8060484Sobrien unsigned int size; 8160484Sobrien struct hash_control *ret; 8260484Sobrien unsigned int alloc; 8333965Sjdp 8460484Sobrien size = DEFAULT_SIZE; 8533965Sjdp 8660484Sobrien ret = (struct hash_control *) xmalloc (sizeof *ret); 8760484Sobrien obstack_begin (&ret->memory, chunksize); 8860484Sobrien alloc = size * sizeof (struct hash_entry *); 8960484Sobrien ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc); 9060484Sobrien memset (ret->table, 0, alloc); 9160484Sobrien ret->size = size; 9233965Sjdp 9360484Sobrien#ifdef HASH_STATISTICS 9460484Sobrien ret->lookups = 0; 9560484Sobrien ret->hash_compares = 0; 9660484Sobrien ret->string_compares = 0; 9760484Sobrien ret->insertions = 0; 9860484Sobrien ret->replacements = 0; 9960484Sobrien ret->deletions = 0; 10060484Sobrien#endif 10133965Sjdp 10277298Sobrien return ret; 10360484Sobrien} 10433965Sjdp 10560484Sobrien/* Delete a hash table, freeing all allocated memory. */ 10633965Sjdp 10760484Sobrienvoid 108130561Sobrienhash_die (struct hash_control *table) 10960484Sobrien{ 11060484Sobrien obstack_free (&table->memory, 0); 11160484Sobrien free (table); 11260484Sobrien} 11333965Sjdp 11460484Sobrien/* Look up a string in a hash table. This returns a pointer to the 11560484Sobrien hash_entry, or NULL if the string is not in the table. If PLIST is 11660484Sobrien not NULL, this sets *PLIST to point to the start of the list which 11760484Sobrien would hold this hash entry. If PHASH is not NULL, this sets *PHASH 11860484Sobrien to the hash code for KEY. 11933965Sjdp 12060484Sobrien Each time we look up a string, we move it to the start of the list 12160484Sobrien for its hash code, to take advantage of referential locality. */ 12233965Sjdp 123130561Sobrienstatic struct hash_entry *hash_lookup (struct hash_control *, 124130561Sobrien const char *, 125130561Sobrien struct hash_entry ***, 126130561Sobrien unsigned long *); 12733965Sjdp 12860484Sobrienstatic struct hash_entry * 129130561Sobrienhash_lookup (struct hash_control *table, const char *key, 130130561Sobrien struct hash_entry ***plist, unsigned long *phash) 13160484Sobrien{ 13260484Sobrien register unsigned long hash; 13360484Sobrien unsigned int len; 13460484Sobrien register const unsigned char *s; 13560484Sobrien register unsigned int c; 13660484Sobrien unsigned int index; 13760484Sobrien struct hash_entry **list; 13860484Sobrien struct hash_entry *p; 13960484Sobrien struct hash_entry *prev; 14033965Sjdp 14160484Sobrien#ifdef HASH_STATISTICS 14260484Sobrien ++table->lookups; 14360484Sobrien#endif 14433965Sjdp 14560484Sobrien hash = 0; 14660484Sobrien len = 0; 14760484Sobrien s = (const unsigned char *) key; 14860484Sobrien while ((c = *s++) != '\0') 14960484Sobrien { 15060484Sobrien hash += c + (c << 17); 15160484Sobrien hash ^= hash >> 2; 15260484Sobrien ++len; 15360484Sobrien } 15460484Sobrien hash += len + (len << 17); 15560484Sobrien hash ^= hash >> 2; 15633965Sjdp 15760484Sobrien if (phash != NULL) 15860484Sobrien *phash = hash; 15933965Sjdp 16060484Sobrien index = hash % table->size; 16160484Sobrien list = table->table + index; 16233965Sjdp 16360484Sobrien if (plist != NULL) 16460484Sobrien *plist = list; 16533965Sjdp 16660484Sobrien prev = NULL; 16760484Sobrien for (p = *list; p != NULL; p = p->next) 16860484Sobrien { 16960484Sobrien#ifdef HASH_STATISTICS 17060484Sobrien ++table->hash_compares; 17160484Sobrien#endif 17233965Sjdp 17360484Sobrien if (p->hash == hash) 17433965Sjdp { 17560484Sobrien#ifdef HASH_STATISTICS 17660484Sobrien ++table->string_compares; 17733965Sjdp#endif 17833965Sjdp 17960484Sobrien if (strcmp (p->string, key) == 0) 18060484Sobrien { 18160484Sobrien if (prev != NULL) 18260484Sobrien { 18360484Sobrien prev->next = p->next; 18460484Sobrien p->next = *list; 18560484Sobrien *list = p; 18660484Sobrien } 18760484Sobrien 18860484Sobrien return p; 18960484Sobrien } 19033965Sjdp } 19160484Sobrien 19260484Sobrien prev = p; 19333965Sjdp } 19460484Sobrien 19560484Sobrien return NULL; 19633965Sjdp} 19760484Sobrien 19860484Sobrien/* Insert an entry into a hash table. This returns NULL on success. 19960484Sobrien On error, it returns a printable string indicating the error. It 20060484Sobrien is considered to be an error if the entry already exists in the 20160484Sobrien hash table. */ 20260484Sobrien 20360484Sobrienconst char * 204130561Sobrienhash_insert (struct hash_control *table, const char *key, PTR value) 20533965Sjdp{ 20660484Sobrien struct hash_entry *p; 20760484Sobrien struct hash_entry **list; 20860484Sobrien unsigned long hash; 20933965Sjdp 21060484Sobrien p = hash_lookup (table, key, &list, &hash); 21160484Sobrien if (p != NULL) 21260484Sobrien return "exists"; 21360484Sobrien 21460484Sobrien#ifdef HASH_STATISTICS 21560484Sobrien ++table->insertions; 21660484Sobrien#endif 21760484Sobrien 21877298Sobrien p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); 21960484Sobrien p->string = key; 22060484Sobrien p->hash = hash; 22160484Sobrien p->data = value; 22260484Sobrien 22360484Sobrien p->next = *list; 22460484Sobrien *list = p; 22560484Sobrien 22660484Sobrien return NULL; 22733965Sjdp} 22833965Sjdp 22960484Sobrien/* Insert or replace an entry in a hash table. This returns NULL on 23060484Sobrien success. On error, it returns a printable string indicating the 23160484Sobrien error. If an entry already exists, its value is replaced. */ 23233965Sjdp 23333965Sjdpconst char * 234130561Sobrienhash_jam (struct hash_control *table, const char *key, PTR value) 23533965Sjdp{ 23660484Sobrien struct hash_entry *p; 23760484Sobrien struct hash_entry **list; 23860484Sobrien unsigned long hash; 23933965Sjdp 24060484Sobrien p = hash_lookup (table, key, &list, &hash); 24160484Sobrien if (p != NULL) 24233965Sjdp { 24360484Sobrien#ifdef HASH_STATISTICS 24460484Sobrien ++table->replacements; 24560484Sobrien#endif 24660484Sobrien 24760484Sobrien p->data = value; 24833965Sjdp } 24960484Sobrien else 25033965Sjdp { 25160484Sobrien#ifdef HASH_STATISTICS 25260484Sobrien ++table->insertions; 25360484Sobrien#endif 25460484Sobrien 25577298Sobrien p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); 25660484Sobrien p->string = key; 25760484Sobrien p->hash = hash; 25860484Sobrien p->data = value; 25960484Sobrien 26060484Sobrien p->next = *list; 26160484Sobrien *list = p; 26233965Sjdp } 26360484Sobrien 26460484Sobrien return NULL; 26533965Sjdp} 26633965Sjdp 26760484Sobrien/* Replace an existing entry in a hash table. This returns the old 26860484Sobrien value stored for the entry. If the entry is not found in the hash 26960484Sobrien table, this does nothing and returns NULL. */ 27060484Sobrien 27160484SobrienPTR 272130561Sobrienhash_replace (struct hash_control *table, const char *key, PTR value) 27333965Sjdp{ 27460484Sobrien struct hash_entry *p; 27560484Sobrien PTR ret; 27633965Sjdp 27760484Sobrien p = hash_lookup (table, key, NULL, NULL); 27860484Sobrien if (p == NULL) 27960484Sobrien return NULL; 28060484Sobrien 28160484Sobrien#ifdef HASH_STATISTICS 28260484Sobrien ++table->replacements; 28333965Sjdp#endif 28433965Sjdp 28560484Sobrien ret = p->data; 28633965Sjdp 28760484Sobrien p->data = value; 28833965Sjdp 28960484Sobrien return ret; 29060484Sobrien} 29133965Sjdp 29260484Sobrien/* Find an entry in a hash table, returning its value. Returns NULL 29360484Sobrien if the entry is not found. */ 29460484Sobrien 29560484SobrienPTR 296130561Sobrienhash_find (struct hash_control *table, const char *key) 29733965Sjdp{ 29860484Sobrien struct hash_entry *p; 29933965Sjdp 30060484Sobrien p = hash_lookup (table, key, NULL, NULL); 30160484Sobrien if (p == NULL) 30260484Sobrien return NULL; 30360484Sobrien 30460484Sobrien return p->data; 30533965Sjdp} 30660484Sobrien 30760484Sobrien/* Delete an entry from a hash table. This returns the value stored 30860484Sobrien for that entry, or NULL if there is no such entry. */ 30960484Sobrien 31033965SjdpPTR 311130561Sobrienhash_delete (struct hash_control *table, const char *key) 31233965Sjdp{ 31360484Sobrien struct hash_entry *p; 31460484Sobrien struct hash_entry **list; 31533965Sjdp 31660484Sobrien p = hash_lookup (table, key, &list, NULL); 31760484Sobrien if (p == NULL) 31833965Sjdp return NULL; 31960484Sobrien 32060484Sobrien if (p != *list) 32160484Sobrien abort (); 32260484Sobrien 32360484Sobrien#ifdef HASH_STATISTICS 32460484Sobrien ++table->deletions; 32560484Sobrien#endif 32660484Sobrien 32760484Sobrien *list = p->next; 32860484Sobrien 32960484Sobrien /* Note that we never reclaim the memory for this entry. If gas 33060484Sobrien ever starts deleting hash table entries in a big way, this will 33160484Sobrien have to change. */ 33260484Sobrien 33360484Sobrien return p->data; 33433965Sjdp} 33533965Sjdp 33660484Sobrien/* Traverse a hash table. Call the function on every entry in the 33760484Sobrien hash table. */ 33833965Sjdp 33960484Sobrienvoid 340130561Sobrienhash_traverse (struct hash_control *table, 341130561Sobrien void (*pfn) (const char *key, PTR value)) 34233965Sjdp{ 34360484Sobrien unsigned int i; 34433965Sjdp 34560484Sobrien for (i = 0; i < table->size; ++i) 34633965Sjdp { 34760484Sobrien struct hash_entry *p; 34833965Sjdp 34960484Sobrien for (p = table->table[i]; p != NULL; p = p->next) 35060484Sobrien (*pfn) (p->string, p->data); 35133965Sjdp } 35233965Sjdp} 35360484Sobrien 35460484Sobrien/* Print hash table statistics on the specified file. NAME is the 35560484Sobrien name of the hash table, used for printing a header. */ 35660484Sobrien 35733965Sjdpvoid 358130561Sobrienhash_print_statistics (FILE *f ATTRIBUTE_UNUSED, 359130561Sobrien const char *name ATTRIBUTE_UNUSED, 360130561Sobrien struct hash_control *table ATTRIBUTE_UNUSED) 36133965Sjdp{ 36260484Sobrien#ifdef HASH_STATISTICS 36360484Sobrien unsigned int i; 36460484Sobrien unsigned long total; 36560484Sobrien unsigned long empty; 36633965Sjdp 36760484Sobrien fprintf (f, "%s hash statistics:\n", name); 36860484Sobrien fprintf (f, "\t%lu lookups\n", table->lookups); 36960484Sobrien fprintf (f, "\t%lu hash comparisons\n", table->hash_compares); 37060484Sobrien fprintf (f, "\t%lu string comparisons\n", table->string_compares); 37160484Sobrien fprintf (f, "\t%lu insertions\n", table->insertions); 37260484Sobrien fprintf (f, "\t%lu replacements\n", table->replacements); 37360484Sobrien fprintf (f, "\t%lu deletions\n", table->deletions); 37433965Sjdp 37560484Sobrien total = 0; 37660484Sobrien empty = 0; 37760484Sobrien for (i = 0; i < table->size; ++i) 37860484Sobrien { 37960484Sobrien struct hash_entry *p; 38033965Sjdp 38160484Sobrien if (table->table[i] == NULL) 38260484Sobrien ++empty; 38360484Sobrien else 38460484Sobrien { 38560484Sobrien for (p = table->table[i]; p != NULL; p = p->next) 38660484Sobrien ++total; 38760484Sobrien } 38860484Sobrien } 38933965Sjdp 39060484Sobrien fprintf (f, "\t%g average chain length\n", (double) total / table->size); 39160484Sobrien fprintf (f, "\t%lu empty slots\n", empty); 39260484Sobrien#endif 39333965Sjdp} 39433965Sjdp 39533965Sjdp#ifdef TEST 39633965Sjdp 39760484Sobrien/* This test program is left over from the old hash table code. */ 39860484Sobrien 39977298Sobrien/* Number of hash tables to maintain (at once) in any testing. */ 40077298Sobrien#define TABLES (6) 40133965Sjdp 40277298Sobrien/* We can have 12 statistics. */ 40377298Sobrien#define STATBUFSIZE (12) 40477298Sobrien 40577298Sobrien/* Display statistics here. */ 40677298Sobrienint statbuf[STATBUFSIZE]; 40777298Sobrien 40877298Sobrien/* Human farts here. */ 40977298Sobrienchar answer[100]; 41077298Sobrien 41177298Sobrien/* We test many hash tables at once. */ 41277298Sobrienchar *hashtable[TABLES]; 41377298Sobrien 414130561Sobrien/* Points to current hash_control. */ 41577298Sobrienchar *h; 41633965Sjdpchar **pp; 41733965Sjdpchar *p; 41833965Sjdpchar *name; 41933965Sjdpchar *value; 42033965Sjdpint size; 42133965Sjdpint used; 42233965Sjdpchar command; 42333965Sjdp 42477298Sobrien/* Number 0:TABLES-1 of current hashed symbol table. */ 42577298Sobrienint number; 42677298Sobrien 42760484Sobrienint 42833965Sjdpmain () 42933965Sjdp{ 43033965Sjdp void applicatee (); 43133965Sjdp void destroy (); 43233965Sjdp char *what (); 43333965Sjdp int *ip; 43433965Sjdp 43533965Sjdp number = 0; 43633965Sjdp h = 0; 43733965Sjdp printf ("type h <RETURN> for help\n"); 43833965Sjdp for (;;) 43933965Sjdp { 44033965Sjdp printf ("hash_test command: "); 44133965Sjdp gets (answer); 44233965Sjdp command = answer[0]; 44389857Sobrien command = TOLOWER (command); /* Ecch! */ 44433965Sjdp switch (command) 44533965Sjdp { 44633965Sjdp case '#': 44733965Sjdp printf ("old hash table #=%d.\n", number); 44833965Sjdp whattable (); 44933965Sjdp break; 45033965Sjdp case '?': 45133965Sjdp for (pp = hashtable; pp < hashtable + TABLES; pp++) 45233965Sjdp { 45377298Sobrien printf ("address of hash table #%d control block is %xx\n", 45477298Sobrien pp - hashtable, *pp); 45533965Sjdp } 45633965Sjdp break; 45733965Sjdp case 'a': 45860484Sobrien hash_traverse (h, applicatee); 45933965Sjdp break; 46033965Sjdp case 'd': 46160484Sobrien hash_traverse (h, destroy); 46233965Sjdp hash_die (h); 46333965Sjdp break; 46433965Sjdp case 'f': 46533965Sjdp p = hash_find (h, name = what ("symbol")); 46633965Sjdp printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); 46733965Sjdp break; 46833965Sjdp case 'h': 46933965Sjdp printf ("# show old, select new default hash table number\n"); 47033965Sjdp printf ("? display all hashtable control block addresses\n"); 47133965Sjdp printf ("a apply a simple display-er to each symbol in table\n"); 47233965Sjdp printf ("d die: destroy hashtable\n"); 47333965Sjdp printf ("f find value of nominated symbol\n"); 47433965Sjdp printf ("h this help\n"); 47533965Sjdp printf ("i insert value into symbol\n"); 47633965Sjdp printf ("j jam value into symbol\n"); 47733965Sjdp printf ("n new hashtable\n"); 47833965Sjdp printf ("r replace a value with another\n"); 47933965Sjdp printf ("s say what %% of table is used\n"); 48033965Sjdp printf ("q exit this program\n"); 48133965Sjdp printf ("x delete a symbol from table, report its value\n"); 48233965Sjdp break; 48333965Sjdp case 'i': 48433965Sjdp p = hash_insert (h, name = what ("symbol"), value = what ("value")); 48533965Sjdp if (p) 48633965Sjdp { 48733965Sjdp printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, 48833965Sjdp p); 48933965Sjdp } 49033965Sjdp break; 49133965Sjdp case 'j': 49233965Sjdp p = hash_jam (h, name = what ("symbol"), value = what ("value")); 49333965Sjdp if (p) 49433965Sjdp { 49533965Sjdp printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); 49633965Sjdp } 49733965Sjdp break; 49833965Sjdp case 'n': 49933965Sjdp h = hashtable[number] = (char *) hash_new (); 50033965Sjdp break; 50133965Sjdp case 'q': 50233965Sjdp exit (EXIT_SUCCESS); 50333965Sjdp case 'r': 50433965Sjdp p = hash_replace (h, name = what ("symbol"), value = what ("value")); 50533965Sjdp printf ("old value was \"%s\"\n", p ? p : "{}"); 50633965Sjdp break; 50733965Sjdp case 's': 50833965Sjdp hash_say (h, statbuf, STATBUFSIZE); 50933965Sjdp for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) 51033965Sjdp { 51133965Sjdp printf ("%d ", *ip); 51233965Sjdp } 51333965Sjdp printf ("\n"); 51433965Sjdp break; 51533965Sjdp case 'x': 51633965Sjdp p = hash_delete (h, name = what ("symbol")); 51733965Sjdp printf ("old value was \"%s\"\n", p ? p : "{}"); 51833965Sjdp break; 51933965Sjdp default: 52033965Sjdp printf ("I can't understand command \"%c\"\n", command); 52133965Sjdp break; 52233965Sjdp } 52333965Sjdp } 52433965Sjdp} 52533965Sjdp 52633965Sjdpchar * 52733965Sjdpwhat (description) 52833965Sjdp char *description; 52933965Sjdp{ 53033965Sjdp printf (" %s : ", description); 53133965Sjdp gets (answer); 532104834Sobrien return xstrdup (answer); 53333965Sjdp} 53433965Sjdp 53533965Sjdpvoid 53633965Sjdpdestroy (string, value) 53733965Sjdp char *string; 53833965Sjdp char *value; 53933965Sjdp{ 54033965Sjdp free (string); 54133965Sjdp free (value); 54233965Sjdp} 54333965Sjdp 54433965Sjdpvoid 54533965Sjdpapplicatee (string, value) 54633965Sjdp char *string; 54733965Sjdp char *value; 54833965Sjdp{ 54933965Sjdp printf ("%.20s-%.20s\n", string, value); 55033965Sjdp} 55133965Sjdp 55277298Sobrien/* Determine number: what hash table to use. 55377298Sobrien Also determine h: points to hash_control. */ 55477298Sobrien 55560484Sobrienvoid 55677298Sobrienwhattable () 55733965Sjdp{ 55833965Sjdp for (;;) 55933965Sjdp { 56033965Sjdp printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); 56133965Sjdp gets (answer); 56233965Sjdp sscanf (answer, "%d", &number); 56333965Sjdp if (number >= 0 && number < TABLES) 56433965Sjdp { 56533965Sjdp h = hashtable[number]; 56633965Sjdp if (!h) 56733965Sjdp { 56833965Sjdp printf ("warning: current hash-table-#%d. has no hash-control\n", number); 56933965Sjdp } 57033965Sjdp return; 57133965Sjdp } 57233965Sjdp else 57333965Sjdp { 57433965Sjdp printf ("invalid hash table number: %d\n", number); 57533965Sjdp } 57633965Sjdp } 57733965Sjdp} 57833965Sjdp 57977298Sobrien#endif /* TEST */ 580