src/native_client/src/trusted/generic_container/container_hash_table.c

   1 /*
   2  * Copyright 2008 The Native Client Authors. All rights reserved.
   3  * Use of this source code is governed by a BSD-style license that can be
   4  * found in the LICENSE file.
   5  */
   6
   7 #include "native_client/src/trusted/generic_container/container_hash_table.h"
   8
   9 #include "native_client/src/include/portability.h"
  10
  11 static struct NaClContainerVtbl const  kNaClContainerHashTblVtbl = {
  12   NaClContainerHashTblInsert,
  13   NaClContainerHashTblFind,
  14   NaClContainerHashTblDtor,
  15   sizeof(struct NaClContainerHashTblIter),
  16   NaClContainerHashTblIterCtor,
  17 };
  18
  19 #define HASH_TABLE_LOAD_FACTOR      2
  20 #define HASH_TABLE_STRIDE           17
  21 /*
  22  * The stride p is prime, so it is co-prime with any num_bucket value
  23  * (except for its own multiples) and thus linear probing by
  24  * increments of the stride will visit every bucket.  (I.e., the
  25  * stride value is a generator for the additive group Z_k^+, where
  26  * k=num_bucket.)  Assume that (k,p)=1.
  27  *
  28  * (p,+) is a generator is another way of saying that
  29  * 0,p,2p,3p,...,(k-1)p (mod k) is a permutation of 0,1,...,k-1.
  30  *
  31  * assume otherwise, so (p,+) generates a subgroup of Z_k^+.  let n be
  32  * the least integer greater than 0 where np=0 mod k, i.e., 0 < n < k.
  33  * since (p) doesn't generate Z_k^+, we have n < k.  then np=mk for
  34  * some integer m>0.  since p is prime and p \not| k but p divides mk,
  35  * p must divide m.  write m=pq.  then np = pqk, so n = qk.  =><=
  36  *
  37  * The co-primality of the stride and number of bucket is a
  38  * precondition for the insertion algorithm terminating.  (Another
  39  * precondition is that there is an unused slot.)
  40  *
  41  * We expand the hash table by doubling the number of buckets.  Thus,
  42  * if num_bucket starts off co-prime with the stride, it will remain
  43  * so.
  44  */
  45 #define HASH_TABLE_MIN_BUCKETS      32
  46 /*
  47  * must be greater than HASH_TABLE_STRIDE and not a multiple so that
  48  * they're co-prime.
  49  */
  50
  51 static struct NaClContainerHashTblEntry *NaClContainerHashTblMakeBucket(
  52     size_t size) {
  53   struct NaClContainerHashTblEntry    *bucket;
  54
  55   if (SIZE_T_MAX / sizeof *bucket < size) {
  56     return NULL;
  57   }
  58   bucket = calloc(size, sizeof *bucket);
  59   return bucket;
  60 }
  61
  62
  63 /*
  64  * The functor_obj is the comparison and hash functor.  It is always
  65  * passed as the first arguments to cmp_fn and hash_fn to allow these
  66  * member functions to use its members to determine how to
  67  * compare/hash.  Arguably we should define a class with a vtable
  68  * containing two virtual functions, but we don't expect there to be
  69  * many object instances.
  70  */
  71 int NaClContainerHashTblCtor(struct NaClContainerHashTbl  *self,
  72                              struct NaClHashFunctor       *hash_functor,
  73                              size_t                       num_buckets) {
  74   int success;
  75
  76   self->base.vtbl = (struct NaClContainerVtbl *) NULL;
  77
  78   /* silently increase number of buckets if too small */
  79   if (num_buckets < HASH_TABLE_MIN_BUCKETS) {
  80     num_buckets = HASH_TABLE_MIN_BUCKETS;
  81   }
  82   /* if a multiple of stride, silently increase it */
  83   if (0 == (num_buckets % HASH_TABLE_STRIDE)) {
  84     ++num_buckets;
  85   }
  86
  87   self->hash_functor = hash_functor;
  88   self->num_buckets = num_buckets;
  89   self->num_entries = 0;
  90   self->bucket = NaClContainerHashTblMakeBucket(num_buckets);
  91
  92   success = self->bucket != 0;
  93
  94   if (success) {
  95     self->base.vtbl = &kNaClContainerHashTblVtbl;
  96   }
  97   return success;
  98 }
  99
 100
 101 int NaClContainerHashTblCheckLoad(struct NaClContainerHashTbl *self) {
 102   struct NaClContainerHashTblEntry  *entry;
 103   struct NaClContainerHashTblEntry  *new_table;
 104   struct NaClContainerHashTblEntry  *old_table;
 105   size_t                            new_size;
 106   size_t                            old_size;
 107   size_t                            i;
 108
 109   /*
 110    * Check load factor.  If greater than THRESHOLD, double number of
 111    * buckets and rehash.
 112    */
 113   if (HASH_TABLE_LOAD_FACTOR * self->num_entries < self->num_buckets)
 114     return 1;
 115
 116   old_size = self->num_buckets;
 117   new_size = 2 * old_size;
 118   /*
 119    * arithmetic overflow?!?  we normally would not have enough memory
 120    */
 121   if (new_size < old_size)
 122     return 0;
 123
 124   new_table = NaClContainerHashTblMakeBucket(new_size);
 125   if (!new_table)
 126     return 0;
 127
 128   old_table = self->bucket;
 129   self->bucket = new_table;
 130
 131   self->num_buckets = new_size;
 132   self->num_entries = 0;
 133
 134   /*
 135    * The rehash/transfer to the new, expanded table should not fail,
 136    * since the Insert method (below) does not fail.
 137    */
 138   for (i = 0; i < old_size; i++) {
 139     entry = &old_table[i];
 140     if (NACL_CHTE_USED != entry->flags) {
 141       continue;
 142     }
 143     (*self->base.vtbl->Insert)((struct NaClContainer *) self,
 144                                entry->datum);
 145   }
 146
 147   free(old_table);
 148   return 1;
 149 }
 150
 151
 152 static uintptr_t HashNext(uintptr_t idx,
 153                           size_t    modulus) {
 154   idx += HASH_TABLE_STRIDE;
 155   while (idx >= modulus) {
 156     idx -= modulus;
 157   }
 158   return idx;
 159 }
 160
 161
 162 int NaClContainerHashTblInsert(struct NaClContainer *vself,
 163                                void                 *obj) {
 164   struct NaClContainerHashTbl *self = (struct NaClContainerHashTbl *) vself;
 165   uintptr_t                   idx;
 166
 167   for (idx = (*self->hash_functor->vtbl->Hash)(self->hash_functor,
 168                                                obj) % self->num_buckets;
 169        NACL_CHTE_USED == self->bucket[idx].flags;
 170        idx = HashNext(idx, self->num_buckets)) {
 171   }
 172   /* unused or deleted */
 173   self->bucket[idx].datum = obj;
 174   self->bucket[idx].flags = NACL_CHTE_USED;
 175   ++self->num_entries;
 176
 177   return NaClContainerHashTblCheckLoad(self);
 178 }
 179
 180
 181 /* fwd */
 182 static struct NaClContainerIterVtbl const kNaClContainerHashTblIterVtbl;
 183
 184
 185 struct NaClContainerIter *NaClContainerHashTblFind(
 186     struct NaClContainer      *vself,
 187     void                      *key,
 188     struct NaClContainerIter  *vout) {
 189   struct NaClContainerHashTbl     *self
 190       = (struct NaClContainerHashTbl *) vself;
 191   uintptr_t                       idx;
 192   struct NaClContainerHashTblIter *out
 193       = (struct NaClContainerHashTblIter *) vout;
 194
 195   for (idx = (*self->hash_functor->vtbl->Hash)(self->hash_functor,
 196                                                key) % self->num_buckets;
 197        0 != self->bucket[idx].flags;
 198        idx = HashNext(idx, self->num_buckets)) {
 199     if (0 != (self->bucket[idx].flags & NACL_CHTE_USED)
 200         && ((*self->hash_functor->vtbl->base.OrderCmp)
 201             ((struct NaClCmpFunctor *) self->hash_functor,
 202              self->bucket[idx].datum, key)) == 0) {
 203       break;
 204     }
 205   }
 206   if (0 == self->bucket[idx].flags) {
 207     /* not found */
 208     idx = self->num_buckets;
 209   }
 210
 211   out->htbl = self;
 212   out->idx = idx;
 213
 214   vout->vtbl = &kNaClContainerHashTblIterVtbl;
 215   return vout;
 216 }
 217
 218
 219 void NaClContainerHashTblDtor(struct NaClContainer *vself) {
 220   struct NaClContainerHashTbl *self = (struct NaClContainerHashTbl *) vself;
 221   unsigned int                idx;
 222
 223   for (idx = 0; idx < self->num_buckets; ++idx) {
 224     if (self->bucket[idx].flags & NACL_CHTE_USED) {
 225       free(self->bucket[idx].datum);
 226     }
 227   }
 228   free(self->bucket);
 229   self->bucket = 0;
 230 }
 231
 232
 233 int NaClContainerHashTblIterAtEnd(struct NaClContainerIter  *vself) {
 234   struct NaClContainerHashTblIter *self
 235       = (struct NaClContainerHashTblIter *) vself;
 236
 237   return self->idx >= self->htbl->num_buckets;
 238 }
 239
 240
 241 void *NaClContainerHashTblIterStar(struct NaClContainerIter  *vself) {
 242   struct NaClContainerHashTblIter *self
 243       = (struct NaClContainerHashTblIter *) vself;
 244
 245   return self->htbl->bucket[self->idx].datum;
 246 }
 247
 248
 249 void NaClContainerHashTblIterIncr(struct NaClContainerIter   *vself) {
 250   struct NaClContainerHashTblIter *self
 251       = (struct NaClContainerHashTblIter *) vself;
 252
 253   while (++self->idx < self->htbl->num_buckets) {
 254     if (self->htbl->bucket[self->idx].flags == NACL_CHTE_USED)
 255       return;
 256   }
 257   /* self->idx == self->htbl->num_buckets imply AtEnd */
 258   return;
 259 }
 260
 261
 262 void NaClContainerHashTblIterErase(struct NaClContainerIter   *vself) {
 263   struct NaClContainerHashTblIter *self
 264       = (struct NaClContainerHashTblIter *) vself;
 265
 266   if (self->htbl->bucket[self->idx].flags == NACL_CHTE_USED) {
 267     --self->htbl->num_entries;
 268   }
 269   self->htbl->bucket[self->idx].flags = NACL_CHTE_DELETED;
 270   free(self->htbl->bucket[self->idx].datum);
 271   self->htbl->bucket[self->idx].datum = 0;
 272   (*vself->vtbl->Incr)(vself);
 273 }
 274
 275
 276 void *NaClContainerHashTblIterExtract(struct NaClContainerIter   *vself) {
 277   struct NaClContainerHashTblIter *self
 278       = (struct NaClContainerHashTblIter *) vself;
 279   void                        *datum;
 280
 281   if (self->htbl->bucket[self->idx].flags == NACL_CHTE_USED) {
 282     --self->htbl->num_entries;
 283   }
 284   self->htbl->bucket[self->idx].flags = NACL_CHTE_DELETED;
 285   datum = self->htbl->bucket[self->idx].datum;
 286   self->htbl->bucket[self->idx].datum = 0;
 287   (*vself->vtbl->Incr)(vself);
 288
 289   return datum;
 290 }
 291
 292
 293 static struct NaClContainerIterVtbl const kNaClContainerHashTblIterVtbl = {
 294   NaClContainerHashTblIterAtEnd,
 295   NaClContainerHashTblIterStar,
 296   NaClContainerHashTblIterIncr,
 297   NaClContainerHashTblIterErase,
 298   NaClContainerHashTblIterExtract,
 299 };
 300
 301
 302 int NaClContainerHashTblIterCtor(struct NaClContainer     *vself,
 303                                  struct NaClContainerIter *viter) {
 304   struct NaClContainerHashTbl     *self
 305       = (struct NaClContainerHashTbl *) vself;
 306   struct NaClContainerHashTblIter *iter
 307       = (struct NaClContainerHashTblIter *) viter;
 308
 309   viter->vtbl = &kNaClContainerHashTblIterVtbl;
 310   iter->htbl = self;
 311   iter->idx = 0;
 312   if (0 == (self->bucket[0].flags & NACL_CHTE_USED)) {
 313     NaClContainerHashTblIterIncr(viter);
 314   }
 315   return 1;
 316 }