Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /* 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, 2009, 2011, 2013
  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 = bfd_hash_set_default_size (size);
  82. }
  83.  
  84. /* Create a hash table.  This return a control block.  */
  85.  
  86. struct hash_control *
  87. hash_new_sized (unsigned long size)
  88. {
  89.   unsigned long alloc;
  90.   struct hash_control *ret;
  91.  
  92.   ret = (struct hash_control *) xmalloc (sizeof *ret);
  93.   obstack_begin (&ret->memory, chunksize);
  94.   alloc = size * sizeof (struct hash_entry *);
  95.   ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  96.   memset (ret->table, 0, alloc);
  97.   ret->size = size;
  98.  
  99. #ifdef HASH_STATISTICS
  100.   ret->lookups = 0;
  101.   ret->hash_compares = 0;
  102.   ret->string_compares = 0;
  103.   ret->insertions = 0;
  104.   ret->replacements = 0;
  105.   ret->deletions = 0;
  106. #endif
  107.  
  108.   return ret;
  109. }
  110.  
  111. struct hash_control *
  112. hash_new (void)
  113. {
  114.   return hash_new_sized (gas_hash_table_size);
  115. }
  116.  
  117. /* Delete a hash table, freeing all allocated memory.  */
  118.  
  119. void
  120. hash_die (struct hash_control *table)
  121. {
  122.   obstack_free (&table->memory, 0);
  123.   free (table);
  124. }
  125.  
  126. /* Look up a string in a hash table.  This returns a pointer to the
  127.    hash_entry, or NULL if the string is not in the table.  If PLIST is
  128.    not NULL, this sets *PLIST to point to the start of the list which
  129.    would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
  130.    to the hash code for KEY.
  131.  
  132.    Each time we look up a string, we move it to the start of the list
  133.    for its hash code, to take advantage of referential locality.  */
  134.  
  135. static struct hash_entry *
  136. hash_lookup (struct hash_control *table, const char *key, size_t len,
  137.              struct hash_entry ***plist, unsigned long *phash)
  138. {
  139.   unsigned long hash;
  140.   size_t n;
  141.   unsigned int c;
  142.   unsigned int hindex;
  143.   struct hash_entry **list;
  144.   struct hash_entry *p;
  145.   struct hash_entry *prev;
  146.  
  147. #ifdef HASH_STATISTICS
  148.   ++table->lookups;
  149. #endif
  150.  
  151.   hash = 0;
  152.   for (n = 0; n < len; n++)
  153.     {
  154.       c = key[n];
  155.       hash += c + (c << 17);
  156.       hash ^= hash >> 2;
  157.     }
  158.   hash += len + (len << 17);
  159.   hash ^= hash >> 2;
  160.  
  161.   if (phash != NULL)
  162.     *phash = hash;
  163.  
  164.   hindex = hash % table->size;
  165.   list = table->table + hindex;
  166.  
  167.   if (plist != NULL)
  168.     *plist = list;
  169.  
  170.   prev = NULL;
  171.   for (p = *list; p != NULL; p = p->next)
  172.     {
  173. #ifdef HASH_STATISTICS
  174.       ++table->hash_compares;
  175. #endif
  176.  
  177.       if (p->hash == hash)
  178.         {
  179. #ifdef HASH_STATISTICS
  180.           ++table->string_compares;
  181. #endif
  182.  
  183.           if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
  184.             {
  185.               if (prev != NULL)
  186.                 {
  187.                   prev->next = p->next;
  188.                   p->next = *list;
  189.                   *list = p;
  190.                 }
  191.  
  192.               return p;
  193.             }
  194.         }
  195.  
  196.       prev = p;
  197.     }
  198.  
  199.   return NULL;
  200. }
  201.  
  202. /* Insert an entry into a hash table.  This returns NULL on success.
  203.    On error, it returns a printable string indicating the error.  It
  204.    is considered to be an error if the entry already exists in the
  205.    hash table.  */
  206.  
  207. const char *
  208. hash_insert (struct hash_control *table, const char *key, void *val)
  209. {
  210.   struct hash_entry *p;
  211.   struct hash_entry **list;
  212.   unsigned long hash;
  213.  
  214.   p = hash_lookup (table, key, strlen (key), &list, &hash);
  215.   if (p != NULL)
  216.     return "exists";
  217.  
  218. #ifdef HASH_STATISTICS
  219.   ++table->insertions;
  220. #endif
  221.  
  222.   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
  223.   p->string = key;
  224.   p->hash = hash;
  225.   p->data = val;
  226.  
  227.   p->next = *list;
  228.   *list = p;
  229.  
  230.   return NULL;
  231. }
  232.  
  233. /* Insert or replace an entry in a hash table.  This returns NULL on
  234.    success.  On error, it returns a printable string indicating the
  235.    error.  If an entry already exists, its value is replaced.  */
  236.  
  237. const char *
  238. hash_jam (struct hash_control *table, const char *key, void *val)
  239. {
  240.   struct hash_entry *p;
  241.   struct hash_entry **list;
  242.   unsigned long hash;
  243.  
  244.   p = hash_lookup (table, key, strlen (key), &list, &hash);
  245.   if (p != NULL)
  246.     {
  247. #ifdef HASH_STATISTICS
  248.       ++table->replacements;
  249. #endif
  250.  
  251.       p->data = val;
  252.     }
  253.   else
  254.     {
  255. #ifdef HASH_STATISTICS
  256.       ++table->insertions;
  257. #endif
  258.  
  259.       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
  260.       p->string = key;
  261.       p->hash = hash;
  262.       p->data = val;
  263.  
  264.       p->next = *list;
  265.       *list = p;
  266.     }
  267.  
  268.   return NULL;
  269. }
  270.  
  271. /* Replace an existing entry in a hash table.  This returns the old
  272.    value stored for the entry.  If the entry is not found in the hash
  273.    table, this does nothing and returns NULL.  */
  274.  
  275. void *
  276. hash_replace (struct hash_control *table, const char *key, void *value)
  277. {
  278.   struct hash_entry *p;
  279.   void *ret;
  280.  
  281.   p = hash_lookup (table, key, strlen (key), NULL, NULL);
  282.   if (p == NULL)
  283.     return NULL;
  284.  
  285. #ifdef HASH_STATISTICS
  286.   ++table->replacements;
  287. #endif
  288.  
  289.   ret = p->data;
  290.  
  291.   p->data = value;
  292.  
  293.   return ret;
  294. }
  295.  
  296. /* Find an entry in a hash table, returning its value.  Returns NULL
  297.    if the entry is not found.  */
  298.  
  299. void *
  300. hash_find (struct hash_control *table, const char *key)
  301. {
  302.   struct hash_entry *p;
  303.  
  304.   p = hash_lookup (table, key, strlen (key), NULL, NULL);
  305.   if (p == NULL)
  306.     return NULL;
  307.  
  308.   return p->data;
  309. }
  310.  
  311. /* As hash_find, but KEY is of length LEN and is not guaranteed to be
  312.    NUL-terminated.  */
  313.  
  314. void *
  315. hash_find_n (struct hash_control *table, const char *key, size_t len)
  316. {
  317.   struct hash_entry *p;
  318.  
  319.   p = hash_lookup (table, key, len, NULL, NULL);
  320.   if (p == NULL)
  321.     return NULL;
  322.  
  323.   return p->data;
  324. }
  325.  
  326. /* Delete an entry from a hash table.  This returns the value stored
  327.    for that entry, or NULL if there is no such entry.  */
  328.  
  329. void *
  330. hash_delete (struct hash_control *table, const char *key, int freeme)
  331. {
  332.   struct hash_entry *p;
  333.   struct hash_entry **list;
  334.  
  335.   p = hash_lookup (table, key, strlen (key), &list, NULL);
  336.   if (p == NULL)
  337.     return NULL;
  338.  
  339.   if (p != *list)
  340.     abort ();
  341.  
  342. #ifdef HASH_STATISTICS
  343.   ++table->deletions;
  344. #endif
  345.  
  346.   *list = p->next;
  347.  
  348.   if (freeme)
  349.     obstack_free (&table->memory, p);
  350.  
  351.   return p->data;
  352. }
  353.  
  354. /* Traverse a hash table.  Call the function on every entry in the
  355.    hash table.  */
  356.  
  357. void
  358. hash_traverse (struct hash_control *table,
  359.                void (*pfn) (const char *key, void *value))
  360. {
  361.   unsigned int i;
  362.  
  363.   for (i = 0; i < table->size; ++i)
  364.     {
  365.       struct hash_entry *p;
  366.  
  367.       for (p = table->table[i]; p != NULL; p = p->next)
  368.         (*pfn) (p->string, p->data);
  369.     }
  370. }
  371.  
  372. /* Print hash table statistics on the specified file.  NAME is the
  373.    name of the hash table, used for printing a header.  */
  374.  
  375. void
  376. hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
  377.                        const char *name ATTRIBUTE_UNUSED,
  378.                        struct hash_control *table ATTRIBUTE_UNUSED)
  379. {
  380. #ifdef HASH_STATISTICS
  381.   unsigned int i;
  382.   unsigned long total;
  383.   unsigned long empty;
  384.  
  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);
  392.  
  393.   total = 0;
  394.   empty = 0;
  395.   for (i = 0; i < table->size; ++i)
  396.     {
  397.       struct hash_entry *p;
  398.  
  399.       if (table->table[i] == NULL)
  400.         ++empty;
  401.       else
  402.         {
  403.           for (p = table->table[i]; p != NULL; p = p->next)
  404.             ++total;
  405.         }
  406.     }
  407.  
  408.   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
  409.   fprintf (f, "\t%lu empty slots\n", empty);
  410. #endif
  411. }
  413. #ifdef TEST
  414.  
  415. /* This test program is left over from the old hash table code.  */
  416.  
  417. /* Number of hash tables to maintain (at once) in any testing.  */
  418. #define TABLES (6)
  419.  
  420. /* We can have 12 statistics.  */
  421. #define STATBUFSIZE (12)
  422.  
  423. /* Display statistics here.  */
  424. int statbuf[STATBUFSIZE];
  425.  
  426. /* Human farts here.  */
  427. char answer[100];
  428.  
  429. /* We test many hash tables at once.  */
  430. char *hashtable[TABLES];
  431.  
  432. /* Points to current hash_control.  */
  433. char *h;
  434. char **pp;
  435. char *p;
  436. char *name;
  437. char *value;
  438. int size;
  439. int used;
  440. char command;
  441.  
  442. /* Number 0:TABLES-1 of current hashed symbol table.  */
  443. int number;
  444.  
  445. int
  446. main ()
  447. {
  448.   void applicatee ();
  449.   void destroy ();
  450.   char *what ();
  451.   int *ip;
  452.  
  453.   number = 0;
  454.   h = 0;
  455.   printf ("type h <RETURN> for help\n");
  456.   for (;;)
  457.     {
  458.       printf ("hash_test command: ");
  459.       gets (answer);
  460.       command = answer[0];
  461.       command = TOLOWER (command);      /* Ecch!  */
  462.       switch (command)
  463.         {
  464.         case '#':
  465.           printf ("old hash table #=%d.\n", number);
  466.           whattable ();
  467.           break;
  468.         case '?':
  469.           for (pp = hashtable; pp < hashtable + TABLES; pp++)
  470.             {
  471.               printf ("address of hash table #%d control block is %xx\n",
  472.                       pp - hashtable, *pp);
  473.             }
  474.           break;
  475.         case 'a':
  476.           hash_traverse (h, applicatee);
  477.           break;
  478.         case 'd':
  479.           hash_traverse (h, destroy);
  480.           hash_die (h);
  481.           break;
  482.         case 'f':
  483.           p = hash_find (h, name = what ("symbol"));
  484.           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
  485.           break;
  486.         case 'h':
  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");
  500.           break;
  501.         case 'i':
  502.           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
  503.           if (p)
  504.             {
  505.               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
  506.                       p);
  507.             }
  508.           break;
  509.         case 'j':
  510.           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
  511.           if (p)
  512.             {
  513.               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
  514.             }
  515.           break;
  516.         case 'n':
  517.           h = hashtable[number] = (char *) hash_new ();
  518.           break;
  519.         case 'q':
  520.           exit (EXIT_SUCCESS);
  521.         case 'r':
  522.           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
  523.           printf ("old value was \"%s\"\n", p ? p : "{}");
  524.           break;
  525.         case 's':
  526.           hash_say (h, statbuf, STATBUFSIZE);
  527.           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
  528.             {
  529.               printf ("%d ", *ip);
  530.             }
  531.           printf ("\n");
  532.           break;
  533.         case 'x':
  534.           p = hash_delete (h, name = what ("symbol"));
  535.           printf ("old value was \"%s\"\n", p ? p : "{}");
  536.           break;
  537.         default:
  538.           printf ("I can't understand command \"%c\"\n", command);
  539.           break;
  540.         }
  541.     }
  542. }
  543.  
  544. char *
  545. what (description)
  546.      char *description;
  547. {
  548.   printf ("   %s : ", description);
  549.   gets (answer);
  550.   return xstrdup (answer);
  551. }
  552.  
  553. void
  554. destroy (string, value)
  555.      char *string;
  556.      char *value;
  557. {
  558.   free (string);
  559.   free (value);
  560. }
  561.  
  562. void
  563. applicatee (string, value)
  564.      char *string;
  565.      char *value;
  566. {
  567.   printf ("%.20s-%.20s\n", string, value);
  568. }
  569.  
  570. /* Determine number: what hash table to use.
  571.    Also determine h: points to hash_control.  */
  572.  
  573. void
  574. whattable ()
  575. {
  576.   for (;;)
  577.     {
  578.       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
  579.       gets (answer);
  580.       sscanf (answer, "%d", &number);
  581.       if (number >= 0 && number < TABLES)
  582.         {
  583.           h = hashtable[number];
  584.           if (!h)
  585.             {
  586.               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
  587.             }
  588.           return;
  589.         }
  590.       else
  591.         {
  592.           printf ("invalid hash table number: %d\n", number);
  593.         }
  594.     }
  595. }
  596.  
  597. #endif /* TEST */
  598.