libbanshee/engine/hashset.c

   1 /*
   2  * Copyright (c) 2000-2001
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  */
  30
  31 #include <stdlib.h>
  32 #include <assert.h>
  33 #include <math.h>
  34
  35 #include "hashset.h"
  36 #include "util.h"
  37 #define INIT_TABLE_SIZE 2
  38 #define EMPTY_KEY 0
  39 #define UB(n) ((1<<n)-1) /* 2^n-1 */
  40 #define CAP(n) (1<<n)   /* 2^n */
  41
  42 struct hash_set
  43 {
  44   int *traditional table;
  45   unsigned int ub;
  46   unsigned int capacity;
  47   unsigned int inserts;
  48   unsigned int size;
  49 };
  50
  51 static const int prime_1 = 83;
  52 static const int prime_2 = 5189;
  53 static const int init_table_size = INIT_TABLE_SIZE;
  54 static const int empty_key = EMPTY_KEY;
  55
  56 hash_set hs_create(region r)
  57 {
  58
  59   hash_set hs = ralloc(r, struct hash_set);
  60
  61   hs->ub = UB(init_table_size);
  62   hs->size = init_table_size;
  63   hs->capacity = CAP(init_table_size);
  64   hs->table = (int *)calloc(hs->capacity, sizeof(int));
  65   hs->inserts = 0;
  66   return hs;
  67 }
  68
  69 int hs_num_items(hash_set hs)
  70 {
  71   return hs->inserts;
  72 }
  73
  74 int *hs_list_items(hash_set hs)
  75 {
  76   return hs->table;
  77 }
  78
  79 static bool member(int *table, int ub, int i, int value)
  80 {
  81   while (table[i] != empty_key)
  82     {
  83       if (table[i] == value)
  84         return TRUE;
  85
  86       else
  87         i = ub & (i + prime_2);
  88     }
  89   return FALSE;
  90 }
  91
  92 static inline void reinsert(int *table, int ub, int value)
  93 {
  94   int i;
  95
  96   i = ub & (prime_1 * value);
  97
  98   while (table[i] != empty_key)
  99     {
 100       /* possibly the value is already present */
 101       if (table[i] == value)
 102         return;
 103
 104       else
 105         i = ub & (i + prime_2);
 106     }
 107
 108   table[i] = value;
 109 }
 110
 111 static bool member_or_insert(int *table, int ub, int i, int value)
 112 {
 113   while (table[i] != empty_key)
 114     {
 115       if (table[i] == value)
 116         return TRUE;
 117
 118       else
 119         i = ub & (i + prime_2);
 120     }
 121   table[i] = value;
 122   return FALSE;
 123 }
 124
 125 static void rehash(hash_set hs)
 126 {
 127   int *old_table;
 128   int old_capacity, i;
 129
 130   old_table = hs->table;
 131   old_capacity = hs->capacity;
 132   hs->capacity *= 2;
 133   hs->ub = UB(++hs->size);
 134   hs->table = (int *)calloc(hs->capacity, sizeof(int));
 135   assert(hs->table);
 136
 137
 138   for (i = 0; i < old_capacity; i++)
 139     {
 140       reinsert(hs->table, hs->ub, old_table[i]);
 141     }
 142
 143   free(old_table);
 144 }
 145 /*
 146 static void post_insert(hash_set hs)
 147 {
 148   float percent_full;
 149
 150   int capacity = hs->capacity;
 151   int inserts = ++hs->inserts;
 152
 153   printf("%d,%d->%f\n",inserts,capacity,percent_full);
 154   assert(capacity);
 155   percent_full = (float) inserts / capacity;
 156
 157
 158   if (percent_full != percent_full)
 159     {
 160       assert (0);
 161     }
 162
 163   if (percent_full >= .85)
 164     rehash(hs);
 165 }
 166 */
 167
 168 static void post_insert(hash_set hs)
 169 {
 170   int capacity = hs->capacity;
 171   int inserts = ++hs->inserts;
 172
 173   float percent_capacity = capacity * .85;
 174
 175  /*
 176   printf("%d,%d->%f\n",inserts,capacity,percent_capacity);
 177  */
 178
 179   if ( (float) inserts >= percent_capacity)
 180     {
 181       rehash(hs);
 182     }
 183
 184 }
 185
 186
 187 bool hs_query(hash_set hs, int entry)
 188 {
 189   int hash;
 190   int ub = hs->ub;
 191
 192   hash = ub & (prime_1 * abs(entry));
 193   return member(hs->table, ub, hash, entry);
 194 }
 195
 196 bool hs_member(hash_set hs, int entry)
 197 {
 198   int hash;
 199   int ub = hs->ub;
 200
 201   hash = ub & (prime_1 * abs(entry));
 202   if (member_or_insert(hs->table, ub, hash, entry))
 203     return TRUE;
 204
 205   else
 206     {
 207       post_insert(hs);
 208       return FALSE;
 209     }
 210 }
 211
 212 void hs_delete(hash_set hs)
 213 {
 214   free(hs->table);
 215 }
 216
 217