OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [binutils-2.18.50/] [gas/] [hash.c] - Blame information for rev 156

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* hash.c -- gas hash table code
2
   Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
3
   2000, 2001, 2002, 2003, 2005, 2007
4
   Free Software Foundation, Inc.
5
 
6
   This file is part of GAS, the GNU Assembler.
7
 
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 3, or (at your option)
11
   any later version.
12
 
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.
17
 
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, 51 Franklin Street - Fifth Floor, Boston, MA
21
   02110-1301, USA.  */
22
 
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
30
   structure.  */
31
 
32
#include "as.h"
33
#include "safe-ctype.h"
34
#include "obstack.h"
35
 
36
/* An entry in a hash table.  */
37
 
38
struct hash_entry {
39
  /* Next entry for this hash code.  */
40
  struct hash_entry *next;
41
  /* String being hashed.  */
42
  const char *string;
43
  /* Hash code.  This is the full hash code, not the index into the
44
     table.  */
45
  unsigned long hash;
46
  /* Pointer being stored in the hash table.  */
47
  PTR data;
48
};
49
 
50
/* A hash table.  */
51
 
52
struct hash_control {
53
  /* The hash array.  */
54
  struct hash_entry **table;
55
  /* The number of slots in the hash table.  */
56
  unsigned int size;
57
  /* An obstack for this hash table.  */
58
  struct obstack memory;
59
 
60
#ifdef HASH_STATISTICS
61
  /* Statistics.  */
62
  unsigned long lookups;
63
  unsigned long hash_compares;
64
  unsigned long string_compares;
65
  unsigned long insertions;
66
  unsigned long replacements;
67
  unsigned long deletions;
68
#endif /* HASH_STATISTICS */
69
};
70
 
71
/* The default number of entries to use when creating a hash table.
72
   Note this value can be reduced to 4051 by using the command line
73
   switch --reduce-memory-overheads, or set to other values by using
74
   the --hash-size=<NUMBER> switch.  */
75
 
76
static unsigned long gas_hash_table_size = 65537;
77
 
78
void
79
set_gas_hash_table_size (unsigned long size)
80
{
81
  gas_hash_table_size = size;
82
}
83
 
84
/* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size().  */
85
static unsigned long
86
get_gas_hash_table_size (void)
87
{
88
  /* Extend this prime list if you want more granularity of hash table size.  */
89
  static const unsigned long hash_size_primes[] =
90
    {
91
      1021, 4051, 8599, 16699, 65537
92
    };
93
  unsigned int index;
94
 
95
  /* Work out the best prime number near the hash_size.
96
     FIXME: This could be a more sophisticated algorithm,
97
     but is it really worth implementing it ?   */
98
  for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
99
    if (gas_hash_table_size <= hash_size_primes[index])
100
      break;
101
 
102
  return hash_size_primes[index];
103
}
104
 
105
/* Create a hash table.  This return a control block.  */
106
 
107
struct hash_control *
108
hash_new (void)
109
{
110
  unsigned long size;
111
  unsigned long alloc;
112
  struct hash_control *ret;
113
 
114
  size = get_gas_hash_table_size ();
115
 
116
  ret = xmalloc (sizeof *ret);
117
  obstack_begin (&ret->memory, chunksize);
118
  alloc = size * sizeof (struct hash_entry *);
119
  ret->table = obstack_alloc (&ret->memory, alloc);
120
  memset (ret->table, 0, alloc);
121
  ret->size = size;
122
 
123
#ifdef HASH_STATISTICS
124
  ret->lookups = 0;
125
  ret->hash_compares = 0;
126
  ret->string_compares = 0;
127
  ret->insertions = 0;
128
  ret->replacements = 0;
129
  ret->deletions = 0;
130
#endif
131
 
132
  return ret;
133
}
134
 
135
/* Delete a hash table, freeing all allocated memory.  */
136
 
137
void
138
hash_die (struct hash_control *table)
139
{
140
  obstack_free (&table->memory, 0);
141
  free (table);
142
}
143
 
144
/* Look up a string in a hash table.  This returns a pointer to the
145
   hash_entry, or NULL if the string is not in the table.  If PLIST is
146
   not NULL, this sets *PLIST to point to the start of the list which
147
   would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
148
   to the hash code for KEY.
149
 
150
   Each time we look up a string, we move it to the start of the list
151
   for its hash code, to take advantage of referential locality.  */
