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