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