benchmark silo added

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

diff --git a/silo/masstree/btree_leaflink.hh b/silo/masstree/btree_leaflink.hh
new file mode 100644 (file)
index 0000000..d1bb060
--- /dev/null
+++ b/silo/masstree/btree_leaflink.hh
@@ -0,0 +1,124 @@
+/* Masstree
+ * Eddie Kohler, Yandong Mao, Robert Morris
+ * Copyright (c) 2012-2014 President and Fellows of Harvard College
+ * Copyright (c) 2012-2014 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 BTREE_LEAFLINK_HH
+#define BTREE_LEAFLINK_HH 1
+#include "compiler.hh"
+
+/** @brief Operations to manage linked lists of B+tree leaves.
+
+    N is the type of nodes. CONCURRENT is true to make operations
+    concurrency-safe (e.g. compare-and-swaps, fences), false to leave them
+    unsafe (only OK on single threaded code, but faster). */
+template <typename N, bool CONCURRENT = N::concurrent> struct btree_leaflink {};
+
+
+// This is the normal version of btree_leaflink; it uses lock-free linked list
+// operations.
+template <typename N> struct btree_leaflink<N, true> {
+  private:
+    static inline N *mark(N *n) {
+        return reinterpret_cast<N *>(reinterpret_cast<uintptr_t>(n) + 1);
+    }
+    static inline bool is_marked(N *n) {
+        return reinterpret_cast<uintptr_t>(n) & 1;
+    }
+    template <typename SF>
+    static inline N *lock_next(N *n, SF spin_function) {
+        while (1) {
+            N *next = n->next_.ptr;
+            if (!next
+                || (!is_marked(next)
+                    && bool_cmpxchg(&n->next_.ptr, next, mark(next))))
+                return next;
+            spin_function();
+        }
+    }
+
+  public:
+    /** @brief Insert a new node @a nr at the right of node @a n.
+        @pre @a n is locked.
+
+        Concurrency correctness: Ensures that all "next" pointers are always
+        valid, even if @a n's successor is deleted concurrently. */
+    static void link_split(N *n, N *nr) {
+        link_split(n, nr, relax_fence_function());
+    }
+    /** @overload */
+    template <typename SF>
+    static void link_split(N *n, N *nr, SF spin_function) {
+        nr->prev_ = n;
+        N *next = lock_next(n, spin_function);
+        nr->next_.ptr = next;
+        if (next)
+            next->prev_ = nr;
+        fence();
+        n->next_.ptr = nr;
+    }
+
+    /** @brief Unlink @a n from the list.
+        @pre @a n is locked.
+
+        Concurrency correctness: Works even in the presence of concurrent
+        splits and deletes. */
+    static void unlink(N *n) {
+        unlink(n, relax_fence_function());
+    }
+    /** @overload */
+    template <typename SF>
+    static void unlink(N *n, SF spin_function) {
+        // Assume node order A <-> N <-> B. Since n is locked, n cannot split;
+        // next node will always be B or one of its successors.
+        N *next = lock_next(n, spin_function);
+        N *prev;
+        while (1) {
+            prev = n->prev_;
+            if (bool_cmpxchg(&prev->next_.ptr, n, mark(n)))
+                break;
+            spin_function();
+        }
+        if (next)
+            next->prev_ = prev;
+        fence();
+        prev->next_.ptr = next;
+    }
+};
+
+
+// This is the single-threaded-only fast version of btree_leaflink.
+template <typename N> struct btree_leaflink<N, false> {
+    static void link_split(N *n, N *nr) {
+        link_split(n, nr, do_nothing());
+    }
+    template <typename SF>
+    static void link_split(N *n, N *nr, SF) {
+        nr->prev_ = n;
+        nr->next_.ptr = n->next_.ptr;
+        n->next_.ptr = nr;
+        if (nr->next_.ptr)
+            nr->next_.ptr->prev_ = nr;
+    }
+    static void unlink(N *n) {
+        unlink(n, do_nothing());
+    }
+    template <typename SF>
+    static void unlink(N *n, SF) {
+        if (n->next_.ptr)
+            n->next_.ptr->prev_ = n->prev_;
+        n->prev_->next_.ptr = n->next_.ptr;
+    }
+};
+
+#endif