gcc/hash.h

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