152
 
153
static struct hash_entry *
154
hash_lookup (struct hash_control *table, const char *key, size_t len,
155
             struct hash_entry ***plist, unsigned long *phash)
156
{
157
  unsigned long hash;
158
  size_t n;
159
  unsigned int c;
160
  unsigned int index;
161
  struct hash_entry **list;
162
  struct hash_entry *p;
163
  struct hash_entry *prev;
164
 
165
#ifdef HASH_STATISTICS
166
  ++table->lookups;
167
#endif
168
 
169
  hash = 0;
170
  for (n = 0; n < len; n++)
171
    {
172
      c = key[n];
173
      hash += c + (c << 17);
174
      hash ^= hash >> 2;
175
    }
176
  hash += len + (len << 17);
177
  hash ^= hash >> 2;
178
 
179
  if (phash != NULL)
180
    *phash = hash;
181
 
182
  index = hash % table->size;
183
  list = table->table + index;
184
 
185
  if (plist != NULL)
186
    *plist = list;
187
 
188
  prev = NULL;
189
  for (p = *list; p != NULL; p = p->next)
190
    {
191
#ifdef HASH_STATISTICS
192
      ++table->hash_compares;
193
#endif
194
 
195
      if (p->hash == hash)
196
        {
197
#ifdef HASH_STATISTICS
198
          ++table->string_compares;
199
#endif
200
 
201
          if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
202
            {
203
              if (prev != NULL)
204
                {
205
                  prev->next = p->next;
206
                  p->next = *list;
207
                  *list = p;
208
                }
209
 
210
              return p;
211
            }
212
        }
213
 
214
      prev = p;
215
    }
216
 
217
  return NULL;
218
}
219
 
220
/* Insert an entry into a hash table.  This returns NULL on success.
221
   On error, it returns a printable string indicating the error.  It
222
   is considered to be an error if the entry already exists in the
223
   hash table.  */
224
 
225
const char *
226
hash_insert (struct hash_control *table, const char *key, PTR value)
227
{
228
  struct hash_entry *p;
229
  struct hash_entry **list;
230
  unsigned long hash;
231
 
232
  p = hash_lookup (table, key, strlen (key), &list, &hash);
233
  if (p != NULL)
234
    return "exists";
235
 
236
#ifdef HASH_STATISTICS
237
  ++table->insertions;
238
#endif
239
 
240
  p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
241
  p->string = key;
242
  p->hash = hash;
243
  p->data = value;
244
 
245
  p->next = *list;
246
  *list = p;
247
 
248
  return NULL;
249
}
250
 
251
/* Insert or replace an entry in a hash table.  This returns NULL on
252
   success.  On error, it returns a printable string indicating the
253
   error.  If an entry already exists, its value is replaced.  */
254
 
255
const char *
256
hash_jam (struct hash_control *table, const char *key, PTR value)
257
{
258
  struct hash_entry *p;
259
  struct hash_entry **list;
260
  unsigned long hash;
261
 
262
  p = hash_lookup (table, key, strlen (key), &list, &hash);
263
  if (p != NULL)
264
    {
265
#ifdef HASH_STATISTICS
266
      ++table->replacements;
267
#endif
268
 
269
      p->data = value;
270
    }
271
  else
272
    {
273
#ifdef HASH_STATISTICS
274
      ++table->insertions;
275
#endif
276
 
277
      p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
278
      p->string = key;
279
      p->hash = hash;
280
      p->data = value;
281
 
282
      p->next = *list;
283
      *list = p;
284
    }
285
 
286
  return NULL;
287
}
288
 
289
/* Replace an existing entry in a hash table.  This returns the old
290
   value stored for the entry.  If the entry is not found in the hash
291
   table, this does nothing and returns NULL.  */
292
 
293
PTR
294
hash_replace (struct hash_control *table, const char *key, PTR value)
295
{
296
  struct hash_entry *p;
297
  PTR ret;
298
 
299
  p = hash_lookup (table, key, strlen (key), NULL, NULL);
300
  if (p == NULL)
301
    return NULL;
302
 
303
#ifdef HASH_STATISTICS
304
  ++table->replacements;
305
#endif
306
 
307
  ret = p->data;
308
 
309
  p->data = value;
310
 
311
  return ret;
312
}
313
 
