1169695Skan/* Hash tables. 2169695Skan Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc. 3169695Skan 4169695SkanThis program is free software; you can redistribute it and/or modify it 5169695Skanunder the terms of the GNU General Public License as published by the 6169695SkanFree Software Foundation; either version 2, or (at your option) any 7169695Skanlater version. 8169695Skan 9169695SkanThis program is distributed in the hope that it will be useful, 10169695Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 11169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12169695SkanGNU General Public License for more details. 13169695Skan 14169695SkanYou should have received a copy of the GNU General Public License 15169695Skanalong with this program; if not, write to the Free Software 16169695SkanFoundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 17169695Skan 18169695Skan#ifndef LIBCPP_SYMTAB_H 19169695Skan#define LIBCPP_SYMTAB_H 20169695Skan 21169695Skan#include "obstack.h" 22169695Skan#define GTY(x) /* nothing */ 23169695Skan 24169695Skan/* This is what each hash table entry points to. It may be embedded 25169695Skan deeply within another object. */ 26169695Skantypedef struct ht_identifier ht_identifier; 27169695Skanstruct ht_identifier GTY(()) 28169695Skan{ 29169695Skan const unsigned char *str; 30169695Skan unsigned int len; 31169695Skan unsigned int hash_value; 32169695Skan}; 33169695Skan 34169695Skan#define HT_LEN(NODE) ((NODE)->len) 35169695Skan#define HT_STR(NODE) ((NODE)->str) 36169695Skan 37169695Skantypedef struct ht hash_table; 38169695Skantypedef struct ht_identifier *hashnode; 39169695Skan 40169695Skanenum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC, HT_ALLOCED}; 41169695Skan 42169695Skan/* An identifier hash table for cpplib and the front ends. */ 43169695Skanstruct ht 44169695Skan{ 45169695Skan /* Identifiers are allocated from here. */ 46169695Skan struct obstack stack; 47169695Skan 48169695Skan hashnode *entries; 49169695Skan /* Call back, allocate a node. */ 50169695Skan hashnode (*alloc_node) (hash_table *); 51169695Skan /* Call back, allocate something that hangs off a node like a cpp_macro. 52169695Skan NULL means use the usual allocator. */ 53169695Skan void * (*alloc_subobject) (size_t); 54169695Skan 55169695Skan unsigned int nslots; /* Total slots in the entries array. */ 56169695Skan unsigned int nelements; /* Number of live elements. */ 57169695Skan 58169695Skan /* Link to reader, if any. For the benefit of cpplib. */ 59169695Skan struct cpp_reader *pfile; 60169695Skan 61169695Skan /* Table usage statistics. */ 62169695Skan unsigned int searches; 63169695Skan unsigned int collisions; 64169695Skan 65169695Skan /* Should 'entries' be freed when it is no longer needed? */ 66169695Skan bool entries_owned; 67169695Skan}; 68169695Skan 69169695Skan/* Initialize the hashtable with 2 ^ order entries. */ 70169695Skanextern hash_table *ht_create (unsigned int order); 71169695Skan 72169695Skan/* Frees all memory associated with a hash table. */ 73169695Skanextern void ht_destroy (hash_table *); 74169695Skan 75169695Skanextern hashnode ht_lookup (hash_table *, const unsigned char *, 76169695Skan size_t, enum ht_lookup_option); 77169695Skanextern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *, 78169695Skan size_t, unsigned int, 79169695Skan enum ht_lookup_option); 80169695Skan#define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); 81169695Skan#define HT_HASHFINISH(r, len) ((r) + (len)) 82169695Skan 83169695Skan/* For all nodes in TABLE, make a callback. The callback takes 84169695Skan TABLE->PFILE, the node, and a PTR, and the callback sequence stops 85169695Skan if the callback returns zero. */ 86169695Skantypedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); 87169695Skanextern void ht_forall (hash_table *, ht_cb, const void *); 88169695Skan 89169695Skan/* Restore the hash table. */ 90169695Skanextern void ht_load (hash_table *ht, hashnode *entries, 91169695Skan unsigned int nslots, unsigned int nelements, bool own); 92169695Skan 93169695Skan/* Dump allocation statistics to stderr. */ 94169695Skanextern void ht_dump_statistics (hash_table *); 95169695Skan 96169695Skan#endif /* LIBCPP_SYMTAB_H */ 97