| /* Header file for generic hash table support. |
| Copyright (C) 1993, 1994, 1997, 1998, 2001 Free Software Foundation, Inc. |
| Written by Steve Chamberlain <sac@cygnus.com> |
| |
| This file was lifted from BFD, the Binary File Descriptor library. |
| |
| This program is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, 59 Temple Place - Suite 330, |
| Boston, MA 02111-1307, USA. */ |
| |
| #ifndef IN_GCC |
| #include <ansidecl.h> |
| #endif /* ! IN_GCC */ |
| |
| #include "obstack.h" |
| |
| typedef PTR hash_table_key; |
| |
| /* Hash table routines. There is no way to free up a hash table. */ |
| |
| /* An element in the hash table. Most uses will actually use a larger |
| structure, and an instance of this will be the first field. */ |
| |
| struct hash_entry |
| { |
| /* Next entry for this hash code. */ |
| struct hash_entry *next; |
| /* The thing being hashed. */ |
| hash_table_key key; |
| /* Hash code. This is the full hash code, not the index into the |
| table. */ |
| unsigned long hash; |
| }; |
| |
| /* A hash table. */ |
| |
| struct hash_table |
| { |
| /* The hash array. */ |
| struct hash_entry **table; |
| /* The number of slots in the hash table. */ |
| unsigned int size; |
| /* A function used to create new elements in the hash table. The |
| first entry is itself a pointer to an element. When this |
| function is first invoked, this pointer will be NULL. However, |
| having the pointer permits a hierarchy of method functions to be |
| built each of which calls the function in the superclass. Thus |
| each function should be written to allocate a new block of memory |
| only if the argument is NULL. */ |
| struct hash_entry *(*newfunc) PARAMS ((struct hash_entry *, |
| struct hash_table *, |
| hash_table_key)); |
| /* A function to compute the hash code for a key in the hash table. */ |
| unsigned long (*hash) PARAMS ((hash_table_key)); |
| /* A function to compare two keys. */ |
| bool (*comp) PARAMS ((hash_table_key, hash_table_key)); |
| /* An obstack for this hash table. */ |
| struct obstack memory; |
| }; |
| |
| /* Initialize a hash table. */ |
| extern void hash_table_init |
| PARAMS ((struct hash_table *, |
| struct hash_entry *(*) (struct hash_entry *, |
| struct hash_table *, |
| hash_table_key), |
| unsigned long (*hash) (hash_table_key), |
| bool (*comp) (hash_table_key, hash_table_key))); |
| |
| /* Initialize a hash table specifying a size. */ |
| extern void hash_table_init_n |
| PARAMS ((struct hash_table *, |
| struct hash_entry *(*) (struct hash_entry *, |
| struct hash_table *, |
| hash_table_key), |
| unsigned long (*hash) (hash_table_key), |
| bool (*comp) (hash_table_key, hash_table_key), |
| unsigned int size)); |
| |
| /* Free up a hash table. */ |
| extern void hash_table_free PARAMS ((struct hash_table *)); |
| |
| /* Look up KEY in a hash table. If CREATE is true, a new entry |
| will be created for this KEY if one does not already exist. If |
| COPY is non-NULL, it is used to copy the KEY before storing it in |
| the hash table. */ |
| extern struct hash_entry *hash_lookup |
| PARAMS ((struct hash_table *, hash_table_key key, int create, |
| hash_table_key (*copy)(struct obstack*, hash_table_key))); |
| |
| /* Base method for creating a hash table entry. */ |
| extern struct hash_entry *hash_newfunc |
| PARAMS ((struct hash_entry *, struct hash_table *, |
| hash_table_key key)); |
| |
| /* Grab some space for a hash table entry. */ |
| extern PTR hash_allocate PARAMS ((struct hash_table *, |
| unsigned int)); |
| |
| /* Traverse a hash table in a random order, calling a function on each |
| element. If the function returns false, the traversal stops. The |
| INFO argument is passed to the function. */ |
| extern void hash_traverse PARAMS ((struct hash_table *, |
| bool (*) (struct hash_entry *, |
| hash_table_key), |
| hash_table_key info)); |
| |
| /* Hash a string K, which is really of type `char*'. */ |
| extern unsigned long string_hash PARAMS ((hash_table_key k)); |
| |
| /* Compare two strings K1, K2 which are really of type `char*'. */ |
| extern bool string_compare PARAMS ((hash_table_key k1, |
| hash_table_key k2)); |
| |
| /* Copy a string K, which is really of type `char*'. */ |
| extern hash_table_key string_copy PARAMS ((struct obstack* memory, |
| hash_table_key k)); |
| |