14fee23f9Smrg /* Hash tables. 2*b1e83836Smrg Copyright (C) 2000-2022 Free Software Foundation, Inc. 34fee23f9Smrg 44fee23f9Smrg This program is free software; you can redistribute it and/or modify it 54fee23f9Smrg under the terms of the GNU General Public License as published by the 64fee23f9Smrg Free Software Foundation; either version 3, or (at your option) any 74fee23f9Smrg later version. 84fee23f9Smrg 94fee23f9Smrg This program is distributed in the hope that it will be useful, 104fee23f9Smrg but WITHOUT ANY WARRANTY; without even the implied warranty of 114fee23f9Smrg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 124fee23f9Smrg GNU General Public License for more details. 134fee23f9Smrg 144fee23f9Smrg You should have received a copy of the GNU General Public License 154fee23f9Smrg along with this program; see the file COPYING3. If not see 164fee23f9Smrg <http://www.gnu.org/licenses/>. */ 174fee23f9Smrg 184fee23f9Smrg #ifndef LIBCPP_SYMTAB_H 194fee23f9Smrg #define LIBCPP_SYMTAB_H 204fee23f9Smrg 214fee23f9Smrg #include "obstack.h" 224fee23f9Smrg 234fee23f9Smrg #ifndef GTY 244fee23f9Smrg #define GTY(x) /* nothing */ 254fee23f9Smrg #endif 264fee23f9Smrg 274fee23f9Smrg /* This is what each hash table entry points to. It may be embedded 284fee23f9Smrg deeply within another object. */ 294fee23f9Smrg typedef struct ht_identifier ht_identifier; 3048fb7bfaSmrg typedef struct ht_identifier *ht_identifier_ptr; 314fee23f9Smrg struct GTY(()) ht_identifier { 324fee23f9Smrg const unsigned char *str; 334fee23f9Smrg unsigned int len; 344fee23f9Smrg unsigned int hash_value; 354fee23f9Smrg }; 364fee23f9Smrg 374fee23f9Smrg #define HT_LEN(NODE) ((NODE)->len) 384fee23f9Smrg #define HT_STR(NODE) ((NODE)->str) 394fee23f9Smrg 4048fb7bfaSmrg typedef struct ht cpp_hash_table; 414fee23f9Smrg typedef struct ht_identifier *hashnode; 424fee23f9Smrg 434fee23f9Smrg enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC}; 444fee23f9Smrg 454fee23f9Smrg /* An identifier hash table for cpplib and the front ends. */ 464fee23f9Smrg struct ht 474fee23f9Smrg { 484fee23f9Smrg /* Identifiers are allocated from here. */ 494fee23f9Smrg struct obstack stack; 504fee23f9Smrg 514fee23f9Smrg hashnode *entries; 524fee23f9Smrg /* Call back, allocate a node. */ 5348fb7bfaSmrg hashnode (*alloc_node) (cpp_hash_table *); 544fee23f9Smrg /* Call back, allocate something that hangs off a node like a cpp_macro. 554fee23f9Smrg NULL means use the usual allocator. */ 564fee23f9Smrg void * (*alloc_subobject) (size_t); 574fee23f9Smrg 584fee23f9Smrg unsigned int nslots; /* Total slots in the entries array. */ 594fee23f9Smrg unsigned int nelements; /* Number of live elements. */ 604fee23f9Smrg 614fee23f9Smrg /* Link to reader, if any. For the benefit of cpplib. */ 624fee23f9Smrg struct cpp_reader *pfile; 634fee23f9Smrg 644fee23f9Smrg /* Table usage statistics. */ 654fee23f9Smrg unsigned int searches; 664fee23f9Smrg unsigned int collisions; 674fee23f9Smrg 684fee23f9Smrg /* Should 'entries' be freed when it is no longer needed? */ 694fee23f9Smrg bool entries_owned; 704fee23f9Smrg }; 714fee23f9Smrg 724fee23f9Smrg /* Initialize the hashtable with 2 ^ order entries. */ 7348fb7bfaSmrg extern cpp_hash_table *ht_create (unsigned int order); 744fee23f9Smrg 754fee23f9Smrg /* Frees all memory associated with a hash table. */ 7648fb7bfaSmrg extern void ht_destroy (cpp_hash_table *); 774fee23f9Smrg 7848fb7bfaSmrg extern hashnode ht_lookup (cpp_hash_table *, const unsigned char *, 794fee23f9Smrg size_t, enum ht_lookup_option); 8048fb7bfaSmrg extern hashnode ht_lookup_with_hash (cpp_hash_table *, const unsigned char *, 814fee23f9Smrg size_t, unsigned int, 824fee23f9Smrg enum ht_lookup_option); 834fee23f9Smrg #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); 844fee23f9Smrg #define HT_HASHFINISH(r, len) ((r) + (len)) 854fee23f9Smrg 864fee23f9Smrg /* For all nodes in TABLE, make a callback. The callback takes 874fee23f9Smrg TABLE->PFILE, the node, and a PTR, and the callback sequence stops 884fee23f9Smrg if the callback returns zero. */ 894fee23f9Smrg typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); 9048fb7bfaSmrg extern void ht_forall (cpp_hash_table *, ht_cb, const void *); 914fee23f9Smrg 924fee23f9Smrg /* For all nodes in TABLE, call the callback. If the callback returns 934fee23f9Smrg a nonzero value, the node is removed from the table. */ 9448fb7bfaSmrg extern void ht_purge (cpp_hash_table *, ht_cb, const void *); 954fee23f9Smrg 964fee23f9Smrg /* Restore the hash table. */ 9748fb7bfaSmrg extern void ht_load (cpp_hash_table *ht, hashnode *entries, 984fee23f9Smrg unsigned int nslots, unsigned int nelements, bool own); 994fee23f9Smrg 1004fee23f9Smrg /* Dump allocation statistics to stderr. */ 10148fb7bfaSmrg extern void ht_dump_statistics (cpp_hash_table *); 1024fee23f9Smrg 1034fee23f9Smrg #endif /* LIBCPP_SYMTAB_H */ 104