From: mdw Date: Sat, 20 Jan 2001 11:50:58 +0000 (+0000) Subject: Hash tables indexed by atoms, to avoid expense of hashing keys on each X-Git-Tag: 2.0.4~133 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/commitdiff_plain/dcda594451ecd4d8ba699da3e4cc3c723f31b538?hp=c1c43500c9dade4d8df9366ae602b08f04f95682 Hash tables indexed by atoms, to avoid expense of hashing keys on each lookup, and to reduce storage used by key texts. --- diff --git a/assoc.c b/assoc.c new file mode 100644 index 0000000..26fe2c9 --- /dev/null +++ b/assoc.c @@ -0,0 +1,175 @@ +/* -*-c-*- + * + * $Id: assoc.c,v 1.1 2001/01/20 11:50:58 mdw Exp $ + * + * Assocation tables + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of the mLib utilities library. + * + * mLib is free software; you can redistribute it and/or modify + * 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: assoc.c,v $ + * Revision 1.1 2001/01/20 11:50:58 mdw + * Hash tables indexed by atoms, to avoid expense of hashing keys on each + * lookup, and to reduce storage used by key texts. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "alloc.h" +#include "assoc.h" +#include "atom.h" +#include "hash.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @assoc_create@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * + * Returns: --- + * + * Use: Creates a new association table. + */ + +void assoc_create(assoc_table *t) +{ + hash_create(&t->t, SYM_INITSZ); + t->load = SYM_LIMIT(SYM_INITSZ); +} + +/* --- @assoc_destroy@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * + * Returns: --- + * + * Use: Destroys an association table. + */ + +void assoc_destroy(assoc_table *t) +{ + hash_iter i; + + HASH_MKITER(&i, &t->t); + for (;;) { + hash_base *p; + HASH_NEXT(&i, p); + x_free(t->t.a, p); + } + hash_destroy(&t->t); +} + +/* --- @assoc_find@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * @atom *a@ = an atom to label the item + * @size_t sz@ = size of block to allocate + * @unsigned *f@ = pointer to `found' flag + * + * Returns: A pointer to the item located or null. + * + * Use: Looks up an atom in an association table. If the atom is + * found, the association is returned. If not, and @sz@ is + * zero, a null pointer is returned. Otherwise, a block of size + * @sz@ is allocated, its @assoc_base@ header is filled in, and + * the pointer returned. The flag @*f@ is cleared if the item + * couldn't be found, or set if it was. + * + * All the atoms used in a particular table should + */ + +void *assoc_find(assoc_table *t, atom *a, size_t sz, unsigned *f) +{ + hash_base **bin = HASH_BIN(&t->t, a->b.b.hash), **p; + assoc_base *q; + + /* --- Try to find the association --- */ + + for (p = bin; *p; p = &(*p)->next) { + q = (assoc_base *)*p; + if (q->a == a) { + *p = q->b.next; + q->b.next = *bin; + *bin = &q->b; + if (f) *f = 1; + return (q); + } + } + + /* --- Failed to find a match --- */ + + if (f) *f = 0; + if (!sz) return (0); + + /* --- Make a new assoication --- */ + + q = x_alloc(t->t.a, sz); + q->b.next = *bin; + q->b.hash = ATOM_HASH(a); + *bin = &q->b; + + /* --- Maybe extend the table --- */ + + if (t->load) + t->load--; + if (!t->load && hash_extend(&t->t)) + t->load = SYM_LIMIT(t->t.mask + 1); + return (q); +} + +/* --- @assoc_remove@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * @void *p@ = pointer to a block to remove + * + * Returns: --- + * + * Use: Removes an association from a table. + */ + +void assoc_remove(assoc_table *t, void *p) +{ + assoc_base *q = p; + hash_remove(&t->t, &q->b); + x_free(t->t.a, q); + t->load++; +} + +/* --- @assoc_mkiter@, @assoc_next@ --- * + * + * Arguments: @assoc_iter *i@ = pointer to an iterator + * @assoc_table *t@ = pointer to an association table + * + * Returns: Next association, or null, for @assoc_next@; nothing for + * @assoc_mkiter@. + * + * Use: Iterates over the associations in a table. + */ + +void assoc_mkiter(assoc_iter *i, assoc_table *t) { ASSOC_MKITER(i, t); } +void *assoc_next(assoc_iter *i) { void *p; ASSOC_NEXT(i, p); return (p); } + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/assoc.h b/assoc.h new file mode 100644 index 0000000..6eea33a --- /dev/null +++ b/assoc.h @@ -0,0 +1,156 @@ +/* -*-c-*- + * + * $Id: assoc.h,v 1.1 2001/01/20 11:50:58 mdw Exp $ + * + * Assocation tables + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of the mLib utilities library. + * + * mLib is free software; you can redistribute it and/or modify + * 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: assoc.h,v $ + * Revision 1.1 2001/01/20 11:50:58 mdw + * Hash tables indexed by atoms, to avoid expense of hashing keys on each + * lookup, and to reduce storage used by key texts. + * + */ + +#ifndef MLIB_ASSOC_H +#define MLIB_ASSOC_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef MLIB_ATOM_H +# include "atom.h" +#endif + +#ifndef MLIB_HASH_H +# include "hash.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct assoc_table { + hash_table t; + size_t load; +} assoc_table; + +typedef struct assoc_base { + hash_base b; + atom *a; +} assoc_base; + +typedef struct { hash_iter i; } assoc_iter; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @assoc_create@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * + * Returns: --- + * + * Use: Creates a new association table. + */ + +extern void assoc_create(assoc_table */*t*/); + +/* --- @assoc_destroy@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * + * Returns: --- + * + * Use: Destroys an association table. + */ + +extern void assoc_destroy(assoc_table */*t*/); + +/* --- @assoc_find@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * @atom *a@ = an atom to label the item + * @size_t sz@ = size of block to allocate + * @unsigned *f@ = pointer to `found' flag + * + * Returns: A pointer to the item located or null. + * + * Use: Looks up an atom in an association table. If the atom is + * found, the association is returned. If not, and @sz@ is + * zero, a null pointer is returned. Otherwise, a block of size + * @sz@ is allocated, its @assoc_base@ header is filled in, and + * the pointer returned. The flag @*f@ is cleared if the item + * couldn't be found, or set if it was. + * + * All the atoms used in a particular table should + */ + +extern void *assoc_find(assoc_table */*t*/, atom */*a*/, + size_t /*sz*/, unsigned */*f*/); + +/* --- @assoc_remove@ --- * + * + * Arguments: @assoc_table *t@ = pointer to an association table + * @void *p@ = pointer to a block to remove + * + * Returns: --- + * + * Use: Removes an association from a table. + */ + +extern void assoc_remove(assoc_table */*t*/, void */*p*/); + +/* --- @assoc_mkiter@, @assoc_next@ --- * + * + * Arguments: @assoc_iter *i@ = pointer to an iterator + * @assoc_table *t@ = pointer to an association table + * + * Returns: Next association, or null, for @assoc_next@; nothing for + * @assoc_mkiter@. + * + * Use: Iterates over the associations in a table. + */ + +#define ASSOC_MKITER(i_, t_) HASH_MKITER(&(i_)->i, &(t_)->t) + +#define ASSOC_NEXT(i_, p) do { \ + hash_base *_q; \ + HASH_NEXT(&(i_)->i, _q); \ + (p) = (void *)_q; \ +} while (0) + +extern void assoc_mkiter(assoc_iter */*i*/, assoc_table */*t*/); +extern void *assoc_next(assoc_iter */*i*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif