1/*
2 Copyright (c) 2010, 2011, Monty Program Ab
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
16
17/**
18 @defgroup Bi-directional LIFO buffers used by DS-MRR implementation
19 @{
20*/
21
22class Forward_lifo_buffer;
23class Backward_lifo_buffer;
24
25
26/*
27 A base class for in-memory buffer used by DS-MRR implementation. Common
28 properties:
29 - The buffer is last-in-first-out, i.e. elements that are written last are
30 read first.
31 - The buffer contains fixed-size elements. The elements are either atomic
32 byte sequences or pairs of them.
33 - The buffer resides in the memory provided by the user. It is possible to
34 = dynamically (ie. between write operations) add ajacent memory space to
35 the buffer
36 = dynamically remove unused space from the buffer.
37 The intent of this is to allow to have two buffers on adjacent memory
38 space, one is being read from (and so its space shrinks), while the other
39 is being written to (and so it needs more and more space).
40
41 There are two concrete classes, Forward_lifo_buffer and Backward_lifo_buffer.
42*/
43
44class Lifo_buffer
45{
46protected:
47 size_t size1;
48 size_t size2;
49
50public:
51 /**
52 write() will put into buffer size1 bytes pointed by write_ptr1. If
53 size2!=0, then they will be accompanied by size2 bytes pointed by
54 write_ptr2.
55 */
56 uchar *write_ptr1;
57 uchar *write_ptr2;
58
59 /**
60 read() will do reading by storing pointers to read data into read_ptr1 or
61 into (read_ptr1, read_ptr2), depending on whether the buffer was set to
62 store single objects or pairs.
63 */
64 uchar *read_ptr1;
65 uchar *read_ptr2;
66
67protected:
68 uchar *start; /**< points to start of buffer space */
69 uchar *end; /**< points to just beyond the end of buffer space */
70public:
71
72 enum enum_direction {
73 BACKWARD=-1, /**< buffer is filled/read from bigger to smaller memory addresses */
74 FORWARD=1 /**< buffer is filled/read from smaller to bigger memory addresses */
75 };
76
77 virtual enum_direction type() = 0;
78
79 /* Buffer space control functions */
80
81 /** Let the buffer store data in the given space. */
82 void set_buffer_space(uchar *start_arg, uchar *end_arg)
83 {
84 start= start_arg;
85 end= end_arg;
86 if (end != start)
87 TRASH_ALLOC(start, size_t(end - start));
88 reset();
89 }
90
91 /**
92 Specify where write() should get the source data from, as well as source
93 data size.
94 */
95 void setup_writing(size_t len1, size_t len2)
96 {
97 size1= len1;
98 size2= len2;
99 }
100
101 /**
102 Specify where read() should store pointers to read data, as well as read
103 data size. The sizes must match those passed to setup_writing().
104 */
105 void setup_reading(size_t len1, size_t len2)
106 {
107 DBUG_ASSERT(len1 == size1);
108 DBUG_ASSERT(len2 == size2);
109 }
110
111 bool can_write()
112 {
113 return have_space_for(size1 + size2);
114 }
115 virtual void write() = 0;
116
117 bool is_empty() { return used_size() == 0; }
118 virtual bool read() = 0;
119
120 void sort(qsort2_cmp cmp_func, void *cmp_func_arg)
121 {
122 size_t elem_size= size1 + size2;
123 size_t n_elements= used_size() / elem_size;
124 my_qsort2(used_area(), n_elements, elem_size, cmp_func, cmp_func_arg);
125 }
126
127 virtual void reset() = 0;
128 virtual uchar *end_of_space() = 0;
129protected:
130 virtual size_t used_size() = 0;
131
132 /* To be used only by iterator class: */
133 virtual uchar *get_pos()= 0;
134 virtual bool read(uchar **position, uchar **ptr1, uchar **ptr2)= 0;
135 friend class Lifo_buffer_iterator;
136public:
137 virtual bool have_space_for(size_t bytes) = 0;
138
139 virtual void remove_unused_space(uchar **unused_start, uchar **unused_end)=0;
140 virtual uchar *used_area() = 0;
141 virtual ~Lifo_buffer() {};
142};
143
144
145/**
146 Forward LIFO buffer
147
148 The buffer that is being written to from start to end and read in the
149 reverse. 'pos' points to just beyond the end of used space.
150
151 It is possible to grow/shink the buffer at the end bound
152
153 used space unused space
154 *==============*-----------------*
155 ^ ^ ^
156 | | +--- end
157 | +---- pos
158 +--- start
159*/
160
161class Forward_lifo_buffer: public Lifo_buffer
162{
163 uchar *pos;
164public:
165 enum_direction type() { return FORWARD; }
166 size_t used_size()
167 {
168 return (size_t)(pos - start);
169 }
170 void reset()
171 {
172 pos= start;
173 }
174 uchar *end_of_space() { return pos; }
175 bool have_space_for(size_t bytes)
176 {
177 return (pos + bytes < end);
178 }
179
180 void write()
181 {
182 write_bytes(write_ptr1, size1);
183 if (size2)
184 write_bytes(write_ptr2, size2);
185 }
186 void write_bytes(const uchar *data, size_t bytes)
187 {
188 DBUG_ASSERT(have_space_for(bytes));
189 memcpy(pos, data, bytes);
190 pos += bytes;
191 }
192 bool have_data(uchar *position, size_t bytes)
193 {
194 return ((position - start) >= (ptrdiff_t)bytes);
195 }
196 uchar *read_bytes(uchar **position, size_t bytes)
197 {
198 DBUG_ASSERT(have_data(*position, bytes));
199 *position= (*position) - bytes;
200 return *position;
201 }
202 bool read() { return read(&pos, &read_ptr1, &read_ptr2); }
203 bool read(uchar **position, uchar **ptr1, uchar **ptr2)
204 {
205 if (!have_data(*position, size1 + size2))
206 return TRUE;
207 if (size2)
208 *ptr2= read_bytes(position, size2);
209 *ptr1= read_bytes(position, size1);
210 return FALSE;
211 }
212 void remove_unused_space(uchar **unused_start, uchar **unused_end)
213 {
214 DBUG_ASSERT(0); /* Don't need this yet */
215 }
216 /**
217 Add more space to the buffer. The caller is responsible that the space
218 being added is adjacent to the end of the buffer.
219
220 @param unused_start Start of space
221 @param unused_end End of space
222 */
223 void grow(uchar *unused_start, uchar *unused_end)
224 {
225 DBUG_ASSERT(unused_end >= unused_start);
226 DBUG_ASSERT(end == unused_start);
227 TRASH_ALLOC(unused_start, size_t(unused_end - unused_start));
228 end= unused_end;
229 }
230 /* Return pointer to start of the memory area that is occupied by the data */
231 uchar *used_area() { return start; }
232 friend class Lifo_buffer_iterator;
233 uchar *get_pos() { return pos; }
234};
235
236
237
238/**
239 Backward LIFO buffer
240
241 The buffer that is being written to from start to end and read in the
242 reverse. 'pos' points to the start of used space.
243
244 It is possible to grow/shink the buffer at the start.
245
246 unused space used space
247 *--------------*=================*
248 ^ ^ ^
249 | | +--- end
250 | +---- pos
251 +--- start
252*/
253class Backward_lifo_buffer: public Lifo_buffer
254{
255 uchar *pos;
256public:
257 enum_direction type() { return BACKWARD; }
258
259 size_t used_size()
260 {
261 return (size_t)(end - pos);
262 }
263 void reset()
264 {
265 pos= end;
266 }
267 uchar *end_of_space() { return end; }
268 bool have_space_for(size_t bytes)
269 {
270 return (pos - bytes >= start);
271 }
272 void write()
273 {
274 if (write_ptr2)
275 write_bytes(write_ptr2, size2);
276 write_bytes(write_ptr1, size1);
277 }
278 void write_bytes(const uchar *data, size_t bytes)
279 {
280 DBUG_ASSERT(have_space_for(bytes));
281 pos -= bytes;
282 memcpy(pos, data, bytes);
283 }
284 bool read()
285 {
286 return read(&pos, &read_ptr1, &read_ptr2);
287 }
288 bool read(uchar **position, uchar **ptr1, uchar **ptr2)
289 {
290 if (!have_data(*position, size1 + size2))
291 return TRUE;
292 *ptr1= read_bytes(position, size1);
293 if (size2)
294 *ptr2= read_bytes(position, size2);
295 return FALSE;
296 }
297 bool have_data(uchar *position, size_t bytes)
298 {
299 return ((end - position) >= (ptrdiff_t)bytes);
300 }
301 uchar *read_bytes(uchar **position, size_t bytes)
302 {
303 DBUG_ASSERT(have_data(*position, bytes));
304 uchar *ret= *position;
305 *position= *position + bytes;
306 return ret;
307 }
308 /**
309 Stop using/return the unused part of the space
310 @param unused_start OUT Start of the unused space
311 @param unused_end OUT End of the unused space
312 */
313 void remove_unused_space(uchar **unused_start, uchar **unused_end)
314 {
315 *unused_start= start;
316 *unused_end= pos;
317 start= pos;
318 }
319 void grow(uchar *unused_start, uchar *unused_end)
320 {
321 DBUG_ASSERT(0); /* Not used for backward buffers */
322 }
323 /* Return pointer to start of the memory area that is occupied by the data */
324 uchar *used_area() { return pos; }
325 friend class Lifo_buffer_iterator;
326 uchar *get_pos() { return pos; }
327};
328
329
330/** Iterator to walk over contents of the buffer without reading from it */
331class Lifo_buffer_iterator
332{
333 uchar *pos;
334 Lifo_buffer *buf;
335
336public:
337 /* The data is read to here */
338 uchar *read_ptr1;
339 uchar *read_ptr2;
340
341 void init(Lifo_buffer *buf_arg)
342 {
343 buf= buf_arg;
344 pos= buf->get_pos();
345 }
346 /*
347 Read the next value. The calling convention is the same as buf->read()
348 has.
349
350 @retval FALSE - ok
351 @retval TRUE - EOF, reached the end of the buffer
352 */
353 bool read()
354 {
355 return buf->read(&pos, &read_ptr1, &read_ptr2);
356 }
357};
358
359
360