X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/8c6d948bbb87df8f1ffb49d3af1419b84ea34a0e..2ae5376b8a8158f38cbbe9c0238b5428ee3ce711:/sym.h diff --git a/sym.h b/sym.h index 3f7db08..db49ff5 100644 --- a/sym.h +++ b/sym.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sym.h,v 1.5 1999/05/13 22:48:37 mdw Exp $ + * $Id: sym.h,v 1.12 2001/01/20 11:49:37 mdw Exp $ * * Symbol table management * @@ -30,6 +30,31 @@ /*----- Revision history --------------------------------------------------* * * $Log: sym.h,v $ + * Revision 1.12 2001/01/20 11:49:37 mdw + * Export tuning parameters from header file, for the benefit of other + * hashtable implementations. Change the storage of symbol names: store + * the name after the allocated symbol block in all cases. This replaces + * the previous complicated and slightly wasteful arrangement. + * + * Revision 1.11 2000/06/17 10:37:39 mdw + * Add support for arena management. + * + * Revision 1.10 1999/12/10 23:42:04 mdw + * Change header file guard names. + * + * Revision 1.9 1999/08/02 16:53:48 mdw + * Improve type safety for sym_iter objects. + * + * Revision 1.8 1999/08/02 14:45:48 mdw + * Break low-level hashtable code out from sym. + * + * Revision 1.7 1999/06/01 09:49:33 mdw + * Allow things to be looked up by just their caller-supplied hashes. This + * actually needs to be thought through better. + * + * Revision 1.6 1999/05/26 21:08:31 mdw + * Rename symbols in line with newer conventions. + * * Revision 1.5 1999/05/13 22:48:37 mdw * Change `-ise' to `-ize' throughout. * @@ -47,8 +72,8 @@ * */ -#ifndef SYM_H -#define SYM_H +#ifndef MLIB_SYM_H +#define MLIB_SYM_H #ifdef __cplusplus extern "C" { @@ -58,6 +83,39 @@ #include +#ifndef MLIB_BITS_H +# include "bits.h" +#endif + +#ifndef MLIB_HASH_H +# include "hash.h" +#endif + +#ifndef MLIB_SUB_H +# include "sub.h" +#endif + +/*----- Tuning parameters -------------------------------------------------*/ + +/* --- Initial hash table size --- * + * + * This is the initial @mask@ value. It must be of the form %$2^n - 1$%, + * so that it can be used to mask of the bottom bits of a hash value. + */ + +#define SYM_INITSZ 32 /* Size of a new hash table */ + +/* --- Maximum load factor --- * + * + * This parameter controls how much the table has to be loaded before the + * table is extended. The number of elements %$n$%, the number of bins %$b$% + * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is + * added to the table and this relation is found to be false, the table is + * doubled in size. + */ + +#define SYM_LIMIT(n) ((n) * 2) /* Load factor for growing table */ + /*----- Type definitions --------------------------------------------------*/ /* --- Symbol table --- * @@ -68,9 +126,9 @@ */ typedef struct sym_table { - unsigned long mask; /* Bit mask for hashing purposes */ - size_t c; /* Down counter for growing table */ - struct sym_base **a; /* Array of hash bins */ + hash_table t; + subarena *s; + size_t load; } sym_table; /* --- A symbol table entry --- * @@ -82,36 +140,29 @@ typedef struct sym_table { * sufficient to allow me to manipulate such objects. */ -#define SYM_BUFSZ 16 /* Size of local string buffer */ - typedef struct sym_base { - struct sym_base *next; /* Next symbol in hash bin */ - unsigned long hash; /* Hash value for symbol's name */ - union { - char *p; /* Pointer to name string */ - char b[SYM_BUFSZ]; /* Buffer containing a short name */ - } name; /* Name of this symbol */ + hash_base b; /* Base structure */ + char *name; /* Pointer to name string */ size_t len; /* Length of the symbol's name */ } sym_base; -/* --- A macro to pick a symbol's name out from the mess --- */ +/* --- Macros for picking out useful information --- * + * + * Note that @SYM_LEN@ returns the size of the symbol key. For textual keys, + * this will include the terminating null. + */ -#define SYM_NAME(sy) \ - (((sym_base *)(sy))->len > SYM_BUFSZ ? \ - ((sym_base *)(sy))->name.p : \ - ((sym_base *)(sy))->name.b) +#define SYM_NAME(sy) ((const char *)(((sym_base *)(sy))->name)) +#define SYM_LEN(sy) (((sym_base *)(sy))->len + 0) +#define SYM_HASH(sy) (((sym_base *)(sy))->b.hash + 0) /* --- An iterator block --- */ -typedef struct sym_iter { - sym_table *t; /* Symbol table being iterated */ - sym_base *n; /* Address of next item to return */ - size_t i; /* Index of next hash bin to use */ -} sym_iter; +typedef struct { hash_iter i; } sym_iter; /*----- External functions ------------------------------------------------*/ -/* --- @sym_createTable@ --- * +/* --- @sym_create@ --- * * * Arguments: @sym_table *t@ = symbol table to initialize * @@ -121,9 +172,9 @@ typedef struct sym_iter { * there isn't enough memory. */ -extern void sym_createTable(sym_table */*t*/); +extern void sym_create(sym_table */*t*/); -/* --- @sym_destroyTable@ --- * +/* --- @sym_destroy@ --- * * * Arguments: @sym_table *t@ = pointer to symbol table in question * @@ -133,7 +184,7 @@ extern void sym_createTable(sym_table */*t*/); * occupy. */ -extern void sym_destroyTable(sym_table */*t*/); +extern void sym_destroy(sym_table */*t*/); /* --- @sym_find@ --- * * @@ -151,7 +202,7 @@ extern void sym_destroyTable(sym_table */*t*/); * may be given, in which case the name may contain arbitrary * binary data, or it may be given as a negative number, in * which case the length of the name is calculated as - * @strlen(n)@. + * @strlen(n) + 1@. * * The return value is the address of a pointer to a @sym_base@ * block (which may have other things on the end, as above). If @@ -171,7 +222,7 @@ extern void *sym_find(sym_table */*t*/, const char */*n*/, long /*l*/, /* --- @sym_remove@ --- * * - * Arguments: @sym_table *i@ = pointer to a symbol table object + * Arguments: @sym_table *t@ = pointer to a symbol table object * @void *b@ = pointer to symbol table entry * * Returns: --- @@ -183,7 +234,7 @@ extern void *sym_find(sym_table */*t*/, const char */*n*/, long /*l*/, extern void sym_remove(sym_table */*t*/, void */*b*/); -/* --- @sym_createIter@ --- * +/* --- @sym_mkiter@ --- * * * Arguments: @sym_iter *i@ = pointer to an iterator object * @sym_table *t@ = pointer to a symbol table object @@ -194,7 +245,9 @@ extern void sym_remove(sym_table */*t*/, void */*b*/); * iterate through a symbol table. */ -extern void sym_createIter(sym_iter */*i*/, sym_table */*t*/); +#define SYM_MKITER(i_, t_) HASH_MKITER(&(i_)->i, &(t_)->t) + +extern void sym_mkiter(sym_iter */*i*/, sym_table */*t*/); /* --- @sym_next@ --- * * @@ -206,6 +259,12 @@ extern void sym_createIter(sym_iter */*i*/, sym_table */*t*/); * returned in any particular order. */ +#define SYM_NEXT(i_, p) do { \ + hash_base *_q; \ + HASH_NEXT(&(i_)->i, _q); \ + (p) = (void *)_q; \ +} while (0) + extern void *sym_next(sym_iter */*i*/); /*----- That's all, folks -------------------------------------------------*/