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
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
= size
;
84 /* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size(). */
86 get_gas_hash_table_size (void)
88 /* Extend this prime list if you want more granularity of hash table size. */
89 static const unsigned long hash_size_primes
[] =
91 1021, 4051, 8599, 16699, 65537
95 /* Work out the best prime number near the hash_size.
96 FIXME: This could be a more sophisticated algorithm,
97 but is it really worth implementing it ? */
98 for (hindex
= 0; hindex
< ARRAY_SIZE (hash_size_primes
) - 1; ++ hindex
)
99 if (gas_hash_table_size
<= hash_size_primes
[hindex
])
102 return hash_size_primes
[hindex
];
105 /* Create a hash table. This return a control block. */
107 struct hash_control
*
112 struct hash_control
*ret
;
114 size
= get_gas_hash_table_size ();
116 ret
= (struct hash_control
*) xmalloc (sizeof *ret
);
117 obstack_begin (&ret
->memory
, chunksize
);
118 alloc
= size
* sizeof (struct hash_entry
*);
119 ret
->table
= (struct hash_entry
**) obstack_alloc (&ret
->memory
, alloc
);
120 memset (ret
->table
, 0, alloc
);
123 #ifdef HASH_STATISTICS
125 ret
->hash_compares
= 0;
126 ret
->string_compares
= 0;
128 ret
->replacements
= 0;
135 /* Delete a hash table, freeing all allocated memory. */
138 hash_die (struct hash_control
*table
)
140 obstack_free (&table
->memory
, 0);
144 /* Look up a string in a hash table. This returns a pointer to the
145 hash_entry, or NULL if the string is not in the table. If PLIST is
146 not NULL, this sets *PLIST to point to the start of the list which
147 would hold this hash entry. If PHASH is not NULL, this sets *PHASH
148 to the hash code for KEY.
150 Each time we look up a string, we move it to the start of the list
151 for its hash code, to take advantage of referential locality. */
153 static struct hash_entry
*
154 hash_lookup (struct hash_control
*table
, const char *key
, size_t len
,
155 struct hash_entry
***plist
, unsigned long *phash
)
161 struct hash_entry
**list
;
162 struct hash_entry
*p
;
163 struct hash_entry
*prev
;
165 #ifdef HASH_STATISTICS
170 for (n
= 0; n
< len
; n
++)
173 hash
+= c
+ (c
<< 17);
176 hash
+= len
+ (len
<< 17);
182 hindex
= hash
% table
->size
;
183 list
= table
->table
+ hindex
;
189 for (p
= *list
; p
!= NULL
; p
= p
->next
)
191 #ifdef HASH_STATISTICS
192 ++table
->hash_compares
;
197 #ifdef HASH_STATISTICS
198 ++table
->string_compares
;
201 if (strncmp (p
->string
, key
, len
) == 0 && p
->string
[len
] == '\0')
205 prev
->next
= p
->next
;
220 /* Insert an entry into a hash table. This returns NULL on success.
221 On error, it returns a printable string indicating the error. It
222 is considered to be an error if the entry already exists in the
226 hash_insert (struct hash_control
*table
, const char *key
, void *val
)
228 struct hash_entry
*p
;
229 struct hash_entry
**list
;
232 p
= hash_lookup (table
, key
, strlen (key
), &list
, &hash
);
236 #ifdef HASH_STATISTICS
240 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
251 /* Insert or replace an entry in a hash table. This returns NULL on
252 success. On error, it returns a printable string indicating the
253 error. If an entry already exists, its value is replaced. */
256 hash_jam (struct hash_control
*table
, const char *key
, void *val
)
258 struct hash_entry
*p
;
259 struct hash_entry
**list
;
262 p
= hash_lookup (table
, key
, strlen (key
), &list
, &hash
);
265 #ifdef HASH_STATISTICS
266 ++table
->replacements
;
273 #ifdef HASH_STATISTICS
277 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
289 /* Replace an existing entry in a hash table. This returns the old
290 value stored for the entry. If the entry is not found in the hash
291 table, this does nothing and returns NULL. */
294 hash_replace (struct hash_control
*table
, const char *key
, void *value
)
296 struct hash_entry
*p
;
299 p
= hash_lookup (table
, key
, strlen (key
), NULL
, NULL
);
303 #ifdef HASH_STATISTICS
304 ++table
->replacements
;
314 /* Find an entry in a hash table, returning its value. Returns NULL
315 if the entry is not found. */
318 hash_find (struct hash_control
*table
, const char *key
)
320 struct hash_entry
*p
;
322 p
= hash_lookup (table
, key
, strlen (key
), NULL
, NULL
);
329 /* As hash_find, but KEY is of length LEN and is not guaranteed to be
333 hash_find_n (struct hash_control
*table
, const char *key
, size_t len
)
335 struct hash_entry
*p
;
337 p
= hash_lookup (table
, key
, len
, NULL
, NULL
);
344 /* Delete an entry from a hash table. This returns the value stored
345 for that entry, or NULL if there is no such entry. */
348 hash_delete (struct hash_control
*table
, const char *key
, int freeme
)
350 struct hash_entry
*p
;
351 struct hash_entry
**list
;
353 p
= hash_lookup (table
, key
, strlen (key
), &list
, NULL
);
360 #ifdef HASH_STATISTICS
367 obstack_free (&table
->memory
, p
);
372 /* Traverse a hash table. Call the function on every entry in the
376 hash_traverse (struct hash_control
*table
,
377 void (*pfn
) (const char *key
, void *value
))
381 for (i
= 0; i
< table
->size
; ++i
)
383 struct hash_entry
*p
;
385 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
386 (*pfn
) (p
->string
, p
->data
);
390 /* Print hash table statistics on the specified file. NAME is the
391 name of the hash table, used for printing a header. */
394 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED
,
395 const char *name ATTRIBUTE_UNUSED
,
396 struct hash_control
*table ATTRIBUTE_UNUSED
)
398 #ifdef HASH_STATISTICS
403 fprintf (f
, "%s hash statistics:\n", name
);
404 fprintf (f
, "\t%lu lookups\n", table
->lookups
);
405 fprintf (f
, "\t%lu hash comparisons\n", table
->hash_compares
);
406 fprintf (f
, "\t%lu string comparisons\n", table
->string_compares
);
407 fprintf (f
, "\t%lu insertions\n", table
->insertions
);
408 fprintf (f
, "\t%lu replacements\n", table
->replacements
);
409 fprintf (f
, "\t%lu deletions\n", table
->deletions
);
413 for (i
= 0; i
< table
->size
; ++i
)
415 struct hash_entry
*p
;
417 if (table
->table
[i
] == NULL
)
421 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
426 fprintf (f
, "\t%g average chain length\n", (double) total
/ table
->size
);
427 fprintf (f
, "\t%lu empty slots\n", empty
);
433 /* This test program is left over from the old hash table code. */
435 /* Number of hash tables to maintain (at once) in any testing. */
438 /* We can have 12 statistics. */
439 #define STATBUFSIZE (12)
441 /* Display statistics here. */
442 int statbuf
[STATBUFSIZE
];
444 /* Human farts here. */
447 /* We test many hash tables at once. */
448 char *hashtable
[TABLES
];
450 /* Points to current hash_control. */
460 /* Number 0:TABLES-1 of current hashed symbol table. */
473 printf ("type h <RETURN> for help\n");
476 printf ("hash_test command: ");
479 command
= TOLOWER (command
); /* Ecch! */
483 printf ("old hash table #=%d.\n", number
);
487 for (pp
= hashtable
; pp
< hashtable
+ TABLES
; pp
++)
489 printf ("address of hash table #%d control block is %xx\n",
490 pp
- hashtable
, *pp
);
494 hash_traverse (h
, applicatee
);
497 hash_traverse (h
, destroy
);
501 p
= hash_find (h
, name
= what ("symbol"));
502 printf ("value of \"%s\" is \"%s\"\n", name
, p
? p
: "NOT-PRESENT");
505 printf ("# show old, select new default hash table number\n");
506 printf ("? display all hashtable control block addresses\n");
507 printf ("a apply a simple display-er to each symbol in table\n");
508 printf ("d die: destroy hashtable\n");
509 printf ("f find value of nominated symbol\n");
510 printf ("h this help\n");
511 printf ("i insert value into symbol\n");
512 printf ("j jam value into symbol\n");
513 printf ("n new hashtable\n");
514 printf ("r replace a value with another\n");
515 printf ("s say what %% of table is used\n");
516 printf ("q exit this program\n");
517 printf ("x delete a symbol from table, report its value\n");
520 p
= hash_insert (h
, name
= what ("symbol"), value
= what ("value"));
523 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
,
528 p
= hash_jam (h
, name
= what ("symbol"), value
= what ("value"));
531 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
, p
);
535 h
= hashtable
[number
] = (char *) hash_new ();
540 p
= hash_replace (h
, name
= what ("symbol"), value
= what ("value"));
541 printf ("old value was \"%s\"\n", p
? p
: "{}");
544 hash_say (h
, statbuf
, STATBUFSIZE
);
545 for (ip
= statbuf
; ip
< statbuf
+ STATBUFSIZE
; ip
++)
552 p
= hash_delete (h
, name
= what ("symbol"));
553 printf ("old value was \"%s\"\n", p
? p
: "{}");
556 printf ("I can't understand command \"%c\"\n", command
);
566 printf (" %s : ", description
);
568 return xstrdup (answer
);
572 destroy (string
, value
)
581 applicatee (string
, value
)
585 printf ("%.20s-%.20s\n", string
, value
);
588 /* Determine number: what hash table to use.
589 Also determine h: points to hash_control. */
596 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
598 sscanf (answer
, "%d", &number
);
599 if (number
>= 0 && number
< TABLES
)
601 h
= hashtable
[number
];
604 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
610 printf ("invalid hash table number: %d\n", number
);
This page took 0.041328 seconds and 4 git commands to generate.