1/* Hash tables. 2 Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc. 3 4This program is free software; you can redistribute it and/or modify it 5under the terms of the GNU General Public License as published by the 6Free Software Foundation; either version 2, or (at your option) any 7later version. 8 9This program is distributed in the hope that it will be useful, 10but WITHOUT ANY WARRANTY; without even the implied warranty of 11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12GNU General Public License for more details. 13 14You should have received a copy of the GNU General Public License 15along with this program; if not, write to the Free Software 16Foundation, 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. */ 26typedef struct ht_identifier ht_identifier; 27struct 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 37typedef struct ht hash_table; 38typedef struct ht_identifier *hashnode; 39 40enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC, HT_ALLOCED}; 41 42/* An identifier hash table for cpplib and the front ends. */ 43struct 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. */ 70extern hash_table *ht_create (unsigned int order); 71 72/* Frees all memory associated with a hash table. */ 73extern void ht_destroy (hash_table *); 74 75extern hashnode ht_lookup (hash_table *, const unsigned char *, 76 size_t, enum ht_lookup_option); 77extern 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. */ 86typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); 87extern void ht_forall (hash_table *, ht_cb, const void *); 88 89/* Restore the hash table. */ 90extern void ht_load (hash_table *ht, hashnode *entries, 91 unsigned int nslots, unsigned int nelements, bool own); 92 93/* Dump allocation statistics to stderr. */ 94extern void ht_dump_statistics (hash_table *); 95 96#endif /* LIBCPP_SYMTAB_H */ 97