btree_leaflink.hh

/* 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