Main Page | Modules | Alphabetical List | Data Structures | File List | Data Fields | Globals

ht_resize.c

Go to the documentation of this file.
00001 /*
00002 ** Copyright (C) 2002 by Kevin L. Mitchell <klmitch@mit.edu>
00003 **
00004 ** This library is free software; you can redistribute it and/or
00005 ** modify it under the terms of the GNU Library General Public
00006 ** License as published by the Free Software Foundation; either
00007 ** version 2 of the License, or (at your option) any later version.
00008 **
00009 ** This library is distributed in the hope that it will be useful,
00010 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012 ** Library General Public License for more details.
00013 **
00014 ** You should have received a copy of the GNU Library General Public
00015 ** License along with this library; if not, write to the Free
00016 ** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00017 ** MA 02111-1307, USA
00018 **
00019 ** @(#)$Id: ht_resize.c,v 1.3 2006/07/13 05:36:16 klmitch Exp $
00020 */
00029 #include <stdlib.h>
00030 #include <errno.h>
00031 
00032 #include "dbprim.h"
00033 #include "dbprim_int.h"
00034 
00035 RCSTAG("@(#)$Id: ht_resize.c,v 1.3 2006/07/13 05:36:16 klmitch Exp $");
00036 
00037 unsigned long
00038 ht_resize(hash_table_t *table, unsigned long new_size)
00039 {
00040   unsigned long retval;
00041   link_head_t *htab;
00042   link_elem_t *elem;
00043   hash_entry_t *ent;
00044   int i;
00045 
00046   initialize_dbpr_error_table(); /* initialize error table */
00047 
00048   if (!ht_verify(table)) /* verify that it's really a table */
00049     return DB_ERR_BADARGS;
00050 
00051   if (table->ht_flags & HASH_FLAG_FREEZE) /* don't resize frozen tables */
00052     return DB_ERR_FROZEN;
00053 
00054   if (!new_size) /* select the new table size, defaulting to fuzzed current */
00055     new_size = _hash_fuzz(table->ht_count ? table->ht_count : 1);
00056   new_size = _hash_prime(new_size); /* prime it! */
00057 
00058   /* Call the resize calback */
00059   if (table->ht_resize && (retval = (*table->ht_resize)(table, new_size)))
00060     return retval;
00061 
00062   /* allocate new table array */
00063   if (!(htab = (link_head_t *)malloc(new_size * sizeof(link_head_t))))
00064     return errno;
00065 
00066   /* initialize the new array */
00067   for (i = 0; i < new_size; i++)
00068     if ((retval = ll_init(&htab[i], table))) { /* initialize listhead array */
00069       free(htab);
00070       return retval;
00071     }
00072 
00073   /* rehash the table */
00074   for (i = 0; i < table->ht_modulus; i++) /* step through each element */
00075     for (elem = ll_first(&table->ht_table[i]); elem;
00076          elem = ll_first(&table->ht_table[i])) {
00077       ent = le_object(elem);
00078 
00079       /* calculate new hash value */
00080       ent->he_hash = (*table->ht_func)(table, &ent->he_key) % new_size;
00081 
00082       if ((retval = ll_remove(&table->ht_table[i], elem)) ||
00083           (retval = ll_add(&htab[ent->he_hash], elem, LINK_LOC_HEAD, 0))) {
00084         /* This is catastrophic!  We've lost some elements.  Shouldn't
00085          * ever happen, but you know bugs...
00086          */
00087         free(htab); /* free allocated memory */
00088         free(table->ht_table);
00089 
00090         table->ht_modulus = 0; /* reset table to reflect empty state */
00091         table->ht_count = 0;
00092         table->ht_rollover = 0;
00093         table->ht_rollunder = 0;
00094         table->ht_table = 0;
00095 
00096         return DB_ERR_UNRECOVERABLE;
00097       }
00098     }
00099 
00100   if (table->ht_table) /* OK, free old table value */
00101     free(table->ht_table);
00102 
00103   table->ht_modulus = new_size; /* set new table size and roll values */
00104   table->ht_rollover = _hash_rollover(new_size);
00105   table->ht_rollunder = _hash_rollunder(new_size);
00106   table->ht_table = htab; /* store new table */
00107 
00108   return 0;
00109 }

Generated on Sat Jul 15 14:10:33 2006 for DatabasePrimitivesLibrary by  doxygen 1.4.4