db2/common/db_shash.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7
   8 #include "config.h"
   9
  10 #ifndef lint
  11 static const char sccsid[] = "@(#)db_shash.c    10.3 (Sleepycat) 6/21/97";
  12 #endif /* not lint */
  13
  14 #ifndef NO_SYSTEM_INCLUDES
  15 #include <sys/types.h>
  16 #endif
  17
  18 #include "db_int.h"
  19 #include "shqueue.h"
  20 #include "common_ext.h"
  21
  22 /* Powers-of-2 and close-by prime number pairs. */
  23 static const struct {
  24         int     power;
  25         int     prime;
  26 } list[] = {
  27         {  64,    67},
  28         { 128,   131},
  29         { 256,   257},
  30         { 512,   521},
  31         {1024,  1031},
  32         {2048,  2053},
  33         {4096,  4099},
  34         {8192,  8191},
  35         {0,        0}
  36 };
  37
  38 /*
  39  * __db_tablesize --
  40  *      Choose a size for the hash table.
  41  *
  42  * PUBLIC: int __db_tablesize __P((int));
  43  */
  44 int
  45 __db_tablesize(n_buckets)
  46         int n_buckets;
  47 {
  48         int i;
  49
  50         /*
  51          * We try to be clever about how big we make the hash tables.  Pick
  52          * a prime number close to the "suggested" number of elements that
  53          * will be in the hash table.  We shoot for minimum collisions (i.e.
  54          * one element in each bucket).  We use 64 as the minimum table size.
  55          *
  56          * Ref: Sedgewick, Algorithms in C, "Hash Functions"
  57          */
  58         if (n_buckets < 64)
  59                 n_buckets = 64;
  60
  61         for (i = 0;; ++i) {
  62                 if (list[i].power == 0) {
  63                         --i;
  64                         break;
  65                 }
  66                 if (list[i].power >= n_buckets)
  67                         break;
  68         }
  69         return (list[i].prime);
  70 }
  71
  72 /*
  73  * __db_hashinit --
  74  *      Initialize a hash table that resides in shared memory.
  75  *
  76  * PUBLIC: void __db_hashinit __P((void *, int));
  77  */
  78 void
  79 __db_hashinit(begin, nelements)
  80         void *begin;
  81         int nelements;
  82 {
  83         int i;
  84         SH_TAILQ_HEAD(hash_head) *headp;
  85
  86         headp = (struct hash_head *)begin;
  87
  88         for (i = 0; i < nelements; i++, headp++)
  89                 SH_TAILQ_INIT(headp);
  90 }