src/runtime/hopscotch.h

   1 /*
   2  * This software is part of the SBCL system. See the README file for
   3  * more information.
   4  *
   5  * This software is derived from the CMU CL system, which was
   6  * written at Carnegie Mellon University and released into the
   7  * public domain. The software is in the public domain and is
   8  * provided with absolutely no warranty. See the COPYING and CREDITS
   9  * files for more information.
  10  */
  11
  12 #ifndef _HOPSCOTCH_H_
  13 #define _HOPSCOTCH_H_
  14
  15 struct hopscotch_table {
  16     uword_t*   keys;
  17     unsigned*  hops;
  18     sword_t*   values;
  19     sword_t    (*get_value)(struct hopscotch_table*,int);
  20     uint32_t   (*hash)(uword_t);
  21     int        (*compare)(uword_t,uword_t);
  22     unsigned   mask;
  23     int  hop_range;
  24     int  count;
  25     int  threshold;  // max count before sizing up
  26     int  prev_size;  // in cells, as specified to hopscotch_create()
  27     int  mem_size;   // in bytes, for zero-filling when done using
  28     // Statistics
  29     struct { int n_seeks, n_probes; } hit, miss;
  30     char value_size; // number of bytes in a value: 0,1,2,4,8
  31     char hashfun;    // 1 or 2 to pick fast or slow
  32     char resized;    // set to 1 if sized up since last reset
  33     char rehashing;  // set to 1 during rehash
  34 };
  35
  36 void hopscotch_init();
  37 void hopscotch_create(struct hopscotch_table*,int,int,int,char);
  38 void hopscotch_destroy(struct hopscotch_table*);
  39 int hopscotch_insert(struct hopscotch_table*,uword_t,sword_t);
  40 int hopscotch_put(struct hopscotch_table*,uword_t,sword_t);
  41 sword_t hopscotch_get(struct hopscotch_table*,uword_t,sword_t);
  42 int hopscotch_containsp(struct hopscotch_table*,uword_t);
  43 void hopscotch_reset(struct hopscotch_table*);
  44 void hopscotch_log_stats(struct hopscotch_table*,char*);
  45
  46 uint32_t hopscotch_hmix(uword_t);
  47
  48 #define HOPSCOTCH_HASH_FUN_DEFAULT 1
  49 #define HOPSCOTCH_HASH_FUN_MIX 2
  50 #define HOPSCOTCH_STRING_HASH 3
  51 #define HOPSCOTCH_VECTOR_HASH 4
  52
  53 /* This confuses me every time I look at it, so here's an example-
  54  * Suppose (unrealistically) that a table has a hop range of 4,
  55  * and 16 logical bins. The largest logical bin index (= the table mask)
  56  * is 15, and there are 3 (not 4) more cells at the end.
  57  * So the largest physical index in which you can probe without
  58  * overrunning the key array is (mask + range - 1).
  59  * i.e. the neighborhood of logical cell index 15 is {15,16,17,18}.
  60  * The total count of physical key cells is (mask + 1) + (range - 1)
  61  * where (mask + 1) is the logical bin count.
  62  */
  63 #define hopscotch_max_key_index(table) ((table).mask+(table).hop_range-1)
  64
  65 #define for_each_hopscotch_key(indexvar, keyvar, tablevar) \
  66   for(indexvar=hopscotch_max_key_index(tablevar) ; indexvar >= 0 ; --indexvar) \
  67     if ((keyvar=tablevar.keys[indexvar])!=0)
  68
  69 #endif