forked from kohler/masstree-beta
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmasstree_traverse.hh
145 lines (134 loc) · 4.24 KB
/
masstree_traverse.hh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/* Masstree
* Eddie Kohler, Yandong Mao, Robert Morris
* Copyright (c) 2012-2013 President and Fellows of Harvard College
* Copyright (c) 2012-2013 Massachusetts Institute of Technology
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, subject to the conditions
* listed in the Masstree LICENSE file. These conditions include: you must
* preserve this copyright notice, and you cannot mention the copyright
* holders in advertising related to the Software without their permission.
* The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
* notice is a summary of the Masstree LICENSE file; the license in that file
* is legally binding.
*/
#ifndef MASSTREE_TRAVERSE_HH
#define MASSTREE_TRAVERSE_HH 1
#include "masstree_struct.hh"
namespace Masstree {
template <typename P>
static inline int stable_last_key_compare(const typename node_base<P>::key_type &ka,
const internode<P> &n,
typename internode<P>::nodeversion_type v,
threadinfo *ti)
{
while (1) {
int cmp = key_compare(ka, n, n.size() - 1);
if (likely(!n.has_changed(v)))
return cmp;
v = n.stable_annotated(ti->stable_fence());
}
}
template <typename P>
static inline int stable_last_key_compare(const typename node_base<P>::key_type &ka,
const leaf<P> &n,
typename leaf<P>::nodeversion_type v,
threadinfo *ti)
{
while (1) {
typename leaf<P>::permuter_type perm(n.permutation_);
int p = perm[perm.size() - 1];
int cmp = key_compare(ka, n, p);
if (likely(!n.has_changed(v)))
return cmp;
v = n.stable_annotated(ti->stable_fence());
}
}
template <typename P>
inline leaf<P> *reach_leaf(const node_base<P> *root,
const typename node_base<P>::key_type &ka,
threadinfo *ti,
typename node_base<P>::nodeversion_type &version)
{
const node_base<P> *n[2];
typename node_base<P>::nodeversion_type v[2];
bool sense;
// Get a non-stale root.
// Detect staleness by checking whether n has ever split.
// The true root has never split.
retry:
sense = false;
n[sense] = root;
while (1) {
v[sense] = n[sense]->stable_annotated(ti->stable_fence());
if (!v[sense].has_split())
break;
ti->mark(tc_root_retry);
n[sense] = n[sense]->unsplit_ancestor();
}
// Loop over internal nodes.
while (!v[sense].isleaf()) {
const internode<P> *in = static_cast<const internode<P> *>(n[sense]);
in->prefetch();
int kp = internode<P>::bound_type::upper(ka, *in);
n[!sense] = in->child_[kp];
if (!n[!sense])
goto retry;
v[!sense] = n[!sense]->stable_annotated(ti->stable_fence());
if (likely(!in->has_changed(v[sense]))) {
sense = !sense;
continue;
}
typename node_base<P>::nodeversion_type oldv = v[sense];
v[sense] = in->stable_annotated(ti->stable_fence());
if (oldv.has_split(v[sense])
&& stable_last_key_compare(ka, *in, v[sense], ti) > 0) {
ti->mark(tc_root_retry);
goto retry;
} else
ti->mark(tc_internode_retry);
}
version = v[sense];
return const_cast<leaf<P> *>(static_cast<const leaf<P> *>(n[sense]));
}
template <typename P>
leaf<P> *forward_at_leaf(const leaf<P> *n,
typename leaf<P>::nodeversion_type &v,
const typename node_base<P>::key_type &ka,
threadinfo *ti)
{
typename leaf<P>::nodeversion_type oldv = v;
v = n->stable_annotated(ti->stable_fence());
if (v.has_split(oldv)
&& stable_last_key_compare(ka, *n, v, ti) > 0) {
leaf<P> *next;
ti->mark(tc_leaf_walk);
while (likely(!v.deleted()) && (next = n->safe_next())
&& compare(ka.ikey(), next->ikey_bound()) >= 0) {
n = next;
v = n->stable_annotated(ti->stable_fence());
}
}
return const_cast<leaf<P> *>(n);
}
template <typename P>
internode<P> *node_base<P>::locked_parent(threadinfo *ti) const
{
const node_base<P> *n = this;
precondition(!n->concurrent || n->locked());
while (1) {
node_base<P> *p = n->parent();
if (!p)
return 0;
nodeversion_type pv = p->lock(*p, ti->lock_fence(tc_internode_lock));
if (p == n->parent()) {
invariant(!p->isleaf());
return static_cast<internode<P> *>(p);
}
p->unlock(pv);
relax_fence();
}
}
} // namespace Masstree
#endif