]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
d652f226 | 2 | Copyright (C) 2000, 2001, 2003, 2004, 2007, 2008, 2009, 2010 |
748086b7 | 3 | Free Software Foundation, Inc. |
2a967f3d NB |
4 | |
5 | This program is free software; you can redistribute it and/or modify it | |
6 | under the terms of the GNU General Public License as published by the | |
748086b7 | 7 | Free Software Foundation; either version 3, or (at your option) any |
2a967f3d NB |
8 | later version. |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License | |
748086b7 JJ |
16 | along with this program; see the file COPYING3. If not see |
17 | <http://www.gnu.org/licenses/>. */ | |
2a967f3d | 18 | |
4f4e53dd PB |
19 | #ifndef LIBCPP_SYMTAB_H |
20 | #define LIBCPP_SYMTAB_H | |
2a967f3d NB |
21 | |
22 | #include "obstack.h" | |
4851089f | 23 | |
5ffeb913 | 24 | #ifndef GTY |
43839642 | 25 | #define GTY(x) /* nothing */ |
5ffeb913 | 26 | #endif |
2a967f3d NB |
27 | |
28 | /* This is what each hash table entry points to. It may be embedded | |
29 | deeply within another object. */ | |
30 | typedef struct ht_identifier ht_identifier; | |
a9429e29 | 31 | typedef struct ht_identifier *ht_identifier_ptr; |
d1b38208 | 32 | struct GTY(()) ht_identifier { |
2a967f3d | 33 | const unsigned char *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 | ||
2a967f3d NB |
41 | typedef struct ht hash_table; |
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. */ |
1d088dee | 54 | hashnode (*alloc_node) (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. */ |
1d088dee | 74 | extern hash_table *ht_create (unsigned int order); |
bef985f3 NB |
75 | |
76 | /* Frees all memory associated with a hash table. */ | |
1d088dee | 77 | extern void ht_destroy (hash_table *); |
bef985f3 | 78 | |
1d088dee | 79 | extern hashnode ht_lookup (hash_table *, const unsigned char *, |
7bb3fbbb | 80 | size_t, enum ht_lookup_option); |
c6e83800 ZW |
81 | extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *, |
82 | size_t, unsigned int, | |
83 | enum ht_lookup_option); | |
84 | #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); | |
85 | #define HT_HASHFINISH(r, len) ((r) + (len)) | |
2a967f3d NB |
86 | |
87 | /* For all nodes in TABLE, make a callback. The callback takes | |
88 | TABLE->PFILE, the node, and a PTR, and the callback sequence stops | |
89 | if the callback returns zero. */ | |
1d088dee AJ |
90 | typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); |
91 | extern void ht_forall (hash_table *, ht_cb, const void *); | |
2a967f3d | 92 | |
dae4174e TT |
93 | /* For all nodes in TABLE, call the callback. If the callback returns |
94 | a nonzero value, the node is removed from the table. */ | |
95 | extern void ht_purge (hash_table *, ht_cb, const void *); | |
96 | ||
b453c95f GK |
97 | /* Restore the hash table. */ |
98 | extern void ht_load (hash_table *ht, hashnode *entries, | |
99 | unsigned int nslots, unsigned int nelements, bool own); | |
100 | ||
2a967f3d | 101 | /* Dump allocation statistics to stderr. */ |
1d088dee | 102 | extern void ht_dump_statistics (hash_table *); |
2a967f3d | 103 | |
4f4e53dd | 104 | #endif /* LIBCPP_SYMTAB_H */ |