hash.c 13.5 KB
Newer Older
1
2
/* hash.c -- gas hash table code
   Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 1999
Richard Henderson's avatar
Richard Henderson committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   Free Software Foundation, Inc.

   This file is part of GAS, the GNU Assembler.

   GAS is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   GAS is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
18
19
20
21
22
23
24
25
26
27
28
29
   along with GAS; see the file COPYING.  If not, write to the Free
   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */

/* This version of the hash table code is a wholescale replacement of
   the old hash table code, which was fairly bad.  This is based on
   the hash table code in BFD, but optimized slightly for the
   asssembler.  The assembler does not need to derive structures that
   are stored in the hash table.  Instead, it always stores a pointer.
   The assembler uses the hash table mostly to store symbols, and we
   don't need to confuse the symbol structure with a hash table
   structure.  */
Richard Henderson's avatar
Richard Henderson committed
30
31

#include "as.h"
32
#include "obstack.h"
Richard Henderson's avatar
Richard Henderson committed
33

34
/* The default number of entries to use when creating a hash table.  */
Richard Henderson's avatar
Richard Henderson committed
35

36
#define DEFAULT_SIZE (4051)
Richard Henderson's avatar
Richard Henderson committed
37

38
/* An entry in a hash table.  */
Richard Henderson's avatar
Richard Henderson committed
39
40
41

struct hash_entry
{
42
43
44
45
46
47
48
49
50
  /* Next entry for this hash code.  */
  struct hash_entry *next;
  /* String being hashed.  */
  const char *string;
  /* Hash code.  This is the full hash code, not the index into the
     table.  */
  unsigned long hash;
  /* Pointer being stored in the hash table.  */
  PTR data;
Richard Henderson's avatar
Richard Henderson committed
51
52
};

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/* A hash table.  */

struct hash_control
{
  /* The hash array.  */
  struct hash_entry **table;
  /* The number of slots in the hash table.  */
  unsigned int size;
  /* An obstack for this hash table.  */
  struct obstack memory;

#ifdef HASH_STATISTICS
  /* Statistics.  */
  unsigned long lookups;
  unsigned long hash_compares;
  unsigned long string_compares;
  unsigned long insertions;
  unsigned long replacements;
  unsigned long deletions;
#endif /* HASH_STATISTICS */
Richard Henderson's avatar
Richard Henderson committed
73
};
74
75
76

/* Create a hash table.  This return a control block.  */

Richard Henderson's avatar
Richard Henderson committed
77
78
79
struct hash_control *
hash_new ()
{
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
  unsigned int size;
  struct hash_control *ret;
  unsigned int alloc;

  size = DEFAULT_SIZE;

  ret = (struct hash_control *) xmalloc (sizeof *ret);
  obstack_begin (&ret->memory, chunksize);
  alloc = size * sizeof (struct hash_entry *);
  ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  memset (ret->table, 0, alloc);
  ret->size = size;

#ifdef HASH_STATISTICS
  ret->lookups = 0;
  ret->hash_compares = 0;
  ret->string_compares = 0;
  ret->insertions = 0;
  ret->replacements = 0;
  ret->deletions = 0;
#endif

  return ret;  
Richard Henderson's avatar
Richard Henderson committed
103
104
}

105
106
/* Delete a hash table, freeing all allocated memory.  */

Richard Henderson's avatar
Richard Henderson committed
107
void
108
109
hash_die (table)
     struct hash_control *table;
Richard Henderson's avatar
Richard Henderson committed
110
{
111
112
  obstack_free (&table->memory, 0);
  free (table);
Richard Henderson's avatar
Richard Henderson committed
113
}
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

/* Look up a string in a hash table.  This returns a pointer to the
   hash_entry, or NULL if the string is not in the table.  If PLIST is
   not NULL, this sets *PLIST to point to the start of the list which
   would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
   to the hash code for KEY.

   Each time we look up a string, we move it to the start of the list
   for its hash code, to take advantage of referential locality.  */

static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
					       const char *,
					       struct hash_entry ***,
					       unsigned long *));

static struct hash_entry *
hash_lookup (table, key, plist, phash)
     struct hash_control *table;
     const char *key;
     struct hash_entry ***plist;
     unsigned long *phash;
