]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
99dee823 | 2 | Copyright (C) 2000-2021 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 { |
2a967f3d | 32 | const unsigned char *str; |
4977bab6 | 33 | unsigned int len; |
5e0c54e5 | 34 | unsigned int hash_value; |
2a967f3d NB |
35 | }; |
36 | ||
37 | #define HT_LEN(NODE) ((NODE)->len) | |
38 | #define HT_STR(NODE) ((NODE)->str) | |
39 | ||
0823efed | 40 | typedef struct ht cpp_hash_table; |
2a967f3d NB |
41 | typedef struct ht_identifier *hashnode; |
42 | ||
dae4174e | 43 | enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC}; |
2a967f3d NB |
44 | |
45 | /* An identifier hash table for cpplib and the front ends. */ | |
46 | struct ht | |
47 | { | |
48 | /* Identifiers are allocated from here. */ | |
49 | struct obstack stack; | |
50 | ||
51 | hashnode *entries; | |
d8044160 | 52 | /* Call back, allocate a node. */ |
0823efed | 53 | hashnode (*alloc_node) (cpp_hash_table *); |
d8044160 GK |
54 | /* Call back, allocate something that hangs off a node like a cpp_macro. |
55 | NULL means use the usual allocator. */ | |
56 | void * (*alloc_subobject) (size_t); | |
2a967f3d NB |
57 | |
58 | unsigned int nslots; /* Total slots in the entries array. */ | |
59 | unsigned int nelements; /* Number of live elements. */ | |
60 | ||
61 | /* Link to reader, if any. For the benefit of cpplib. */ | |
62 | struct cpp_reader *pfile; | |
63 | ||
64 | /* Table usage statistics. */ | |
65 | unsigned int searches; | |
66 | unsigned int collisions; | |
b453c95f GK |
67 | |
68 | /* Should 'entries' be freed when it is no longer needed? */ | |
69 | bool entries_owned; | |
2a967f3d NB |
70 | }; |
71 | ||
4912a07c | 72 | /* Initialize the hashtable with 2 ^ order entries. */ |
0823efed | 73 | extern cpp_hash_table *ht_create (unsigned int order); |
bef985f3 NB |
74 | |
75 | /* Frees all memory associated with a hash table. */ | |
0823efed | 76 | extern void ht_destroy (cpp_hash_table *); |
bef985f3 | 77 | |
0823efed | 78 | extern hashnode ht_lookup (cpp_hash_table *, const unsigned char *, |
7bb3fbbb | 79 | size_t, enum ht_lookup_option); |
0823efed | 80 | extern hashnode ht_lookup_with_hash (cpp_hash_table *, const unsigned char *, |
c6e83800 ZW |
81 | size_t, unsigned int, |
82 | enum ht_lookup_option); | |
83 | #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); | |
84 | #define HT_HASHFINISH(r, len) ((r) + (len)) | |
2a967f3d NB |
85 | |
86 | /* For all nodes in TABLE, make a callback. The callback takes | |
87 | TABLE->PFILE, the node, and a PTR, and the callback sequence stops | |
88 | if the callback returns zero. */ | |
1d088dee | 89 | typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); |
0823efed | 90 | extern void ht_forall (cpp_hash_table *, ht_cb, const void *); |
2a967f3d | 91 | |
dae4174e TT |
92 | /* For all nodes in TABLE, call the callback. If the callback returns |
93 | a nonzero value, the node is removed from the table. */ | |
0823efed | 94 | extern void ht_purge (cpp_hash_table *, ht_cb, const void *); |
dae4174e | 95 | |
b453c95f | 96 | /* Restore the hash table. */ |
0823efed | 97 | extern void ht_load (cpp_hash_table *ht, hashnode *entries, |
b453c95f GK |
98 | unsigned int nslots, unsigned int nelements, bool own); |
99 | ||
2a967f3d | 100 | /* Dump allocation statistics to stderr. */ |
0823efed | 101 | extern void ht_dump_statistics (cpp_hash_table *); |
2a967f3d | 102 | |
4f4e53dd | 103 | #endif /* LIBCPP_SYMTAB_H */ |