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
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
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"
22 template <typename P> struct gc_layer_rcu_callback;
25 class unlocked_tcursor {
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;
34 inline unlocked_tcursor(const basic_table<P>& table, Str str)
35 : ka_(str), lv_(leafvalue<P>::make_empty()),
38 inline unlocked_tcursor(basic_table<P>& table, Str str)
39 : ka_(str), lv_(leafvalue<P>::make_empty()),
40 root_(table.fix_root()) {
42 inline unlocked_tcursor(const basic_table<P>& table,
43 const char* s, int len)
44 : ka_(s, len), lv_(leafvalue<P>::make_empty()),
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()) {
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()) {
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()) {
63 bool find_unlocked(threadinfo& ti);
65 inline value_type value() const {
68 inline leaf<P>* node() const {
71 inline permuter_type permutation() const {
74 inline int compare_key(const key_type& a, int bp) const {
75 return n_->compare_key(a, bp);
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();
85 typename leaf<P>::nodeversion_type v_;
88 const node_base<P>* root_;
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;
108 tcursor(basic_table<P>& table, Str str)
109 : ka_(str), root_(table.fix_root()) {
111 tcursor(basic_table<P>& table, const char* s, int len)
112 : ka_(s, len), root_(table.fix_root()) {
114 tcursor(basic_table<P>& table, const unsigned char* s, int len)
115 : ka_(reinterpret_cast<const char*>(s), len), root_(table.fix_root()) {
117 tcursor(node_base<P>* root, const char* s, int len)
118 : ka_(s, len), root_(root) {
120 tcursor(node_base<P>* root, const unsigned char* s, int len)
121 : ka_(reinterpret_cast<const char*>(s), len), root_(root) {
124 inline bool has_value() const {
127 inline value_type &value() const {
128 return n_->lv_[kx_.p].value();
131 inline bool is_first_layer() const {
132 return !ka_.is_shifted();
135 inline leaf<P>* node() const {
138 inline kvtimestamp_t node_timestamp() const {
141 inline kvtimestamp_t &node_timestamp() {
145 inline leaf_type *original_node() const {
149 inline nodeversion_value_type original_version_value() const {
153 inline nodeversion_value_type updated_version_value() const {
157 inline const new_nodes_type &new_nodes() const {
161 inline bool find_locked(threadinfo& ti);
162 inline bool find_insert(threadinfo& ti);
164 inline void finish(int answer, threadinfo& ti);
166 inline nodeversion_value_type previous_full_version_value() const;
167 inline nodeversion_value_type next_full_version_value(int state) const;
172 key_indexed_position kx_;
176 leaf_type *original_n_;
177 nodeversion_value_type original_v_;
178 nodeversion_value_type updated_v_;
179 new_nodes_type new_nodes_;
181 inline node_type* reset_retry() {
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);
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);
201 bool gc_layer(threadinfo& ti);
202 friend struct gc_layer_rcu_callback<P>;
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();
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_);
218 nodeversion_value_type result = (v.version_value() << leaf<P>::permuter_type::size_bits) + n_->size();
219 if (state < 0 && (state_ & 1))
221 else if (state > 0 && state_ == 2)
227 } // namespace Masstree