]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
a945c346 | 2 | Copyright (C) 2000-2024 Free Software Foundation, Inc. |
2a967f3d NB |
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 | |
748086b7 | 6 | Free Software Foundation; either version 3, or (at your option) any |
2a967f3d NB |
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 | |
748086b7 JJ |
15 | along with this program; see the file COPYING3. If not see |
16 | <http://www.gnu.org/licenses/>. */ | |
2a967f3d | 17 | |
4f4e53dd PB |
18 | #ifndef LIBCPP_SYMTAB_H |
19 | #define LIBCPP_SYMTAB_H | |
2a967f3d NB |
20 | |
21 | #include "obstack.h" | |
4851089f | 22 | |
5ffeb913 | 23 | #ifndef GTY |
43839642 | 24 | #define GTY(x) /* nothing */ |
5ffeb913 | 25 | #endif |
2a967f3d NB |
26 | |
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; | |
a9429e29 | 30 | typedef struct ht_identifier *ht_identifier_ptr; |
d1b38208 | 31 | struct GTY(()) ht_identifier { |
62db795a | 32 | /* We know the 'len'gth of the 'str'ing; use it in the GTY markup. */ |
f3b957ea | 33 | const unsigned char * GTY((string_length ("1 + %h.len"))) str; |
4977bab6 | 34 | unsigned int len; |
5e0c54e5 | 35 | unsigned int hash_value; |
2a967f3d NB |
36 | }; |
37 | ||
38 | #define HT_LEN(NODE) ((NODE)->len) | |
39 | #define HT_STR(NODE) ((NODE)->str) | |
40 | ||
0823efed | 41 | typedef struct ht cpp_hash_table; |
2a967f3d NB |
42 | typedef struct ht_identifier *hashnode; |
43 | ||
dae4174e | 44 | enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC}; |
2a967f3d NB |
45 | |
46 | /* An identifier hash table for cpplib and the front ends. */ | |
47 | struct ht | |
48 | { | |
49 | /* Identifiers are allocated from here. */ | |
50 | struct obstack stack; | |
51 | ||
52 | hashnode *entries; | |
d8044160 | 53 | /* Call back, allocate a node. */ |
0823efed | 54 | hashnode (*alloc_node) (cpp_hash_table *); |
d8044160 GK |
55 | /* Call back, allocate something that hangs off a node like a cpp_macro. |
56 | NULL means use the usual allocator. */ | |
57 | void * (*alloc_subobject) (size_t); | |
2a967f3d NB |
58 | |
59 | unsigned int nslots; /* Total slots in the entries array. */ | |
60 | unsigned int nelements; /* Number of live elements. */ | |
61 | ||
62 | /* Link to reader, if any. For the benefit of cpplib. */ | |
63 | struct cpp_reader *pfile; | |
64 | ||
65 | /* Table usage statistics. */ | |
66 | unsigned int searches; | |
67 | unsigned int collisions; | |
b453c95f GK |
68 | |
69 | /* Should 'entries' be freed when it is no longer needed? */ | |
70 | bool entries_owned; | |
2a967f3d NB |
71 | }; |
72 | ||
4912a07c | 73 | /* Initialize the hashtable with 2 ^ order entries. */ |
0823efed | 74 | extern cpp_hash_table *ht_create (unsigned int order); |
bef985f3 NB |
75 | |
76 | /* Frees all memory associated with a hash table. */ | |
0823efed | 77 | extern void ht_destroy (cpp_hash_table *); |
bef985f3 | 78 | |
0823efed | 79 | extern hashnode ht_lookup (cpp_hash_table *, const unsigned char *, |
7bb3fbbb | 80 | size_t, enum ht_lookup_option); |
0823efed | 81 | extern hashnode ht_lookup_with_hash (cpp_hash_table *, const unsigned char *, |
c6e83800 ZW |
82 | size_t, unsigned int, |
83 | enum ht_lookup_option); | |
cb05acdc LH |
84 | inline hashnode ht_lookup (cpp_hash_table *ht, const ht_identifier &id, |
85 | ht_lookup_option opt) | |
86 | { | |
87 | return ht_lookup_with_hash (ht, id.str, id.len, id.hash_value, opt); | |
88 | } | |
89 | ||
c6e83800 ZW |
90 | #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); |
91 | #define HT_HASHFINISH(r, len) ((r) + (len)) | |
2a967f3d NB |
92 | |
93 | /* For all nodes in TABLE, make a callback. The callback takes | |
94 | TABLE->PFILE, the node, and a PTR, and the callback sequence stops | |
95 | if the callback returns zero. */ | |
1d088dee | 96 | typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); |
0823efed | 97 | extern void ht_forall (cpp_hash_table *, ht_cb, const void *); |
2a967f3d | 98 | |
dae4174e TT |
99 | /* For all nodes in TABLE, call the callback. If the callback returns |
100 | a nonzero value, the node is removed from the table. */ | |
0823efed | 101 | extern void ht_purge (cpp_hash_table *, ht_cb, const void *); |
dae4174e | 102 | |
b453c95f | 103 | /* Restore the hash table. */ |
0823efed | 104 | extern void ht_load (cpp_hash_table *ht, hashnode *entries, |
b453c95f GK |
105 | unsigned int nslots, unsigned int nelements, bool own); |
106 | ||
2a967f3d | 107 | /* Dump allocation statistics to stderr. */ |
0823efed | 108 | extern void ht_dump_statistics (cpp_hash_table *); |
2a967f3d | 109 | |
4f4e53dd | 110 | #endif /* LIBCPP_SYMTAB_H */ |