silo/masstree/masstree_tcursor.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_TCURSOR_HH
  17 #define MASSTREE_TCURSOR_HH 1
  18 #include "local_vector.hh"
  19 #include "masstree_key.hh"
  20 #include "masstree_struct.hh"
  21 namespace Masstree {
  22 template <typename P> struct gc_layer_rcu_callback;
  23
  24 template <typename P>
  25 class unlocked_tcursor {
  26   public:
  27     typedef typename P::value_type value_type;
  28     typedef key<typename P::ikey_type> key_type;
  29     typedef typename P::threadinfo_type threadinfo;
  30     typedef typename leaf<P>::nodeversion_type nodeversion_type;
  31     typedef typename nodeversion_type::value_type nodeversion_value_type;
  32     typedef typename leaf<P>::permuter_type permuter_type;
  33
  34     inline unlocked_tcursor(const basic_table<P>& table, Str str)
  35         : ka_(str), lv_(leafvalue<P>::make_empty()),
  36           root_(table.root()) {
  37     }
  38     inline unlocked_tcursor(basic_table<P>& table, Str str)
  39         : ka_(str), lv_(leafvalue<P>::make_empty()),
  40           root_(table.fix_root()) {
  41     }
  42     inline unlocked_tcursor(const basic_table<P>& table,
  43                             const char* s, int len)
  44         : ka_(s, len), lv_(leafvalue<P>::make_empty()),
  45           root_(table.root()) {
  46     }
  47     inline unlocked_tcursor(basic_table<P>& table,
  48                             const char* s, int len)
  49         : ka_(s, len), lv_(leafvalue<P>::make_empty()),
  50           root_(table.fix_root()) {
  51     }
  52     inline unlocked_tcursor(const basic_table<P>& table,
  53                             const unsigned char* s, int len)
  54         : ka_(reinterpret_cast<const char*>(s), len),
  55           lv_(leafvalue<P>::make_empty()), root_(table.root()) {
  56     }
  57     inline unlocked_tcursor(basic_table<P>& table,
  58                             const unsigned char* s, int len)
  59         : ka_(reinterpret_cast<const char*>(s), len),
  60           lv_(leafvalue<P>::make_empty()), root_(table.fix_root()) {
  61     }
  62
  63     bool find_unlocked(threadinfo& ti);
  64
  65     inline value_type value() const {
  66         return lv_.value();
  67     }
  68     inline leaf<P>* node() const {
  69         return n_;
  70     }
  71     inline permuter_type permutation() const {
  72         return perm_;
  73     }
  74     inline int compare_key(const key_type& a, int bp) const {
  75         return n_->compare_key(a, bp);
  76     }
  77     inline nodeversion_value_type full_version_value() const {
  78         static_assert(int(nodeversion_type::traits_type::top_stable_bits) >= int(leaf<P>::permuter_type::size_bits), "not enough bits to add size to version");
  79         return (v_.version_value() << leaf<P>::permuter_type::size_bits) + perm_.size();
  80     }
  81
  82   private:
  83     leaf<P>* n_;
  84     key_type ka_;
  85     typename leaf<P>::nodeversion_type v_;
  86     permuter_type perm_;
  87     leafvalue<P> lv_;
  88     const node_base<P>* root_;
  89 };
  90
  91 template <typename P>
  92 class tcursor {
  93   public:
  94     typedef node_base<P> node_type;
  95     typedef leaf<P> leaf_type;
  96     typedef internode<P> internode_type;
  97     typedef typename P::value_type value_type;
  98     typedef leafvalue<P> leafvalue_type;
  99     typedef typename leaf_type::permuter_type permuter_type;
 100     typedef typename P::ikey_type ikey_type;
 101     typedef key<ikey_type> key_type;
 102     typedef typename leaf<P>::nodeversion_type nodeversion_type;
 103     typedef typename nodeversion_type::value_type nodeversion_value_type;
 104     typedef typename P::threadinfo_type threadinfo;
 105     static constexpr int new_nodes_size = 1; // unless we make a new trie newnodes will have at most 1 item
 106     typedef local_vector<std::pair<leaf_type*, nodeversion_value_type>, new_nodes_size> new_nodes_type;
 107
 108     tcursor(basic_table<P>& table, Str str)
 109         : ka_(str), root_(table.fix_root()) {
 110     }
 111     tcursor(basic_table<P>& table, const char* s, int len)
 112         : ka_(s, len), root_(table.fix_root()) {
 113     }
 114     tcursor(basic_table<P>& table, const unsigned char* s, int len)
 115         : ka_(reinterpret_cast<const char*>(s), len), root_(table.fix_root()) {
 116     }
 117     tcursor(node_base<P>* root, const char* s, int len)
 118         : ka_(s, len), root_(root) {
 119     }
 120     tcursor(node_base<P>* root, const unsigned char* s, int len)
 121         : ka_(reinterpret_cast<const char*>(s), len), root_(root) {
 122     }
 123
 124     inline bool has_value() const {
 125         return kx_.p >= 0;
 126     }
 127     inline value_type &value() const {
 128         return n_->lv_[kx_.p].value();
 129     }
 130
 131     inline bool is_first_layer() const {
 132         return !ka_.is_shifted();
 133     }
 134
 135     inline leaf<P>* node() const {
 136         return n_;
 137     }
 138     inline kvtimestamp_t node_timestamp() const {
 139         return n_->node_ts_;
 140     }
 141     inline kvtimestamp_t &node_timestamp() {
 142         return n_->node_ts_;
 143     }
 144
 145     inline leaf_type *original_node() const {
 146         return original_n_;
 147     }
 148
 149     inline nodeversion_value_type original_version_value() const {
 150         return original_v_;
 151     }
 152
 153     inline nodeversion_value_type updated_version_value() const {
 154         return updated_v_;
 155     }
 156
 157     inline const new_nodes_type &new_nodes() const {
 158         return new_nodes_;
 159     }
 160
 161     inline bool find_locked(threadinfo& ti);
 162     inline bool find_insert(threadinfo& ti);
 163
 164     inline void finish(int answer, threadinfo& ti);
 165
 166     inline nodeversion_value_type previous_full_version_value() const;
 167     inline nodeversion_value_type next_full_version_value(int state) const;
 168
 169   private:
 170     leaf_type *n_;
 171     key_type ka_;
 172     key_indexed_position kx_;
 173     node_base<P>* root_;
 174     int state_;
 175
 176     leaf_type *original_n_;
 177     nodeversion_value_type original_v_;
 178     nodeversion_value_type updated_v_;
 179     new_nodes_type new_nodes_;
 180
 181     inline node_type* reset_retry() {
 182         ka_.unshift_all();
 183         return root_;
 184     }
 185
 186     bool make_new_layer(threadinfo& ti);
 187     bool make_split(threadinfo& ti);
 188     inline void finish_insert();
 189     inline bool finish_remove(threadinfo& ti);
 190
 191     static void collapse(internode_type* p, ikey_type ikey,
 192                          node_type* root, Str prefix, threadinfo& ti);
 193     /** Remove @a leaf from the Masstree rooted at @a rootp.
 194      * @param prefix String defining the path to the tree containing this leaf.
 195      *   If removing a leaf in layer 0, @a prefix is empty.
 196      *   If removing, for example, the node containing key "01234567ABCDEF" in the layer-1 tree
 197      *   rooted at "01234567", then @a prefix should equal "01234567". */
 198     static bool remove_leaf(leaf_type* leaf, node_type* root,
 199                             Str prefix, threadinfo& ti);
 200
 201     bool gc_layer(threadinfo& ti);
 202     friend struct gc_layer_rcu_callback<P>;
 203 };
 204
 205 template <typename P>
 206 inline typename tcursor<P>::nodeversion_value_type
 207 tcursor<P>::previous_full_version_value() const {
 208     static_assert(int(nodeversion_type::traits_type::top_stable_bits) >= int(leaf<P>::permuter_type::size_bits), "not enough bits to add size to version");
 209     return (n_->unlocked_version_value() << leaf<P>::permuter_type::size_bits) + n_->size();
 210 }
 211
 212 template <typename P>
 213 inline typename tcursor<P>::nodeversion_value_type
 214 tcursor<P>::next_full_version_value(int state) const {
 215     static_assert(int(nodeversion_type::traits_type::top_stable_bits) >= int(leaf<P>::permuter_type::size_bits), "not enough bits to add size to version");
 216     typename node_base<P>::nodeversion_type v(*n_);
 217     v.unlock();
 218     nodeversion_value_type result = (v.version_value() << leaf<P>::permuter_type::size_bits) + n_->size();
 219     if (state < 0 && (state_ & 1))
 220         return result - 1;
 221     else if (state > 0 && state_ == 2)
 222         return result + 1;
 223     else
 224         return result;
 225 }
 226
 227 } // namespace Masstree
 228 #endif