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_SCAN_HH
17 #define MASSTREE_SCAN_HH
18 #include "masstree_tcursor.hh"
19 #include "masstree_struct.hh"
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;
34 leaf<P>* node() const {
37 typename nodeversion_type::value_type full_version_value() const {
38 return (v_.version_value() << permuter_type::size_bits) + perm_.size();
43 permuter_type permutation() const {
46 int operator()(const key_type &k, const scanstackelt<P> &n, int p) {
47 return n.n_->compare_key(k, p);
57 enum { scan_emit, scan_find_next, scan_down, scan_up, scan_retry };
63 int find_initial(H& helper, key_type& ka, bool emit_equal,
64 leafvalue_type& entry, threadinfo& ti);
66 int find_retry(H& helper, key_type& ka, threadinfo& ti);
68 int find_next(H& helper, key_type& ka, leafvalue_type& entry);
71 if (unsigned(ki_) < unsigned(perm_.size()))
77 template <typename PX> friend class basic_table;
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);
84 template <typename K> bool is_duplicate(const K &k,
85 typename K::ikey_type ikey,
87 return k.compare(ikey, keylenx) >= 0;
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;
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);
100 int next(int ki) const {
103 template <typename N, typename K>
104 N *advance(const N *n, const K &) const {
105 return n->safe_next();
107 template <typename N, typename K>
108 typename N::nodeversion_type stable(const N *n, const K &) const {
111 template <typename K> void shift_clear(K &ka) const {
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) {
128 bool initial_ksuf_match(int ksuf_compare, bool emit_equal) const {
129 return ksuf_compare < 0 || (ksuf_compare == 0 && emit_equal);
131 template <typename K> bool is_duplicate(const K &k,
132 typename K::ikey_type ikey,
134 return k.compare(ikey, keylenx) <= 0 && !upper_bound_;
136 template <typename K, typename N> int lower(const K &k, const N *n) const {
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);
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);
146 return kx.i - (kx.p < 0);
148 int next(int ki) const {
152 upper_bound_ = false;
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);
160 template <typename N, typename K>
161 typename N::nodeversion_type stable(N *&n, const K &k) const {
163 typename N::nodeversion_type v = n->stable();
164 N *next = n->safe_next();
167 || (cmp = ::compare(k.ikey(), next->ikey_bound())) < 0
168 || (cmp == 0 && k.length() == 0))
173 template <typename K> void shift_clear(K &ka) const {
174 ka.shift_clear_reverse();
178 mutable bool upper_bound_;
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)
187 char suffixbuf[MASSTREE_MAXKEYLEN];
191 n_ = root_->reach_leaf(ka, v_, ti);
197 perm_ = n_->permutation();
199 ki_ = helper.lower_with_position(ka, this, kp);
201 keylenx = n_->keylenx_[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;
211 if (n_->has_changed(v_)) {
212 ti.mark(tc_leaf_retry);
213 n_ = n_->advance_to_key(ka, v_, ti);
218 if (n_->keylenx_is_layer(keylenx)) {
219 this[1].root_ = entry.layer();
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);
228 } else if (emit_equal)
230 // otherwise, this entry must be skipped
231 ki_ = helper.next(ki_);
234 return scan_find_next;
237 template <typename P> template <typename H>
238 int scanstackelt<P>::find_retry(H& helper, key_type& ka, threadinfo& ti)
241 n_ = root_->reach_leaf(ka, v_, ti);
246 perm_ = n_->permutation();
247 ki_ = helper.lower(ka, this);
248 return scan_find_next;
251 template <typename P> template <typename H>
252 int scanstackelt<P>::find_next(H &helper, key_type &ka, leafvalue_type &entry)
262 ikey_type ikey = n_->ikey0_[kp];
263 int keylenx = n_->keylenx_[kp];
264 int keylen = keylenx;
267 entry.prefetch(keylenx);
268 if (n_->keylenx_has_ksuf(keylenx))
269 keylen = ka.assign_store_suffix(n_->ksuf(kp));
271 if (n_->has_changed(v_))
273 else if (helper.is_duplicate(ka, ikey, keylenx)) {
274 ki_ = helper.next(ki_);
278 // We know we can emit the data collected above.
279 ka.assign_store_ikey(ikey);
281 if (n_->keylenx_is_layer(keylenx)) {
282 this[1].root_ = entry.layer();
285 ka.assign_store_length(keylen);
290 if (!n_->has_changed(v_)) {
291 n_ = helper.advance(n_, ka);
298 v_ = helper.stable(n_, ka);
299 perm_ = n_->permutation();
300 ki_ = helper.lower(ka, this);
301 return scan_find_next;
304 template <typename P> template <typename H, typename F>
305 int basic_table<P>::scan(H helper,
306 Str firstkey, bool emit_firstkey,
308 threadinfo& ti) const
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;
314 ikey_type x[(MASSTREE_MAXKEYLEN + sizeof(ikey_type) - 1)/sizeof(ikey_type)];
315 char s[MASSTREE_MAXKEYLEN];
317 masstree_precondition(firstkey.len <= (int) sizeof(keybuf));
318 memcpy(keybuf.s, firstkey.s, firstkey.len);
319 key_type ka(keybuf.s, firstkey.len);
321 typedef scanstackelt<param_type> mystack_type;
322 mystack_type stack[(MASSTREE_MAXKEYLEN + sizeof(ikey_type) - 1) / sizeof(ikey_type)];
324 stack[0].root_ = root_;
325 leafvalue_type entry = leafvalue_type::make_empty();
331 state = stack[stackpos].find_initial(helper, ka, emit_firstkey,
333 scanner.visit_leaf(stack[stackpos], ka, ti);
334 if (state != mystack_type::scan_down)
342 case mystack_type::scan_emit:
344 if (!scanner.visit_value(ka, entry.value(), ti))
346 stack[stackpos].ki_ = helper.next(stack[stackpos].ki_);
347 state = stack[stackpos].find_next(helper, ka, entry);
350 case mystack_type::scan_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);
357 case mystack_type::scan_up:
362 stack[stackpos].ki_ = helper.next(stack[stackpos].ki_);
363 } while (unlikely(ka.empty()));
366 case mystack_type::scan_down:
367 helper.shift_clear(ka);
371 case mystack_type::scan_retry:
373 state = stack[stackpos].find_retry(helper, ka, ti);
382 template <typename P> template <typename F>
383 int basic_table<P>::scan(Str firstkey, bool emit_firstkey,
385 threadinfo& ti) const
387 return scan(forward_scan_helper(), firstkey, emit_firstkey, scanner, ti);
390 template <typename P> template <typename F>
391 int basic_table<P>::rscan(Str firstkey, bool emit_firstkey,
393 threadinfo& ti) const
395 return scan(reverse_scan_helper(), firstkey, emit_firstkey, scanner, ti);
398 } // namespace Masstree