Richard Henderson's avatar
Richard Henderson committed
135
{
136
137
138
139
140
141
142
143
144
145
146
147
  register unsigned long hash;
  unsigned int len;
  register const unsigned char *s;
  register unsigned int c;
  unsigned int index;
  struct hash_entry **list;
  struct hash_entry *p;
  struct hash_entry *prev;

#ifdef HASH_STATISTICS
  ++table->lookups;
#endif
Richard Henderson's avatar
Richard Henderson committed
148

149
150
151
152
  hash = 0;
  len = 0;
  s = (const unsigned char *) key;
  while ((c = *s++) != '\0')
Richard Henderson's avatar
Richard Henderson committed
153
    {
154
155
156
      hash += c + (c << 17);
      hash ^= hash >> 2;
      ++len;
Richard Henderson's avatar
Richard Henderson committed
157
    }
158
159
160
161
162
163
164
165
  hash += len + (len << 17);
  hash ^= hash >> 2;

  if (phash != NULL)
    *phash = hash;

  index = hash % table->size;
  list = table->table + index;
Richard Henderson's avatar
Richard Henderson committed
166

167
168
169
170
171
  if (plist != NULL)
    *plist = list;

  prev = NULL;
  for (p = *list; p != NULL; p = p->next)
Richard Henderson's avatar
Richard Henderson committed
172
    {
173
174
175
176
177
#ifdef HASH_STATISTICS
      ++table->hash_compares;
#endif

      if (p->hash == hash)
Richard Henderson's avatar
Richard Henderson committed
178
	{
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#ifdef HASH_STATISTICS
	  ++table->string_compares;
#endif

	  if (strcmp (p->string, key) == 0)
	    {
	      if (prev != NULL)
		{
		  prev->next = p->next;
		  p->next = *list;
		  *list = p;
		}

	      return p;
	    }
Richard Henderson's avatar
Richard Henderson committed
194
195
	}

196
      prev = p;
Richard Henderson's avatar
Richard Henderson committed
197
    }
198
199

  return NULL;
Richard Henderson's avatar
Richard Henderson committed
200
}
201
202
203
204
205
206
207
208
209
210

/* Insert an entry into a hash table.  This returns NULL on success.
   On error, it returns a printable string indicating the error.  It
   is considered to be an error if the entry already exists in the
   hash table.  */

const char *
hash_insert (table, key, value)
     struct hash_control *table;
     const char *key;
Richard Henderson's avatar
Richard Henderson committed
211
212
     PTR value;
{
213
214
215
  struct hash_entry *p;
  struct hash_entry **list;
  unsigned long hash;
Richard Henderson's avatar
Richard Henderson committed
216

217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
  p = hash_lookup (table, key, &list, &hash);
  if (p != NULL)
    return "exists";

#ifdef HASH_STATISTICS
  ++table->insertions;
#endif

  p = obstack_alloc (&table->memory, sizeof *p);
  p->string = key;
  p->hash = hash;
  p->data = value;

  p->next = *list;
  *list = p;

  return NULL;
Richard Henderson's avatar
Richard Henderson committed
234
}
235
236
237
238
239

/* Insert or replace an entry in a hash table.  This returns NULL on
   success.  On error, it returns a printable string indicating the
   error.  If an entry already exists, its value is replaced.  */

Richard Henderson's avatar
Richard Henderson committed
240
const char *
241
242
243
hash_jam (table, key, value)
     struct hash_control *table;
     const char *key;
Richard Henderson's avatar
Richard Henderson committed
244
245
     PTR value;
{
246
247
248
  struct hash_entry *p;
  struct hash_entry **list;
  unsigned long hash;
Richard Henderson's avatar
Richard Henderson committed
249

250
251
  p = hash_lookup (table, key, &list, &hash);
  if (p != NULL)
Richard Henderson's avatar
Richard Henderson committed
252
    {
253
254
255
256
257
#ifdef HASH_STATISTICS
      ++table->replacements;
#endif

      p->data = value;
Richard Henderson's avatar
Richard Henderson committed
258
    }
259
  else
Richard Henderson's avatar
Richard Henderson committed
260
    {
261
262
263
264
265
266
267
268
269
270
271
#ifdef HASH_STATISTICS
      ++table->insertions;
#endif

      p = obstack_alloc (&table->memory, sizeof *p);
      p->string = key;
      p->hash = hash;
      p->data = value;

      p->next = *list;
      *list = p;
Richard Henderson's avatar
Richard Henderson committed
272
    }
273
274

  return NULL;
Richard Henderson's avatar
Richard Henderson committed
275
276
}

277
278
279
280
281
282
283
284
285
/* Replace an existing entry in a hash table.  This returns the old
   value stored for the entry.  If the entry is not found in the hash
   table, this does nothing and returns NULL.  */

PTR
hash_replace (table, key, value)
     struct hash_control *table;
     const char *key;
     PTR value;
