From 2ae5376b8a8158f38cbbe9c0238b5428ee3ce711 Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 20 Jan 2001 11:49:37 +0000 Subject: [PATCH] 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. --- sym.c | 53 +++++++++++++++-------------------------------------- sym.h | 51 ++++++++++++++++++++++++++++++++++++++------------- 2 files changed, 53 insertions(+), 51 deletions(-) diff --git a/sym.c b/sym.c index 4e11fba..c6d1e43 100644 --- a/sym.c +++ b/sym.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sym.c,v 1.11 2000/06/17 10:37:39 mdw Exp $ + * $Id: sym.c,v 1.12 2001/01/20 11:49:37 mdw Exp $ * * Symbol table management * @@ -30,6 +30,12 @@ /*----- Revision history --------------------------------------------------* * * $Log: sym.c,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. * @@ -85,27 +91,6 @@ #include "sub.h" #include "sym.h" -/*----- 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 64 /* 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 */ - /*----- Main code ---------------------------------------------------------*/ /* --- @sym_create@ --- * @@ -145,8 +130,6 @@ void sym_destroy(sym_table *t) SYM_NEXT(&i, p); if (!p) break; - if (p->len > SYM_BUFSZ) - subarena_free(t->s, p->name.p, p->len); x_free(t->t.a, p); } hash_destroy(&t->t); @@ -224,21 +207,17 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f) if (f) *f = 0; if (!sz) return (0); - /* --- Create a new symbol block and initialize it --- */ + /* --- Create a new symbol block and initialize it --- * + * + * The name is attached to the end of the symbol block. + */ - q = x_alloc(t->t.a, sz); + q = x_alloc(t->t.a, sz + len); q->b.next = *bin; q->b.hash = hash; + q->name = (char *)q + sz; + memcpy(q->name, n, len); q->len = len; - if (n) { - if (len <= SYM_BUFSZ) - memcpy(q->name.b, n, len); - else { - q->name.p = subarena_alloc(t->s, len); - memcpy(q->name.p, n, len); - } - } - *bin = &q->b; /* --- Consider growing the array --- */ @@ -246,7 +225,7 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f) if (t->load) t->load--; if (!t->load && hash_extend(&t->t)) - t->load = SYM_LIMIT(t->t.mask / 2 + 1); + t->load = SYM_LIMIT(t->t.mask + 1); /* --- Finished that, so return the new symbol block --- */ @@ -269,8 +248,6 @@ void sym_remove(sym_table *t, void *p) { sym_base *q = p; hash_remove(&t->t, &q->b); - if (q->len > SYM_BUFSZ) - subarena_free(t->s, q->name.p, q->len); xfree(q); t->load++; } diff --git a/sym.h b/sym.h index d9d270c..db49ff5 100644 --- a/sym.h +++ b/sym.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sym.h,v 1.11 2000/06/17 10:37:39 mdw Exp $ + * $Id: sym.h,v 1.12 2001/01/20 11:49:37 mdw Exp $ * * Symbol table management * @@ -30,6 +30,12 @@ /*----- 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. * @@ -89,6 +95,27 @@ # 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 --- * @@ -113,23 +140,21 @@ 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 --- */ -- 2.11.0