]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
b453c95f | 2 | Copyright (C) 2000, 2001, 2003, 2004 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 | |
6 | Free Software Foundation; either version 2, or (at your option) any | |
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 | |
15 | along with this program; if not, write to the Free Software | |
16 | Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ | |
17 | ||
4f4e53dd PB |
18 | #ifndef LIBCPP_SYMTAB_H |
19 | #define LIBCPP_SYMTAB_H | |
2a967f3d NB |
20 | |
21 | #include "obstack.h" | |
43839642 | 22 | #define GTY(x) /* nothing */ |
2a967f3d NB |
23 | |
24 | /* This is what each hash table entry points to. It may be embedded | |
25 | deeply within another object. */ | |
26 | typedef struct ht_identifier ht_identifier; | |
e2500fed | 27 | struct ht_identifier GTY(()) |
2a967f3d | 28 | { |
2a967f3d | 29 | const unsigned char *str; |
4977bab6 | 30 | unsigned int len; |
5e0c54e5 | 31 | unsigned int hash_value; |
2a967f3d NB |
32 | }; |
33 | ||
34 | #define HT_LEN(NODE) ((NODE)->len) | |
35 | #define HT_STR(NODE) ((NODE)->str) | |
36 | ||
2a967f3d NB |
37 | typedef struct ht hash_table; |
38 | typedef struct ht_identifier *hashnode; | |
39 | ||
40 | enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC, HT_ALLOCED}; | |
41 | ||
42 | /* An identifier hash table for cpplib and the front ends. */ | |
43 | struct ht | |
44 | { | |
45 | /* Identifiers are allocated from here. */ | |
46 | struct obstack stack; | |
47 | ||
48 | hashnode *entries; | |
d8044160 | 49 | /* Call back, allocate a node. */ |
1d088dee | 50 | hashnode (*alloc_node) (hash_table *); |
d8044160 GK |
51 | /* Call back, allocate something that hangs off a node like a cpp_macro. |
52 | NULL means use the usual allocator. */ | |
53 | void * (*alloc_subobject) (size_t); | |
2a967f3d NB |
54 | |
55 | unsigned int nslots; /* Total slots in the entries array. */ | |
56 | unsigned int nelements; /* Number of live elements. */ | |
57 | ||
58 | /* Link to reader, if any. For the benefit of cpplib. */ | |
59 | struct cpp_reader *pfile; | |
60 | ||
61 | /* Table usage statistics. */ | |
62 | unsigned int searches; | |
63 | unsigned int collisions; | |
b453c95f GK |
64 | |
65 | /* Should 'entries' be freed when it is no longer needed? */ | |
66 | bool entries_owned; | |
2a967f3d NB |
67 | }; |
68 | ||
4912a07c | 69 | /* Initialize the hashtable with 2 ^ order entries. */ |
1d088dee | 70 | extern hash_table *ht_create (unsigned int order); |
bef985f3 NB |
71 | |
72 | /* Frees all memory associated with a hash table. */ | |
1d088dee | 73 | extern void ht_destroy (hash_table *); |
bef985f3 | 74 | |
1d088dee | 75 | extern hashnode ht_lookup (hash_table *, const unsigned char *, |
7bb3fbbb | 76 | size_t, enum ht_lookup_option); |
c6e83800 ZW |
77 | extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *, |
78 | size_t, unsigned int, | |
79 | enum ht_lookup_option); | |
80 | #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); | |
81 | #define HT_HASHFINISH(r, len) ((r) + (len)) | |
2a967f3d NB |
82 | |
83 | /* For all nodes in TABLE, make a callback. The callback takes | |
84 | TABLE->PFILE, the node, and a PTR, and the callback sequence stops | |
85 | if the callback returns zero. */ | |
1d088dee AJ |
86 | typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *); |
87 | extern void ht_forall (hash_table *, ht_cb, const void *); | |
2a967f3d | 88 | |
b453c95f GK |
89 | /* Restore the hash table. */ |
90 | extern void ht_load (hash_table *ht, hashnode *entries, | |
91 | unsigned int nslots, unsigned int nelements, bool own); | |
92 | ||
2a967f3d | 93 | /* Dump allocation statistics to stderr. */ |
1d088dee | 94 | extern void ht_dump_statistics (hash_table *); |
2a967f3d | 95 | |
4f4e53dd | 96 | #endif /* LIBCPP_SYMTAB_H */ |