Richard Henderson's avatar
Richard Henderson committed
286
{
287
288
  struct hash_entry *p;
  PTR ret;
Richard Henderson's avatar
Richard Henderson committed
289

290
291
292
293
294
295
  p = hash_lookup (table, key, NULL, NULL);
  if (p == NULL)
    return NULL;

#ifdef HASH_STATISTICS
  ++table->replacements;
Richard Henderson's avatar
Richard Henderson committed
296
297
#endif

298
  ret = p->data;
Richard Henderson's avatar
Richard Henderson committed
299

300
  p->data = value;
Richard Henderson's avatar
Richard Henderson committed
301

302
  return ret;
Richard Henderson's avatar
Richard Henderson committed
303
}
304
305
306
307

/* Find an entry in a hash table, returning its value.  Returns NULL
   if the entry is not found.  */

Richard Henderson's avatar
Richard Henderson committed
308
PTR
309
310
311
hash_find (table, key)
     struct hash_control *table;
     const char *key;
Richard Henderson's avatar
Richard Henderson committed
312
{
313
  struct hash_entry *p;
Richard Henderson's avatar
Richard Henderson committed
314

315
316
  p = hash_lookup (table, key, NULL, NULL);
  if (p == NULL)
Richard Henderson's avatar
Richard Henderson committed
317
    return NULL;
318
319

  return p->data;
Richard Henderson's avatar
Richard Henderson committed
320
}
321
322
323
324
325
326
327
328

/* Delete an entry from a hash table.  This returns the value stored
   for that entry, or NULL if there is no such entry.  */

PTR
hash_delete (table, key)
     struct hash_control *table;
     const char *key;
Richard Henderson's avatar
Richard Henderson committed
329
{
330
331
332
333
334
335
336
337
338
339
340
341
  struct hash_entry *p;
  struct hash_entry **list;

  p = hash_lookup (table, key, &list, NULL);
  if (p == NULL)
    return NULL;

  if (p != *list)
    abort ();

#ifdef HASH_STATISTICS
  ++table->deletions;
Richard Henderson's avatar
Richard Henderson committed
342
#endif
343
344
345
346
347
348
349
350

  *list = p->next;

  /* Note that we never reclaim the memory for this entry.  If gas
     ever starts deleting hash table entries in a big way, this will
     have to change.  */

  return p->data;
Richard Henderson's avatar
Richard Henderson committed
351
}
352
353
354
355

/* Traverse a hash table.  Call the function on every entry in the
   hash table.  */

Richard Henderson's avatar
Richard Henderson committed
356
void
357
358
359
hash_traverse (table, pfn)
     struct hash_control *table;
     void (*pfn) PARAMS ((const char *key, PTR value));
Richard Henderson's avatar
Richard Henderson committed
360
{
361
  unsigned int i;
Richard Henderson's avatar
Richard Henderson committed
362

363
364
365
  for (i = 0; i < table->size; ++i)
    {
      struct hash_entry *p;
Richard Henderson's avatar
Richard Henderson committed
366

367
368
369
370
      for (p = table->table[i]; p != NULL; p = p->next)
	(*pfn) (p->string, p->data);
    }
}
Richard Henderson's avatar
Richard Henderson committed
371

372
373
/* Print hash table statistics on the specified file.  NAME is the
   name of the hash table, used for printing a header.  */
Richard Henderson's avatar
Richard Henderson committed
374

375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
void
hash_print_statistics (f, name, table)
     FILE *f;
     const char *name;
     struct hash_control *table;
{
#ifdef HASH_STATISTICS
  unsigned int i;
  unsigned long total;
  unsigned long empty;

  fprintf (f, "%s hash statistics:\n", name);
  fprintf (f, "\t%lu lookups\n", table->lookups);
  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
  fprintf (f, "\t%lu insertions\n", table->insertions);
  fprintf (f, "\t%lu replacements\n", table->replacements);
  fprintf (f, "\t%lu deletions\n", table->deletions);

  total = 0;
  empty = 0;
  for (i = 0; i < table->size; ++i)
    {
      struct hash_entry *p;
Richard Henderson's avatar
Richard Henderson committed
399

400
401
402
403
404
405
406
407
      if (table->table[i] == NULL)
	++empty;
      else
	{
	  for (p = table->table[i]; p != NULL; p = p->next)
	    ++total;
	}
    }
Richard Henderson's avatar
Richard Henderson committed
408

409
410
411
  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
  fprintf (f, "\t%lu empty slots\n", empty);
#endif
Richard Henderson's avatar
Richard Henderson committed
412
413
414
415
}

#ifdef TEST

416
417
/* This test program is left over from the old hash table code.  */

Richard Henderson's avatar
Richard Henderson committed
418
#define TABLES (6)		/* number of hash tables to maintain */
419
				/* (at once) in any testing */
Richard Henderson's avatar
Richard Henderson committed
420
421
422
423
424
425
426
427
428
429
430
431
432
433
#define STATBUFSIZE (12)	/* we can have 12 statistics */

