.RE
.sp 1
..
-.TH sym 3 "8 May 1999" mLib
+.TH sym 3 "8 May 1999" "Straylight/Edgeware" "mLib utilities library"
.SH NAME
sym \- symbol table manager
.\" @sym_create
.\" @sym_next
.\"
.\" @SYM_NAME
+.\" @SYM_LEN
+.\" @SYM_HASH
.\"
.SH SYNOPSIS
.nf
.BI "void sym_create(sym_table *" t );
.BI "void sym_destroy(sym_table *" t );
-.BI "char *SYM_NAME(void *" p );
.BI "void *sym_find(sym_table *" t ,
.BI " const char *" n ", long " l ,
.BI " size_t " sz ", unsigned *" f );
.BI "void sym_remove(sym_table *" t ", void *" b );
+.BI "const char *SYM_NAME(const void *" p );
+.BI "size_t SYM_LEN(const void *" p );
+.BI "uint32 SYM_HASH(const void *" p );
+
.BI "void sym_mkiter(sym_iter *" i ", sym_table *" t );
.BI "void *sym_next(sym_iter *" i );
.fi
-.SH "HOW IT WORKS"
+.SH "DESCRIPTION"
The
.B sym
functions implement a data structure often described as a dictionary, a
.IR opaque :
don't try looking inside. Representations have changed in the past, and
they may change again in the future.
-.SH "CREATION AND DESTRUCTION"
+.SS "Creation and destruction"
The
.B sym_table
object itself needs to be allocated by the caller. It is initialized by
When a symbol table is no longer needed, the memory occupied by the
values and other maintenance structures can be reclaimed by calling
.BR sym_destroy .
-Any bits of user data attached to the symbol table values should have
-previously been destroyed.
-.SH "ADDING, SEARCHING AND REMOVING"
+Any bits of user data attached to values should previously have been
+destroyed.
+.SS "Adding, searching and removing"
Most of the actual work is done by the function
.BR sym_find .
It does both lookup and creation, depending on its arguments. To do its
job, it needs to know the following bits of information:
.TP
-.I t
+.BI "sym_table *" t
A pointer to a symbol table to manipulate.
.TP
-.I n
+.BI "const char *" n
The address of the
.I key
to look up or create. Usually this will be a simple text string,
although it can actually be any arbitrary binary data.
.TP
-.I l
+.BI "long " l
The length of the key. If this is \-1,
.B sym_find
assumes that the key is a null-terminated string, and calculates its
-length itself.
+length itself. This is entirely equivalent to passing
+.BI strlen( n )\fR.
.TP
-.I sz
+.BI "size_t " sz
The size of the value block to allocate if the key could not be found.
If this is zero, no value is allocated, and a null pointer is returned
to indicate an unsuccessful lookup.
.TP
-.I f
+.BI "unsigned *" f
The address of a `found' flag to set. This is an output parameter. On
exit,
.B sym_find
can be used to tell whether the value returned has been newly allocated,
or whether it was already in the table.
.PP
-The macro
-.B SYM_NAME
-will return the key associated with a given value block. You must use
-this macro rather than fiddling inside the
-.B sym_base
-structure.
+A terminating null byte is appended to the copy of the symbol's name in
+memory. This is not considered to be a part of the symbol's name, and
+does not contribute to the name's length as reported by the
+.B SYM_LEN
+macro.
.PP
A symbol can be removed from the table by calling
.BR sym_remove ,
passing the symbol table itself, and the value block that needs
removing.
-.SH ENUMERATION
+.SS "Enquiries about symbols"
+Three macros are provided to enable simple enquiries about a symbol.
+Given a pointer
+.I s
+to a symbol table entry,
+.BI SYM_LEN( s )
+returns the length of the symbol's name (excluding any terminating null
+byte);
+.BI SYM_NAME( s )
+returns a pointer to the symbol's name; and
+.BI SYM_HASH( s )
+returns the symbol's hash value.
+.SS "Enumerating symbols"
Enumerating the values in a symbol table is fairly simple. Allocate a
.B sym_iter
object from somewhere. Attach it to a symbol table by calling
.PP
When you've finished with an iterator, it's safe to just throw it away.
You don't need to call any functions beforehand.
-.SH "USE IN PRACTICE"
+.SS "Use in practice"
In normal use, the keys are simple strings (usually identifiers from
some language), and the values are nontrivial structures providing
information about types and values.
}
.VE
That ought to be enough examples to be getting on with.
-.SH CAVEATS
-The symbol table manager requires the suballocator (see
-.BR sub (3)
-for details). You must ensure that
-.B sub_init
-has been called before using any symbol tables in your program.
-.SH IMPLEMENTATION
+.SS Implementation
The symbol table is an extensible hashtable, using a 32-bit CRC as the
hash function. The hash chains are kept very short (probably too short,
actually). Every time a symbol is found, its block is promoted to the
front of its bin chain so it gets found faster next time.
.SH SEE ALSO
-.BR sub (3),
+.BR hash (3),
.BR mLib (3).
.SH AUTHOR
Mark Wooding, <mdw@nsict.org>