2 Copyright (C) 2000-2023 Free Software Foundation, Inc.
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 3, or (at your option) any
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.
14 You should have received a copy of the GNU General Public License
15 along with this program; see the file COPYING3. If not see
16 <http://www.gnu.org/licenses/>. */
18 #ifndef LIBCPP_SYMTAB_H
19 #define LIBCPP_SYMTAB_H
24 #define GTY(x) /* nothing */
27 /* This is what each hash table entry points to. It may be embedded
28 deeply within another object. */
29 typedef struct ht_identifier ht_identifier
;
30 typedef struct ht_identifier
*ht_identifier_ptr
;
31 struct GTY(()) ht_identifier
{
32 /* This GTY markup arranges that the null-terminated identifier would still
33 stream to PCH correctly, if a null byte were to make its way into an
34 identifier somehow. */
35 const unsigned char * GTY((string_length ("1 + %h.len"))) str
;
37 unsigned int hash_value
;
40 #define HT_LEN(NODE) ((NODE)->len)
41 #define HT_STR(NODE) ((NODE)->str)
43 typedef struct ht cpp_hash_table
;
44 typedef struct ht_identifier
*hashnode
;
46 enum ht_lookup_option
{HT_NO_INSERT
= 0, HT_ALLOC
};
48 /* An identifier hash table for cpplib and the front ends. */
51 /* Identifiers are allocated from here. */
55 /* Call back, allocate a node. */
56 hashnode (*alloc_node
) (cpp_hash_table
*);
57 /* Call back, allocate something that hangs off a node like a cpp_macro.
58 NULL means use the usual allocator. */
59 void * (*alloc_subobject
) (size_t);
61 unsigned int nslots
; /* Total slots in the entries array. */
62 unsigned int nelements
; /* Number of live elements. */
64 /* Link to reader, if any. For the benefit of cpplib. */
65 struct cpp_reader
*pfile
;
67 /* Table usage statistics. */
68 unsigned int searches
;
69 unsigned int collisions
;
71 /* Should 'entries' be freed when it is no longer needed? */
75 /* Initialize the hashtable with 2 ^ order entries. */
76 extern cpp_hash_table
*ht_create (unsigned int order
);
78 /* Frees all memory associated with a hash table. */
79 extern void ht_destroy (cpp_hash_table
*);
81 extern hashnode
ht_lookup (cpp_hash_table
*, const unsigned char *,
82 size_t, enum ht_lookup_option
);
83 extern hashnode
ht_lookup_with_hash (cpp_hash_table
*, const unsigned char *,
85 enum ht_lookup_option
);
86 #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
87 #define HT_HASHFINISH(r, len) ((r) + (len))
89 /* For all nodes in TABLE, make a callback. The callback takes
90 TABLE->PFILE, the node, and a PTR, and the callback sequence stops
91 if the callback returns zero. */
92 typedef int (*ht_cb
) (struct cpp_reader
*, hashnode
, const void *);
93 extern void ht_forall (cpp_hash_table
*, ht_cb
, const void *);
95 /* For all nodes in TABLE, call the callback. If the callback returns
96 a nonzero value, the node is removed from the table. */
97 extern void ht_purge (cpp_hash_table
*, ht_cb
, const void *);
99 /* Restore the hash table. */
100 extern void ht_load (cpp_hash_table
*ht
, hashnode
*entries
,
101 unsigned int nslots
, unsigned int nelements
, bool own
);
103 /* Dump allocation statistics to stderr. */
104 extern void ht_dump_statistics (cpp_hash_table
*);
106 #endif /* LIBCPP_SYMTAB_H */