]>
Commit | Line | Data |
---|---|---|
1e59de90 TL |
1 | /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */ |
2 | // vim: ft=cpp:expandtab:ts=8:sw=2:softtabstop=2: | |
3 | #ident "$Id$" | |
4 | /*====== | |
5 | This file is part of PerconaFT. | |
6 | ||
7 | ||
8 | Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. | |
9 | ||
10 | PerconaFT is free software: you can redistribute it and/or modify | |
11 | it under the terms of the GNU General Public License, version 2, | |
12 | as published by the Free Software Foundation. | |
13 | ||
14 | PerconaFT is distributed in the hope that it will be useful, | |
15 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | GNU General Public License for more details. | |
18 | ||
19 | You should have received a copy of the GNU General Public License | |
20 | along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. | |
21 | ||
22 | ---------------------------------------- | |
23 | ||
24 | PerconaFT is free software: you can redistribute it and/or modify | |
25 | it under the terms of the GNU Affero General Public License, version 3, | |
26 | as published by the Free Software Foundation. | |
27 | ||
28 | PerconaFT is distributed in the hope that it will be useful, | |
29 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
30 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
31 | GNU Affero General Public License for more details. | |
32 | ||
33 | You should have received a copy of the GNU Affero General Public License | |
34 | along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. | |
35 | ||
36 | ---------------------------------------- | |
37 | ||
38 | Licensed under the Apache License, Version 2.0 (the "License"); | |
39 | you may not use this file except in compliance with the License. | |
40 | You may obtain a copy of the License at | |
41 | ||
42 | http://www.apache.org/licenses/LICENSE-2.0 | |
43 | ||
44 | Unless required by applicable law or agreed to in writing, software | |
45 | distributed under the License is distributed on an "AS IS" BASIS, | |
46 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
47 | See the License for the specific language governing permissions and | |
48 | limitations under the License. | |
49 | ======= */ | |
50 | ||
51 | #ident \ | |
52 | "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." | |
53 | ||
54 | #pragma once | |
55 | ||
56 | #include "../ft/comparator.h" | |
57 | #include "keyrange.h" | |
58 | #include "treenode.h" | |
59 | ||
60 | namespace toku { | |
61 | ||
62 | // A concurrent_tree stores non-overlapping ranges. | |
63 | // Access to disjoint parts of the tree usually occurs concurrently. | |
64 | ||
65 | class concurrent_tree { | |
66 | public: | |
67 | // A locked_keyrange gives you exclusive access to read and write | |
68 | // operations that occur on any keys in that range. You only have | |
69 | // the right to operate on keys in that range or keys that were read | |
70 | // from the keyrange using iterate() | |
71 | // | |
72 | // Access model: | |
73 | // - user prepares a locked keyrange. all threads serialize behind prepare(). | |
74 | // - user breaks the serialzation point by acquiring a range, or releasing. | |
75 | // - one thread operates on a certain locked_keyrange object at a time. | |
76 | // - when the thread is finished, it releases | |
77 | ||
78 | class locked_keyrange { | |
79 | public: | |
80 | // effect: prepare to acquire a locked keyrange over the given | |
81 | // concurrent_tree, preventing other threads from preparing | |
82 | // until this thread either does acquire() or release(). | |
83 | // note: operations performed on a prepared keyrange are equivalent | |
84 | // to ones performed on an acquired keyrange over -inf, +inf. | |
85 | // rationale: this provides the user with a serialization point for | |
86 | // descending | |
87 | // or modifying the the tree. it also proives a convenient way of | |
88 | // doing serializable operations on the tree. | |
89 | // There are two valid sequences of calls: | |
90 | // - prepare, acquire, [operations], release | |
91 | // - prepare, [operations],release | |
92 | void prepare(concurrent_tree *tree); | |
93 | ||
94 | // requires: the locked keyrange was prepare()'d | |
95 | // effect: acquire a locked keyrange over the given concurrent_tree. | |
96 | // the locked keyrange represents the range of keys overlapped | |
97 | // by the given range | |
98 | void acquire(const keyrange &range); | |
99 | ||
100 | // effect: releases a locked keyrange and the mutex it holds | |
101 | void release(void); | |
102 | ||
103 | // effect: iterate over each range this locked_keyrange represents, | |
104 | // calling function->fn() on each node's keyrange and txnid | |
105 | // until there are no more or the function returns false | |
106 | template <class F> | |
107 | void iterate(F *function) const { | |
108 | // if the subtree is non-empty, traverse it by calling the given | |
109 | // function on each range, txnid pair found that overlaps. | |
110 | if (!m_subtree->is_empty()) { | |
111 | m_subtree->traverse_overlaps(m_range, function); | |
112 | } | |
113 | } | |
114 | ||
115 | // Adds another owner to the lock on the specified keyrange. | |
116 | // requires: the keyrange contains one treenode whose bounds are | |
117 | // exactly equal to the specifed range (no sub/supersets) | |
118 | bool add_shared_owner(const keyrange &range, TXNID new_owner); | |
119 | ||
120 | // inserts the given range into the tree, with an associated txnid. | |
121 | // requires: range does not overlap with anything in this locked_keyrange | |
122 | // rationale: caller is responsible for only inserting unique ranges | |
123 | void insert(const keyrange &range, TXNID txnid, bool is_shared); | |
124 | ||
125 | // effect: removes the given range from the tree. | |
126 | // - txnid=TXNID_ANY means remove the range no matter what its | |
127 | // owners are | |
128 | // - Other value means remove the specified txnid from | |
129 | // ownership (if the range has other owners, it will remain | |
130 | // in the tree) | |
131 | // requires: range exists exactly in this locked_keyrange | |
132 | // rationale: caller is responsible for only removing existing ranges | |
133 | void remove(const keyrange &range, TXNID txnid); | |
134 | ||
135 | // effect: removes all of the keys represented by this locked keyrange | |
136 | // rationale: we'd like a fast way to empty out a tree | |
137 | void remove_all(void); | |
138 | ||
139 | private: | |
140 | // the concurrent tree this locked keyrange is for | |
141 | concurrent_tree *m_tree; | |
142 | ||
143 | // the range of keys this locked keyrange represents | |
144 | keyrange m_range; | |
145 | ||
146 | // the subtree under which all overlapping ranges exist | |
147 | treenode *m_subtree; | |
148 | ||
149 | friend class concurrent_tree_unit_test; | |
150 | }; | |
151 | ||
152 | // effect: initialize the tree to an empty state | |
153 | void create(const comparator *cmp); | |
154 | ||
155 | // effect: destroy the tree. | |
156 | // requires: tree is empty | |
157 | void destroy(void); | |
158 | ||
159 | // returns: true iff the tree is empty | |
160 | bool is_empty(void); | |
161 | ||
162 | // returns: the memory overhead of a single insertion into the tree | |
163 | static uint64_t get_insertion_memory_overhead(void); | |
164 | ||
165 | private: | |
166 | // the root needs to always exist so there's a lock to grab | |
167 | // even if the tree is empty. that's why we store a treenode | |
168 | // here and not a pointer to one. | |
169 | treenode m_root; | |
170 | ||
171 | friend class concurrent_tree_unit_test; | |
172 | }; | |
173 | ||
174 | } /* namespace toku */ |