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