chiark / gitweb /
Infrastructure: Split the files into subdirectories.
[mLib] / struct / sym.h
CommitLineData
0875b58f 1/* -*-c-*-
2 *
0875b58f 3 * Symbol table management
4 *
5 * (c) 1998 Straylight/Edgeware
6 */
7
d4efbcd9 8/*----- Licensing notice --------------------------------------------------*
0875b58f 9 *
10 * This file is part of the mLib utilities library.
11 *
12 * mLib is free software; you can redistribute it and/or modify
c846879c 13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
d4efbcd9 16 *
0875b58f 17 * mLib is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
c846879c 20 * GNU Library General Public License for more details.
d4efbcd9 21 *
c846879c 22 * You should have received a copy of the GNU Library General Public
0bd98442 23 * License along with mLib; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
0875b58f 26 */
27
c6e0eaf0 28#ifndef MLIB_SYM_H
29#define MLIB_SYM_H
0875b58f 30
31#ifdef __cplusplus
32 extern "C" {
33#endif
34
35/*----- Required headers --------------------------------------------------*/
36
37#include <stddef.h>
38
c6e0eaf0 39#ifndef MLIB_BITS_H
d4d7a053 40# include "bits.h"
41#endif
42
c6e0eaf0 43#ifndef MLIB_HASH_H
03d53b73 44# include "hash.h"
45#endif
46
20eb516f 47#ifndef MLIB_SUB_H
48# include "sub.h"
49#endif
50
2ae5376b 51/*----- Tuning parameters -------------------------------------------------*/
52
53/* --- Initial hash table size --- *
54 *
55 * This is the initial @mask@ value. It must be of the form %$2^n - 1$%,
56 * so that it can be used to mask of the bottom bits of a hash value.
57 */
58
59#define SYM_INITSZ 32 /* Size of a new hash table */
60
61/* --- Maximum load factor --- *
62 *
63 * This parameter controls how much the table has to be loaded before the
64 * table is extended. The number of elements %$n$%, the number of bins %$b$%
65 * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is
66 * added to the table and this relation is found to be false, the table is
67 * doubled in size.
68 */
69
70#define SYM_LIMIT(n) ((n) * 2) /* Load factor for growing table */
71
0875b58f 72/*----- Type definitions --------------------------------------------------*/
73
74/* --- Symbol table --- *
75 *
76 * A @sym_table@ contains the information needed to manage a symbol table.
77 * Users shouldn't fiddle with this information directly, but it needs to be
78 * here so that objects of the correct type can be created.
79 */
80
81typedef struct sym_table {
03d53b73 82 hash_table t;
20eb516f 83 subarena *s;
03d53b73 84 size_t load;
0875b58f 85} sym_table;
86
87/* --- A symbol table entry --- *
88 *
89 * I don't care what actually gets stored in symbol entries because I don't
90 * create them: that's the responsibility of my client. All I care about
91 * here is that whatever gets passed to me is a structure whose first member
92 * is a @sym_base@. The ANSI guarantees about structure layout are
93 * sufficient to allow me to manipulate such objects.
94 */
95
0875b58f 96typedef struct sym_base {
2ae5376b 97 hash_base b; /* Base structure */
98 char *name; /* Pointer to name string */
0875b58f 99 size_t len; /* Length of the symbol's name */
100} sym_base;
101
2ae5376b 102/* --- Macros for picking out useful information --- *
103 *
104 * Note that @SYM_LEN@ returns the size of the symbol key. For textual keys,
105 * this will include the terminating null.
106 */
a5d14ede 107
2ae5376b 108#define SYM_NAME(sy) ((const char *)(((sym_base *)(sy))->name))
109#define SYM_LEN(sy) (((sym_base *)(sy))->len + 0)
110#define SYM_HASH(sy) (((sym_base *)(sy))->b.hash + 0)
a5d14ede 111
0875b58f 112/* --- An iterator block --- */
113
dc2feaa9 114typedef struct { hash_iter i; } sym_iter;
0875b58f 115
116/*----- External functions ------------------------------------------------*/
117
34b97201 118/* --- @sym_create@ --- *
0875b58f 119 *
8c6d948b 120 * Arguments: @sym_table *t@ = symbol table to initialize
0875b58f 121 *
122 * Returns: ---
123 *
8c6d948b 124 * Use: Initializes the given symbol table. Raises @EXC_NOMEM@ if
0875b58f 125 * there isn't enough memory.
126 */
127
34b97201 128extern void sym_create(sym_table */*t*/);
0875b58f 129
34b97201 130/* --- @sym_destroy@ --- *
0875b58f 131 *
132 * Arguments: @sym_table *t@ = pointer to symbol table in question
133 *
134 * Returns: ---
135 *
136 * Use: Destroys a symbol table, freeing all the memory it used to
137 * occupy.
138 */
139
34b97201 140extern void sym_destroy(sym_table */*t*/);
0875b58f 141
142/* --- @sym_find@ --- *
143 *
144 * Arguments: @sym_table *t@ = pointer to symbol table in question
6f444bda 145 * @const char *n@ = pointer to symbol name to look up
0875b58f 146 * @long l@ = length of the name string or negative to measure
147 * @size_t sz@ = size of desired symbol object, or zero
148 * @unsigned *f@ = pointer to a flag, or null.
149 *
150 * Returns: The address of a @sym_base@ structure, or null if not found
151 * and @sz@ is zero.
152 *
153 * Use: Looks up a symbol in a given symbol table. The name is
154 * passed by the address of its first character. The length
155 * may be given, in which case the name may contain arbitrary
156 * binary data, or it may be given as a negative number, in
157 * which case the length of the name is calculated as
03d53b73 158 * @strlen(n) + 1@.
0875b58f 159 *
160 * The return value is the address of a pointer to a @sym_base@
161 * block (which may have other things on the end, as above). If
162 * the symbol could be found, the return value points to the
163 * symbol block. If the symbol wasn't there, then if @sz@ is
164 * nonzero, a new symbol is created and its address is returned;
165 * otherwise a null pointer is returned. The exception
166 * @EXC_NOMEM@ is raised if the block can't be allocated.
167 *
168 * The value of @*f@ indicates whether a new symbol entry was
169 * created: a nonzero value indicates that an old value was
170 * found.
171 */
172
173extern void *sym_find(sym_table */*t*/, const char */*n*/, long /*l*/,
174 size_t /*sz*/, unsigned */*f*/);
175
176/* --- @sym_remove@ --- *
177 *
c6e0eaf0 178 * Arguments: @sym_table *t@ = pointer to a symbol table object
0875b58f 179 * @void *b@ = pointer to symbol table entry
180 *
181 * Returns: ---
182 *
183 * Use: Removes the object from the symbol table. The space occupied
184 * by the object and its name is freed; anything else attached
185 * to the entry should already be gone by this point.
186 */
187
188extern void sym_remove(sym_table */*t*/, void */*b*/);
189
34b97201 190/* --- @sym_mkiter@ --- *
0875b58f 191 *
192 * Arguments: @sym_iter *i@ = pointer to an iterator object
193 * @sym_table *t@ = pointer to a symbol table object
194 *
195 * Returns: ---
196 *
197 * Use: Creates a new symbol table iterator which may be used to
198 * iterate through a symbol table.
199 */
200
dc2feaa9 201#define SYM_MKITER(i_, t_) HASH_MKITER(&(i_)->i, &(t_)->t)
03d53b73 202
34b97201 203extern void sym_mkiter(sym_iter */*i*/, sym_table */*t*/);
0875b58f 204
205/* --- @sym_next@ --- *
206 *
207 * Arguments: @sym_iter *i@ = pointer to iterator object
208 *
209 * Returns: Pointer to the next symbol found, or null when finished.
210 *
211 * Use: Returns the next symbol from the table. Symbols are not
212 * returned in any particular order.
213 */
214
dc2feaa9 215#define SYM_NEXT(i_, p) do { \
03d53b73 216 hash_base *_q; \
dc2feaa9 217 HASH_NEXT(&(i_)->i, _q); \
03d53b73 218 (p) = (void *)_q; \
219} while (0)
220
0875b58f 221extern void *sym_next(sym_iter */*i*/);
222
223/*----- That's all, folks -------------------------------------------------*/
224
225#ifdef __cplusplus
226 }
227#endif
228
229#endif