1 /* hash.c -- gas hash table code
2 Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
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 2, 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, 59 Temple Place - Suite 330, 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 /* The default number of entries to use when creating a hash table. */
38 #define DEFAULT_SIZE (4051)
40 /* An entry in a hash table. */
43 /* Next entry for this hash code. */
44 struct hash_entry
*next
;
45 /* String being hashed. */
47 /* Hash code. This is the full hash code, not the index into the
50 /* Pointer being stored in the hash table. */
58 struct hash_entry
**table
;
59 /* The number of slots in the hash table. */
61 /* An obstack for this hash table. */
62 struct obstack memory
;
64 #ifdef HASH_STATISTICS
66 unsigned long lookups
;
67 unsigned long hash_compares
;
68 unsigned long string_compares
;
69 unsigned long insertions
;
70 unsigned long replacements
;
71 unsigned long deletions
;
72 #endif /* HASH_STATISTICS */
75 /* Create a hash table. This return a control block. */
81 struct hash_control
*ret
;
86 ret
= (struct hash_control
*) xmalloc (sizeof *ret
);
87 obstack_begin (&ret
->memory
, chunksize
);
88 alloc
= size
* sizeof (struct hash_entry
*);
89 ret
->table
= (struct hash_entry
**) obstack_alloc (&ret
->memory
, alloc
);
90 memset (ret
->table
, 0, alloc
);
93 #ifdef HASH_STATISTICS
95 ret
->hash_compares
= 0;
96 ret
->string_compares
= 0;
98 ret
->replacements
= 0;
105 /* Delete a hash table, freeing all allocated memory. */
108 hash_die (struct hash_control
*table
)
110 obstack_free (&table
->memory
, 0);
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.
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. */
123 static struct hash_entry
*hash_lookup (struct hash_control
*,
125 struct hash_entry
***,
128 static struct hash_entry
*
129 hash_lookup (struct hash_control
*table
, const char *key
,
130 struct hash_entry
***plist
, unsigned long *phash
)
132 register unsigned long hash
;
134 register const unsigned char *s
;
135 register unsigned int c
;
137 struct hash_entry
**list
;
138 struct hash_entry
*p
;
139 struct hash_entry
*prev
;
141 #ifdef HASH_STATISTICS
147 s
= (const unsigned char *) key
;
148 while ((c
= *s
++) != '\0')
150 hash
+= c
+ (c
<< 17);
154 hash
+= len
+ (len
<< 17);
160 index
= hash
% table
->size
;
161 list
= table
->table
+ index
;
167 for (p
= *list
; p
!= NULL
; p
= p
->next
)
169 #ifdef HASH_STATISTICS
170 ++table
->hash_compares
;
175 #ifdef HASH_STATISTICS
176 ++table
->string_compares
;
179 if (strcmp (p
->string
, key
) == 0)
183 prev
->next
= p
->next
;
198 /* Insert an entry into a hash table. This returns NULL on success.
199 On error, it returns a printable string indicating the error. It
200 is considered to be an error if the entry already exists in the
204 hash_insert (struct hash_control
*table
, const char *key
, PTR value
)
206 struct hash_entry
*p
;
207 struct hash_entry
**list
;
210 p
= hash_lookup (table
, key
, &list
, &hash
);
214 #ifdef HASH_STATISTICS
218 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
229 /* Insert or replace an entry in a hash table. This returns NULL on
230 success. On error, it returns a printable string indicating the
231 error. If an entry already exists, its value is replaced. */
234 hash_jam (struct hash_control
*table
, const char *key
, PTR value
)
236 struct hash_entry
*p
;
237 struct hash_entry
**list
;
240 p
= hash_lookup (table
, key
, &list
, &hash
);
243 #ifdef HASH_STATISTICS
244 ++table
->replacements
;
251 #ifdef HASH_STATISTICS
255 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
267 /* Replace an existing entry in a hash table. This returns the old
268 value stored for the entry. If the entry is not found in the hash
269 table, this does nothing and returns NULL. */
272 hash_replace (struct hash_control
*table
, const char *key
, PTR value
)
274 struct hash_entry
*p
;
277 p
= hash_lookup (table
, key
, NULL
, NULL
);
281 #ifdef HASH_STATISTICS
282 ++table
->replacements
;
292 /* Find an entry in a hash table, returning its value. Returns NULL
293 if the entry is not found. */
296 hash_find (struct hash_control
*table
, const char *key
)
298 struct hash_entry
*p
;
300 p
= hash_lookup (table
, key
, NULL
, NULL
);
307 /* Delete an entry from a hash table. This returns the value stored
308 for that entry, or NULL if there is no such entry. */
311 hash_delete (struct hash_control
*table
, const char *key
)
313 struct hash_entry
*p
;
314 struct hash_entry
**list
;
316 p
= hash_lookup (table
, key
, &list
, NULL
);
323 #ifdef HASH_STATISTICS
329 /* Note that we never reclaim the memory for this entry. If gas
330 ever starts deleting hash table entries in a big way, this will
336 /* Traverse a hash table. Call the function on every entry in the
340 hash_traverse (struct hash_control
*table
,
341 void (*pfn
) (const char *key
, PTR value
))
345 for (i
= 0; i
< table
->size
; ++i
)
347 struct hash_entry
*p
;
349 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
350 (*pfn
) (p
->string
, p
->data
);
354 /* Print hash table statistics on the specified file. NAME is the
355 name of the hash table, used for printing a header. */
358 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED
,
359 const char *name ATTRIBUTE_UNUSED
,
360 struct hash_control
*table ATTRIBUTE_UNUSED
)
362 #ifdef HASH_STATISTICS
367 fprintf (f
, "%s hash statistics:\n", name
);
368 fprintf (f
, "\t%lu lookups\n", table
->lookups
);
369 fprintf (f
, "\t%lu hash comparisons\n", table
->hash_compares
);
370 fprintf (f
, "\t%lu string comparisons\n", table
->string_compares
);
371 fprintf (f
, "\t%lu insertions\n", table
->insertions
);
372 fprintf (f
, "\t%lu replacements\n", table
->replacements
);
373 fprintf (f
, "\t%lu deletions\n", table
->deletions
);
377 for (i
= 0; i
< table
->size
; ++i
)
379 struct hash_entry
*p
;
381 if (table
->table
[i
] == NULL
)
385 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
390 fprintf (f
, "\t%g average chain length\n", (double) total
/ table
->size
);
391 fprintf (f
, "\t%lu empty slots\n", empty
);
397 /* This test program is left over from the old hash table code. */
399 /* Number of hash tables to maintain (at once) in any testing. */
402 /* We can have 12 statistics. */
403 #define STATBUFSIZE (12)
405 /* Display statistics here. */
406 int statbuf
[STATBUFSIZE
];
408 /* Human farts here. */
411 /* We test many hash tables at once. */
412 char *hashtable
[TABLES
];
414 /* Points to current hash_control. */
424 /* Number 0:TABLES-1 of current hashed symbol table. */
437 printf ("type h <RETURN> for help\n");
440 printf ("hash_test command: ");
443 command
= TOLOWER (command
); /* Ecch! */
447 printf ("old hash table #=%d.\n", number
);
451 for (pp
= hashtable
; pp
< hashtable
+ TABLES
; pp
++)
453 printf ("address of hash table #%d control block is %xx\n",
454 pp
- hashtable
, *pp
);
458 hash_traverse (h
, applicatee
);
461 hash_traverse (h
, destroy
);
465 p
= hash_find (h
, name
= what ("symbol"));
466 printf ("value of \"%s\" is \"%s\"\n", name
, p
? p
: "NOT-PRESENT");
469 printf ("# show old, select new default hash table number\n");
470 printf ("? display all hashtable control block addresses\n");
471 printf ("a apply a simple display-er to each symbol in table\n");
472 printf ("d die: destroy hashtable\n");
473 printf ("f find value of nominated symbol\n");
474 printf ("h this help\n");
475 printf ("i insert value into symbol\n");
476 printf ("j jam value into symbol\n");
477 printf ("n new hashtable\n");
478 printf ("r replace a value with another\n");
479 printf ("s say what %% of table is used\n");
480 printf ("q exit this program\n");
481 printf ("x delete a symbol from table, report its value\n");
484 p
= hash_insert (h
, name
= what ("symbol"), value
= what ("value"));
487 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
,
492 p
= hash_jam (h
, name
= what ("symbol"), value
= what ("value"));
495 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
, p
);
499 h
= hashtable
[number
] = (char *) hash_new ();
504 p
= hash_replace (h
, name
= what ("symbol"), value
= what ("value"));
505 printf ("old value was \"%s\"\n", p
? p
: "{}");
508 hash_say (h
, statbuf
, STATBUFSIZE
);
509 for (ip
= statbuf
; ip
< statbuf
+ STATBUFSIZE
; ip
++)
516 p
= hash_delete (h
, name
= what ("symbol"));
517 printf ("old value was \"%s\"\n", p
? p
: "{}");
520 printf ("I can't understand command \"%c\"\n", command
);
530 printf (" %s : ", description
);
532 return xstrdup (answer
);
536 destroy (string
, value
)
545 applicatee (string
, value
)
549 printf ("%.20s-%.20s\n", string
, value
);
552 /* Determine number: what hash table to use.
553 Also determine h: points to hash_control. */
560 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
562 sscanf (answer
, "%d", &number
);
563 if (number
>= 0 && number
< TABLES
)
565 h
= hashtable
[number
];
568 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
574 printf ("invalid hash table number: %d\n", number
);
This page took 0.040889 seconds and 4 git commands to generate.