1 /* hash.c -- gas hash table code
2 Copyright (C) 1987-2020 Free Software Foundation, Inc.
4 This file is part of GAS, the GNU Assembler.
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 3, or (at your option)
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.
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 the Free
18 Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
21 /* This version of the hash table code is a wholescale replacement of
22 the old hash table code, which was fairly bad. This is based on
23 the hash table code in BFD, but optimized slightly for the
24 assembler. The assembler does not need to derive structures that
25 are stored in the hash table. Instead, it always stores a pointer.
26 The assembler uses the hash table mostly to store symbols, and we
27 don't need to confuse the symbol structure with a hash table
31 #include "safe-ctype.h"
34 /* An entry in a hash table. */
37 /* Next entry for this hash code. */
38 struct hash_entry
*next
;
39 /* String being hashed. */
41 /* Hash code. This is the full hash code, not the index into the
44 /* Pointer being stored in the hash table. */
52 struct hash_entry
**table
;
53 /* The number of slots in the hash table. */
55 /* An obstack for this hash table. */
56 struct obstack memory
;
58 #ifdef HASH_STATISTICS
60 unsigned long lookups
;
61 unsigned long hash_compares
;
62 unsigned long string_compares
;
63 unsigned long insertions
;
64 unsigned long replacements
;
65 unsigned long deletions
;
66 #endif /* HASH_STATISTICS */
69 /* The default number of entries to use when creating a hash table.
70 Note this value can be reduced to 4051 by using the command line
71 switch --reduce-memory-overheads, or set to other values by using
72 the --hash-size=<NUMBER> switch. */
74 static unsigned long gas_hash_table_size
= 65537;
77 set_gas_hash_table_size (unsigned long size
)
79 gas_hash_table_size
= bfd_hash_set_default_size (size
);
82 /* Create a hash table. This return a control block. */
85 hash_new_sized (unsigned long size
)
88 struct hash_control
*ret
;
90 ret
= XNEW (struct hash_control
);
91 obstack_begin (&ret
->memory
, chunksize
);
92 alloc
= size
* sizeof (struct hash_entry
*);
93 ret
->table
= (struct hash_entry
**) obstack_alloc (&ret
->memory
, alloc
);
94 memset (ret
->table
, 0, alloc
);
97 #ifdef HASH_STATISTICS
99 ret
->hash_compares
= 0;
100 ret
->string_compares
= 0;
102 ret
->replacements
= 0;
109 struct hash_control
*
112 return hash_new_sized (gas_hash_table_size
);
115 /* Delete a hash table, freeing all allocated memory. */
118 hash_die (struct hash_control
*table
)
120 obstack_free (&table
->memory
, 0);
124 /* Look up a string in a hash table. This returns a pointer to the
125 hash_entry, or NULL if the string is not in the table. If PLIST is
126 not NULL, this sets *PLIST to point to the start of the list which
127 would hold this hash entry. If PHASH is not NULL, this sets *PHASH
128 to the hash code for KEY.
130 Each time we look up a string, we move it to the start of the list
131 for its hash code, to take advantage of referential locality. */
133 static struct hash_entry
*
134 hash_lookup (struct hash_control
*table
, const char *key
, size_t len
,
135 struct hash_entry
***plist
, unsigned long *phash
)
141 struct hash_entry
**list
;
142 struct hash_entry
*p
;
143 struct hash_entry
*prev
;
145 #ifdef HASH_STATISTICS
150 for (n
= 0; n
< len
; n
++)
153 hash
+= c
+ (c
<< 17);
156 hash
+= len
+ (len
<< 17);
162 hindex
= hash
% table
->size
;
163 list
= table
->table
+ hindex
;
169 for (p
= *list
; p
!= NULL
; p
= p
->next
)
171 #ifdef HASH_STATISTICS
172 ++table
->hash_compares
;
177 #ifdef HASH_STATISTICS
178 ++table
->string_compares
;
181 if (strncmp (p
->string
, key
, len
) == 0 && p
->string
[len
] == '\0')
185 prev
->next
= p
->next
;
200 /* Insert an entry into a hash table. This returns NULL on success.
201 On error, it returns a printable string indicating the error. It
202 is considered to be an error if the entry already exists in the
206 hash_insert (struct hash_control
*table
, const char *key
, void *val
)
208 struct hash_entry
*p
;
209 struct hash_entry
**list
;
212 p
= hash_lookup (table
, key
, strlen (key
), &list
, &hash
);
216 #ifdef HASH_STATISTICS
220 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
231 /* Insert or replace an entry in a hash table. This returns NULL on
232 success. On error, it returns a printable string indicating the
233 error. If an entry already exists, its value is replaced. */
236 hash_jam (struct hash_control
*table
, const char *key
, void *val
)
238 struct hash_entry
*p
;
239 struct hash_entry
**list
;
242 p
= hash_lookup (table
, key
, strlen (key
), &list
, &hash
);
245 #ifdef HASH_STATISTICS
246 ++table
->replacements
;
253 #ifdef HASH_STATISTICS
257 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
269 /* Replace an existing entry in a hash table. This returns the old
270 value stored for the entry. If the entry is not found in the hash
271 table, this does nothing and returns NULL. */
274 hash_replace (struct hash_control
*table
, const char *key
, void *value
)
276 struct hash_entry
*p
;
279 p
= hash_lookup (table
, key
, strlen (key
), NULL
, NULL
);
283 #ifdef HASH_STATISTICS
284 ++table
->replacements
;
294 /* Find an entry in a hash table, returning its value. Returns NULL
295 if the entry is not found. */
298 hash_find (struct hash_control
*table
, const char *key
)
300 struct hash_entry
*p
;
302 p
= hash_lookup (table
, key
, strlen (key
), NULL
, NULL
);
309 /* As hash_find, but KEY is of length LEN and is not guaranteed to be
313 hash_find_n (struct hash_control
*table
, const char *key
, size_t len
)
315 struct hash_entry
*p
;
317 p
= hash_lookup (table
, key
, len
, NULL
, NULL
);
324 /* Delete an entry from a hash table. This returns the value stored
325 for that entry, or NULL if there is no such entry. */
328 hash_delete (struct hash_control
*table
, const char *key
, int freeme
)
330 struct hash_entry
*p
;
331 struct hash_entry
**list
;
333 p
= hash_lookup (table
, key
, strlen (key
), &list
, NULL
);
340 #ifdef HASH_STATISTICS
347 obstack_free (&table
->memory
, p
);
352 /* Traverse a hash table. Call the function on every entry in the
356 hash_traverse (struct hash_control
*table
,
357 void (*pfn
) (const char *key
, void *value
))
361 for (i
= 0; i
< table
->size
; ++i
)
363 struct hash_entry
*p
;
365 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
366 (*pfn
) (p
->string
, p
->data
);
370 /* Print hash table statistics on the specified file. NAME is the
371 name of the hash table, used for printing a header. */
374 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED
,
375 const char *name ATTRIBUTE_UNUSED
,
376 struct hash_control
*table ATTRIBUTE_UNUSED
)
378 #ifdef HASH_STATISTICS
383 fprintf (f
, "%s hash statistics:\n", name
);
384 fprintf (f
, "\t%lu lookups\n", table
->lookups
);
385 fprintf (f
, "\t%lu hash comparisons\n", table
->hash_compares
);
386 fprintf (f
, "\t%lu string comparisons\n", table
->string_compares
);
387 fprintf (f
, "\t%lu insertions\n", table
->insertions
);
388 fprintf (f
, "\t%lu replacements\n", table
->replacements
);
389 fprintf (f
, "\t%lu deletions\n", table
->deletions
);
393 for (i
= 0; i
< table
->size
; ++i
)
395 struct hash_entry
*p
;
397 if (table
->table
[i
] == NULL
)
401 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
406 fprintf (f
, "\t%g average chain length\n", (double) total
/ table
->size
);
407 fprintf (f
, "\t%lu empty slots\n", empty
);
411 /* Insert ELEMENT into HTAB. If the element exists, it is overwritten. */
414 htab_insert (htab_t htab
, PTR element
)
416 void **slot
= htab_find_slot (htab
, element
, INSERT
);
417 if (slot
!= NULL
&& htab
->del_f
)
418 (*htab
->del_f
) (*slot
);
423 /* Print statistics about a hash table. */
426 htab_print_statistics (FILE *f
, const char *name
, htab_t table
)
428 fprintf (f
, "%s hash statistics:\n", name
);
429 fprintf (f
, "\t%u searches\n", table
->searches
);
430 fprintf (f
, "\t%u collisions\n", table
->collisions
);
431 fprintf (f
, "\t%lu elements\n", (unsigned long) htab_elements (table
));
432 fprintf (f
, "\t%lu table size\n", (unsigned long) htab_size (table
));
437 /* This test program is left over from the old hash table code. */
439 /* Number of hash tables to maintain (at once) in any testing. */
442 /* We can have 12 statistics. */
443 #define STATBUFSIZE (12)
445 /* Display statistics here. */
446 int statbuf
[STATBUFSIZE
];
448 /* Human farts here. */
451 /* We test many hash tables at once. */
452 char *hashtable
[TABLES
];
454 /* Points to current hash_control. */
464 /* Number 0:TABLES-1 of current hashed symbol table. */
477 printf ("type h <RETURN> for help\n");
480 printf ("hash_test command: ");
483 command
= TOLOWER (command
); /* Ecch! */
487 printf ("old hash table #=%d.\n", number
);
491 for (pp
= hashtable
; pp
< hashtable
+ TABLES
; pp
++)
493 printf ("address of hash table #%d control block is %xx\n",
494 pp
- hashtable
, *pp
);
498 hash_traverse (h
, applicatee
);
501 hash_traverse (h
, destroy
);
505 p
= hash_find (h
, name
= what ("symbol"));
506 printf ("value of \"%s\" is \"%s\"\n", name
, p
? p
: "NOT-PRESENT");
509 printf ("# show old, select new default hash table number\n");
510 printf ("? display all hashtable control block addresses\n");
511 printf ("a apply a simple display-er to each symbol in table\n");
512 printf ("d die: destroy hashtable\n");
513 printf ("f find value of nominated symbol\n");
514 printf ("h this help\n");
515 printf ("i insert value into symbol\n");
516 printf ("j jam value into symbol\n");
517 printf ("n new hashtable\n");
518 printf ("r replace a value with another\n");
519 printf ("s say what %% of table is used\n");
520 printf ("q exit this program\n");
521 printf ("x delete a symbol from table, report its value\n");
524 p
= hash_insert (h
, name
= what ("symbol"), value
= what ("value"));
527 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
,
532 p
= hash_jam (h
, name
= what ("symbol"), value
= what ("value"));
535 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
, p
);
539 h
= hashtable
[number
] = (char *) hash_new ();
544 p
= hash_replace (h
, name
= what ("symbol"), value
= what ("value"));
545 printf ("old value was \"%s\"\n", p
? p
: "{}");
548 hash_say (h
, statbuf
, STATBUFSIZE
);
549 for (ip
= statbuf
; ip
< statbuf
+ STATBUFSIZE
; ip
++)
556 p
= hash_delete (h
, name
= what ("symbol"));
557 printf ("old value was \"%s\"\n", p
? p
: "{}");
560 printf ("I can't understand command \"%c\"\n", command
);
570 printf (" %s : ", description
);
572 return xstrdup (answer
);
576 destroy (string
, value
)
585 applicatee (string
, value
)
589 printf ("%.20s-%.20s\n", string
, value
);
592 /* Determine number: what hash table to use.
593 Also determine h: points to hash_control. */
600 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
602 sscanf (answer
, "%d", &number
);
603 if (number
>= 0 && number
< TABLES
)
605 h
= hashtable
[number
];
608 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
614 printf ("invalid hash table number: %d\n", number
);