| 1 | /* hash.c -- gas hash table code
|
|---|
| 2 | Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
|
|---|
| 3 | 2000
|
|---|
| 4 | Free Software Foundation, Inc.
|
|---|
| 5 |
|
|---|
| 6 | This file is part of GAS, the GNU Assembler.
|
|---|
| 7 |
|
|---|
| 8 | GAS is free software; you can redistribute it and/or modify
|
|---|
| 9 | it under the terms of the GNU General Public License as published by
|
|---|
| 10 | the Free Software Foundation; either version 2, or (at your option)
|
|---|
| 11 | any later version.
|
|---|
| 12 |
|
|---|
| 13 | GAS is distributed in the hope that it will be useful,
|
|---|
| 14 | but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|---|
| 16 | GNU General Public License for more details.
|
|---|
| 17 |
|
|---|
| 18 | You should have received a copy of the GNU General Public License
|
|---|
| 19 | along with GAS; see the file COPYING. If not, write to the Free
|
|---|
| 20 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA
|
|---|
| 21 | 02111-1307, USA. */
|
|---|
| 22 |
|
|---|
| 23 | /* This version of the hash table code is a wholescale replacement of
|
|---|
| 24 | the old hash table code, which was fairly bad. This is based on
|
|---|
| 25 | the hash table code in BFD, but optimized slightly for the
|
|---|
| 26 | asssembler. The assembler does not need to derive structures that
|
|---|
| 27 | are stored in the hash table. Instead, it always stores a pointer.
|
|---|
| 28 | The assembler uses the hash table mostly to store symbols, and we
|
|---|
| 29 | don't need to confuse the symbol structure with a hash table
|
|---|
| 30 | structure. */
|
|---|
| 31 |
|
|---|
| 32 | #include "as.h"
|
|---|
| 33 | #include "obstack.h"
|
|---|
| 34 |
|
|---|
| 35 | /* The default number of entries to use when creating a hash table. */
|
|---|
| 36 |
|
|---|
| 37 | #define DEFAULT_SIZE (4051)
|
|---|
| 38 |
|
|---|
| 39 | /* An entry in a hash table. */
|
|---|
| 40 |
|
|---|
| 41 | struct hash_entry {
|
|---|
| 42 | /* Next entry for this hash code. */
|
|---|
| 43 | struct hash_entry *next;
|
|---|
| 44 | /* String being hashed. */
|
|---|
| 45 | const char *string;
|
|---|
| 46 | /* Hash code. This is the full hash code, not the index into the
|
|---|
| 47 | table. */
|
|---|
| 48 | unsigned long hash;
|
|---|
| 49 | /* Pointer being stored in the hash table. */
|
|---|
| 50 | PTR data;
|
|---|
| 51 | };
|
|---|
| 52 |
|
|---|
| 53 | /* A hash table. */
|
|---|
| 54 |
|
|---|
| 55 | struct hash_control {
|
|---|
| 56 | /* The hash array. */
|
|---|
| 57 | struct hash_entry **table;
|
|---|
| 58 | /* The number of slots in the hash table. */
|
|---|
| 59 | unsigned int size;
|
|---|
| 60 | /* An obstack for this hash table. */
|
|---|
| 61 | struct obstack memory;
|
|---|
| 62 |
|
|---|
| 63 | #ifdef HASH_STATISTICS
|
|---|
| 64 | /* Statistics. */
|
|---|
| 65 | unsigned long lookups;
|
|---|
| 66 | unsigned long hash_compares;
|
|---|
| 67 | unsigned long string_compares;
|
|---|
| 68 | unsigned long insertions;
|
|---|
| 69 | unsigned long replacements;
|
|---|
| 70 | unsigned long deletions;
|
|---|
| 71 | #endif /* HASH_STATISTICS */
|
|---|
| 72 | };
|
|---|
| 73 |
|
|---|
| 74 | /* Create a hash table. This return a control block. */
|
|---|
| 75 |
|
|---|
| 76 | struct hash_control *
|
|---|
| 77 | hash_new ()
|
|---|
| 78 | {
|
|---|
| 79 | unsigned int size;
|
|---|
| 80 | struct hash_control *ret;
|
|---|
| 81 | unsigned int alloc;
|
|---|
| 82 |
|
|---|
| 83 | size = DEFAULT_SIZE;
|
|---|
| 84 |
|
|---|
| 85 | ret = (struct hash_control *) xmalloc (sizeof *ret);
|
|---|
| 86 | obstack_begin (&ret->memory, chunksize);
|
|---|
| 87 | alloc = size * sizeof (struct hash_entry *);
|
|---|
| 88 | ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
|
|---|
| 89 | memset (ret->table, 0, alloc);
|
|---|
| 90 | ret->size = size;
|
|---|
| 91 |
|
|---|
| 92 | #ifdef HASH_STATISTICS
|
|---|
| 93 | ret->lookups = 0;
|
|---|
| 94 | ret->hash_compares = 0;
|
|---|
| 95 | ret->string_compares = 0;
|
|---|
| 96 | ret->insertions = 0;
|
|---|
| 97 | ret->replacements = 0;
|
|---|
| 98 | ret->deletions = 0;
|
|---|
| 99 | #endif
|
|---|
| 100 |
|
|---|
| 101 | return ret;
|
|---|
| 102 | }
|
|---|
| 103 |
|
|---|
| 104 | /* Delete a hash table, freeing all allocated memory. */
|
|---|
| 105 |
|
|---|
| 106 | void
|
|---|
| 107 | hash_die (table)
|
|---|
| 108 | struct hash_control *table;
|
|---|
| 109 | {
|
|---|
| 110 | obstack_free (&table->memory, 0);
|
|---|
| 111 | free (table);
|
|---|
| 112 | }
|
|---|
| 113 |
|
|---|
| 114 | /* Look up a string in a hash table. This returns a pointer to the
|
|---|
| 115 | hash_entry, or NULL if the string is not in the table. If PLIST is
|
|---|
| 116 | not NULL, this sets *PLIST to point to the start of the list which
|
|---|
| 117 | would hold this hash entry. If PHASH is not NULL, this sets *PHASH
|
|---|
| 118 | to the hash code for KEY.
|
|---|
| 119 |
|
|---|
| 120 | Each time we look up a string, we move it to the start of the list
|
|---|
| 121 | for its hash code, to take advantage of referential locality. */
|
|---|
| 122 |
|
|---|
| 123 | static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
|
|---|
| 124 | const char *,
|
|---|
| 125 | struct hash_entry ***,
|
|---|
| 126 | unsigned long *));
|
|---|
| 127 |
|
|---|
| 128 | static struct hash_entry *
|
|---|
| 129 | hash_lookup (table, key, plist, phash)
|
|---|
| 130 | struct hash_control *table;
|
|---|
| 131 | const char *key;
|
|---|
| 132 | struct hash_entry ***plist;
|
|---|
| 133 | unsigned long *phash;
|
|---|
| 134 | {
|
|---|
| 135 | register unsigned long hash;
|
|---|
| 136 | unsigned int len;
|
|---|
| 137 | register const unsigned char *s;
|
|---|
| 138 | register unsigned int c;
|
|---|
| 139 | unsigned int index;
|
|---|
| 140 | struct hash_entry **list;
|
|---|
| 141 | struct hash_entry *p;
|
|---|
| 142 | struct hash_entry *prev;
|
|---|
| 143 |
|
|---|
| 144 | #ifdef HASH_STATISTICS
|
|---|
| 145 | ++table->lookups;
|
|---|
|
|---|
