common/db_shash.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996-2009 Oracle.  All rights reserved.
   5  *
   6  * $Id$
   7  */
   8
   9 #include "db_config.h"
  10
  11 #include "db_int.h"
  12
  13 /*
  14  * __db_tablesize --
  15  *      Choose a size for the hash table.
  16  *
  17  * PUBLIC: u_int32_t __db_tablesize __P((u_int32_t));
  18  */
  19 u_int32_t
  20 __db_tablesize(n_buckets)
  21         u_int32_t n_buckets;
  22 {
  23         /*
  24          * We try to be clever about how big we make the hash tables.  Use a
  25          * prime number close to the "suggested" number of elements that will
  26          * be in the hash table.  Use 32 as the minimum hash table size.
  27          *
  28          * Ref: Sedgewick, Algorithms in C, "Hash Functions"
  29          *
  30          * Up to ~250,000 buckets, we use powers of 2.  After that, we slow
  31          * the rate of increase by half.  For each choice, we then use a
  32          * nearby prime number as the hash value.
  33          *
  34          * If a terabyte is the maximum cache we'll see, and we assume there
  35          * are 10 1K buckets on each hash chain, then 107374182 is the maximum
  36          * number of buckets we'll ever need.
  37          *
  38          * We don't use the obvious static data structure because some C
  39          * compilers (and I use the term loosely), can't handle them.
  40          */
  41 #define HASH_SIZE(power, prime) {                                       \
  42         if ((power) >= n_buckets)                                       \
  43                 return (prime);                                         \
  44 }
  45         HASH_SIZE(32, 37);                      /* 2^5 */
  46         HASH_SIZE(64, 67);                      /* 2^6 */
  47         HASH_SIZE(128, 131);                    /* 2^7 */
  48         HASH_SIZE(256, 257);                    /* 2^8 */
  49         HASH_SIZE(512, 521);                    /* 2^9 */
  50         HASH_SIZE(1024, 1031);                  /* 2^10 */
  51         HASH_SIZE(2048, 2053);                  /* 2^11 */
  52         HASH_SIZE(4096, 4099);                  /* 2^12 */
  53         HASH_SIZE(8192, 8191);                  /* 2^13 */
  54         HASH_SIZE(16384, 16381);                /* 2^14 */
  55         HASH_SIZE(32768, 32771);                /* 2^15 */
  56         HASH_SIZE(65536, 65537);                /* 2^16 */
  57         HASH_SIZE(131072, 131071);              /* 2^17 */
  58         HASH_SIZE(262144, 262147);              /* 2^18 */
  59         HASH_SIZE(393216, 393209);              /* 2^18 + 2^18/2 */
  60         HASH_SIZE(524288, 524287);              /* 2^19 */
  61         HASH_SIZE(786432, 786431);              /* 2^19 + 2^19/2 */
  62         HASH_SIZE(1048576, 1048573);            /* 2^20 */
  63         HASH_SIZE(1572864, 1572869);            /* 2^20 + 2^20/2 */
  64         HASH_SIZE(2097152, 2097169);            /* 2^21 */
  65         HASH_SIZE(3145728, 3145721);            /* 2^21 + 2^21/2 */
  66         HASH_SIZE(4194304, 4194301);            /* 2^22 */
  67         HASH_SIZE(6291456, 6291449);            /* 2^22 + 2^22/2 */
  68         HASH_SIZE(8388608, 8388617);            /* 2^23 */
  69         HASH_SIZE(12582912, 12582917);          /* 2^23 + 2^23/2 */
  70         HASH_SIZE(16777216, 16777213);          /* 2^24 */
  71         HASH_SIZE(25165824, 25165813);          /* 2^24 + 2^24/2 */
  72         HASH_SIZE(33554432, 33554393);          /* 2^25 */
  73         HASH_SIZE(50331648, 50331653);          /* 2^25 + 2^25/2 */
  74         HASH_SIZE(67108864, 67108859);          /* 2^26 */
  75         HASH_SIZE(100663296, 100663291);        /* 2^26 + 2^26/2 */
  76         HASH_SIZE(134217728, 134217757);        /* 2^27 */
  77         HASH_SIZE(201326592, 201326611);        /* 2^27 + 2^27/2 */
  78         HASH_SIZE(268435456, 268435459);        /* 2^28 */
  79         HASH_SIZE(402653184, 402653189);        /* 2^28 + 2^28/2 */
  80         HASH_SIZE(536870912, 536870909);        /* 2^29 */
  81         HASH_SIZE(805306368, 805306357);        /* 2^29 + 2^29/2 */
  82         HASH_SIZE(1073741824, 1073741827);      /* 2^30 */
  83         return (1073741827);
  84 }
  85
  86 /*
  87  * __db_hashinit --
  88  *      Initialize a hash table that resides in shared memory.
  89  *
  90  * PUBLIC: void __db_hashinit __P((void *, u_int32_t));
  91  */
  92 void
  93 __db_hashinit(begin, nelements)
  94         void *begin;
  95         u_int32_t nelements;
  96 {
  97         u_int32_t i;
  98         SH_TAILQ_HEAD(hash_head) *headp;
  99
 100         headp = (struct hash_head *)begin;
 101
 102         for (i = 0; i < nelements; i++, headp++)
 103                 SH_TAILQ_INIT(headp);
 104 }