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#include "keyrange.h"
40
41#include <util/dbt.h>
42
43namespace toku {
44
45 // create a keyrange by borrowing the left and right dbt
46 // pointers. no memory is copied. no checks for infinity needed.
47 void keyrange::create(const DBT *left, const DBT *right) {
48 init_empty();
49 m_left_key = left;
50 m_right_key = right;
51 }
52
53 // destroy the key copies. if they were never set, then destroy does nothing.
54 void keyrange::destroy(void) {
55 toku_destroy_dbt(&m_left_key_copy);
56 toku_destroy_dbt(&m_right_key_copy);
57 }
58
59 // create a keyrange by copying the keys from the given range.
60 void keyrange::create_copy(const keyrange &range) {
61 // start with an initialized, empty range
62 init_empty();
63
64 // optimize the case where the left and right keys are the same.
65 // we'd like to only have one copy of the data.
66 if (toku_dbt_equals(range.get_left_key(), range.get_right_key())) {
67 set_both_keys(range.get_left_key());
68 } else {
69 // replace our empty left and right keys with
70 // copies of the range's left and right keys
71 replace_left_key(range.get_left_key());
72 replace_right_key(range.get_right_key());
73 }
74 }
75
76 // extend this keyrange by choosing the leftmost and rightmost
77 // endpoints between this range and the given. replaced keys
78 // in this range are freed and inherited keys are copied.
79 void keyrange::extend(const comparator &cmp, const keyrange &range) {
80 const DBT *range_left = range.get_left_key();
81 const DBT *range_right = range.get_right_key();
82 if (cmp(range_left, get_left_key()) < 0) {
83 replace_left_key(range_left);
84 }
85 if (cmp(range_right, get_right_key()) > 0) {
86 replace_right_key(range_right);
87 }
88 }
89
90 // how much memory does this keyrange take?
91 // - the size of the left and right keys
92 // --- ignore the fact that we may have optimized the point case.
93 // it complicates things for little gain.
94 // - the size of the keyrange class itself
95 uint64_t keyrange::get_memory_size(void) const {
96 const DBT *left_key = get_left_key();
97 const DBT *right_key = get_right_key();
98 return left_key->size + right_key->size + sizeof(keyrange);
99 }
100
101 // compare ranges.
102 keyrange::comparison keyrange::compare(const comparator &cmp, const keyrange &range) const {
103 if (cmp(get_right_key(), range.get_left_key()) < 0) {
104 return comparison::LESS_THAN;
105 } else if (cmp(get_left_key(), range.get_right_key()) > 0) {
106 return comparison::GREATER_THAN;
107 } else if (cmp(get_left_key(), range.get_left_key()) == 0 &&
108 cmp(get_right_key(), range.get_right_key()) == 0) {
109 return comparison::EQUALS;
110 } else {
111 return comparison::OVERLAPS;
112 }
113 }
114
115 bool keyrange::overlaps(const comparator &cmp, const keyrange &range) const {
116 // equality is a stronger form of overlapping.
117 // so two ranges "overlap" if they're either equal or just overlapping.
118 comparison c = compare(cmp, range);
119 return c == comparison::EQUALS || c == comparison::OVERLAPS;
120 }
121
122 keyrange keyrange::get_infinite_range(void) {
123 keyrange range;
124 range.create(toku_dbt_negative_infinity(), toku_dbt_positive_infinity());
125 return range;
126 }
127
128 void keyrange::init_empty(void) {
129 m_left_key = nullptr;
130 m_right_key = nullptr;
131 toku_init_dbt(&m_left_key_copy);
132 toku_init_dbt(&m_right_key_copy);
133 m_point_range = false;
134 }
135
136 const DBT *keyrange::get_left_key(void) const {
137 if (m_left_key) {
138 return m_left_key;
139 } else {
140 return &m_left_key_copy;
141 }
142 }
143
144 const DBT *keyrange::get_right_key(void) const {
145 if (m_right_key) {
146 return m_right_key;
147 } else {
148 return &m_right_key_copy;
149 }
150 }
151
152 // copy the given once and set both the left and right pointers.
153 // optimization for point ranges, so the left and right ranges
154 // are not copied twice.
155 void keyrange::set_both_keys(const DBT *key) {
156 if (toku_dbt_is_infinite(key)) {
157 m_left_key = key;
158 m_right_key = key;
159 } else {
160 toku_clone_dbt(&m_left_key_copy, *key);
161 toku_copyref_dbt(&m_right_key_copy, m_left_key_copy);
162 }
163 m_point_range = true;
164 }
165
166 // destroy the current left key. set and possibly copy the new one
167 void keyrange::replace_left_key(const DBT *key) {
168 // a little magic:
169 //
170 // if this is a point range, then the left and right keys share
171 // one copy of the data, and it lives in the left key copy. so
172 // if we're replacing the left key, move the real data to the
173 // right key copy instead of destroying it. now, the memory is
174 // owned by the right key and the left key may be replaced.
175 if (m_point_range) {
176 m_right_key_copy = m_left_key_copy;
177 } else {
178 toku_destroy_dbt(&m_left_key_copy);
179 }
180
181 if (toku_dbt_is_infinite(key)) {
182 m_left_key = key;
183 } else {
184 toku_clone_dbt(&m_left_key_copy, *key);
185 m_left_key = nullptr;
186 }
187 m_point_range = false;
188 }
189
190 // destroy the current right key. set and possibly copy the new one
191 void keyrange::replace_right_key(const DBT *key) {
192 toku_destroy_dbt(&m_right_key_copy);
193 if (toku_dbt_is_infinite(key)) {
194 m_right_key = key;
195 } else {
196 toku_clone_dbt(&m_right_key_copy, *key);
197 m_right_key = nullptr;
198 }
199 m_point_range = false;
200 }
201
202} /* namespace toku */
203