1 /* hash.c -- gas hash table code
2 Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
3 2000, 2001, 2002, 2003, 2005, 2007, 2008, 2009, 2011, 2013
4 Free Software Foundation, Inc.
6 This file is part of GAS, the GNU Assembler.
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 3, or (at your option)
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.
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, 51 Franklin Street - Fifth Floor, Boston, MA
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 assembler. 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
33 #include "safe-ctype.h"
36 /* An entry in a hash table. */
39 /* Next entry for this hash code. */
40 struct hash_entry
*next
;
41 /* String being hashed. */
43 /* Hash code. This is the full hash code, not the index into the
46 /* Pointer being stored in the hash table. */
54 struct hash_entry
**table
;
55 /* The number of slots in the hash table. */
57 /* An obstack for this hash table. */
58 struct obstack memory
;
60 #ifdef HASH_STATISTICS
62 unsigned long lookups
;
63 unsigned long hash_compares
;
64 unsigned long string_compares
;
65 unsigned long insertions
;
66 unsigned long replacements
;
67 unsigned long deletions
;
68 #endif /* HASH_STATISTICS */
71 /* The default number of entries to use when creating a hash table.
72 Note this value can be reduced to 4051 by using the command line
73 switch --reduce-memory-overheads, or set to other values by using
74 the --hash-size=<NUMBER> switch. */
76 static unsigned long gas_hash_table_size
= 65537;
79 set_gas_hash_table_size (unsigned long size
)
81 gas_hash_table_size
= bfd_hash_set_default_size (size
);
84 /* Create a hash table. This return a control block. */
87 hash_new_sized (unsigned long size
)
90 struct hash_control
*ret
;
92 ret
= (struct hash_control
*) xmalloc (sizeof *ret
);
93 obstack_begin (&ret
->memory
, chunksize
);
94 alloc
= size
* sizeof (struct hash_entry
*);
95 ret
->table
= (struct hash_entry
**) obstack_alloc (&ret
->memory
, alloc
);
96 memset (ret
->table
, 0, alloc
);
99 #ifdef HASH_STATISTICS
101 ret
->hash_compares
= 0;
102 ret
->string_compares
= 0;
104 ret
->replacements
= 0;
111 struct hash_control
*
114 return hash_new_sized (gas_hash_table_size
);
117 /* Delete a hash table, freeing all allocated memory. */
120 hash_die (struct hash_control
*table
)
122 obstack_free (&table
->memory
, 0);
126 /* Look up a string in a hash table. This returns a pointer to the
127 hash_entry, or NULL if the string is not in the table. If PLIST is
128 not NULL, this sets *PLIST to point to the start of the list which
129 would hold this hash entry. If PHASH is not NULL, this sets *PHASH
130 to the hash code for KEY.
132 Each time we look up a string, we move it to the start of the list
133 for its hash code, to take advantage of referential locality. */
135 static struct hash_entry
*
136 hash_lookup (struct hash_control
*table
, const char *key
, size_t len
,
137 struct hash_entry
***plist
, unsigned long *phash
)
143 struct hash_entry
**list
;
144 struct hash_entry
*p
;
145 struct hash_entry
*prev
;
147 #ifdef HASH_STATISTICS
152 for (n
= 0; n
< len
; n
++)
155 hash
+= c
+ (c
<< 17);
158 hash
+= len
+ (len
<< 17);
164 hindex
= hash
% table
->size
;
165 list
= table
->table
+ hindex
;
171 for (p
= *list
; p
!= NULL
; p
= p
->next
)
173 #ifdef HASH_STATISTICS
174 ++table
->hash_compares
;
179 #ifdef HASH_STATISTICS
180 ++table
->string_compares
;
183 if (strncmp (p
->string
, key
, len
) == 0 && p
->string
[len
] == '\0')
187 prev
->next
= p
->next
;
202 /* Insert an entry into a hash table. This returns NULL on success.
203 On error, it returns a printable string indicating the error. It
204 is considered to be an error if the entry already exists in the
208 hash_insert (struct hash_control
*table
, const char *key
, void *val
)
210 struct hash_entry
*p
;
211 struct hash_entry
**list
;
214 p
= hash_lookup (table
, key
, strlen (key
), &list
, &hash
);
218 #ifdef HASH_STATISTICS
222 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
233 /* Insert or replace an entry in a hash table. This returns NULL on
234 success. On error, it returns a printable string indicating the
235 error. If an entry already exists, its value is replaced. */
238 hash_jam (struct hash_control
*table
, const char *key
, void *val
)
240 struct hash_entry
*p
;
241 struct hash_entry
**list
;
244 p
= hash_lookup (table
, key
, strlen (key
), &list
, &hash
);
247 #ifdef HASH_STATISTICS
248 ++table
->replacements
;
255 #ifdef HASH_STATISTICS
259 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
271 /* Replace an existing entry in a hash table. This returns the old
272 value stored for the entry. If the entry is not found in the hash
273 table, this does nothing and returns NULL. */
276 hash_replace (struct hash_control
*table
, const char *key
, void *value
)
278 struct hash_entry
*p
;
281 p
= hash_lookup (table
, key
, strlen (key
), NULL
, NULL
);
285 #ifdef HASH_STATISTICS
286 ++table
->replacements
;
296 /* Find an entry in a hash table, returning its value. Returns NULL
297 if the entry is not found. */
300 hash_find (struct hash_control
*table
, const char *key
)
302 struct hash_entry
*p
;
304 p
= hash_lookup (table
, key
, strlen (key
), NULL
, NULL
);
311 /* As hash_find, but KEY is of length LEN and is not guaranteed to be
315 hash_find_n (struct hash_control
*table
, const char *key
, size_t len
)
317 struct hash_entry
*p
;
319 p
= hash_lookup (table
, key
, len
, NULL
, NULL
);
326 /* Delete an entry from a hash table. This returns the value stored
327 for that entry, or NULL if there is no such entry. */
330 hash_delete (struct hash_control
*table
, const char *key
, int freeme
)
332 struct hash_entry
*p
;
333 struct hash_entry
**list
;
335 p
= hash_lookup (table
, key
, strlen (key
), &list
, NULL
);
342 #ifdef HASH_STATISTICS
349 obstack_free (&table
->memory
, p
);
354 /* Traverse a hash table. Call the function on every entry in the
358 hash_traverse (struct hash_control
*table
,
359 void (*pfn
) (const char *key
, void *value
))
363 for (i
= 0; i
< table
->size
; ++i
)
365 struct hash_entry
*p
;
367 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
368 (*pfn
) (p
->string
, p
->data
);
372 /* Print hash table statistics on the specified file. NAME is the
373 name of the hash table, used for printing a header. */
376 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED
,
377 const char *name ATTRIBUTE_UNUSED
,
378 struct hash_control
*table ATTRIBUTE_UNUSED
)
380 #ifdef HASH_STATISTICS
385 fprintf (f
, "%s hash statistics:\n", name
);
386 fprintf (f
, "\t%lu lookups\n", table
->lookups
);
387 fprintf (f
, "\t%lu hash comparisons\n", table
->hash_compares
);
388 fprintf (f
, "\t%lu string comparisons\n", table
->string_compares
);
389 fprintf (f
, "\t%lu insertions\n", table
->insertions
);
390 fprintf (f
, "\t%lu replacements\n", table
->replacements
);
391 fprintf (f
, "\t%lu deletions\n", table
->deletions
);
395 for (i
= 0; i
< table
->size
; ++i
)
397 struct hash_entry
*p
;
399 if (table
->table
[i
] == NULL
)
403 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
408 fprintf (f
, "\t%g average chain length\n", (double) total
/ table
->size
);
409 fprintf (f
, "\t%lu empty slots\n", empty
);
415 /* This test program is left over from the old hash table code. */
417 /* Number of hash tables to maintain (at once) in any testing. */
420 /* We can have 12 statistics. */
421 #define STATBUFSIZE (12)
423 /* Display statistics here. */
424 int statbuf
[STATBUFSIZE
];
426 /* Human farts here. */
429 /* We test many hash tables at once. */
430 char *hashtable
[TABLES
];
432 /* Points to current hash_control. */
442 /* Number 0:TABLES-1 of current hashed symbol table. */
455 printf ("type h <RETURN> for help\n");
458 printf ("hash_test command: ");
461 command
= TOLOWER (command
); /* Ecch! */
465 printf ("old hash table #=%d.\n", number
);
469 for (pp
= hashtable
; pp
< hashtable
+ TABLES
; pp
++)
471 printf ("address of hash table #%d control block is %xx\n",
472 pp
- hashtable
, *pp
);
476 hash_traverse (h
, applicatee
);
479 hash_traverse (h
, destroy
);
483 p
= hash_find (h
, name
= what ("symbol"));
484 printf ("value of \"%s\" is \"%s\"\n", name
, p
? p
: "NOT-PRESENT");
487 printf ("# show old, select new default hash table number\n");
488 printf ("? display all hashtable control block addresses\n");
489 printf ("a apply a simple display-er to each symbol in table\n");
490 printf ("d die: destroy hashtable\n");
491 printf ("f find value of nominated symbol\n");
492 printf ("h this help\n");
493 printf ("i insert value into symbol\n");
494 printf ("j jam value into symbol\n");
495 printf ("n new hashtable\n");
496 printf ("r replace a value with another\n");
497 printf ("s say what %% of table is used\n");
498 printf ("q exit this program\n");
499 printf ("x delete a symbol from table, report its value\n");
502 p
= hash_insert (h
, name
= what ("symbol"), value
= what ("value"));
505 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
,
510 p
= hash_jam (h
, name
= what ("symbol"), value
= what ("value"));
513 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
, p
);
517 h
= hashtable
[number
] = (char *) hash_new ();
522 p
= hash_replace (h
, name
= what ("symbol"), value
= what ("value"));
523 printf ("old value was \"%s\"\n", p
? p
: "{}");
526 hash_say (h
, statbuf
, STATBUFSIZE
);
527 for (ip
= statbuf
; ip
< statbuf
+ STATBUFSIZE
; ip
++)
534 p
= hash_delete (h
, name
= what ("symbol"));
535 printf ("old value was \"%s\"\n", p
? p
: "{}");
538 printf ("I can't understand command \"%c\"\n", command
);
548 printf (" %s : ", description
);
550 return xstrdup (answer
);
554 destroy (string
, value
)
563 applicatee (string
, value
)
567 printf ("%.20s-%.20s\n", string
, value
);
570 /* Determine number: what hash table to use.
571 Also determine h: points to hash_control. */
578 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
580 sscanf (answer
, "%d", &number
);
581 if (number
>= 0 && number
< TABLES
)
583 h
= hashtable
[number
];
586 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
592 printf ("invalid hash table number: %d\n", number
);
This page took 0.041433 seconds and 4 git commands to generate.