gcc/hash.h

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