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. */
41 /* Next entry for this hash code. */
42 struct hash_entry
*next
;
43 /* String being hashed. */
45 /* Hash code. This is the full hash code, not the index into the
48 /* Pointer being stored in the hash table. */
56 struct hash_entry
**table
;
57 /* The number of slots in the hash table. */
59 /* An obstack for this hash table. */
60 struct obstack memory
;
62 #ifdef HASH_STATISTICS
64 unsigned long lookups
;
65 unsigned long hash_compares
;
66 unsigned long string_compares
;
67 unsigned long insertions
;
68 unsigned long replacements
;
69 unsigned long deletions
;
70 #endif /* HASH_STATISTICS */
73 /* Create a hash table. This return a control block. */
79 struct hash_control
*ret
;
84 ret
= (struct hash_control
*) xmalloc (sizeof *ret
);
85 obstack_begin (&ret
->memory
, chunksize
);
86 alloc
= size
* sizeof (struct hash_entry
*);
87 ret
->table
= (struct hash_entry
**) obstack_alloc (&ret
->memory
, alloc
);
88 memset (ret
->table
, 0, alloc
);
91 #ifdef HASH_STATISTICS
93 ret
->hash_compares
= 0;
94 ret
->string_compares
= 0;
96 ret
->replacements
= 0;
103 /* Delete a hash table, freeing all allocated memory. */
107 struct hash_control
*table
;
109 obstack_free (&table
->memory
, 0);
113 /* Look up a string in a hash table. This returns a pointer to the
114 hash_entry, or NULL if the string is not in the table. If PLIST is
115 not NULL, this sets *PLIST to point to the start of the list which
116 would hold this hash entry. If PHASH is not NULL, this sets *PHASH
117 to the hash code for KEY.
119 Each time we look up a string, we move it to the start of the list
120 for its hash code, to take advantage of referential locality. */
122 static struct hash_entry
*hash_lookup
PARAMS ((struct hash_control
*,
124 struct hash_entry
***,
127 static struct hash_entry
*
128 hash_lookup (table
, key
, plist
, phash
)
129 struct hash_control
*table
;
131 struct hash_entry
***plist
;
132 unsigned long *phash
;
134 register unsigned long hash
;
136 register const unsigned char *s
;
137 register unsigned int c
;
139 struct hash_entry
**list
;
140 struct hash_entry
*p
;
141 struct hash_entry
*prev
;
143 #ifdef HASH_STATISTICS
149 s
= (const unsigned char *) key
;
150 while ((c
= *s
++) != '\0')
152 hash
+= c
+ (c
<< 17);
156 hash
+= len
+ (len
<< 17);
162 index
= hash
% table
->size
;
163 list
= table
->table
+ index
;
169 for (p
= *list
; p
!= NULL
; p
= p
->next
)
171 #ifdef HASH_STATISTICS
172 ++table
->hash_compares
;
177 #ifdef HASH_STATISTICS
178 ++table
->string_compares
;
181 if (strcmp (p
->string
, key
) == 0)
185 prev
->next
= p
->next
;
200 /* Insert an entry into a hash table. This returns NULL on success.
201 On error, it returns a printable string indicating the error. It
202 is considered to be an error if the entry already exists in the
206 hash_insert (table
, key
, value
)
207 struct hash_control
*table
;
211 struct hash_entry
*p
;
212 struct hash_entry
**list
;
215 p
= hash_lookup (table
, key
, &list
, &hash
);
219 #ifdef HASH_STATISTICS
223 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
234 /* Insert or replace an entry in a hash table. This returns NULL on
235 success. On error, it returns a printable string indicating the
236 error. If an entry already exists, its value is replaced. */
239 hash_jam (table
, key
, value
)
240 struct hash_control
*table
;
244 struct hash_entry
*p
;
245 struct hash_entry
**list
;
248 p
= hash_lookup (table
, key
, &list
, &hash
);
251 #ifdef HASH_STATISTICS
252 ++table
->replacements
;
259 #ifdef HASH_STATISTICS
263 p
= (struct hash_entry
*) obstack_alloc (&table
->memory
, sizeof (*p
));
275 /* Replace an existing entry in a hash table. This returns the old
276 value stored for the entry. If the entry is not found in the hash
277 table, this does nothing and returns NULL. */
280 hash_replace (table
, key
, value
)
281 struct hash_control
*table
;
285 struct hash_entry
*p
;
288 p
= hash_lookup (table
, key
, NULL
, NULL
);
292 #ifdef HASH_STATISTICS
293 ++table
->replacements
;
303 /* Find an entry in a hash table, returning its value. Returns NULL
304 if the entry is not found. */
307 hash_find (table
, key
)
308 struct hash_control
*table
;
311 struct hash_entry
*p
;
313 p
= hash_lookup (table
, key
, NULL
, NULL
);
320 /* Delete an entry from a hash table. This returns the value stored
321 for that entry, or NULL if there is no such entry. */
324 hash_delete (table
, key
)
325 struct hash_control
*table
;
328 struct hash_entry
*p
;
329 struct hash_entry
**list
;
331 p
= hash_lookup (table
, key
, &list
, NULL
);
338 #ifdef HASH_STATISTICS
344 /* Note that we never reclaim the memory for this entry. If gas
345 ever starts deleting hash table entries in a big way, this will
351 /* Traverse a hash table. Call the function on every entry in the
355 hash_traverse (table
, pfn
)
356 struct hash_control
*table
;
357 void (*pfn
) PARAMS ((const char *key
, PTR value
));
361 for (i
= 0; i
< table
->size
; ++i
)
363 struct hash_entry
*p
;
365 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
366 (*pfn
) (p
->string
, p
->data
);
370 /* Print hash table statistics on the specified file. NAME is the
371 name of the hash table, used for printing a header. */
374 hash_print_statistics (f
, name
, table
)
375 FILE *f ATTRIBUTE_UNUSED
;
376 const char *name ATTRIBUTE_UNUSED
;
377 struct hash_control
*table ATTRIBUTE_UNUSED
;
379 #ifdef HASH_STATISTICS
384 fprintf (f
, "%s hash statistics:\n", name
);
385 fprintf (f
, "\t%lu lookups\n", table
->lookups
);
386 fprintf (f
, "\t%lu hash comparisons\n", table
->hash_compares
);
387 fprintf (f
, "\t%lu string comparisons\n", table
->string_compares
);
388 fprintf (f
, "\t%lu insertions\n", table
->insertions
);
389 fprintf (f
, "\t%lu replacements\n", table
->replacements
);
390 fprintf (f
, "\t%lu deletions\n", table
->deletions
);
394 for (i
= 0; i
< table
->size
; ++i
)
396 struct hash_entry
*p
;
398 if (table
->table
[i
] == NULL
)
402 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
407 fprintf (f
, "\t%g average chain length\n", (double) total
/ table
->size
);
408 fprintf (f
, "\t%lu empty slots\n", empty
);
414 /* This test program is left over from the old hash table code. */
416 /* Number of hash tables to maintain (at once) in any testing. */
419 /* We can have 12 statistics. */
420 #define STATBUFSIZE (12)
422 /* Display statistics here. */
423 int statbuf
[STATBUFSIZE
];
425 /* Human farts here. */
428 /* We test many hash tables at once. */
429 char *hashtable
[TABLES
];
431 /* Points to curent hash_control. */
441 /* Number 0:TABLES-1 of current hashed symbol table. */
454 printf ("type h <RETURN> for help\n");
457 printf ("hash_test command: ");
460 if (isupper (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
);
551 printf (" %s : ", description
);
553 /* Will one day clean up answer here. */
554 retval
= malloc (strlen (answer
) + 1);
559 (void) strcpy (retval
, answer
);
564 destroy (string
, value
)
573 applicatee (string
, value
)
577 printf ("%.20s-%.20s\n", string
, value
);
580 /* Determine number: what hash table to use.
581 Also determine h: points to hash_control. */
588 printf (" what hash table (%d:%d) ? ", 0, TABLES
- 1);
590 sscanf (answer
, "%d", &number
);
591 if (number
>= 0 && number
< TABLES
)
593 h
= hashtable
[number
];
596 printf ("warning: current hash-table-#%d. has no hash-control\n", number
);
602 printf ("invalid hash table number: %d\n", number
);
This page took 0.042216 seconds and 4 git commands to generate.