X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/03d53b73fc6663cef4493cfda7193c958557c240..d4efbcd93c940ad522fcf8c601ec1829d2e0b10d:/sym.h diff --git a/sym.h b/sym.h index edd3284..7a40b74 100644 --- a/sym.h +++ b/sym.h @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: sym.h,v 1.8 1999/08/02 14:45:48 mdw Exp $ + * $Id: sym.h,v 1.14 2004/04/08 01:36:13 mdw Exp $ * * Symbol table management * * (c) 1998 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of the mLib utilities library. * @@ -15,50 +15,20 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * mLib is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with mLib; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: sym.h,v $ - * 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. - * - * Revision 1.4 1999/05/06 19:51:35 mdw - * Reformatted the LGPL notice a little bit. - * - * Revision 1.3 1999/05/05 18:50:31 mdw - * Change licensing conditions to LGPL. - * - * Revision 1.2 1998/11/26 19:27:34 mdw - * Move SYM_NAME into the header file. Fix bugs. - * - * Revision 1.1.1.1 1998/06/17 23:44:42 mdw - * Initial version of mLib - * - */ - -#ifndef SYM_H -#define SYM_H +#ifndef MLIB_SYM_H +#define MLIB_SYM_H #ifdef __cplusplus extern "C" { @@ -68,14 +38,39 @@ #include -#ifndef BITS_H +#ifndef MLIB_BITS_H # include "bits.h" #endif -#ifndef HASH_H +#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 --- * @@ -87,6 +82,7 @@ typedef struct sym_table { hash_table t; + subarena *s; size_t load; } sym_table; @@ -99,27 +95,25 @@ 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 { - hash_base b; - 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 hash_iter sym_iter; +typedef struct { hash_iter i; } sym_iter; /*----- External functions ------------------------------------------------*/ @@ -150,7 +144,7 @@ extern void sym_destroy(sym_table */*t*/); /* --- @sym_find@ --- * * * Arguments: @sym_table *t@ = pointer to symbol table in question - * @const char *n@ = pointer to symbol table to look up + * @const char *n@ = pointer to symbol name to look up * @long l@ = length of the name string or negative to measure * @size_t sz@ = size of desired symbol object, or zero * @unsigned *f@ = pointer to a flag, or null. @@ -183,7 +177,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: --- @@ -206,7 +200,7 @@ extern void sym_remove(sym_table */*t*/, void */*b*/); * iterate through a symbol table. */ -#define SYM_MKITER(i, t) HASH_MKITER((i), &(t)->t) +#define SYM_MKITER(i_, t_) HASH_MKITER(&(i_)->i, &(t_)->t) extern void sym_mkiter(sym_iter */*i*/, sym_table */*t*/); @@ -220,9 +214,9 @@ extern void sym_mkiter(sym_iter */*i*/, sym_table */*t*/); * returned in any particular order. */ -#define SYM_NEXT(i, p) do { \ +#define SYM_NEXT(i_, p) do { \ hash_base *_q; \ - HASH_NEXT((i), _q); \ + HASH_NEXT(&(i_)->i, _q); \ (p) = (void *)_q; \ } while (0)