silo/benchmarks/masstree/kvrandom.hh

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012 President and Fellows of Harvard College
   4  * Copyright (c) 2012 Massachusetts Institute of Technology
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, subject to the conditions
   9  * listed in the Masstree LICENSE file. These conditions include: you must
  10  * preserve this copyright notice, and you cannot mention the copyright
  11  * holders in advertising related to the Software without their permission.
  12  * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
  13  * notice is a summary of the Masstree LICENSE file; the license in that file is
  14  * legally binding.
  15  */
  16 #ifndef KVRANDOM_HH
  17 #define KVRANDOM_HH 1
  18 #include <inttypes.h>
  19 #include <stdlib.h>
  20
  21 // A simple LCG with parameters from Numerical Recipes.
  22 class kvrandom_lcg_nr_simple { public:
  23     enum { min_value = 0, max_value = 0xFFFFFFFFU };
  24     typedef uint32_t value_type;
  25     typedef uint32_t seed_type;
  26     kvrandom_lcg_nr_simple()
  27         : seed_(default_seed) {
  28     }
  29     explicit kvrandom_lcg_nr_simple(seed_type seed)
  30         : seed_(seed) {
  31     }
  32     void reset(seed_type seed) {
  33         seed_ = seed;
  34     }
  35     value_type next() {
  36         return (seed_ = seed_ * a + c);
  37     }
  38   private:
  39     uint32_t seed_;
  40     enum { default_seed = 819234718U, a = 1664525U, c = 1013904223U };
  41 };
  42
  43 // A combination version of the NR LCG that uses only its higher order
  44 // digits. (In the default NR LCG the lowest bits have less randomness; e.g.,
  45 // the low bit flips between 0 and 1 with every call.)
  46 class kvrandom_lcg_nr : public kvrandom_lcg_nr_simple { public:
  47     enum { min_value = 0, max_value = 0x7FFFFFFF };
  48     typedef int32_t value_type;
  49     kvrandom_lcg_nr(seed_type seed) : kvrandom_lcg_nr_simple(seed) {}
  50     value_type next() {
  51         uint32_t x0 = kvrandom_lcg_nr_simple::next(),
  52             x1 = kvrandom_lcg_nr_simple::next();
  53         return (x0 >> 15) | ((x1 & 0x7FFE) << 16);
  54     }
  55 };
  56
  57 // A random number generator taken from NR's ran4. Based on hashing.
  58 class kvrandom_psdes_nr { public:
  59     enum { min_value = 0, max_value = 0xFFFFFFFFU };
  60     typedef uint32_t value_type;
  61     typedef uint32_t seed_type;
  62     kvrandom_psdes_nr() {
  63         reset(1);
  64     }
  65     explicit kvrandom_psdes_nr(seed_type seed) {
  66         reset(seed);
  67     }
  68     void reset(seed_type seed) {
  69         seed_ = seed;
  70         next_ = 1;
  71     }
  72     value_type next() {
  73         uint32_t value = psdes(seed_, next_);
  74         ++next_;
  75         return value;
  76     }
  77     value_type operator[](uint32_t index) const {
  78         return psdes(seed_, index);
  79     }
  80   private:
  81     uint32_t seed_;
  82     uint32_t next_;
  83     enum { niter = 4 };
  84     static const uint32_t c1[niter], c2[niter];
  85     static uint32_t psdes(uint32_t lword, uint32_t irword);
  86 };
  87
  88 // a wrapper around random(), for backwards compatibility
  89 class kvrandom_random { public:
  90     kvrandom_random() {
  91     }
  92     void reset(uint32_t seed) {
  93         srandom(seed);
  94     }
  95     int32_t next() const {
  96         return random();
  97     }
  98 };
  99
 100 #endif