1 /* hash.c -- gas hash table code
2 Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 99, 2000
3 Free Software Foundation, Inc.
5 This file is part of GAS, the GNU Assembler.
7 GAS is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GAS is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GAS; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This version of the hash table code is a wholescale replacement of
23 the old hash table code, which was fairly bad. This is based on
24 the hash table code in BFD, but optimized slightly for the
25 asssembler. The assembler does not need to derive structures that
26 are stored in the hash table. Instead, it always stores a pointer.
27 The assembler uses the hash table mostly to store symbols, and we
28 don't need to confuse the symbol structure with a hash table
34 /* The default number of entries to use when creating a hash table. */
36 #define DEFAULT_SIZE (4051)
38 /* An entry in a hash table. */
42 /* Next entry for this hash code. */
43 struct hash_entry
*next
;
44 /* String being hashed. */
46 /* Hash code. This is the full hash code, not the index into the
49 /* 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. */
109 struct hash_control
*table
;
111 obstack_free (&table
->memory
, 0);
115 /* Look up a string in a hash table. This returns a pointer to the
116 hash_entry, or NULL if the string is not in the table. If PLIST is
117 not NULL, this sets *PLIST to point to the start of the list which
118 would hold this hash entry. If PHASH is not NULL, this sets *PHASH
119 to the hash code for KEY.
121 Each time we look up a string, we move it to the start of the list
122 for its hash code, to take advantage of referential locality. */
124 static struct hash_entry
*hash_lookup
PARAMS ((struct hash_control
*,
126 struct hash_entry
***,
129 static struct hash_entry
*
130 hash_lookup (table
, key
, plist
, phash
)
131 struct hash_control
*table
;
133 struct hash_entry
***plist
;
134 unsigned long *phash
;
136 register unsigned long hash
;
138 register const unsigned char *s
;
139 register unsigned int c
;
141 struct hash_entry
**list
;
142 struct hash_entry
*p
;
143 struct hash_entry
*prev
;
145 #ifdef HASH_STATISTICS
151 s
= (const unsigned char *) key
;
152 while ((c
= *s
++) != '\0')
154 hash
+= c
+ (c
<< 17);
158 hash
+= len
+ (len
<< 17);
164 index
= hash
% table
->size
;
165 list
= table
->table
+ index
;
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 (strcmp (p
->string
, key
) == 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 (table
, key
, value
)
209 struct hash_control
*table
;
213 struct hash_entry
*p
;
214 struct hash_entry
**list
;
217 p
= hash_lookup (table
, key
, &list
, &hash
);
221 #ifdef HASH_STATISTICS
225 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
236 /* Insert or replace an entry in a hash table. This returns NULL on
237 success. On error, it returns a printable string indicating the
238 error. If an entry already exists, its value is replaced. */
241 hash_jam (table
, key
, value
)
242 struct hash_control
*table
;
246 struct hash_entry
*p
;
247 struct hash_entry
**list
;
250 p
= hash_lookup (table
, key
, &list
, &hash
);
253 #ifdef HASH_STATISTICS
254 ++table
->replacements
;
261 #ifdef HASH_STATISTICS
265 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
277 /* Replace an existing entry in a hash table. This returns the old
278 value stored for the entry. If the entry is not found in the hash
279 table, this does nothing and returns NULL. */
282 hash_replace (table
, key
, value
)
283 struct hash_control
*table
;
287 struct hash_entry
*p
;
290 p
= hash_lookup (table
, key
, NULL
, NULL
);
294 #ifdef HASH_STATISTICS
295 ++table
->replacements
;
305 /* Find an entry in a hash table, returning its value. Returns NULL
306 if the entry is not found. */
309 hash_find (table
, key
)
310 struct hash_control
*table
;
313 struct hash_entry
*p
;
315 p
= hash_lookup (table
, key
, NULL
, NULL
);
322 /* Delete an entry from a hash table. This returns the value stored
323 for that entry, or NULL if there is no such entry. */
326 hash_delete (table
, key
)
327 struct hash_control
*table
;
330 struct hash_entry
*p
;
331 struct hash_entry
**list
;
333 p
= hash_lookup (table
, key
, &list
, NULL
);
340 #ifdef HASH_STATISTICS
346 /* Note that we never reclaim the memory for this entry. If gas
347 ever starts deleting hash table entries in a big way, this will
353 /* Traverse a hash table. Call the function on every entry in the
357 hash_traverse (table
, pfn
)
358 struct hash_control
*table
;
359 void (*pfn
) PARAMS ((const char *key
, PTR 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 (f
, name
, table
)
377 FILE *f ATTRIBUTE_UNUSED
;
378 const char *name ATTRIBUTE_UNUSED
;
379 struct hash_control
*table ATTRIBUTE_UNUSED
;
381 #ifdef HASH_STATISTICS
386 fprintf (f
, "%s hash statistics:\n", name
);
387 fprintf (f
, "\t%lu lookups\n", table
->lookups
);
388 fprintf (f
, "\t%lu hash comparisons\n", table
->hash_compares
);
389 fprintf (f
, "\t%lu string comparisons\n", table
->string_compares
);
390 fprintf (f
, "\t%lu insertions\n", table
->insertions
);
391 fprintf (f
, "\t%lu replacements\n", table
->replacements
);
392 fprintf (f
, "\t%lu deletions\n", table
->deletions
);
396 for (i
= 0; i
< table
->size
; ++i
)
398 struct hash_entry
*p
;
400 if (table
->table
[i
] == NULL
)
404 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
409 fprintf (f
, "\t%g average chain length\n", (double) total
/ table
->size
);
410 fprintf (f
, "\t%lu empty slots\n", empty
);
416 /* This test program is left over from the old hash table code. */
418 /* Number of hash tables to maintain (at once) in any testing. */
421 /* We can have 12 statistics. */
422 #define STATBUFSIZE (12)
424 /* Display statistics here. */
425 int statbuf
[STATBUFSIZE
];
427 /* Human farts here. */
430 /* We test many hash tables at once. */
431 char *hashtable
[TABLES
];
433 /* Points to curent hash_control. */
443 /* Number 0:TABLES-1 of current hashed symbol table. */
456 printf ("type h <RETURN> for help\n");
459 printf ("hash_test command: ");
462 if (isupper (command
))
463 command
= tolower (command
); /* Ecch! */
467 printf ("old hash table #=%d.\n", number
);
471 for (pp
= hashtable
; pp
< hashtable
+ TABLES
; pp
++)
473 printf ("address of hash table #%d control block is %xx\n",
474 pp
- hashtable
, *pp
);
478 hash_traverse (h
, applicatee
);
481 hash_traverse (h
, destroy
);
485 p
= hash_find (h
, name
= what ("symbol"));
486 printf ("value of \"%s\" is \"%s\"\n", name
, p
? p
: "NOT-PRESENT");
489 printf ("# show old, select new default hash table number\n");
490 printf ("? display all hashtable control block addresses\n");
491 printf ("a apply a simple display-er to each symbol in table\n");
492 printf ("d die: destroy hashtable\n");
493 printf ("f find value of nominated symbol\n");
494 printf ("h this help\n");
495 printf ("i insert value into symbol\n");
496 printf ("j jam value into symbol\n");
497 printf ("n new hashtable\n");
498 printf ("r replace a value with another\n");
499 printf ("s say what %% of table is used\n");
500 printf ("q exit this program\n");
501 printf ("x delete a symbol from table, report its value\n");
504 p
= hash_insert (h
, name
= what ("symbol"), value
= what ("value"));
507 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
,
512 p
= hash_jam (h
, name
= what ("symbol"), value
= what ("value"));
515 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
, p
);
519 h
= hashtable
[number
] = (char *) hash_new ();
524 p
= hash_replace (h
, name
= what ("symbol"), value
= what ("value"));
525 printf ("old value was \"%s\"\n", p
? p
: "{}");
528 hash_say (h
, statbuf
, STATBUFSIZE
);
529 for (ip
= statbuf
; ip
< statbuf
+ STATBUFSIZE
; ip
++)
536 p
= hash_delete (h
, name
= what ("symbol"));
537 printf ("old value was \"%s\"\n", p
? p
: "{}");
540 printf ("I can't understand command \"%c\"\n", command
);
553 printf (" %s : ", description
);
555 /* Will one day clean up answer here. */
556 retval
= malloc (strlen (answer
) + 1);
561 (void) strcpy (retval
, answer
);
566 destroy (string
, value
)
575 applicatee (string
, value
)
579 printf ("%.20s-%.20s\n", string
, value
);
582 /* Determine number: what hash table to use.
583 Also determine h: points to hash_control. */
590 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
592 sscanf (answer
, "%d", &number
);
593 if (number
>= 0 && number
< TABLES
)
595 h
= hashtable
[number
];
598 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
604 printf ("invalid hash table number: %d\n", number
);
This page took 0.040724 seconds and 4 git commands to generate.