14 .TH sym 3 "8 May 1999" "Straylight/Edgeware" "mLib utilities library"
16 sym \- symbol table manager
30 .B "#include <mLib/sym.h>"
32 .B "type struct { ...\& } sym_table;"
33 .B "type struct { ...\& } sym_base;"
34 .B "type struct { ...\& } sym_iter;"
36 .BI "void sym_create(sym_table *" t );
37 .BI "void sym_destroy(sym_table *" t );
39 .ds mT \fBvoid *sym_find(
40 .BI "\*(mTsym_table *" t ,
41 .BI "\h'\w'\*(mT'u'const char *" n ", long " l ,
42 .BI "\h'\w'\*(mT'u'size_t " sz ", unsigned *" f );
43 .BI "void sym_remove(sym_table *" t ", void *" b );
45 .BI "const char *SYM_NAME(const void *" p );
46 .BI "size_t SYM_LEN(const void *" p );
47 .BI "uint32 SYM_HASH(const void *" p );
49 .BI "void sym_mkiter(sym_iter *" i ", sym_table *" t );
50 .BI "void *sym_next(sym_iter *" i );
55 functions implement a data structure often described as a dictionary, a
56 finite map, an associative array, or a symbol table. It associates
60 such that the value corresponding to a given key can be found quickly.
61 Additionally, all stored associations can be enumerated.
63 The interface provides an
65 symbol table. The data objects stored in the table must include a small
66 header used by the symbol table manager. This reduces the amount of
67 pointer fiddling that needs to be done, and in practice doesn't seem to
68 be much of a problem. It's also fairly easy to construct a
69 non-intrusive interface if you really want one.
71 There are three main data structures involved in the interface:
74 Keeps track of the information associated with a particular table.
77 The header which must be attached to the front of all the value
81 An iterator object, used for enumerating all of the associations stored
84 All of the above data structures should be considered
86 don't try looking inside. Representations have changed in the past, and
87 they may change again in the future.
88 .SS "Creation and destruction"
91 object itself needs to be allocated by the caller. It is initialized by
92 passing it to the function
94 After initialization, the table contains no entries.
96 Initializing a symbol table involves allocating some memory. If this
101 When a symbol table is no longer needed, the memory occupied by the
102 values and other maintenance structures can be reclaimed by calling
104 Any bits of user data attached to values should previously have been
106 .SS "Adding, searching and removing"
107 Most of the actual work is done by the function
109 It does both lookup and creation, depending on its arguments. To do its
110 job, it needs to know the following bits of information:
113 A pointer to a symbol table to manipulate.
118 to look up or create. Usually this will be a simple text string,
119 although it can actually be any arbitrary binary data.
122 The length of the key. If this is \-1,
124 assumes that the key is a null-terminated string, and calculates its
125 length itself. This is entirely equivalent to passing
129 The size of the value block to allocate if the key could not be found.
130 If this is zero, no value is allocated, and a null pointer is returned
131 to indicate an unsuccessful lookup.
134 The address of a `found' flag to set. This is an output parameter. On
137 will set the value of
139 to zero if the key could not be found, or nonzero if it was found. This
140 can be used to tell whether the value returned has been newly allocated,
141 or whether it was already in the table.
143 A terminating null byte is appended to the copy of the symbol's name in
144 memory. This is not considered to be a part of the symbol's name, and
145 does not contribute to the name's length as reported by the
149 A symbol can be removed from the table by calling
151 passing the symbol table itself, and the value block that needs
153 .SS "Enquiries about symbols"
154 Three macros are provided to enable simple enquiries about a symbol.
157 to a symbol table entry,
159 returns the length of the symbol's name (excluding any terminating null
162 returns a pointer to the symbol's name; and
164 returns the symbol's hash value.
165 .SS "Enumerating symbols"
166 Enumerating the values in a symbol table is fairly simple. Allocate a
168 object from somewhere. Attach it to a symbol table by calling
170 and passing in the addresses of the iterator and the symbol table.
173 will return a different value from the symbol table, until all of them
174 have been enumerated, at which point,
176 returns a null pointer.
178 It's safe to remove the symbol you've just been returned by
180 However, it's not safe to remove any other symbol. So don't do that.
182 When you've finished with an iterator, it's safe to just throw it away.
183 You don't need to call any functions beforehand.
184 .SS "Use in practice"
185 In normal use, the keys are simple strings (usually identifiers from
186 some language), and the values are nontrivial structures providing
187 information about types and values.
189 In this case, you'd define something like the following structure for
193 sym_base _base; /* Symbol header */
194 unsigned type; /* Type of this symbol */
195 int dispoff; /* Which display variable is in */
196 size_t frameoff; /* Offset of variable in frame */
203 you can find the variable's name by calling
204 .BI SYM_NAME( v )\fR.
206 You can look up a name in the table by saying something like:
208 val *v = sym_find(t, name, -1, 0, 0);
210 error("unknown variable `%s'", name);
212 You can add in a new variable by saying something like
215 val *v = sym_find(t, name, -1, sizeof(val), &f);
217 error("variable `%s' already exists", name);
220 You can examine all the variables in your symbol table by saying
226 for (sym_mkiter(&i, t); (v = sym_next(&i)) != 0; ) {
230 That ought to be enough examples to be getting on with.
232 The symbol table is an extensible hashtable, using the universal hash
233 function described in
235 and the global hashing key. The hash chains are kept very short
236 (probably too short, actually). Every time a symbol is found, its block
237 is promoted to the front of its bin chain so it gets found faster next
243 Mark Wooding, <mdw@distorted.org.uk>
~mdw / mLib / blob