314
/* Find an entry in a hash table, returning its value.  Returns NULL
315
   if the entry is not found.  */
316
 
317
PTR
318
hash_find (struct hash_control *table, const char *key)
319
{
320
  struct hash_entry *p;
321
 
322
  p = hash_lookup (table, key, strlen (key), NULL, NULL);
323
  if (p == NULL)
324
    return NULL;
325
 
326
  return p->data;
327
}
328
 
329
/* As hash_find, but KEY is of length LEN and is not guaranteed to be
330
   NUL-terminated.  */
331
 
332
PTR
333
hash_find_n (struct hash_control *table, const char *key, size_t len)
334
{
335
  struct hash_entry *p;
336
 
337
  p = hash_lookup (table, key, len, NULL, NULL);
338
  if (p == NULL)
339
    return NULL;
340
 
341
  return p->data;
342
}
343
 
344
/* Delete an entry from a hash table.  This returns the value stored
345
   for that entry, or NULL if there is no such entry.  */
346
 
347
PTR
348
hash_delete (struct hash_control *table, const char *key)
349
{
350
  struct hash_entry *p;
351
  struct hash_entry **list;
352
 
353
  p = hash_lookup (table, key, strlen (key), &list, NULL);
354
  if (p == NULL)
355
    return NULL;
356
 
357
  if (p != *list)
358
    abort ();
359
 
360
#ifdef HASH_STATISTICS
361
  ++table->deletions;
362
#endif
363
 
364
  *list = p->next;
365
 
366
  /* Note that we never reclaim the memory for this entry.  If gas
367
     ever starts deleting hash table entries in a big way, this will
368
     have to change.  */
369
 
370
  return p->data;
371
}
372
 
373
/* Traverse a hash table.  Call the function on every entry in the
374
   hash table.  */
375
 
376
void
377
hash_traverse (struct hash_control *table,
378
               void (*pfn) (const char *key, PTR value))
379
{
380
  unsigned int i;
381
 
382
  for (i = 0; i < table->size; ++i)
383
    {
384
      struct hash_entry *p;
385
 
386
      for (p = table->table[i]; p != NULL; p = p->next)
387
        (*pfn) (p->string, p->data);
388
    }
389
}
390
 
391
/* Print hash table statistics on the specified file.  NAME is the
392
   name of the hash table, used for printing a header.  */
393
 
394
void
395
hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
396
                       const char *name ATTRIBUTE_UNUSED,
397
                       struct hash_control *table ATTRIBUTE_UNUSED)
398
{
399
#ifdef HASH_STATISTICS
400
  unsigned int i;
401
  unsigned long total;
402
  unsigned long empty;
403
 
404
  fprintf (f, "%s hash statistics:\n", name);
405
  fprintf (f, "\t%lu lookups\n", table->lookups);
406
  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
407
  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
408
  fprintf (f, "\t%lu insertions\n", table->insertions);
409
  fprintf (f, "\t%lu replacements\n", table->replacements);
410
  fprintf (f, "\t%lu deletions\n", table->deletions);
411
 
412
  total = 0;
413
  empty = 0;
414
  for (i = 0; i < table->size; ++i)
415
    {
416
      struct hash_entry *p;
417
 
418
      if (table->table[i] == NULL)
419
        ++empty;
420
      else
421
        {
422
          for (p = table->table[i]; p != NULL; p = p->next)
423
            ++total;
424
        }
425
    }
426
 
427
  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
428
  fprintf (f, "\t%lu empty slots\n", empty);
429
#endif
430
}
431
 
432
#ifdef TEST
433
 
434
/* This test program is left over from the old hash table code.  */
435
 
436
/* Number of hash tables to maintain (at once) in any testing.  */
437
#define TABLES (6)
438
 
439
/* We can have 12 statistics.  */
440
#define STATBUFSIZE (12)
441
 
442
/* Display statistics here.  */
443
int statbuf[STATBUFSIZE];
444
 
445
/* Human farts here.  */
446
char answer[100];
447
 
448
/* We test many hash tables at once.  */
449
char *hashtable[TABLES];
450
 
451
/* Points to current hash_control.  */
452
char *h;
453
char **pp;
454
char *p;
455
char *name;
456
char *value;
457
int size;
458
int used;
459
char command;
460
 
