contrib/gcc/hash.h

   1 /* Header file for generic hash table support.
   2    Copyright (C) 1993, 1994, 1997, 1998 Free Software Foundation, Inc.
   3    Written by Steve Chamberlain <sac@cygnus.com>
   4
   5 This file was lifted from BFD, the Binary File Descriptor library.
   6
   7 This program 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 of the License, or
  10 (at your option) any later version.
  11
  12 This program 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.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #ifndef IN_GCC
  23 #include <ansidecl.h>
  24 #endif /* ! IN_GCC */
  25
  26 #include "obstack.h"
  27
  28 typedef enum {false, true} boolean;
  29
  30 typedef PTR hash_table_key;
  31
  32 /* Hash table routines.  There is no way to free up a hash table.  */
  33
  34 /* An element in the hash table.  Most uses will actually use a larger
  35    structure, and an instance of this will be the first field.  */
  36
  37 struct hash_entry
  38 {
  39   /* Next entry for this hash code.  */
  40   struct hash_entry *next;
  41   /* The thing being hashed.  */
  42   hash_table_key key;
  43   /* Hash code.  This is the full hash code, not the index into the
  44      table.  */
  45   unsigned long hash;
  46 };
  47
  48 /* A hash table.  */
  49
  50 struct hash_table
  51 {
  52   /* The hash array.  */
  53   struct hash_entry **table;
  54   /* The number of slots in the hash table.  */
  55   unsigned int size;
  56   /* A function used to create new elements in the hash table.  The
  57      first entry is itself a pointer to an element.  When this
  58      function is first invoked, this pointer will be NULL.  However,
  59      having the pointer permits a hierarchy of method functions to be
  60      built each of which calls the function in the superclass.  Thus
  61      each function should be written to allocate a new block of memory
  62      only if the argument is NULL.  */
  63   struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *,
  64                                          struct hash_table *,
  65                                          hash_table_key));
  66   /* A function to compute the hash code for a key in the hash table.  */
  67   unsigned long (*hash) PARAMS ((hash_table_key));
  68   /* A function to compare two keys.  */
  69   boolean (*comp) PARAMS ((hash_table_key, hash_table_key));
  70   /* An obstack for this hash table.  */
  71   struct obstack memory;
  72 };
  73
  74 /* Initialize a hash table.  */
  75 extern boolean hash_table_init
  76   PARAMS ((struct hash_table *,
  77            struct hash_entry *(*) (struct hash_entry *,
  78                                    struct hash_table *,
  79                                    hash_table_key),
  80            unsigned long (*hash) (hash_table_key),
  81            boolean (*comp) (hash_table_key, hash_table_key)));
  82
  83 /* Initialize a hash table specifying a size.  */
  84 extern boolean hash_table_init_n
  85   PARAMS ((struct hash_table *,
  86            struct hash_entry *(*) (struct hash_entry *,
  87                                    struct hash_table *,
  88                                    hash_table_key),
  89            unsigned long (*hash) (hash_table_key),
  90            boolean (*comp) (hash_table_key, hash_table_key),
  91            unsigned int size));
  92
  93 /* Free up a hash table.  */
  94 extern void hash_table_free PARAMS ((struct hash_table *));
  95
  96 /* Look up KEY in a hash table.  If CREATE is true, a new entry
  97    will be created for this KEY if one does not already exist.  If
  98    COPY is non-NULL, it is used to copy the KEY before storing it in
  99    the hash table.  */
 100 extern struct hash_entry *hash_lookup
 101   PARAMS ((struct hash_table *, hash_table_key key, boolean create,
 102            hash_table_key (*copy)(struct obstack*, hash_table_key)));
 103
 104 /* Base method for creating a hash table entry.  */
 105 extern struct hash_entry *hash_newfunc
 106   PARAMS ((struct hash_entry *, struct hash_table *,
 107            hash_table_key key));
 108
 109 /* Grab some space for a hash table entry.  */
 110 extern PTR hash_allocate PARAMS ((struct hash_table *,
 111                                   unsigned int));
 112
 113 /* Traverse a hash table in a random order, calling a function on each
 114    element.  If the function returns false, the traversal stops.  The
 115    INFO argument is passed to the function.  */
 116 extern void hash_traverse PARAMS ((struct hash_table *,
 117                                    boolean (*) (struct hash_entry *,
 118                                                 hash_table_key),
 119                                    hash_table_key info));
 120
 121 /* Hash a string K, which is really of type `char*'.  */
 122 extern unsigned long string_hash PARAMS ((hash_table_key k));
 123
 124 /* Compare two strings K1, K2 which are really of type `char*'.  */
 125 extern boolean string_compare PARAMS ((hash_table_key k1,
 126                                        hash_table_key k2));
 127
 128 /* Copy a string K, which is really of type `char*'.  */
 129 extern hash_table_key string_copy PARAMS ((struct obstack* memory,
 130                                            hash_table_key k));
 131