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 <string.h>
54 
55 #include "portability/memory.h"
56 
57 #include "locktree/range_buffer.h"
58 #include "util/dbt.h"
59 
60 namespace toku {
61 
left_is_infinite(void) const62     bool range_buffer::record_header::left_is_infinite(void) const {
63         return left_neg_inf || left_pos_inf;
64     }
65 
right_is_infinite(void) const66     bool range_buffer::record_header::right_is_infinite(void) const {
67         return right_neg_inf || right_pos_inf;
68     }
69 
init(const DBT * left_key,const DBT * right_key)70     void range_buffer::record_header::init(const DBT *left_key, const DBT *right_key) {
71         left_neg_inf = left_key == toku_dbt_negative_infinity();
72         left_pos_inf = left_key == toku_dbt_positive_infinity();
73         left_key_size = toku_dbt_is_infinite(left_key) ? 0 : left_key->size;
74         if (right_key) {
75             right_neg_inf = right_key == toku_dbt_negative_infinity();
76             right_pos_inf = right_key == toku_dbt_positive_infinity();
77             right_key_size = toku_dbt_is_infinite(right_key) ? 0 : right_key->size;
78         } else {
79             right_neg_inf = left_neg_inf;
80             right_pos_inf = left_pos_inf;
81             right_key_size = 0;
82         }
83     }
84 
get_left_key(void) const85     const DBT *range_buffer::iterator::record::get_left_key(void) const {
86         if (_header.left_neg_inf) {
87             return toku_dbt_negative_infinity();
88         } else if (_header.left_pos_inf) {
89             return toku_dbt_positive_infinity();
90         } else {
91             return &_left_key;
92         }
93     }
94 
get_right_key(void) const95     const DBT *range_buffer::iterator::record::get_right_key(void) const {
96         if (_header.right_neg_inf) {
97             return toku_dbt_negative_infinity();
98         } else if (_header.right_pos_inf) {
99             return toku_dbt_positive_infinity();
100         } else {
101             return &_right_key;
102         }
103     }
104 
size(void) const105     size_t range_buffer::iterator::record::size(void) const {
106         return sizeof(record_header) + _header.left_key_size + _header.right_key_size;
107     }
108 
deserialize(const char * buf)109     void range_buffer::iterator::record::deserialize(const char *buf) {
110         size_t current = 0;
111 
112         // deserialize the header
113         memcpy(&_header, buf, sizeof(record_header));
114         current += sizeof(record_header);
115 
116         // deserialize the left key if necessary
117         if (!_header.left_is_infinite()) {
118             // point the left DBT's buffer into ours
119             toku_fill_dbt(&_left_key, buf + current, _header.left_key_size);
120             current += _header.left_key_size;
121         }
122 
123         // deserialize the right key if necessary
124         if (!_header.right_is_infinite()) {
125             if (_header.right_key_size == 0) {
126                 toku_copyref_dbt(&_right_key, _left_key);
127             } else {
128                 toku_fill_dbt(&_right_key, buf + current, _header.right_key_size);
129             }
130         }
131     }
132 
iterator()133     toku::range_buffer::iterator::iterator() :
134         _ma_chunk_iterator(nullptr),
135         _current_chunk_base(nullptr),
136         _current_chunk_offset(0), _current_chunk_max(0),
137         _current_rec_size(0) {
138     }
139 
iterator(const range_buffer * buffer)140     toku::range_buffer::iterator::iterator(const range_buffer *buffer) :
141         _ma_chunk_iterator(&buffer->_arena),
142         _current_chunk_base(nullptr),
143         _current_chunk_offset(0), _current_chunk_max(0),
144         _current_rec_size(0) {
145         reset_current_chunk();
146     }
147 
reset_current_chunk()148     void range_buffer::iterator::reset_current_chunk() {
149         _current_chunk_base = _ma_chunk_iterator.current(&_current_chunk_max);
150         _current_chunk_offset = 0;
151     }
152 
current(record * rec)153     bool range_buffer::iterator::current(record *rec) {
154         if (_current_chunk_offset < _current_chunk_max) {
155             const char *buf = reinterpret_cast<const char *>(_current_chunk_base);
156             rec->deserialize(buf + _current_chunk_offset);
157             _current_rec_size = rec->size();
158             return true;
159         } else {
160             return false;
161         }
162     }
163 
164     // move the iterator to the next record in the buffer
next(void)165     void range_buffer::iterator::next(void) {
166         invariant(_current_chunk_offset < _current_chunk_max);
167         invariant(_current_rec_size > 0);
168 
169         // the next record is _current_rec_size bytes forward
170         _current_chunk_offset += _current_rec_size;
171         // now, we don't know how big the current is, set it to 0.
172         _current_rec_size = 0;
173 
174         if (_current_chunk_offset >= _current_chunk_max) {
175             // current chunk is exhausted, try moving to the next one
176             if (_ma_chunk_iterator.more()) {
177                 _ma_chunk_iterator.next();
178                 reset_current_chunk();
179             }
180         }
181     }
182 
create(void)183     void range_buffer::create(void) {
184         // allocate buffer space lazily instead of on creation. this way,
185         // no malloc/free is done if the transaction ends up taking no locks.
186         _arena.create(0);
187         _num_ranges = 0;
188     }
189 
append(const DBT * left_key,const DBT * right_key)190     void range_buffer::append(const DBT *left_key, const DBT *right_key) {
191         // if the keys are equal, then only one copy is stored.
192         if (toku_dbt_equals(left_key, right_key)) {
193             invariant(left_key->size <= MAX_KEY_SIZE);
194             append_point(left_key);
195         } else {
196             invariant(left_key->size <= MAX_KEY_SIZE);
197             invariant(right_key->size <= MAX_KEY_SIZE);
198             append_range(left_key, right_key);
199         }
200         _num_ranges++;
201     }
202 
is_empty(void) const203     bool range_buffer::is_empty(void) const {
204         return total_memory_size() == 0;
205     }
206 
total_memory_size(void) const207     uint64_t range_buffer::total_memory_size(void) const {
208         return _arena.total_size_in_use();
209     }
210 
get_num_ranges(void) const211     int range_buffer::get_num_ranges(void) const {
212         return _num_ranges;
213     }
214 
destroy(void)215     void range_buffer::destroy(void) {
216         _arena.destroy();
217     }
218 
append_range(const DBT * left_key,const DBT * right_key)219     void range_buffer::append_range(const DBT *left_key, const DBT *right_key) {
220         size_t record_length = sizeof(record_header) + left_key->size + right_key->size;
221         char *buf = reinterpret_cast<char *>(_arena.malloc_from_arena(record_length));
222 
223         record_header h;
224         h.init(left_key, right_key);
225 
226         // serialize the header
227         memcpy(buf, &h, sizeof(record_header));
228         buf += sizeof(record_header);
229 
230         // serialize the left key if necessary
231         if (!h.left_is_infinite()) {
232             memcpy(buf, left_key->data, left_key->size);
233             buf += left_key->size;
234         }
235 
236         // serialize the right key if necessary
237         if (!h.right_is_infinite()) {
238             memcpy(buf, right_key->data, right_key->size);
239         }
240     }
241 
append_point(const DBT * key)242     void range_buffer::append_point(const DBT *key) {
243         size_t record_length = sizeof(record_header) + key->size;
244         char *buf = reinterpret_cast<char *>(_arena.malloc_from_arena(record_length));
245 
246         record_header h;
247         h.init(key, nullptr);
248 
249         // serialize the header
250         memcpy(buf, &h, sizeof(record_header));
251         buf += sizeof(record_header);
252 
253         // serialize the key if necessary
254         if (!h.left_is_infinite()) {
255             memcpy(buf, key->data, key->size);
256         }
257     }
258 
259 } /* namespace toku */
260