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
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
16 #ifndef BTREE_LEAFLINK_HH
17 #define BTREE_LEAFLINK_HH 1
18 #include "compiler.hh"
20 /** @brief Operations to manage linked lists of B+tree leaves.
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 {};
28 // This is the normal version of btree_leaflink; it uses lock-free linked list
30 template <typename N> struct btree_leaflink<N, true> {
32 static inline N *mark(N *n) {
33 return reinterpret_cast<N *>(reinterpret_cast<uintptr_t>(n) + 1);
35 static inline bool is_marked(N *n) {
36 return reinterpret_cast<uintptr_t>(n) & 1;
38 template <typename SF>
39 static inline N *lock_next(N *n, SF spin_function) {
41 N *next = n->next_.ptr;
44 && bool_cmpxchg(&n->next_.ptr, next, mark(next))))
51 /** @brief Insert a new node @a nr at the right of node @a n.
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());
60 template <typename SF>
61 static void link_split(N *n, N *nr, SF spin_function) {
63 N *next = lock_next(n, spin_function);
71 /** @brief Unlink @a n from the list.
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());
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);
88 if (bool_cmpxchg(&prev->next_.ptr, n, mark(n)))
95 prev->next_.ptr = next;
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());
105 template <typename SF>
106 static void link_split(N *n, N *nr, SF) {
108 nr->next_.ptr = n->next_.ptr;
111 nr->next_.ptr->prev_ = nr;
113 static void unlink(N *n) {
114 unlink(n, do_nothing());
116 template <typename SF>
117 static void unlink(N *n, SF) {
119 n->next_.ptr->prev_ = n->prev_;
120 n->prev_->next_.ptr = n->next_.ptr;