silo/masstree/btree_leaflink.hh

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012-2014 President and Fellows of Harvard College
   4  * Copyright (c) 2012-2014 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
  14  * is legally binding.
  15  */
  16 #ifndef BTREE_LEAFLINK_HH
  17 #define BTREE_LEAFLINK_HH 1
  18 #include "compiler.hh"
  19
  20 /** @brief Operations to manage linked lists of B+tree leaves.
  21
  22     N is the type of nodes. CONCURRENT is true to make operations
  23     concurrency-safe (e.g. compare-and-swaps, fences), false to leave them
  24     unsafe (only OK on single threaded code, but faster). */
  25 template <typename N, bool CONCURRENT = N::concurrent> struct btree_leaflink {};
  26
  27
  28 // This is the normal version of btree_leaflink; it uses lock-free linked list
  29 // operations.
  30 template <typename N> struct btree_leaflink<N, true> {
  31   private:
  32     static inline N *mark(N *n) {
  33         return reinterpret_cast<N *>(reinterpret_cast<uintptr_t>(n) + 1);
  34     }
  35     static inline bool is_marked(N *n) {
  36         return reinterpret_cast<uintptr_t>(n) & 1;
  37     }
  38     template <typename SF>
  39     static inline N *lock_next(N *n, SF spin_function) {
  40         while (1) {
  41             N *next = n->next_.ptr;
  42             if (!next
  43                 || (!is_marked(next)
  44                     && bool_cmpxchg(&n->next_.ptr, next, mark(next))))
  45                 return next;
  46             spin_function();
  47         }
  48     }
  49
  50   public:
  51     /** @brief Insert a new node @a nr at the right of node @a n.
  52         @pre @a n is locked.
  53
  54         Concurrency correctness: Ensures that all "next" pointers are always
  55         valid, even if @a n's successor is deleted concurrently. */
  56     static void link_split(N *n, N *nr) {
  57         link_split(n, nr, relax_fence_function());
  58     }
  59     /** @overload */
  60     template <typename SF>
  61     static void link_split(N *n, N *nr, SF spin_function) {
  62         nr->prev_ = n;
  63         N *next = lock_next(n, spin_function);
  64         nr->next_.ptr = next;
  65         if (next)
  66             next->prev_ = nr;
  67         fence();
  68         n->next_.ptr = nr;
  69     }
  70
  71     /** @brief Unlink @a n from the list.
  72         @pre @a n is locked.
  73
  74         Concurrency correctness: Works even in the presence of concurrent
  75         splits and deletes. */
  76     static void unlink(N *n) {
  77         unlink(n, relax_fence_function());
  78     }
  79     /** @overload */
  80     template <typename SF>
  81     static void unlink(N *n, SF spin_function) {
  82         // Assume node order A <-> N <-> B. Since n is locked, n cannot split;
  83         // next node will always be B or one of its successors.
  84         N *next = lock_next(n, spin_function);
  85         N *prev;
  86         while (1) {
  87             prev = n->prev_;
  88             if (bool_cmpxchg(&prev->next_.ptr, n, mark(n)))
  89                 break;
  90             spin_function();
  91         }
  92         if (next)
  93             next->prev_ = prev;
  94         fence();
  95         prev->next_.ptr = next;
  96     }
  97 };
  98
  99
 100 // This is the single-threaded-only fast version of btree_leaflink.
 101 template <typename N> struct btree_leaflink<N, false> {
 102     static void link_split(N *n, N *nr) {
 103         link_split(n, nr, do_nothing());
 104     }
 105     template <typename SF>
 106     static void link_split(N *n, N *nr, SF) {
 107         nr->prev_ = n;
 108         nr->next_.ptr = n->next_.ptr;
 109         n->next_.ptr = nr;
 110         if (nr->next_.ptr)
 111             nr->next_.ptr->prev_ = nr;
 112     }
 113     static void unlink(N *n) {
 114         unlink(n, do_nothing());
 115     }
 116     template <typename SF>
 117     static void unlink(N *n, SF) {
 118         if (n->next_.ptr)
 119             n->next_.ptr->prev_ = n->prev_;
 120         n->prev_->next_.ptr = n->next_.ptr;
 121     }
 122 };
 123
 124 #endif