silo/masstree/masstree_get.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_GET_HH
  17 #define MASSTREE_GET_HH 1
  18 #include "masstree_tcursor.hh"
  19 #include "masstree_key.hh"
  20 namespace Masstree {
  21
  22 template <typename P>
  23 bool unlocked_tcursor<P>::find_unlocked(threadinfo& ti)
  24 {
  25     int match;
  26     key_indexed_position kx;
  27     node_base<P>* root = const_cast<node_base<P>*>(root_);
  28
  29  retry:
  30     n_ = root->reach_leaf(ka_, v_, ti);
  31
  32  forward:
  33     if (v_.deleted())
  34         goto retry;
  35
  36     n_->prefetch();
  37     perm_ = n_->permutation();
  38     kx = leaf<P>::bound_type::lower(ka_, *this);
  39     if (kx.p >= 0) {
  40         lv_ = n_->lv_[kx.p];
  41         lv_.prefetch(n_->keylenx_[kx.p]);
  42         match = n_->ksuf_matches(kx.p, ka_);
  43     } else
  44         match = 0;
  45     if (n_->has_changed(v_)) {
  46         ti.mark(threadcounter(tc_stable_leaf_insert + n_->simple_has_split(v_)));
  47         n_ = n_->advance_to_key(ka_, v_, ti);
  48         goto forward;
  49     }
  50
  51     if (match < 0) {
  52         ka_.shift_by(-match);
  53         root = lv_.layer();
  54         goto retry;
  55     } else
  56         return match;
  57 }
  58
  59 template <typename P>
  60 inline bool basic_table<P>::get(Str key, value_type &value,
  61                                 threadinfo& ti) const
  62 {
  63     unlocked_tcursor<P> lp(*this, key);
  64     bool found = lp.find_unlocked(ti);
  65     if (found)
  66         value = lp.value();
  67     return found;
  68 }
  69
  70 template <typename P>
  71 bool tcursor<P>::find_locked(threadinfo& ti)
  72 {
  73     node_base<P>* root = const_cast<node_base<P>*>(root_);
  74     nodeversion_type v;
  75     permuter_type perm;
  76
  77  retry:
  78     n_ = root->reach_leaf(ka_, v, ti);
  79
  80  forward:
  81     if (v.deleted())
  82         goto retry;
  83
  84     n_->prefetch();
  85     perm = n_->permutation();
  86     fence();
  87     kx_ = leaf<P>::bound_type::lower(ka_, *n_);
  88     if (kx_.p >= 0) {
  89         leafvalue<P> lv = n_->lv_[kx_.p];
  90         lv.prefetch(n_->keylenx_[kx_.p]);
  91         state_ = n_->ksuf_matches(kx_.p, ka_);
  92         if (state_ < 0 && !n_->has_changed(v) && !lv.layer()->has_split()) {
  93             ka_.shift_by(-state_);
  94             root = lv.layer();
  95             goto retry;
  96         }
  97     } else
  98         state_ = 0;
  99
 100     n_->lock(v, ti.lock_fence(tc_leaf_lock));
 101     if (n_->has_changed(v) || n_->permutation() != perm) {
 102         ti.mark(threadcounter(tc_stable_leaf_insert + n_->simple_has_split(v)));
 103         n_->unlock();
 104         n_ = n_->advance_to_key(ka_, v, ti);
 105         goto forward;
 106     } else if (unlikely(state_ < 0)) {
 107         ka_.shift_by(-state_);
 108         n_->lv_[kx_.p] = root = n_->lv_[kx_.p].layer()->unsplit_ancestor();
 109         n_->unlock();
 110         goto retry;
 111     } else if (unlikely(n_->deleted_layer())) {
 112         ka_.unshift_all();
 113         root = const_cast<node_base<P>*>(root_);
 114         goto retry;
 115     }
 116     return state_;
 117 }
 118
 119 } // namespace Masstree
 120 #endif