1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (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#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#pragma once
40
41#include <ft/comparator.h>
42
43#include "treenode.h"
44#include "keyrange.h"
45
46namespace toku {
47
48// A concurrent_tree stores non-overlapping ranges.
49// Access to disjoint parts of the tree usually occurs concurrently.
50
51class concurrent_tree {
52public:
53
54 // A locked_keyrange gives you exclusive access to read and write
55 // operations that occur on any keys in that range. You only have
56 // the right to operate on keys in that range or keys that were read
57 // from the keyrange using iterate()
58 //
59 // Access model:
60 // - user prepares a locked keyrange. all threads serialize behind prepare().
61 // - user breaks the serialzation point by acquiring a range, or releasing.
62 // - one thread operates on a certain locked_keyrange object at a time.
63 // - when the thread is finished, it releases
64
65 class locked_keyrange {
66 public:
67 // effect: prepare to acquire a locked keyrange over the given
68 // concurrent_tree, preventing other threads from preparing
69 // until this thread either does acquire() or release().
70 // note: operations performed on a prepared keyrange are equivalent
71 // to ones performed on an acquired keyrange over -inf, +inf.
72 // rationale: this provides the user with a serialization point for descending
73 // or modifying the the tree. it also proives a convenient way of
74 // doing serializable operations on the tree.
75 // There are two valid sequences of calls:
76 // - prepare, acquire, [operations], release
77 // - prepare, [operations],release
78 void prepare(concurrent_tree *tree);
79
80 // requires: the locked keyrange was prepare()'d
81 // effect: acquire a locked keyrange over the given concurrent_tree.
82 // the locked keyrange represents the range of keys overlapped
83 // by the given range
84 void acquire(const keyrange &range);
85
86 // effect: releases a locked keyrange and the mutex it holds
87 void release(void);
88
89 // effect: iterate over each range this locked_keyrange represents,
90 // calling function->fn() on each node's keyrange and txnid
91 // until there are no more or the function returns false
92 template <class F>
93 void iterate(F *function) const;
94
95 // inserts the given range into the tree, with an associated txnid.
96 // requires: range does not overlap with anything in this locked_keyrange
97 // rationale: caller is responsible for only inserting unique ranges
98 void insert(const keyrange &range, TXNID txnid);
99
100 // effect: removes the given range from the tree
101 // requires: range exists exactly in this locked_keyrange
102 // rationale: caller is responsible for only removing existing ranges
103 void remove(const keyrange &range);
104
105 // effect: removes all of the keys represented by this locked keyrange
106 // rationale: we'd like a fast way to empty out a tree
107 void remove_all(void);
108
109 private:
110 // the concurrent tree this locked keyrange is for
111 concurrent_tree *m_tree;
112
113 // the range of keys this locked keyrange represents
114 keyrange m_range;
115
116 // the subtree under which all overlapping ranges exist
117 treenode *m_subtree;
118
119 friend class concurrent_tree_unit_test;
120 };
121
122 // effect: initialize the tree to an empty state
123 void create(const comparator *cmp);
124
125 // effect: destroy the tree.
126 // requires: tree is empty
127 void destroy(void);
128
129 // returns: true iff the tree is empty
130 bool is_empty(void);
131
132 // returns: the memory overhead of a single insertion into the tree
133 static uint64_t get_insertion_memory_overhead(void);
134
135private:
136 // the root needs to always exist so there's a lock to grab
137 // even if the tree is empty. that's why we store a treenode
138 // here and not a pointer to one.
139 treenode m_root;
140
141 friend class concurrent_tree_unit_test;
142};
143
144// include the implementation here so we can use templated member
145// functions in locked_keyrange, which are expanded and defined in the
146// compilation unit that includes "concurrent_tree.h". if we didn't
147// include the source here, then there would be problems with multiple
148// definitions of the tree functions
149#include "concurrent_tree.cc"
150
151} /* namespace toku */
152