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