/* -*-c-*-
*
* $Id: hash.c,v 1.3 2000/07/16 12:29:16 mdw Exp $
*
* General hashtable infrastructure
*
* (c) 1999 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: hash.c,v $
* Revision 1.3 2000/07/16 12:29:16 mdw
* Change to arena `realloc' interface, to fix a design bug.
*
* Revision 1.2 2000/06/17 10:37:39 mdw
* Add support for arena management.
*
* Revision 1.1 1999/08/02 14:45:48 mdw
* Break low-level hashtable code out from sym.
*
*/
/*----- Header files ------------------------------------------------------*/
#include
#include
#include
#include "alloc.h"
#include "arena.h"
#include "bits.h"
#include "exc.h"
#include "hash.h"
/*----- Main code ---------------------------------------------------------*/
/* --- @hash_create@ --- *
*
* Arguments: @hash_table *t@ = pointer to hashtable to initialize
* @size_t n@ = number of bins to allocate (zero initially)
*
* Returns: ---
*
* Use: Initializes a hashtable with a given number of bins. The
* bins are initially empty. The number of bins must be a power
* of two. This is not checked.
*/
void hash_create(hash_table *t, size_t n)
{
hash_base **v;
t->a = arena_global;
t->v = x_alloc(t->a, n * sizeof(hash_base *));
t->mask = n - 1;
for (v = t->v; n; v++, n--)
*v = 0;
}
/* --- @hash_destroy@ --- *
*
* Arguments: @hash_table *t@ = pointer to hashtable to destroy
*
* Returns: ---
*
* Use: Frees a hashtable. The items are not freed: they are the
* responsibility of the implementation.
*/
void hash_destroy(hash_table *t)
{
x_free(t->a, t->v);
}
/* --- @hash_bin@ --- *
*
* Arguments: @hash_table *t@ = pointer to hashtable
* @uint32 hash@ = hash value to look up
*
* Returns: Pointer to the bin's list head.
*
* Use: Given a hash value return the address of the appropriate list
* head. It is safe to remove the current entry from the table.
*/
hash_base **hash_bin(hash_table *t, uint32 hash)
{
return (HASH_BIN(t, hash));
}
/* --- @hash_extend@ --- *
*
* Arguments: @hash_table *t@ = pointer to hashtable to extend
*
* Returns: Nonzero if extension was successful.
*
* Use: Extends a hashtable. The number of bins is doubled and the
* entries are redistributed.
*/
int hash_extend(hash_table *t)
{
hash_base **v;
uint32 m = t->mask + 1;
size_t i;
/* --- Allocate a new hash bin vector --- */
if ((v = A_REALLOC(t->a, t->v,
2 * m * sizeof(hash_base *),
m * sizeof(hash_base *))) == 0) {
return (0);
}
t->v = v;
t->mask = (m * 2) - 1;
/* --- Wander through the table rehashing things --- */
for (i = 0; i < m; i++) {
hash_base **p = v + i;
hash_base **q = p + m;
while (*p) {
if (!((*p)->hash & m))
p = &(*p)->next;
else {
*q = *p;
q = &(*q)->next;
*p = (*p)->next;
}
}
*p = 0;
*q = 0;
}
return (1);
}
/* --- @hash_remove@ --- *
*
* Arguments: @hash_table *t@ = pointer to hashtable
* @hash_base *p@ = pointer to item to remove
*
* Returns: ---
*
* Use: Removes an item from a hashtable. The item itself is not
* freed, although it is removed from the data structure and is
* safe to free.
*/
void hash_remove(hash_table *t, hash_base *p)
{
hash_base **b = HASH_BIN(t, p->hash);
while (*b) {
if (*b == p) {
*b = p->next;
return;
}
b = &(*b)->next;
}
return;
}
/* --- @hash_mkiter@ --- *
*
* Arguments: @hash_iter *i@ = pointer to iterator to create
* @hash_table *t@ = pointer to hashtable to iterate
*
* Returns: ---
*
* Use: Initializes a hashtable iterator.
*/
void hash_mkiter(hash_iter *i, hash_table *t) { HASH_MKITER(i, t); }
/* --- @hash_next@ --- *
*
* Arguments: @hash_iter *i@ = pointer to iterator
*
* Returns: Pointer to the next hashtable entry found, or null.
*
* Use: Returns the next entry from the hashtable.
*/
hash_base *hash_next(hash_iter *i)
{
hash_base *b;
HASH_NEXT(i, b);
return (b);
}
/*----- That's all, folks -------------------------------------------------*/