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 #pragma once 54 55 #include "portability/toku_stdint.h" 56 57 #include "util/dbt.h" 58 #include "util/memarena.h" 59 60 namespace toku { 61 62 // a key range buffer represents a set of key ranges that can 63 // be stored, iterated over, and then destroyed all at once. 64 class range_buffer { 65 private: 66 67 // the key range buffer is a bunch of records in a row. 68 // each record has the following header, followed by the 69 // left key and right key data payload, if applicable. 70 // we limit keys to be 2^16, since we store lengths as 2 bytes. 71 static const size_t MAX_KEY_SIZE = 1 << 16; 72 73 struct record_header { 74 bool left_neg_inf; 75 bool left_pos_inf; 76 bool right_pos_inf; 77 bool right_neg_inf; 78 uint16_t left_key_size; 79 uint16_t right_key_size; 80 81 bool left_is_infinite(void) const; 82 83 bool right_is_infinite(void) const; 84 85 void init(const DBT *left_key, const DBT *right_key); 86 }; 87 static_assert(sizeof(record_header) == 8, "record header format is off"); 88 89 public: 90 91 // the iterator abstracts reading over a buffer of variable length 92 // records one by one until there are no more left. 93 class iterator { 94 public: 95 iterator(); 96 iterator(const range_buffer *buffer); 97 98 // a record represents the user-view of a serialized key range. 99 // it handles positive and negative infinity and the optimized 100 // point range case, where left and right points share memory. 101 class record { 102 public: 103 // get a read-only pointer to the left key of this record's range 104 const DBT *get_left_key(void) const; 105 106 // get a read-only pointer to the right key of this record's range 107 const DBT *get_right_key(void) const; 108 109 // how big is this record? this tells us where the next record is 110 size_t size(void) const; 111 112 // populate a record header and point our DBT's 113 // buffers into ours if they are not infinite. 114 void deserialize(const char *buf); 115 116 private: 117 record_header _header; 118 DBT _left_key; 119 DBT _right_key; 120 }; 121 122 // populate the given record object with the current 123 // the memory referred to by record is valid for only 124 // as long as the record exists. 125 bool current(record *rec); 126 127 // move the iterator to the next record in the buffer 128 void next(void); 129 130 private: 131 void reset_current_chunk(); 132 133 // the key range buffer we are iterating over, the current 134 // offset in that buffer, and the size of the current record. 135 memarena::chunk_iterator _ma_chunk_iterator; 136 const void *_current_chunk_base; 137 size_t _current_chunk_offset; 138 size_t _current_chunk_max; 139 size_t _current_rec_size; 140 }; 141 142 // allocate buffer space lazily instead of on creation. this way, 143 // no malloc/free is done if the transaction ends up taking no locks. 144 void create(void); 145 146 // append a left/right key range to the buffer. 147 // if the keys are equal, then only one copy is stored. 148 void append(const DBT *left_key, const DBT *right_key); 149 150 // is this range buffer empty? 151 bool is_empty(void) const; 152 153 // how much memory is being used by this range buffer? 154 uint64_t total_memory_size(void) const; 155 156 // how many ranges are stored in this range buffer? 157 int get_num_ranges(void) const; 158 159 void destroy(void); 160 161 private: 162 memarena _arena; 163 int _num_ranges; 164 165 void append_range(const DBT *left_key, const DBT *right_key); 166 167 // append a point to the buffer. this is the space/time saving 168 // optimization for key ranges where left == right. 169 void append_point(const DBT *key); 170 }; 171 172 } /* namespace toku */ 173