silo/masstree/masstree_scan.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 MASSTREE_SCAN_HH
  17 #define MASSTREE_SCAN_HH
  18 #include "masstree_tcursor.hh"
  19 #include "masstree_struct.hh"
  20 namespace Masstree {
  21
  22 template <typename P>
  23 class scanstackelt {
  24   public:
  25     typedef leaf<P> leaf_type;
  26     typedef typename leaf_type::leafvalue_type leafvalue_type;
  27     typedef typename leaf_type::bound_type bound_type;
  28     typedef typename P::ikey_type ikey_type;
  29     typedef key<ikey_type> key_type;
  30     typedef typename leaf_type::permuter_type permuter_type;
  31     typedef typename P::threadinfo_type threadinfo;
  32     typedef typename node_base<P>::nodeversion_type nodeversion_type;
  33
  34     leaf<P>* node() const {
  35         return n_;
  36     }
  37     typename nodeversion_type::value_type full_version_value() const {
  38         return (v_.version_value() << permuter_type::size_bits) + perm_.size();
  39     }
  40     int size() const {
  41         return perm_.size();
  42     }
  43     permuter_type permutation() const {
  44         return perm_;
  45     }
  46     int operator()(const key_type &k, const scanstackelt<P> &n, int p) {
  47         return n.n_->compare_key(k, p);
  48     }
  49
  50   private:
  51     node_base<P> *root_;
  52     leaf<P> *n_;
  53     nodeversion_type v_;
  54     permuter_type perm_;
  55     int ki_;
  56
  57     enum { scan_emit, scan_find_next, scan_down, scan_up, scan_retry };
  58
  59     scanstackelt() {
  60     }
  61
  62     template <typename H>
  63     int find_initial(H& helper, key_type& ka, bool emit_equal,
  64                      leafvalue_type& entry, threadinfo& ti);
  65     template <typename H>
  66     int find_retry(H& helper, key_type& ka, threadinfo& ti);
  67     template <typename H>
  68     int find_next(H& helper, key_type& ka, leafvalue_type& entry);
  69
  70     int kp() const {
  71         if (unsigned(ki_) < unsigned(perm_.size()))
  72             return perm_[ki_];
  73         else
  74             return -1;
  75     }
  76
  77     template <typename PX> friend class basic_table;
  78 };
  79
  80 struct forward_scan_helper {
  81     bool initial_ksuf_match(int ksuf_compare, bool emit_equal) const {
  82         return ksuf_compare > 0 || (ksuf_compare == 0 && emit_equal);
  83     }
  84     template <typename K> bool is_duplicate(const K &k,
  85                                             typename K::ikey_type ikey,
  86                                             int keylenx) const {
  87         return k.compare(ikey, keylenx) >= 0;
  88     }
  89     template <typename K, typename N> int lower(const K &k, const N *n) const {
  90         return N::bound_type::lower_by(k, *n, *n).i;
  91     }
  92     template <typename K, typename N>
  93     int lower_with_position(const K &k, const N *n, int &kp) const {
  94         key_indexed_position kx = N::bound_type::lower_by(k, *n, *n);
  95         kp = kx.p;
  96         return kx.i;
  97     }
  98     void found() const {
  99     }
 100     int next(int ki) const {
 101         return ki + 1;
 102     }
 103     template <typename N, typename K>
 104     N *advance(const N *n, const K &) const {
 105         return n->safe_next();
 106     }
 107     template <typename N, typename K>
 108     typename N::nodeversion_type stable(const N *n, const K &) const {
 109         return n->stable();
 110     }
 111     template <typename K> void shift_clear(K &ka) const {
 112         ka.shift_clear();
 113     }
 114 };
 115
 116 struct reverse_scan_helper {
 117     // We run ki backwards, referring to perm.size() each time through,
 118     // because inserting elements into a node need not bump its version.
 119     // Therefore, if we decremented ki, starting from a node's original
 120     // size(), we might miss some concurrently inserted keys!
 121     // Also, a node's size might change DURING a lower_bound operation.
 122     // The "backwards" ki must be calculated using the size taken by the
 123     // lower_bound, NOT some later size() (which might be bigger or smaller).
 124     // The helper type reverse_scan_node allows this.
 125     reverse_scan_helper()
 126         : upper_bound_(false) {
 127     }
 128     bool initial_ksuf_match(int ksuf_compare, bool emit_equal) const {
 129         return ksuf_compare < 0 || (ksuf_compare == 0 && emit_equal);
 130     }
 131     template <typename K> bool is_duplicate(const K &k,
 132                                             typename K::ikey_type ikey,
 133                                             int keylenx) const {
 134         return k.compare(ikey, keylenx) <= 0 && !upper_bound_;
 135     }
 136     template <typename K, typename N> int lower(const K &k, const N *n) const {
 137         if (upper_bound_)
 138             return n->size() - 1;
 139         key_indexed_position kx = N::bound_type::lower_by(k, *n, *n);
 140         return kx.i - (kx.p < 0);
 141     }
 142     template <typename K, typename N>
 143     int lower_with_position(const K &k, const N *n, int &kp) const {
 144         key_indexed_position kx = N::bound_type::lower_by(k, *n, *n);
 145         kp = kx.p;
 146         return kx.i - (kx.p < 0);
 147     }
 148     int next(int ki) const {
 149         return ki - 1;
 150     }
 151     void found() const {
 152         upper_bound_ = false;
 153     }
 154     template <typename N, typename K>
 155     N *advance(const N *n, K &k) const {
 156         k.assign_store_ikey(n->ikey_bound());
 157         k.assign_store_length(0);
 158         return n->prev_;
 159     }
 160     template <typename N, typename K>
 161     typename N::nodeversion_type stable(N *&n, const K &k) const {
 162         while (1) {
 163             typename N::nodeversion_type v = n->stable();
 164             N *next = n->safe_next();
 165             int cmp;
 166             if (!next
 167                 || (cmp = ::compare(k.ikey(), next->ikey_bound())) < 0
 168                 || (cmp == 0 && k.length() == 0))
 169                 return v;
 170             n = next;
 171         }
 172     }
 173     template <typename K> void shift_clear(K &ka) const {
 174         ka.shift_clear_reverse();
 175         upper_bound_ = true;
 176     }
 177   private:
 178     mutable bool upper_bound_;
 179 };
 180
 181
 182 template <typename P> template <typename H>
 183 int scanstackelt<P>::find_initial(H& helper, key_type& ka, bool emit_equal,
 184                                   leafvalue_type& entry, threadinfo& ti)
 185 {
 186     int kp, keylenx = 0;
 187     char suffixbuf[MASSTREE_MAXKEYLEN];
 188     Str suffix;
 189
 190  retry_root:
 191     n_ = root_->reach_leaf(ka, v_, ti);
 192
 193  retry_node:
 194     if (v_.deleted())
 195         goto retry_root;
 196     n_->prefetch();
 197     perm_ = n_->permutation();
 198
 199     ki_ = helper.lower_with_position(ka, this, kp);
 200     if (kp >= 0) {
 201         keylenx = n_->keylenx_[kp];
 202         fence();
 203         entry = n_->lv_[kp];
 204         entry.prefetch(keylenx);
 205         if (n_->keylenx_has_ksuf(keylenx)) {
 206             suffix = n_->ksuf(kp);
 207             memcpy(suffixbuf, suffix.s, suffix.len);
 208             suffix.s = suffixbuf;
 209         }
 210     }
 211     if (n_->has_changed(v_)) {
 212         ti.mark(tc_leaf_retry);
 213         n_ = n_->advance_to_key(ka, v_, ti);
 214         goto retry_node;
 215     }
 216
 217     if (kp >= 0) {
 218         if (n_->keylenx_is_layer(keylenx)) {
 219             this[1].root_ = entry.layer();
 220             return scan_down;
 221         } else if (n_->keylenx_has_ksuf(keylenx)) {
 222             int ksuf_compare = suffix.compare(ka.suffix());
 223             if (helper.initial_ksuf_match(ksuf_compare, emit_equal)) {
 224                 int keylen = ka.assign_store_suffix(suffix);
 225                 ka.assign_store_length(keylen);
 226                 return scan_emit;
 227             }
 228         } else if (emit_equal)
 229             return scan_emit;
 230         // otherwise, this entry must be skipped
 231         ki_ = helper.next(ki_);
 232     }
 233
 234     return scan_find_next;
 235 }
 236
 237 template <typename P> template <typename H>
 238 int scanstackelt<P>::find_retry(H& helper, key_type& ka, threadinfo& ti)
 239 {
 240  retry:
 241     n_ = root_->reach_leaf(ka, v_, ti);
 242     if (v_.deleted())
 243         goto retry;
 244
 245     n_->prefetch();
 246     perm_ = n_->permutation();
 247     ki_ = helper.lower(ka, this);
 248     return scan_find_next;
 249 }
 250
 251 template <typename P> template <typename H>
 252 int scanstackelt<P>::find_next(H &helper, key_type &ka, leafvalue_type &entry)
 253 {
 254     int kp;
 255
 256     if (v_.deleted())
 257         return scan_retry;
 258
 259  retry_entry:
 260     kp = this->kp();
 261     if (kp >= 0) {
 262         ikey_type ikey = n_->ikey0_[kp];
 263         int keylenx = n_->keylenx_[kp];
 264         int keylen = keylenx;
 265         fence();
 266         entry = n_->lv_[kp];
 267         entry.prefetch(keylenx);
 268         if (n_->keylenx_has_ksuf(keylenx))
 269             keylen = ka.assign_store_suffix(n_->ksuf(kp));
 270
 271         if (n_->has_changed(v_))
 272             goto changed;
 273         else if (helper.is_duplicate(ka, ikey, keylenx)) {
 274             ki_ = helper.next(ki_);
 275             goto retry_entry;
 276         }
 277
 278         // We know we can emit the data collected above.
 279         ka.assign_store_ikey(ikey);
 280         helper.found();
 281         if (n_->keylenx_is_layer(keylenx)) {
 282             this[1].root_ = entry.layer();
 283             return scan_down;
 284         } else {
 285             ka.assign_store_length(keylen);
 286             return scan_emit;
 287         }
 288     }
 289
 290     if (!n_->has_changed(v_)) {
 291         n_ = helper.advance(n_, ka);
 292         if (!n_)
 293             return scan_up;
 294         n_->prefetch();
 295     }
 296
 297  changed:
 298     v_ = helper.stable(n_, ka);
 299     perm_ = n_->permutation();
 300     ki_ = helper.lower(ka, this);
 301     return scan_find_next;
 302 }
 303
 304 template <typename P> template <typename H, typename F>
 305 int basic_table<P>::scan(H helper,
 306                          Str firstkey, bool emit_firstkey,
 307                          F& scanner,
 308                          threadinfo& ti) const
 309 {
 310     typedef typename P::ikey_type ikey_type;
 311     typedef typename node_type::key_type key_type;
 312     typedef typename node_type::leaf_type::leafvalue_type leafvalue_type;
 313     union {
 314         ikey_type x[(MASSTREE_MAXKEYLEN + sizeof(ikey_type) - 1)/sizeof(ikey_type)];
 315         char s[MASSTREE_MAXKEYLEN];
 316     } keybuf;
 317     masstree_precondition(firstkey.len <= (int) sizeof(keybuf));
 318     memcpy(keybuf.s, firstkey.s, firstkey.len);
 319     key_type ka(keybuf.s, firstkey.len);
 320
 321     typedef scanstackelt<param_type> mystack_type;
 322     mystack_type stack[(MASSTREE_MAXKEYLEN + sizeof(ikey_type) - 1) / sizeof(ikey_type)];
 323     int stackpos = 0;
 324     stack[0].root_ = root_;
 325     leafvalue_type entry = leafvalue_type::make_empty();
 326
 327     int scancount = 0;
 328     int state;
 329
 330     while (1) {
 331         state = stack[stackpos].find_initial(helper, ka, emit_firstkey,
 332                                              entry, ti);
 333         scanner.visit_leaf(stack[stackpos], ka, ti);
 334         if (state != mystack_type::scan_down)
 335             break;
 336         ka.shift();
 337         ++stackpos;
 338     }
 339
 340     while (1) {
 341         switch (state) {
 342         case mystack_type::scan_emit:
 343             ++scancount;
 344             if (!scanner.visit_value(ka, entry.value(), ti))
 345                 goto done;
 346             stack[stackpos].ki_ = helper.next(stack[stackpos].ki_);
 347             state = stack[stackpos].find_next(helper, ka, entry);
 348             break;
 349
 350         case mystack_type::scan_find_next:
 351         find_next:
 352             state = stack[stackpos].find_next(helper, ka, entry);
 353             if (state != mystack_type::scan_up)
 354                 scanner.visit_leaf(stack[stackpos], ka, ti);
 355             break;
 356
 357         case mystack_type::scan_up:
 358             do {
 359                 if (--stackpos < 0)
 360                     goto done;
 361                 ka.unshift();
 362                 stack[stackpos].ki_ = helper.next(stack[stackpos].ki_);
 363             } while (unlikely(ka.empty()));
 364             goto find_next;
 365
 366         case mystack_type::scan_down:
 367             helper.shift_clear(ka);
 368             ++stackpos;
 369             goto retry;
 370
 371         case mystack_type::scan_retry:
 372         retry:
 373             state = stack[stackpos].find_retry(helper, ka, ti);
 374             break;
 375         }
 376     }
 377
 378  done:
 379     return scancount;
 380 }
 381
 382 template <typename P> template <typename F>
 383 int basic_table<P>::scan(Str firstkey, bool emit_firstkey,
 384                          F& scanner,
 385                          threadinfo& ti) const
 386 {
 387     return scan(forward_scan_helper(), firstkey, emit_firstkey, scanner, ti);
 388 }
 389
 390 template <typename P> template <typename F>
 391 int basic_table<P>::rscan(Str firstkey, bool emit_firstkey,
 392                           F& scanner,
 393                           threadinfo& ti) const
 394 {
 395     return scan(reverse_scan_helper(), firstkey, emit_firstkey, scanner, ti);
 396 }
 397
 398 } // namespace Masstree
 399 #endif