ceph/src/rocksdb/utilities/transactions/lock/range/range_tree/lib/locktree/concurrent_tree.h

   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 */