silo/masstree_btree.h

   1 // -*- c-basic-offset: 2 -*-
   2 #pragma once
   3
   4 #include <assert.h>
   5 #include <malloc.h>
   6 #include <pthread.h>
   7 #include <stdint.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 #include <iostream>
  12 #include <string>
  13 #include <vector>
  14 #include <utility>
  15 #include <atomic>
  16
  17 #include "log2.hh"
  18 #include "ndb_type_traits.h"
  19 #include "varkey.h"
  20 #include "counter.h"
  21 #include "macros.h"
  22 #include "prefetch.h"
  23 #include "amd64.h"
  24 #include "rcu.h"
  25 #include "util.h"
  26 #include "small_vector.h"
  27 #include "ownership_checker.h"
  28
  29 #include "masstree/masstree_scan.hh"
  30 #include "masstree/masstree_insert.hh"
  31 #include "masstree/masstree_remove.hh"
  32 #include "masstree/masstree_print.hh"
  33 #include "masstree/timestamp.hh"
  34 #include "masstree/mtcounters.hh"
  35 #include "masstree/circular_int.hh"
  36
  37 class simple_threadinfo {
  38  public:
  39     simple_threadinfo()
  40         : ts_(0) { // XXX?
  41     }
  42     class rcu_callback {
  43     public:
  44       virtual void operator()(simple_threadinfo& ti) = 0;
  45     };
  46
  47  private:
  48     static inline void rcu_callback_function(void* p) {
  49       simple_threadinfo ti;
  50       static_cast<rcu_callback*>(p)->operator()(ti);
  51     }
  52
  53  public:
  54     // XXX Correct node timstamps are needed for recovery, but for no other
  55     // reason.
  56     kvtimestamp_t operation_timestamp() const {
  57       return 0;
  58     }
  59     kvtimestamp_t update_timestamp() const {
  60         return ts_;
  61     }
  62     kvtimestamp_t update_timestamp(kvtimestamp_t x) const {
  63         if (circular_int<kvtimestamp_t>::less_equal(ts_, x))
  64             // x might be a marker timestamp; ensure result is not
  65             ts_ = (x | 1) + 1;
  66         return ts_;
  67     }
  68     kvtimestamp_t update_timestamp(kvtimestamp_t x, kvtimestamp_t y) const {
  69         if (circular_int<kvtimestamp_t>::less(x, y))
  70             x = y;
  71         if (circular_int<kvtimestamp_t>::less_equal(ts_, x))
  72             // x might be a marker timestamp; ensure result is not
  73             ts_ = (x | 1) + 1;
  74         return ts_;
  75     }
  76     void increment_timestamp() {
  77         ts_ += 2;
  78     }
  79     void advance_timestamp(kvtimestamp_t x) {
  80         if (circular_int<kvtimestamp_t>::less(ts_, x))
  81             ts_ = x;
  82     }
  83
  84     // event counters
  85     void mark(threadcounter) {
  86     }
  87     void mark(threadcounter, int64_t) {
  88     }
  89     bool has_counter(threadcounter) const {
  90         return false;
  91     }
  92     uint64_t counter(threadcounter ci) const {
  93         return 0;
  94     }
  95
  96     /** @brief Return a function object that calls mark(ci); relax_fence().
  97      *
  98      * This function object can be used to count the number of relax_fence()s
  99      * executed. */
 100     relax_fence_function accounting_relax_fence(threadcounter) {
 101         return relax_fence_function();
 102     }
 103
 104     class accounting_relax_fence_function {
 105     public:
 106       template <typename V>
 107       void operator()(V) {
 108         relax_fence();
 109       }
 110     };
 111     /** @brief Return a function object that calls mark(ci); relax_fence().
 112      *
 113      * This function object can be used to count the number of relax_fence()s
 114      * executed. */
 115     accounting_relax_fence_function stable_fence() {
 116         return accounting_relax_fence_function();
 117     }
 118
 119     relax_fence_function lock_fence(threadcounter) {
 120         return relax_fence_function();
 121     }
 122
 123     // memory allocation
 124     void* allocate(size_t sz, memtag) {
 125         return rcu::s_instance.alloc(sz);
 126     }
 127     void deallocate(void* p, size_t sz, memtag) {
 128         // in C++ allocators, 'p' must be nonnull
 129         rcu::s_instance.dealloc(p, sz);
 130     }
 131     void deallocate_rcu(void *p, size_t sz, memtag) {
 132         assert(p);
 133         rcu::s_instance.dealloc_rcu(p, sz);
 134     }
 135
 136     void* pool_allocate(size_t sz, memtag) {
 137         int nl = (sz + CACHE_LINE_SIZE - 1) / CACHE_LINE_SIZE;
 138         return rcu::s_instance.alloc(nl * CACHE_LINE_SIZE);
 139     }
 140     void pool_deallocate(void* p, size_t sz, memtag) {
 141         int nl = (sz + CACHE_LINE_SIZE - 1) / CACHE_LINE_SIZE;
 142         rcu::s_instance.dealloc(p, nl * CACHE_LINE_SIZE);
 143     }
 144     void pool_deallocate_rcu(void* p, size_t sz, memtag) {
 145         assert(p);
 146         int nl = (sz + CACHE_LINE_SIZE - 1) / CACHE_LINE_SIZE;
 147         rcu::s_instance.dealloc_rcu(p, nl * CACHE_LINE_SIZE);
 148     }
 149
 150     // RCU
 151     void rcu_register(rcu_callback *cb) {
 152       scoped_rcu_base<false> guard;
 153       rcu::s_instance.free_with_fn(cb, rcu_callback_function);
 154     }
 155
 156   private:
 157     mutable kvtimestamp_t ts_;
 158 };
 159
 160 struct masstree_params : public Masstree::nodeparams<> {
 161   typedef uint8_t* value_type;
 162   typedef Masstree::value_print<value_type> value_print_type;
 163   typedef simple_threadinfo threadinfo_type;
 164   enum { RcuRespCaller = true };
 165 };
 166
 167 struct masstree_single_threaded_params : public masstree_params {
 168   static constexpr bool concurrent = false;
 169 };
 170
 171 template <typename P>
 172 class mbtree {
 173  public:
 174   typedef Masstree::node_base<P> node_base_type;
 175   typedef Masstree::internode<P> internode_type;
 176   typedef Masstree::leaf<P> leaf_type;
 177   typedef Masstree::leaf<P> node_type;
 178   typedef typename node_base_type::nodeversion_type nodeversion_type;
 179
 180   typedef varkey key_type;
 181   typedef lcdf::Str string_type;
 182   typedef uint64_t key_slice;
 183   typedef typename P::value_type value_type;
 184   typedef typename P::threadinfo_type threadinfo;
 185   typedef typename std::conditional<!P::RcuRespCaller,
 186       scoped_rcu_region,
 187       disabled_rcu_region>::type rcu_region;
 188
 189   // public to assist in testing
 190   static const unsigned int NKeysPerNode    = P::leaf_width;
 191   static const unsigned int NMinKeysPerNode = P::leaf_width / 2;
 192
 193   // XXX(stephentu): trying out a very opaque node API for now
 194   typedef node_type node_opaque_t;
 195   typedef std::pair< const node_opaque_t *, uint64_t > versioned_node_t;
 196   struct insert_info_t {
 197     const node_opaque_t* node;
 198     uint64_t old_version;
 199     uint64_t new_version;
 200   };
 201
 202   void invariant_checker() {} // stub for now
 203
 204 #ifdef BTREE_LOCK_OWNERSHIP_CHECKING
 205 public:
 206   static inline void
 207   NodeLockRegionBegin()
 208   {
 209     // XXX: implement me
 210     ALWAYS_ASSERT(false);
 211     //ownership_checker<mbtree<P>, node_base_type>::NodeLockRegionBegin();
 212   }
 213   static inline void
 214   AssertAllNodeLocksReleased()
 215   {
 216     // XXX: implement me
 217     ALWAYS_ASSERT(false);
 218     //ownership_checker<mbtree<P>, node_base_type>::AssertAllNodeLocksReleased();
 219   }
 220 private:
 221   static inline void
 222   AddNodeToLockRegion(const node_base_type *n)
 223   {
 224     // XXX: implement me
 225     ALWAYS_ASSERT(false);
 226     //ownership_checker<mbtree<P>, node_base_type>::AddNodeToLockRegion(n);
 227   }
 228 public:
 229 #endif
 230
 231   mbtree() {
 232     threadinfo ti;
 233     table_.initialize(ti);
 234   }
 235
 236   ~mbtree() {
 237     rcu_region guard;
 238     threadinfo ti;
 239     table_.destroy(ti);
 240   }
 241
 242   /**
 243    * NOT THREAD SAFE
 244    */
 245   inline void clear() {
 246     rcu_region guard;
 247     threadinfo ti;
 248     table_.destroy(ti);
 249     table_.initialize(ti);
 250   }
 251
 252   /** Note: invariant checking is not thread safe */
 253   inline void invariant_checker() const {
 254   }
 255
 256           /** NOTE: the public interface assumes that the caller has taken care
 257            * of setting up RCU */
 258
 259   inline bool search(const key_type &k, value_type &v,
 260                      versioned_node_t *search_info = nullptr) const;
 261
 262   /**
 263    * The low level callback interface is as follows:
 264    *
 265    * Consider a scan in the range [a, b):
 266    *   1) on_resp_node() is called at least once per node which
 267    *      has a responibility range that overlaps with the scan range
 268    *   2) invoke() is called per <k, v>-pair such that k is in [a, b)
 269    *
 270    * The order of calling on_resp_node() and invoke() is up to the implementation.
 271    */
 272   class low_level_search_range_callback {
 273   public:
 274     virtual ~low_level_search_range_callback() {}
 275
 276     /**
 277      * This node lies within the search range (at version v)
 278      */
 279     virtual void on_resp_node(const node_opaque_t *n, uint64_t version) = 0;
 280
 281     /**
 282      * This key/value pair was read from node n @ version
 283      */
 284     virtual bool invoke(const string_type &k, value_type v,
 285                         const node_opaque_t *n, uint64_t version) = 0;
 286   };
 287
 288   /**
 289    * For all keys in [lower, *upper), invoke callback in ascending order.
 290    * If upper is NULL, then there is no upper bound
 291    *
 292
 293    * This function by default provides a weakly consistent view of the b-tree. For
 294    * instance, consider the following tree, where n = 3 is the max number of
 295    * keys in a node:
 296    *
 297    *              [D|G]
 298    *             /  |  \
 299    *            /   |   \
 300    *           /    |    \
 301    *          /     |     \
 302    *   [A|B|C]<->[D|E|F]<->[G|H|I]
 303    *
 304    * Suppose we want to scan [A, inf), so we traverse to the leftmost leaf node
 305    * and start a left-to-right walk. Suppose we have emitted keys A, B, and C,
 306    * and we are now just about to scan the middle leaf node.  Now suppose
 307    * another thread concurrently does delete(A), followed by a delete(H).  Now
 308    * the scaning thread resumes and emits keys D, E, F, G, and I, omitting H
 309    * because H was deleted. This is an inconsistent view of the b-tree, since
 310    * the scanning thread has observed the deletion of H but did not observe the
 311    * deletion of A, but we know that delete(A) happens before delete(H).
 312    *
 313    * The weakly consistent guarantee provided is the following: all keys
 314    * which, at the time of invocation, are known to exist in the btree
 315    * will be discovered on a scan (provided the key falls within the scan's range),
 316    * and provided there are no concurrent modifications/removals of that key
 317    *
 318    * Note that scans within a single node are consistent
 319    *
 320    * XXX: add other modes which provide better consistency:
 321    * A) locking mode
 322    * B) optimistic validation mode
 323    *
 324    * the last string parameter is an optional string buffer to use:
 325    * if null, a stack allocated string will be used. if not null, must
 326    * ensure:
 327    *   A) buf->empty() at the beginning
 328    *   B) no concurrent mutation of string
 329    * note that string contents upon return are arbitrary
 330    */
 331   void
 332   search_range_call(const key_type &lower,
 333                     const key_type *upper,
 334                     low_level_search_range_callback &callback,
 335                     std::string *buf = nullptr) const;
 336
 337   // (lower, upper]
 338   void
 339   rsearch_range_call(const key_type &upper,
 340                      const key_type *lower,
 341                      low_level_search_range_callback &callback,
 342                      std::string *buf = nullptr) const;
 343
 344   class search_range_callback : public low_level_search_range_callback {
 345   public:
 346     virtual void
 347     on_resp_node(const node_opaque_t *n, uint64_t version)
 348     {
 349     }
 350
 351     virtual bool
 352     invoke(const string_type &k, value_type v,
 353            const node_opaque_t *n, uint64_t version)
 354     {
 355       return invoke(k, v);
 356     }
 357
 358     virtual bool invoke(const string_type &k, value_type v) = 0;
 359   };
 360
 361   /**
 362    * [lower, *upper)
 363    *
 364    * Callback is expected to implement bool operator()(key_slice k, value_type v),
 365    * where the callback returns true if it wants to keep going, false otherwise
 366    */
 367   template <typename F>
 368   inline void
 369   search_range(const key_type &lower,
 370                const key_type *upper,
 371                F& callback,
 372                std::string *buf = nullptr) const;
 373
 374   /**
 375    * (*lower, upper]
 376    *
 377    * Callback is expected to implement bool operator()(key_slice k, value_type v),
 378    * where the callback returns true if it wants to keep going, false otherwise
 379    */
 380   template <typename F>
 381   inline void
 382   rsearch_range(const key_type &upper,
 383                 const key_type *lower,
 384                 F& callback,
 385                 std::string *buf = nullptr) const;
 386
 387   /**
 388    * returns true if key k did not already exist, false otherwise
 389    * If k exists with a different mapping, still returns false
 390    *
 391    * If false and old_v is not NULL, then the overwritten value of v
 392    * is written into old_v
 393    */
 394   inline bool
 395   insert(const key_type &k, value_type v,
 396          value_type *old_v = NULL,
 397          insert_info_t *insert_info = NULL);
 398
 399   /**
 400    * Only puts k=>v if k does not exist in map. returns true
 401    * if k inserted, false otherwise (k exists already)
 402    */
 403   inline bool
 404   insert_if_absent(const key_type &k, value_type v,
 405                    insert_info_t *insert_info = NULL);
 406
 407   /**
 408    * return true if a value was removed, false otherwise.
 409    *
 410    * if true and old_v is not NULL, then the removed value of v
 411    * is written into old_v
 412    */
 413   inline bool
 414   remove(const key_type &k, value_type *old_v = NULL);
 415
 416   /**
 417    * The tree walk API is a bit strange, due to the optimistic nature of the
 418    * btree.
 419    *
 420    * The way it works is that, on_node_begin() is first called. In
 421    * on_node_begin(), a callback function should read (but not modify) the
 422    * values it is interested in, and save them.
 423    *
 424    * Then, either one of on_node_success() or on_node_failure() is called. If
 425    * on_node_success() is called, then the previous values read in
 426    * on_node_begin() are indeed valid.  If on_node_failure() is called, then
 427    * the previous values are not valid and should be discarded.
 428    */
 429   class tree_walk_callback {
 430   public:
 431     virtual ~tree_walk_callback() {}
 432     virtual void on_node_begin(const node_opaque_t *n) = 0;
 433     virtual void on_node_success() = 0;
 434     virtual void on_node_failure() = 0;
 435   };
 436
 437   void tree_walk(tree_walk_callback &callback) const;
 438
 439   /**
 440    * Is thread-safe, but not really designed to perform well with concurrent
 441    * modifications. also the value returned is not consistent given concurrent
 442    * modifications
 443    */
 444   inline size_t size() const;
 445
 446   static inline uint64_t
 447   ExtractVersionNumber(const node_opaque_t *n) {
 448     // XXX(stephentu): I think we must use stable_version() for
 449     // correctness, but I am not 100% sure. It's definitely correct to use it,
 450     // but maybe we can get away with unstable_version()?
 451     return n->full_version_value();
 452   }
 453
 454   // [value, has_suffix]
 455   static std::vector< std::pair<value_type, bool> >
 456   ExtractValues(const node_opaque_t *n);
 457
 458   /**
 459    * Not well defined if n is being concurrently modified, just for debugging
 460    */
 461   static std::string
 462   NodeStringify(const node_opaque_t *n);
 463
 464   void print();
 465
 466   static inline size_t InternalNodeSize() {
 467     return sizeof(internode_type);
 468   }
 469
 470   static inline size_t LeafNodeSize() {
 471     return sizeof(leaf_type);
 472   }
 473
 474  private:
 475   Masstree::basic_table<P> table_;
 476
 477   static leaf_type* leftmost_descend_layer(node_base_type* n);
 478   class size_walk_callback;
 479   template <bool Reverse> class search_range_scanner_base;
 480   template <bool Reverse> class low_level_search_range_scanner;
 481   template <typename F> class low_level_search_range_callback_wrapper;
 482 };
 483
 484 template <typename P>
 485 typename mbtree<P>::leaf_type *
 486 mbtree<P>::leftmost_descend_layer(node_base_type *n)
 487 {
 488   node_base_type *cur = n;
 489   while (true) {
 490     if (cur->isleaf())
 491       return static_cast<leaf_type*>(cur);
 492     internode_type *in = static_cast<internode_type*>(cur);
 493     nodeversion_type version = cur->stable();
 494     node_base_type *child = in->child_[0];
 495     if (unlikely(in->has_changed(version)))
 496       continue;
 497     cur = child;
 498   }
 499 }
 500
 501 template <typename P>
 502 void mbtree<P>::tree_walk(tree_walk_callback &callback) const {
 503   rcu_region guard;
 504   INVARIANT(rcu::s_instance.in_rcu_region());
 505   std::vector<node_base_type *> q, layers;
 506   q.push_back(table_.root());
 507   while (!q.empty()) {
 508     node_base_type *cur = q.back();
 509     q.pop_back();
 510     prefetch(cur);
 511     leaf_type *leaf = leftmost_descend_layer(cur);
 512     INVARIANT(leaf);
 513     while (leaf) {
 514       leaf->prefetch();
 515     process:
 516       auto version = leaf->stable();
 517       auto perm = leaf->permutation();
 518       for (int i = 0; i != perm.size(); ++i)
 519         if (leaf->is_layer(perm[i]))
 520           layers.push_back(leaf->lv_[perm[i]].layer());
 521       leaf_type *next = leaf->safe_next();
 522       callback.on_node_begin(leaf);
 523       if (unlikely(leaf->has_changed(version))) {
 524         callback.on_node_failure();
 525         layers.clear();
 526         goto process;
 527       }
 528       callback.on_node_success();
 529       leaf = next;
 530       if (!layers.empty()) {
 531         q.insert(q.end(), layers.begin(), layers.end());
 532         layers.clear();
 533       }
 534     }
 535   }
 536 }
 537
 538 template <typename P>
 539 class mbtree<P>::size_walk_callback : public tree_walk_callback {
 540  public:
 541   size_walk_callback()
 542     : size_(0) {
 543   }
 544   virtual void on_node_begin(const node_opaque_t *n);
 545   virtual void on_node_success();
 546   virtual void on_node_failure();
 547   size_t size_;
 548   int node_size_;
 549 };
 550
 551 template <typename P>
 552 void
 553 mbtree<P>::size_walk_callback::on_node_begin(const node_opaque_t *n)
 554 {
 555   auto perm = n->permutation();
 556   node_size_ = 0;
 557   for (int i = 0; i != perm.size(); ++i)
 558     if (!n->is_layer(perm[i]))
 559       ++node_size_;
 560 }
 561
 562 template <typename P>
 563 void
 564 mbtree<P>::size_walk_callback::on_node_success()
 565 {
 566   size_ += node_size_;
 567 }
 568
 569 template <typename P>
 570 void
 571 mbtree<P>::size_walk_callback::on_node_failure()
 572 {
 573 }
 574
 575 template <typename P>
 576 inline size_t mbtree<P>::size() const
 577 {
 578   size_walk_callback c;
 579   tree_walk(c);
 580   return c.size_;
 581 }
 582
 583 template <typename P>
 584 inline bool mbtree<P>::search(const key_type &k, value_type &v,
 585                               versioned_node_t *search_info) const
 586 {
 587   rcu_region guard;
 588   threadinfo ti;
 589   Masstree::unlocked_tcursor<P> lp(table_, k.data(), k.length());
 590   bool found = lp.find_unlocked(ti);
 591   if (found)
 592     v = lp.value();
 593   if (search_info)
 594     *search_info = versioned_node_t(lp.node(), lp.full_version_value());
 595   return found;
 596 }
 597
 598 template <typename P>
 599 inline bool mbtree<P>::insert(const key_type &k, value_type v,
 600                               value_type *old_v,
 601                               insert_info_t *insert_info)
 602 {
 603   rcu_region guard;
 604   threadinfo ti;
 605   Masstree::tcursor<P> lp(table_, k.data(), k.length());
 606   bool found = lp.find_insert(ti);
 607   if (!found)
 608     ti.advance_timestamp(lp.node_timestamp());
 609   if (found && old_v)
 610     *old_v = lp.value();
 611   lp.value() = v;
 612   if (insert_info) {
 613     insert_info->node = lp.node();
 614     insert_info->old_version = lp.previous_full_version_value();
 615     insert_info->new_version = lp.next_full_version_value(1);
 616   }
 617   lp.finish(1, ti);
 618   return !found;
 619 }
 620
 621 template <typename P>
 622 inline bool mbtree<P>::insert_if_absent(const key_type &k, value_type v,
 623                                         insert_info_t *insert_info)
 624 {
 625   rcu_region guard;
 626   threadinfo ti;
 627   Masstree::tcursor<P> lp(table_, k.data(), k.length());
 628   bool found = lp.find_insert(ti);
 629   if (!found) {
 630     ti.advance_timestamp(lp.node_timestamp());
 631     lp.value() = v;
 632     if (insert_info) {
 633       insert_info->node = lp.node();
 634       insert_info->old_version = lp.previous_full_version_value();
 635       insert_info->new_version = lp.next_full_version_value(1);
 636     }
 637   }
 638   lp.finish(!found, ti);
 639   return !found;
 640 }
 641
 642 /**
 643  * return true if a value was removed, false otherwise.
 644  *
 645  * if true and old_v is not NULL, then the removed value of v
 646  * is written into old_v
 647  */
 648 template <typename P>
 649 inline bool mbtree<P>::remove(const key_type &k, value_type *old_v)
 650 {
 651   rcu_region guard;
 652   threadinfo ti;
 653   Masstree::tcursor<P> lp(table_, k.data(), k.length());
 654   bool found = lp.find_locked(ti);
 655   if (found && old_v)
 656     *old_v = lp.value();
 657   lp.finish(found ? -1 : 0, ti);
 658   return found;
 659 }
 660
 661 template <typename P>
 662 template <bool Reverse>
 663 class mbtree<P>::search_range_scanner_base {
 664  public:
 665   search_range_scanner_base(const key_type* boundary)
 666     : boundary_(boundary), boundary_compar_(false) {
 667   }
 668   void check(const Masstree::scanstackelt<P>& iter,
 669              const Masstree::key<uint64_t>& key) {
 670     int min = std::min(boundary_->length(), key.prefix_length());
 671     int cmp = memcmp(boundary_->data(), key.full_string().data(), min);
 672     if (!Reverse) {
 673       if (cmp < 0 || (cmp == 0 && boundary_->length() <= key.prefix_length()))
 674         boundary_compar_ = true;
 675       else if (cmp == 0) {
 676         uint64_t last_ikey = iter.node()->ikey0_[iter.permutation()[iter.permutation().size() - 1]];
 677         boundary_compar_ = boundary_->slice_at(key.prefix_length()) <= last_ikey;
 678       }
 679     } else {
 680       if (cmp >= 0)
 681         boundary_compar_ = true;
 682     }
 683   }
 684  protected:
 685   const key_type* boundary_;
 686   bool boundary_compar_;
 687 };
 688
 689 template <typename P>
 690 template <bool Reverse>
 691 class mbtree<P>::low_level_search_range_scanner
 692   : public search_range_scanner_base<Reverse> {
 693  public:
 694   low_level_search_range_scanner(const key_type* boundary,
 695                                  low_level_search_range_callback& callback)
 696     : search_range_scanner_base<Reverse>(boundary), callback_(callback) {
 697   }
 698   void visit_leaf(const Masstree::scanstackelt<P>& iter,
 699                   const Masstree::key<uint64_t>& key, threadinfo&) {
 700     this->n_ = iter.node();
 701     this->v_ = iter.full_version_value();
 702     callback_.on_resp_node(this->n_, this->v_);
 703     if (this->boundary_)
 704       this->check(iter, key);
 705   }
 706   bool visit_value(const Masstree::key<uint64_t>& key,
 707                    value_type value, threadinfo&) {
 708     if (this->boundary_compar_) {
 709       lcdf::Str bs(this->boundary_->data(), this->boundary_->size());
 710       if ((!Reverse && bs <= key.full_string()) ||
 711           ( Reverse && bs >= key.full_string()))
 712         return false;
 713     }
 714     return callback_.invoke(key.full_string(), value, this->n_, this->v_);
 715   }
 716  private:
 717   Masstree::leaf<P>* n_;
 718   uint64_t v_;
 719   low_level_search_range_callback& callback_;
 720 };
 721
 722 template <typename P>
 723 template <typename F>
 724 class mbtree<P>::low_level_search_range_callback_wrapper :
 725   public mbtree<P>::low_level_search_range_callback {
 726 public:
 727   low_level_search_range_callback_wrapper(F& callback) : callback_(callback) {}
 728
 729   void on_resp_node(const node_opaque_t *n, uint64_t version) OVERRIDE {}
 730
 731   bool
 732   invoke(const string_type &k, value_type v,
 733          const node_opaque_t *n, uint64_t version) OVERRIDE
 734   {
 735     return callback_(k, v);
 736   }
 737
 738  private:
 739   F& callback_;
 740 };
 741
 742 template <typename P>
 743 inline void mbtree<P>::search_range_call(const key_type &lower,
 744                                          const key_type *upper,
 745                                          low_level_search_range_callback &callback,
 746                                          std::string*) const {
 747   low_level_search_range_scanner<false> scanner(upper, callback);
 748   threadinfo ti;
 749   table_.scan(lcdf::Str(lower.data(), lower.length()), true, scanner, ti);
 750 }
 751
 752 template <typename P>
 753 inline void mbtree<P>::rsearch_range_call(const key_type &upper,
 754                                           const key_type *lower,
 755                                           low_level_search_range_callback &callback,
 756                                           std::string*) const {
 757   low_level_search_range_scanner<true> scanner(lower, callback);
 758   threadinfo ti;
 759   table_.rscan(lcdf::Str(upper.data(), upper.length()), true, scanner, ti);
 760 }
 761
 762 template <typename P> template <typename F>
 763 inline void mbtree<P>::search_range(const key_type &lower,
 764                                     const key_type *upper,
 765                                     F& callback,
 766                                     std::string*) const {
 767   low_level_search_range_callback_wrapper<F> wrapper(callback);
 768   low_level_search_range_scanner<false> scanner(upper, wrapper);
 769   threadinfo ti;
 770   table_.scan(lcdf::Str(lower.data(), lower.length()), true, scanner, ti);
 771 }
 772
 773 template <typename P> template <typename F>
 774 inline void mbtree<P>::rsearch_range(const key_type &upper,
 775                                      const key_type *lower,
 776                                      F& callback,
 777                                      std::string*) const {
 778   low_level_search_range_callback_wrapper<F> wrapper(callback);
 779   low_level_search_range_scanner<true> scanner(lower, wrapper);
 780   threadinfo ti;
 781   table_.rscan(lcdf::Str(upper.data(), upper.length()), true, scanner, ti);
 782 }
 783
 784 template <typename P>
 785 std::string mbtree<P>::NodeStringify(const node_opaque_t *n)
 786 {
 787   std::ostringstream b;
 788   b << "node[v=" << n->version_value() << "]";
 789   return b.str();
 790 }
 791
 792 template <typename P>
 793 std::vector<std::pair<typename mbtree<P>::value_type, bool>>
 794 mbtree<P>::ExtractValues(const node_opaque_t *n)
 795 {
 796   std::vector< std::pair<value_type, bool> > ret;
 797   auto perm = n->permutation();
 798   for (int i = 0; i != perm.size(); ++i) {
 799     int keylenx = n->keylenx_[perm[i]];
 800     if (!n->keylenx_is_layer(keylenx))
 801       ret.emplace_back(n->lv_[perm[i]].value(), n->keylenx_has_ksuf(keylenx));
 802   }
 803   return ret;
 804 }
 805
 806 template <typename P>
 807 void mbtree<P>::print() {
 808   table_.print();
 809 }
 810
 811 typedef mbtree<masstree_params> concurrent_btree;
 812 typedef mbtree<masstree_single_threaded_params> single_threaded_btree;