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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [binutils-2.20.1/] [gas/] [hash.c] - Blame information for rev 853

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 205 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, 2008
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
  void *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 = (struct hash_control *) xmalloc (sizeof *ret);
117
  obstack_begin (&ret->memory, chunksize);
118
  alloc = size * sizeof (struct hash_entry *);
119
  ret->table = (struct hash_entry **) 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, void *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, void *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
void *
294
hash_replace (struct hash_control *table, const char *key, void *value)
295
{
296
  struct hash_entry *p;
297
  void *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
void *
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
void *
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
void *
348
hash_delete (struct hash_control *table, const char *key, int freeme)
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
  if (freeme)
367
    obstack_free (&table->memory, p);
368
 
369
  return p->data;
370
}
371
 
372
/* Traverse a hash table.  Call the function on every entry in the
373
   hash table.  */
374
 
375
void
376
hash_traverse (struct hash_control *table,
377
               void (*pfn) (const char *key, void *value))
378
{
379
  unsigned int i;
380
 
381
  for (i = 0; i < table->size; ++i)
382
    {
383
      struct hash_entry *p;
384
 
385
      for (p = table->table[i]; p != NULL; p = p->next)
386
        (*pfn) (p->string, p->data);
387
    }
388
}
389
 
390
/* Print hash table statistics on the specified file.  NAME is the
391
   name of the hash table, used for printing a header.  */
392
 
393
void
394
hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
395
                       const char *name ATTRIBUTE_UNUSED,
396
                       struct hash_control *table ATTRIBUTE_UNUSED)
397
{
398
#ifdef HASH_STATISTICS
399
  unsigned int i;
400
  unsigned long total;
401
  unsigned long empty;
402
 
403
  fprintf (f, "%s hash statistics:\n", name);
404
  fprintf (f, "\t%lu lookups\n", table->lookups);
405
  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
406
  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
407
  fprintf (f, "\t%lu insertions\n", table->insertions);
408
  fprintf (f, "\t%lu replacements\n", table->replacements);
409
  fprintf (f, "\t%lu deletions\n", table->deletions);
410
 
411
  total = 0;
412
  empty = 0;
413
  for (i = 0; i < table->size; ++i)
414
    {
415
      struct hash_entry *p;
416
 
417
      if (table->table[i] == NULL)
418
        ++empty;
419
      else
420
        {
421
          for (p = table->table[i]; p != NULL; p = p->next)
422
            ++total;
423
        }
424
    }
425
 
426
  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
427
  fprintf (f, "\t%lu empty slots\n", empty);
428
#endif
429
}
430
 
431
#ifdef TEST
432
 
433
/* This test program is left over from the old hash table code.  */
434
 
435
/* Number of hash tables to maintain (at once) in any testing.  */
436
#define TABLES (6)
437
 
438
/* We can have 12 statistics.  */
439
#define STATBUFSIZE (12)
440
 
441
/* Display statistics here.  */
442
int statbuf[STATBUFSIZE];
443
 
444
/* Human farts here.  */
445
char answer[100];
446
 
447
/* We test many hash tables at once.  */
448
char *hashtable[TABLES];
449
 
450
/* Points to current hash_control.  */
451
char *h;
452
char **pp;
453
char *p;
454
char *name;
455
char *value;
456
int size;
457
int used;
458
char command;
459
 
460
/* Number 0:TABLES-1 of current hashed symbol table.  */
461
int number;
462
 
463
int
464
main ()
465
{
466
  void applicatee ();
467
  void destroy ();
468
  char *what ();
469
  int *ip;
470
 
471
  number = 0;
472
  h = 0;
473
  printf ("type h <RETURN> for help\n");
474
  for (;;)
475
    {
476
      printf ("hash_test command: ");
477
      gets (answer);
478
      command = answer[0];
479
      command = TOLOWER (command);      /* Ecch!  */
480
      switch (command)
481
        {
482
        case '#':
483
          printf ("old hash table #=%d.\n", number);
484
          whattable ();
485
          break;
486
        case '?':
487
          for (pp = hashtable; pp < hashtable + TABLES; pp++)
488
            {
489
              printf ("address of hash table #%d control block is %xx\n",
490
                      pp - hashtable, *pp);
491
            }
492
          break;
493
        case 'a':
494
          hash_traverse (h, applicatee);
495
          break;
496
        case 'd':
497
          hash_traverse (h, destroy);
498
          hash_die (h);
499
          break;
500
        case 'f':
501
          p = hash_find (h, name = what ("symbol"));
502
          printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
503
          break;
504
        case 'h':
505
          printf ("# show old, select new default hash table number\n");
506
          printf ("? display all hashtable control block addresses\n");
507
          printf ("a apply a simple display-er to each symbol in table\n");
508
          printf ("d die: destroy hashtable\n");
509
          printf ("f find value of nominated symbol\n");
510
          printf ("h this help\n");
511
          printf ("i insert value into symbol\n");
512
          printf ("j jam value into symbol\n");
513
          printf ("n new hashtable\n");
514
          printf ("r replace a value with another\n");
515
          printf ("s say what %% of table is used\n");
516
          printf ("q exit this program\n");
517
          printf ("x delete a symbol from table, report its value\n");
518
          break;
519
        case 'i':
520
          p = hash_insert (h, name = what ("symbol"), value = what ("value"));
521
          if (p)
522
            {
523
              printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
524
                      p);
525
            }
526
          break;
527
        case 'j':
528
          p = hash_jam (h, name = what ("symbol"), value = what ("value"));
529
          if (p)
530
            {
531
              printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
532
            }
533
          break;
534
        case 'n':
535
          h = hashtable[number] = (char *) hash_new ();
536
          break;
537
        case 'q':
538
          exit (EXIT_SUCCESS);
539
        case 'r':
540
          p = hash_replace (h, name = what ("symbol"), value = what ("value"));
541
          printf ("old value was \"%s\"\n", p ? p : "{}");
542
          break;
543
        case 's':
544
          hash_say (h, statbuf, STATBUFSIZE);
545
          for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
546
            {
547
              printf ("%d ", *ip);
548
            }
549
          printf ("\n");
550
          break;
551
        case 'x':
552
          p = hash_delete (h, name = what ("symbol"));
553
          printf ("old value was \"%s\"\n", p ? p : "{}");
554
          break;
555
        default:
556
          printf ("I can't understand command \"%c\"\n", command);
557
          break;
558
        }
559
    }
560
}
561
 
562
char *
563
what (description)
564
     char *description;
565
{
566
  printf ("   %s : ", description);
567
  gets (answer);
568
  return xstrdup (answer);
569
}
570
 
571
void
572
destroy (string, value)
573
     char *string;
574
     char *value;
575
{
576
  free (string);
577
  free (value);
578
}
579
 
580
void
581
applicatee (string, value)
582
     char *string;
583
     char *value;
584
{
585
  printf ("%.20s-%.20s\n", string, value);
586
}
587
 
588
/* Determine number: what hash table to use.
589
   Also determine h: points to hash_control.  */
590
 
591
void
592
whattable ()
593
{
594
  for (;;)
595
    {
596
      printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
597
      gets (answer);
598
      sscanf (answer, "%d", &number);
599
      if (number >= 0 && number < TABLES)
600
        {
601
          h = hashtable[number];
602
          if (!h)
603
            {
604
              printf ("warning: current hash-table-#%d. has no hash-control\n", number);
605
            }
606
          return;
607
        }
608
      else
609
        {
610
          printf ("invalid hash table number: %d\n", number);
611
        }
612
    }
613
}
614
 
615
#endif /* TEST */

powered by: WebSVN 2.1.0

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