benchmark silo added

[c11concurrency-benchmarks.git] / silo / masstree / kvrandom.hh

diff --git a/silo/masstree/kvrandom.hh b/silo/masstree/kvrandom.hh
new file mode 100644 (file)
index 0000000..5331e01
--- /dev/null
+++ b/silo/masstree/kvrandom.hh
@@ -0,0 +1,99 @@
+/* Masstree
+ * Eddie Kohler, Yandong Mao, Robert Morris
+ * Copyright (c) 2012-2013 President and Fellows of Harvard College
+ * Copyright (c) 2012-2013 Massachusetts Institute of Technology
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, subject to the conditions
+ * listed in the Masstree LICENSE file. These conditions include: you must
+ * preserve this copyright notice, and you cannot mention the copyright
+ * holders in advertising related to the Software without their permission.
+ * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
+ * notice is a summary of the Masstree LICENSE file; the license in that file
+ * is legally binding.
+ */
+#ifndef KVRANDOM_HH
+#define KVRANDOM_HH 1
+#include <inttypes.h>
+#include <stdlib.h>
+
+// A simple LCG with parameters from Numerical Recipes.
+class kvrandom_lcg_nr_simple { public:
+    enum { min_value = 0, max_value = 0xFFFFFFFFU };
+    typedef uint32_t value_type;
+    typedef uint32_t seed_type;
+    kvrandom_lcg_nr_simple()
+       : seed_(default_seed) {
+    }
+    explicit kvrandom_lcg_nr_simple(seed_type seed)
+       : seed_(seed) {
+    }
+    void reset(seed_type seed) {
+       seed_ = seed;
+    }
+    value_type next() {
+       return (seed_ = seed_ * a + c);
+    }
+  private:
+    uint32_t seed_;
+    enum { default_seed = 819234718U, a = 1664525U, c = 1013904223U };
+};
+
+// A combination version of the NR LCG that uses only its higher order
+// digits. (In the default NR LCG the lowest bits have less randomness; e.g.,
+// the low bit flips between 0 and 1 with every call.)
+class kvrandom_lcg_nr : public kvrandom_lcg_nr_simple { public:
+    enum { min_value = 0, max_value = 0x7FFFFFFF };
+    typedef int32_t value_type;
+    value_type next() {
+       uint32_t x0 = kvrandom_lcg_nr_simple::next(),
+           x1 = kvrandom_lcg_nr_simple::next();
+       return (x0 >> 15) | ((x1 & 0x7FFE) << 16);
+    }
+};
+
+// A random number generator taken from NR's ran4. Based on hashing.
+class kvrandom_psdes_nr { public:
+    enum { min_value = 0, max_value = 0xFFFFFFFFU };
+    typedef uint32_t value_type;
+    typedef uint32_t seed_type;
+    kvrandom_psdes_nr() {
+       reset(1);
+    }
+    explicit kvrandom_psdes_nr(seed_type seed) {
+       reset(seed);
+    }
+    void reset(seed_type seed) {
+       seed_ = seed;
+       next_ = 1;
+    }
+    value_type next() {
+       uint32_t value = psdes(seed_, next_);
+       ++next_;
+       return value;
+    }
+    value_type operator[](uint32_t index) const {
+       return psdes(seed_, index);
+    }
+  private:
+    uint32_t seed_;
+    uint32_t next_;
+    enum { niter = 4 };
+    static const uint32_t c1[niter], c2[niter];
+    static uint32_t psdes(uint32_t lword, uint32_t irword);
+};
+
+// a wrapper around random(), for backwards compatibility
+class kvrandom_random { public:
+    kvrandom_random() {
+    }
+    void reset(uint32_t seed) {
+       srandom(seed);
+    }
+    int32_t next() const {
+       return random();
+    }
+};
+
+#endif