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 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
35 /* The default number of entries to use when creating a hash table. */
37 #define DEFAULT_SIZE (4051)
39 /* 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. */
57 struct hash_entry
**table
;
58 /* The number of slots in the hash table. */
60 /* An obstack for this hash table. */
61 struct obstack memory
;
63 #ifdef HASH_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 */
74 /* Create a hash table. This return a control block. */
80 struct hash_control
*ret
;
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
);
92 #ifdef HASH_STATISTICS
94 ret
->hash_compares
= 0;
95 ret
->string_compares
= 0;
97 ret
->replacements
= 0;
104 /* Delete a hash table, freeing all allocated memory. */
108 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
PARAMS ((struct hash_control
*,
125 struct hash_entry
***,
128 static struct hash_entry
*
129 hash_lookup (table
, key
, plist
, phash
)
130 struct hash_control
*table
;
132 struct hash_entry
***plist
;
133 unsigned long *phash
;
135 register unsigned long hash
;
137 register const unsigned char *s
;
138 register unsigned int c
;
140 struct hash_entry
**list
;
141 struct hash_entry
*p
;
142 struct hash_entry
*prev
;
144 #ifdef HASH_STATISTICS
150 s
= (const unsigned char *) key
;
151 while ((c
= *s
++) != '\0')
153 hash
+= c
+ (c
<< 17);
157 hash
+= len
+ (len
<< 17);
163 index
= hash
% table
->size
;
164 list
= table
->table
+ index
;
170 for (p
= *list
; p
!= NULL
; p
= p
->next
)
172 #ifdef HASH_STATISTICS
173 ++table
->hash_compares
;
178 #ifdef HASH_STATISTICS
179 ++table
->string_compares
;
182 if (strcmp (p
->string
, key
) == 0)
186 prev
->next
= p
->next
;
201 /* Insert an entry into a hash table. This returns NULL on success.
202 On error, it returns a printable string indicating the error. It
203 is considered to be an error if the entry already exists in the
207 hash_insert (table
, key
, value
)
208 struct hash_control
*table
;
212 struct hash_entry
*p
;
213 struct hash_entry
**list
;
216 p
= hash_lookup (table
, key
, &list
, &hash
);
220 #ifdef HASH_STATISTICS
224 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
235 /* Insert or replace an entry in a hash table. This returns NULL on
236 success. On error, it returns a printable string indicating the
237 error. If an entry already exists, its value is replaced. */
240 hash_jam (table
, key
, value
)
241 struct hash_control
*table
;
245 struct hash_entry
*p
;
246 struct hash_entry
**list
;
249 p
= hash_lookup (table
, key
, &list
, &hash
);
252 #ifdef HASH_STATISTICS
253 ++table
->replacements
;
260 #ifdef HASH_STATISTICS
264 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
276 /* Replace an existing entry in a hash table. This returns the old
277 value stored for the entry. If the entry is not found in the hash
278 table, this does nothing and returns NULL. */
281 hash_replace (table
, key
, value
)
282 struct hash_control
*table
;
286 struct hash_entry
*p
;
289 p
= hash_lookup (table
, key
, NULL
, NULL
);
293 #ifdef HASH_STATISTICS
294 ++table
->replacements
;
304 /* Find an entry in a hash table, returning its value. Returns NULL
305 if the entry is not found. */
308 hash_find (table
, key
)
309 struct hash_control
*table
;
312 struct hash_entry
*p
;
314 p
= hash_lookup (table
, key
, NULL
, NULL
);
321 /* Delete an entry from a hash table. This returns the value stored
322 for that entry, or NULL if there is no such entry. */
325 hash_delete (table
, key
)
326 struct hash_control
*table
;
329 struct hash_entry
*p
;
330 struct hash_entry
**list
;
332 p
= hash_lookup (table
, key
, &list
, NULL
);
339 #ifdef HASH_STATISTICS
345 /* Note that we never reclaim the memory for this entry. If gas
346 ever starts deleting hash table entries in a big way, this will
352 /* Traverse a hash table. Call the function on every entry in the
356 hash_traverse (table
, pfn
)
357 struct hash_control
*table
;
358 void (*pfn
) PARAMS ((const char *key
, PTR value
));
362 for (i
= 0; i
< table
->size
; ++i
)
364 struct hash_entry
*p
;
366 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
367 (*pfn
) (p
->string
, p
->data
);
371 /* Print hash table statistics on the specified file. NAME is the
372 name of the hash table, used for printing a header. */
375 hash_print_statistics (f
, name
, table
)
376 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 curent 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 if (isupper (command
))
462 command
= tolower (command
); /* Ecch! */
466 printf ("old hash table #=%d.\n", number
);
470 for (pp
= hashtable
; pp
< hashtable
+ TABLES
; pp
++)
472 printf ("address of hash table #%d control block is %xx\n",
473 pp
- hashtable
, *pp
);
477 hash_traverse (h
, applicatee
);
480 hash_traverse (h
, destroy
);
484 p
= hash_find (h
, name
= what ("symbol"));
485 printf ("value of \"%s\" is \"%s\"\n", name
, p
? p
: "NOT-PRESENT");
488 printf ("# show old, select new default hash table number\n");
489 printf ("? display all hashtable control block addresses\n");
490 printf ("a apply a simple display-er to each symbol in table\n");
491 printf ("d die: destroy hashtable\n");
492 printf ("f find value of nominated symbol\n");
493 printf ("h this help\n");
494 printf ("i insert value into symbol\n");
495 printf ("j jam value into symbol\n");
496 printf ("n new hashtable\n");
497 printf ("r replace a value with another\n");
498 printf ("s say what %% of table is used\n");
499 printf ("q exit this program\n");
500 printf ("x delete a symbol from table, report its value\n");
503 p
= hash_insert (h
, name
= what ("symbol"), value
= what ("value"));
506 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
,
511 p
= hash_jam (h
, name
= what ("symbol"), value
= what ("value"));
514 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name
, value
, p
);
518 h
= hashtable
[number
] = (char *) hash_new ();
523 p
= hash_replace (h
, name
= what ("symbol"), value
= what ("value"));
524 printf ("old value was \"%s\"\n", p
? p
: "{}");
527 hash_say (h
, statbuf
, STATBUFSIZE
);
528 for (ip
= statbuf
; ip
< statbuf
+ STATBUFSIZE
; ip
++)
535 p
= hash_delete (h
, name
= what ("symbol"));
536 printf ("old value was \"%s\"\n", p
? p
: "{}");
539 printf ("I can't understand command \"%c\"\n", command
);
552 printf (" %s : ", description
);
554 /* Will one day clean up answer here. */
555 retval
= malloc (strlen (answer
) + 1);
560 (void) strcpy (retval
, answer
);
565 destroy (string
, value
)
574 applicatee (string
, value
)
578 printf ("%.20s-%.20s\n", string
, value
);
581 /* Determine number: what hash table to use.
582 Also determine h: points to hash_control. */
589 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
591 sscanf (answer
, "%d", &number
);
592 if (number
>= 0 && number
< TABLES
)
594 h
= hashtable
[number
];
597 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
603 printf ("invalid hash table number: %d\n", number
);
This page took 0.040997 seconds and 4 git commands to generate.