int statbuf[STATBUFSIZE];	/* display statistics here */
char answer[100];		/* human farts here */
char *hashtable[TABLES];	/* we test many hash tables at once */
char *h;			/* points to curent hash_control */
char **pp;
char *p;
char *name;
char *value;
int size;
int used;
char command;
int number;			/* number 0:TABLES-1 of current hashed */
434
				/* symbol table */
Richard Henderson's avatar
Richard Henderson committed
435

436
int
Richard Henderson's avatar
Richard Henderson committed
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
main ()
{
  void applicatee ();
  void destroy ();
  char *what ();
  int *ip;

  number = 0;
  h = 0;
  printf ("type h <RETURN> for help\n");
  for (;;)
    {
      printf ("hash_test command: ");
      gets (answer);
      command = answer[0];
      if (isupper (command))
	command = tolower (command);	/* ecch! */
      switch (command)
	{
	case '#':
	  printf ("old hash table #=%d.\n", number);
	  whattable ();
	  break;
	case '?':
	  for (pp = hashtable; pp < hashtable + TABLES; pp++)
	    {
	      printf ("address of hash table #%d control block is %xx\n"
		      ,pp - hashtable, *pp);
	    }
	  break;
	case 'a':
468
	  hash_traverse (h, applicatee);
Richard Henderson's avatar
Richard Henderson committed
469
470
	  break;
	case 'd':
471
	  hash_traverse (h, destroy);
Richard Henderson's avatar
Richard Henderson committed
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
	  hash_die (h);
	  break;
	case 'f':
	  p = hash_find (h, name = what ("symbol"));
	  printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
	  break;
	case 'h':
	  printf ("# show old, select new default hash table number\n");
	  printf ("? display all hashtable control block addresses\n");
	  printf ("a apply a simple display-er to each symbol in table\n");
	  printf ("d die: destroy hashtable\n");
	  printf ("f find value of nominated symbol\n");
	  printf ("h this help\n");
	  printf ("i insert value into symbol\n");
	  printf ("j jam value into symbol\n");
	  printf ("n new hashtable\n");
	  printf ("r replace a value with another\n");
	  printf ("s say what %% of table is used\n");
	  printf ("q exit this program\n");
	  printf ("x delete a symbol from table, report its value\n");
	  break;
	case 'i':
	  p = hash_insert (h, name = what ("symbol"), value = what ("value"));
	  if (p)
	    {
	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
		      p);
	    }
	  break;
	case 'j':
	  p = hash_jam (h, name = what ("symbol"), value = what ("value"));
	  if (p)
	    {
	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
	    }
	  break;
	case 'n':
	  h = hashtable[number] = (char *) hash_new ();
	  break;
	case 'q':
	  exit (EXIT_SUCCESS);
	case 'r':
	  p = hash_replace (h, name = what ("symbol"), value = what ("value"));
	  printf ("old value was \"%s\"\n", p ? p : "{}");
	  break;
	case 's':
	  hash_say (h, statbuf, STATBUFSIZE);
	  for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
	    {
	      printf ("%d ", *ip);
	    }
	  printf ("\n");
	  break;
	case 'x':
	  p = hash_delete (h, name = what ("symbol"));
	  printf ("old value was \"%s\"\n", p ? p : "{}");
	  break;
	default:
	  printf ("I can't understand command \"%c\"\n", command);
	  break;
	}
    }
}

char *
what (description)
     char *description;
{
  char *retval;
  char *malloc ();

  printf ("   %s : ", description);
  gets (answer);
  /* will one day clean up answer here */
  retval = malloc (strlen (answer) + 1);
  if (!retval)
    {
      error ("room");
    }
  (void) strcpy (retval, answer);
  return (retval);
}

void
destroy (string, value)
     char *string;
     char *value;
{
  free (string);
  free (value);
}


void
applicatee (string, value)
     char *string;
     char *value;
{
  printf ("%.20s-%.20s\n", string, value);
}

573
void
Richard Henderson's avatar
Richard Henderson committed
574
whattable ()			/* determine number: what hash table to use */
575
			        /* also determine h: points to hash_control */
Richard Henderson's avatar
Richard Henderson committed
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
{

  for (;;)
    {
      printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
      gets (answer);
      sscanf (answer, "%d", &number);
      if (number >= 0 && number < TABLES)
	{
	  h = hashtable[number];
	  if (!h)
	    {
	      printf ("warning: current hash-table-#%d. has no hash-control\n", number);
	    }
	  return;
	}
      else
	{
	  printf ("invalid hash table number: %d\n", number);
	}
    }
}

#endif /* #ifdef TEST */

/* end of hash.c */