1 /* Hash tables. 2 Copyright (C) 2000, 2001, 2003 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 17 18 #ifndef GCC_HASHTABLE_H 19 #define GCC_HASHTABLE_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. */ 50 hashnode (*alloc_node) (hash_table *); 51 52 unsigned int nslots; /* Total slots in the entries array. */ 53 unsigned int nelements; /* Number of live elements. */ 54 55 /* Link to reader, if any. For the benefit of cpplib. */ 56 struct cpp_reader *pfile; 57 58 /* Table usage statistics. */ 59 unsigned int searches; 60 unsigned int collisions; 61 }; 62 63 /* Initialize the hashtable with 2 ^ order entries. */ 64 extern hash_table *ht_create (unsigned int order); 65 66 /* Frees all memory associated with a hash table. */ 67 extern void ht_destroy (hash_table *); 68 69 extern hashnode ht_lookup (hash_table *, const unsigned char *, 70 size_t, enum ht_lookup_option); 71 72 /* For all nodes in TABLE, make a callback. The callback takes 73 TABLE->PFILE, the node, and a PTR, and the callback sequence stops 74 if the callback returns zero. */ 75 typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); 76 extern void ht_forall (hash_table *, ht_cb, const void *); 77 78 /* Dump allocation statistics to stderr. */ 79 extern void ht_dump_statistics (hash_table *); 80 81 #endif /* GCC_HASHTABLE_H */ 82