461
/* Number 0:TABLES-1 of current hashed symbol table.  */
462
int number;
463
 
464
int
465
main ()
466
{
467
  void applicatee ();
468
  void destroy ();
469
  char *what ();
470
  int *ip;
471
 
472
  number = 0;
473
  h = 0;
474
  printf ("type h <RETURN> for help\n");
475
  for (;;)
476
    {
477
      printf ("hash_test command: ");
478
      gets (answer);
479
      command = answer[0];
480
      command = TOLOWER (command);      /* Ecch!  */
481
      switch (command)
482
        {
483
        case '#':
484
          printf ("old hash table #=%d.\n", number);
485
          whattable ();
486
          break;
487
        case '?':
488
          for (pp = hashtable; pp < hashtable + TABLES; pp++)
489
            {
490
              printf ("address of hash table #%d control block is %xx\n",
491
                      pp - hashtable, *pp);
492
            }
493
          break;
494
        case 'a':
495
          hash_traverse (h, applicatee);
496
          break;
497
        case 'd':
498
          hash_traverse (h, destroy);
499
          hash_die (h);
500
          break;
501
        case 'f':
502
          p = hash_find (h, name = what ("symbol"));
503
          printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
504
          break;
505
        case 'h':
506
          printf ("# show old, select new default hash table number\n");
507
          printf ("? display all hashtable control block addresses\n");
508
          printf ("a apply a simple display-er to each symbol in table\n");
509
          printf ("d die: destroy hashtable\n");
510
          printf ("f find value of nominated symbol\n");
511
          printf ("h this help\n");
512
          printf ("i insert value into symbol\n");
513
          printf ("j jam value into symbol\n");
514
          printf ("n new hashtable\n");
515
          printf ("r replace a value with another\n");
516
          printf ("s say what %% of table is used\n");
517
          printf ("q exit this program\n");
518
          printf ("x delete a symbol from table, report its value\n");
519
          break;
520
        case 'i':
521
          p = hash_insert (h, name = what ("symbol"), value = what ("value"));
522
          if (p)
523
            {
524
              printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
525
                      p);
526
            }
527
          break;
528
        case 'j':
529
          p = hash_jam (h, name = what ("symbol"), value = what ("value"));
530
          if (p)
531
            {
532
              printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
533
            }
534
          break;
535
        case 'n':
536
          h = hashtable[number] = (char *) hash_new ();
537
          break;
538
        case 'q':
539
          exit (EXIT_SUCCESS);
540
        case 'r':
541
          p = hash_replace (h, name = what ("symbol"), value = what ("value"));
542
          printf ("old value was \"%s\"\n", p ? p : "{}");
543
          break;
544
        case 's':
545
          hash_say (h, statbuf, STATBUFSIZE);
546
          for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
547
            {
548
              printf ("%d ", *ip);
549
            }
550
          printf ("\n");
551
          break;
552
        case 'x':
553
          p = hash_delete (h, name = what ("symbol"));
554
          printf ("old value was \"%s\"\n", p ? p : "{}");
555
          break;
556
        default:
557
          printf ("I can't understand command \"%c\"\n", command);
558
          break;
559
        }
560
    }
561
}
562
 
563
char *
564
what (description)
565
     char *description;
566
{
567
  printf ("   %s : ", description);
568
  gets (answer);
569
  return xstrdup (answer);
570
}
571
 
572
void
573
destroy (string, value)
574
     char *string;
575
     char *value;
576
{
577
  free (string);
578
  free (value);
579
}
580
 
581
void
582
applicatee (string, value)
583
     char *string;
584
     char *value;
585
{
586
  printf ("%.20s-%.20s\n", string, value);
587
}
588
 
589
/* Determine number: what hash table to use.
590
   Also determine h: points to hash_control.  */
591
 
592
void
593
whattable ()
594
{
595
  for (;;)
596
    {
597
      printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
598
      gets (answer);
599
      sscanf (answer, "%d", &number);
600
      if (number >= 0 && number < TABLES)
601
        {
602
          h = hashtable[number];
603
          if (!h)
604
            {
605
              printf ("warning: current hash-table-#%d. has no hash-control\n", number);
606
            }
607
          return;
608
        }
609
      else
610
        {
611
          printf ("invalid hash table number: %d\n", number);
612
        }
613
    }
614
}
615
 
616
#endif /* TEST */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.