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 5This file was lifted from BFD, the Binary File Descriptor library. 6 7This program is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2 of the License, or 10(at your option) any later version. 11 12This program is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with this program; if not, write to the Free Software 19Foundation, 59 Temple Place - Suite 330, 20Boston, MA 02111-1307, USA. */ 21 22#ifndef IN_GCC 23#include <ansidecl.h> 24#endif /* ! IN_GCC */ 25 26#include "obstack.h" 27 28typedef enum {false, true} boolean; 29 30typedef 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 37struct 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 50struct 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. */ 75extern 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. */ 84extern 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. */ 94extern 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. */ 100extern 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. */ 105extern 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. */ 110extern 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. */ 116extern 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*'. */ 122extern unsigned long string_hash PARAMS ((hash_table_key k)); 123 124/* Compare two strings K1, K2 which are really of type `char*'. */ 125extern 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*'. */ 129extern hash_table_key string_copy PARAMS ((struct obstack* memory, 130 hash_table_key k)); 131 132