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 .BI "void *sym_find(sym_table *" t ,
36 .BI " const char *" n ", long " l ,
37 .BI " size_t " sz ", unsigned *" f );
38 .BI "void sym_remove(sym_table *" t ", void *" b );
40 .BI "const char *SYM_NAME(const void *" p );
41 .BI "size_t SYM_LEN(const void *" p );
42 .BI "uint32 SYM_HASH(const void *" p );
44 .BI "void sym_mkiter(sym_iter *" i ", sym_table *" t );
45 .BI "void *sym_next(sym_iter *" i );
50 functions implement a data structure often described as a dictionary, a
51 finite map, an associative array, or a symbol table. It associates
55 such that the value corresponding to a given key can be found quickly.
56 Additionally, all stored associations can be enumerated.
58 The interface provides an
60 symbol table. The data objects stored in the table must include a small
61 header used by the symbol table manager. This reduces the amount of
62 pointer fiddling that needs to be done, and in practice doesn't seem to
63 be much of a problem. It's also fairly easy to construct a
64 non-intrusive interface if you really want one.
66 There are three main data structures involved in the interface:
69 Keeps track of the information associated with a particular table.
72 The header which must be attached to the front of all the value
76 An iterator object, used for enumerating all of the associations stored
79 All of the above data structures should be considered
81 don't try looking inside. Representations have changed in the past, and
82 they may change again in the future.
83 .SS "Creation and destruction"
86 object itself needs to be allocated by the caller. It is initialized by
87 passing it to the function
89 After initialization, the table contains no entries.
91 Initializing a symbol table involves allocating some memory. If this
96 When a symbol table is no longer needed, the memory occupied by the
97 values and other maintenance structures can be reclaimed by calling
99 Any bits of user data attached to values should previously have been
101 .SS "Adding, searching and removing"
102 Most of the actual work is done by the function
104 It does both lookup and creation, depending on its arguments. To do its
105 job, it needs to know the following bits of information:
108 A pointer to a symbol table to manipulate.
113 to look up or create. Usually this will be a simple text string,
114 although it can actually be any arbitrary binary data.
117 The length of the key. If this is \-1,
119 assumes that the key is a null-terminated string, and calculates its
120 length itself. This is entirely equivalent to passing
124 The size of the value block to allocate if the key could not be found.
125 If this is zero, no value is allocated, and a null pointer is returned
126 to indicate an unsuccessful lookup.
129 The address of a `found' flag to set. This is an output parameter. On
132 will set the value of
134 to zero if the key could not be found, or nonzero if it was found. This
135 can be used to tell whether the value returned has been newly allocated,
136 or whether it was already in the table.
138 A terminating null byte is appended to the copy of the symbol's name in
139 memory. This is not considered to be a part of the symbol's name, and
140 does not contribute to the name's length as reported by the
144 A symbol can be removed from the table by calling
146 passing the symbol table itself, and the value block that needs
148 .SS "Enquiries about symbols"
149 Three macros are provided to enable simple enquiries about a symbol.
152 to a symbol table entry,
154 returns the length of the symbol's name (excluding any terminating null
157 returns a pointer to the symbol's name; and
159 returns the symbol's hash value.
160 .SS "Enumerating symbols"
161 Enumerating the values in a symbol table is fairly simple. Allocate a
163 object from somewhere. Attach it to a symbol table by calling
165 and passing in the addresses of the iterator and the symbol table.
168 will return a different value from the symbol table, until all of them
169 have been enumerated, at which point,
171 returns a null pointer.
173 It's safe to remove the symbol you've just been returned by
175 However, it's not safe to remove any other symbol. So don't do that.
177 When you've finished with an iterator, it's safe to just throw it away.
178 You don't need to call any functions beforehand.
179 .SS "Use in practice"
180 In normal use, the keys are simple strings (usually identifiers from
181 some language), and the values are nontrivial structures providing
182 information about types and values.
184 In this case, you'd define something like the following structure for
188 sym_base _base; /* Symbol header */
189 unsigned type; /* Type of this symbol */
190 int dispoff; /* Which display variable is in */
191 size_t frameoff; /* Offset of variable in frame */
198 you can find the variable's name by calling
199 .BI SYM_NAME( v )\fR.
201 You can look up a name in the table by saying something like:
203 val *v = sym_find(t, name, -1, 0, 0);
205 error("unknown variable `%s'", name);
207 You can add in a new variable by saying something like
210 val *v = sym_find(t, name, -1, sizeof(val), &f);
212 error("variable `%s' already exists", name);
215 You can examine all the variables in your symbol table by saying
221 for (sym_mkiter(&i, t); (v = sym_next(&i)) != 0; ) {
225 That ought to be enough examples to be getting on with.
227 The symbol table is an extensible hashtable, using the universal hash
228 function described in
230 and the global hashing key. The hash chains are kept very short
231 (probably too short, actually). Every time a symbol is found, its block
232 is promoted to the front of its bin chain so it gets found faster next
238 Mark Wooding, <mdw@distorted.org.uk>
~mdw / mLib / blob