xref: /netbsd-src/external/gpl3/gcc/dist/libcpp/include/symtab.h (revision b1e838363e3c6fc78a55519254d99869742dd33c)
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