libs/dbprim/ht_resize.c

   1 /*
   2 ** Copyright (C) 2002 by Kevin L. Mitchell <klmitch@mit.edu>
   3 **
   4 ** This library is free software; you can redistribute it and/or
   5 ** modify it under the terms of the GNU Library General Public
   6 ** License as published by the Free Software Foundation; either
   7 ** version 2 of the License, or (at your option) any later version.
   8 **
   9 ** This library is distributed in the hope that it will be useful,
  10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 ** Library General Public License for more details.
  13 **
  14 ** You should have received a copy of the GNU Library General Public
  15 ** License along with this library; if not, write to the Free
  16 ** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  17 ** MA 02111-1307, USA
  18 **
  19 ** @(#)$Id$
  20 */
  21 #include <stdlib.h>
  22 #include <errno.h>
  23
  24 #include "dbprim.h"
  25 #include "dbprim_int.h"
  26
  27 RCSTAG("@(#)$Id$");
  28
  29 /** \ingroup dbprim_hash
  30  * \brief Resize a hash table.
  31  *
  32  * This function resizes a hash table to the given \p new_size.  If \p
  33  * new_size is 0, then an appropriate new size based on the current
  34  * number of items in the hash table will be selected.
  35  *
  36  * \param table A pointer to a #hash_table_t.
  37  * \param new_size
  38  *              A new size value for the table.
  39  *
  40  * \retval DB_ERR_BADARGS       An argument was invalid.
  41  * \retval DB_ERR_FROZEN        The table is currently frozen.
  42  * \retval DB_ERR_UNRECOVERABLE A catastrophic error was encountered.
  43  *                              The table is now unusable.
  44  * \retval ENOMEM               No memory could be allocated for the
  45  *                              new bucket table.
  46  */
  47 unsigned long
  48 ht_resize(hash_table_t *table, unsigned long new_size)
  49 {
  50   unsigned long retval;
  51   link_head_t *htab;
  52   link_elem_t *elem;
  53   hash_entry_t *ent;
  54   int i;
  55
  56   initialize_dbpr_error_table(); /* initialize error table */
  57
  58   if (!ht_verify(table)) /* verify that it's really a table */
  59     return DB_ERR_BADARGS;
  60
  61   if (table->ht_flags & HASH_FLAG_FREEZE) /* don't resize frozen tables */
  62     return DB_ERR_FROZEN;
  63
  64   if (!new_size) /* select the new table size, defaulting to fuzzed current */
  65     new_size = _hash_fuzz(table->ht_count ? table->ht_count : 1);
  66   new_size = _hash_prime(new_size); /* prime it! */
  67
  68   /* Call the resize calback */
  69   if (table->ht_resize && (retval = (*table->ht_resize)(table, new_size)))
  70     return retval;
  71
  72   /* allocate new table array */
  73   if (!(htab = (link_head_t *)malloc(new_size * sizeof(link_head_t))))
  74     return errno;
  75
  76   /* initialize the new array */
  77   for (i = 0; i < new_size; i++)
  78     if ((retval = ll_init(&htab[i], table))) { /* initialize listhead array */
  79       free(htab);
  80       return retval;
  81     }
  82
  83   /* rehash the table */
  84   for (i = 0; i < table->ht_modulus; i++) /* step through each element */
  85     for (elem = ll_first(&table->ht_table[i]); elem;
  86          elem = ll_first(&table->ht_table[i])) {
  87       ent = le_object(elem);
  88
  89       /* calculate new hash value */
  90       ent->he_hash = (*table->ht_func)(table, &ent->he_key) % new_size;
  91
  92       if ((retval = ll_remove(&table->ht_table[i], elem)) ||
  93           (retval = ll_add(&htab[ent->he_hash], elem, LINK_LOC_HEAD, 0))) {
  94         /* This is catastrophic!  We've lost some elements.  Shouldn't
  95          * ever happen, but you know bugs...
  96          */
  97         free(htab); /* free allocated memory */
  98         free(table->ht_table);
  99
 100         table->ht_modulus = 0; /* reset table to reflect empty state */
 101         table->ht_count = 0;
 102         table->ht_rollover = 0;
 103         table->ht_rollunder = 0;
 104         table->ht_table = 0;
 105
 106         return DB_ERR_UNRECOVERABLE;
 107       }
 108     }
 109
 110   if (table->ht_table) /* OK, free old table value */
 111     free(table->ht_table);
 112
 113   table->ht_modulus = new_size; /* set new table size and roll values */
 114   table->ht_rollover = _hash_rollover(new_size);
 115   table->ht_rollunder = _hash_rollunder(new_size);
 116   table->ht_table = htab; /* store new table */
 117
 118   return 0;
 119 }