1*404b540aSrobert /* Hash tables. 2*404b540aSrobert Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc. 3*404b540aSrobert 4*404b540aSrobert This program is free software; you can redistribute it and/or modify it 5*404b540aSrobert under the terms of the GNU General Public License as published by the 6*404b540aSrobert Free Software Foundation; either version 2, or (at your option) any 7*404b540aSrobert later version. 8*404b540aSrobert 9*404b540aSrobert This program is distributed in the hope that it will be useful, 10*404b540aSrobert but WITHOUT ANY WARRANTY; without even the implied warranty of 11*404b540aSrobert MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12*404b540aSrobert GNU General Public License for more details. 13*404b540aSrobert 14*404b540aSrobert You should have received a copy of the GNU General Public License 15*404b540aSrobert along with this program; if not, write to the Free Software 16*404b540aSrobert Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 17*404b540aSrobert 18*404b540aSrobert #ifndef LIBCPP_SYMTAB_H 19*404b540aSrobert #define LIBCPP_SYMTAB_H 20*404b540aSrobert 21*404b540aSrobert #include "obstack.h" 22*404b540aSrobert #define GTY(x) /* nothing */ 23*404b540aSrobert 24*404b540aSrobert /* This is what each hash table entry points to. It may be embedded 25*404b540aSrobert deeply within another object. */ 26*404b540aSrobert typedef struct ht_identifier ht_identifier; 27*404b540aSrobert struct ht_identifier GTY(()) 28*404b540aSrobert { 29*404b540aSrobert const unsigned char *str; 30*404b540aSrobert unsigned int len; 31*404b540aSrobert unsigned int hash_value; 32*404b540aSrobert }; 33*404b540aSrobert 34*404b540aSrobert #define HT_LEN(NODE) ((NODE)->len) 35*404b540aSrobert #define HT_STR(NODE) ((NODE)->str) 36*404b540aSrobert 37*404b540aSrobert typedef struct ht hash_table; 38*404b540aSrobert typedef struct ht_identifier *hashnode; 39*404b540aSrobert 40*404b540aSrobert enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC, HT_ALLOCED}; 41*404b540aSrobert 42*404b540aSrobert /* An identifier hash table for cpplib and the front ends. */ 43*404b540aSrobert struct ht 44*404b540aSrobert { 45*404b540aSrobert /* Identifiers are allocated from here. */ 46*404b540aSrobert struct obstack stack; 47*404b540aSrobert 48*404b540aSrobert hashnode *entries; 49*404b540aSrobert /* Call back, allocate a node. */ 50*404b540aSrobert hashnode (*alloc_node) (hash_table *); 51*404b540aSrobert /* Call back, allocate something that hangs off a node like a cpp_macro. 52*404b540aSrobert NULL means use the usual allocator. */ 53*404b540aSrobert void * (*alloc_subobject) (size_t); 54*404b540aSrobert 55*404b540aSrobert unsigned int nslots; /* Total slots in the entries array. */ 56*404b540aSrobert unsigned int nelements; /* Number of live elements. */ 57*404b540aSrobert 58*404b540aSrobert /* Link to reader, if any. For the benefit of cpplib. */ 59*404b540aSrobert struct cpp_reader *pfile; 60*404b540aSrobert 61*404b540aSrobert /* Table usage statistics. */ 62*404b540aSrobert unsigned int searches; 63*404b540aSrobert unsigned int collisions; 64*404b540aSrobert 65*404b540aSrobert /* Should 'entries' be freed when it is no longer needed? */ 66*404b540aSrobert bool entries_owned; 67*404b540aSrobert }; 68*404b540aSrobert 69*404b540aSrobert /* Initialize the hashtable with 2 ^ order entries. */ 70*404b540aSrobert extern hash_table *ht_create (unsigned int order); 71*404b540aSrobert 72*404b540aSrobert /* Frees all memory associated with a hash table. */ 73*404b540aSrobert extern void ht_destroy (hash_table *); 74*404b540aSrobert 75*404b540aSrobert extern hashnode ht_lookup (hash_table *, const unsigned char *, 76*404b540aSrobert size_t, enum ht_lookup_option); 77*404b540aSrobert extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *, 78*404b540aSrobert size_t, unsigned int, 79*404b540aSrobert enum ht_lookup_option); 80*404b540aSrobert #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); 81*404b540aSrobert #define HT_HASHFINISH(r, len) ((r) + (len)) 82*404b540aSrobert 83*404b540aSrobert /* For all nodes in TABLE, make a callback. The callback takes 84*404b540aSrobert TABLE->PFILE, the node, and a PTR, and the callback sequence stops 85*404b540aSrobert if the callback returns zero. */ 86*404b540aSrobert typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); 87*404b540aSrobert extern void ht_forall (hash_table *, ht_cb, const void *); 88*404b540aSrobert 89*404b540aSrobert /* Restore the hash table. */ 90*404b540aSrobert extern void ht_load (hash_table *ht, hashnode *entries, 91*404b540aSrobert unsigned int nslots, unsigned int nelements, bool own); 92*404b540aSrobert 93*404b540aSrobert /* Dump allocation statistics to stderr. */ 94*404b540aSrobert extern void ht_dump_statistics (hash_table *); 95*404b540aSrobert 96*404b540aSrobert #endif /* LIBCPP_SYMTAB_H */ 97