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> iterate(F * function)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 */ 175