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