drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
sql_list.h
1/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3 *
4 * Copyright (C) 2008 Sun Microsystems, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20#pragma once
21
22#include <cstdlib>
23#include <cassert>
24#include <utility>
25#include <algorithm>
26#include <drizzled/memory/sql_alloc.h>
27#include <drizzled/visibility.h>
28
29namespace drizzled {
30
31struct SQL_LIST
32{
33 uint32_t elements;
34 unsigned char *first;
35 unsigned char **next;
36
37 void clear()
38 {
39 elements=0;
40 first=0;
41 next= &first;
42 }
43
44 size_t size() const
45 {
46 return elements;
47 }
48
49 void link_in_list(unsigned char *element,unsigned char **next_ptr)
50 {
51 elements++;
52 (*next)=element;
53 next= next_ptr;
54 *next=0;
55 }
56 void save_and_clear(SQL_LIST *save)
57 {
58 *save= *this;
59 clear();
60 }
61 void push_front(SQL_LIST *save)
62 {
63 *save->next= first; /* link current list last */
64 first= save->first;
65 elements+= save->elements;
66 }
67 void push_back(SQL_LIST *save)
68 {
69 if (save->first)
70 {
71 *next= save->first;
72 next= save->next;
73 elements+= save->elements;
74 }
75 }
76};
77
78/*
79 Basic single linked list
80 Used for item and item_buffs.
81 All list ends with a pointer to the 'end_of_list' element, which
82 data pointer is a null pointer and the next pointer points to itself.
83 This makes it very fast to traverse lists as we don't have to
84 test for a specialend condition for list that can't contain a null
85 pointer.
86*/
87
88
93
94struct list_node : public memory::SqlAlloc
95{
96 list_node *next;
97 void *info;
98 list_node(void *info_par,list_node *next_par)
99 :next(next_par),info(info_par)
100 {}
101 list_node() /* For end_of_list */
102 {
103 info= 0;
104 next= this;
105 }
106};
107
108extern DRIZZLED_API list_node end_of_list;
109
110class base_list :public memory::SqlAlloc
111{
112protected:
113 list_node *first,**last;
114 uint32_t elements;
115public:
116
117 void clear() { elements=0; first= &end_of_list; last=&first;}
118 base_list() { clear(); }
128 base_list(const base_list &tmp) :memory::SqlAlloc()
129 {
130 elements= tmp.elements;
131 first= tmp.first;
132 last= elements ? tmp.last : &first;
133 }
134 base_list& operator=(const base_list &tmp)
135 {
136 elements= tmp.elements;
137 first= tmp.first;
138 last= elements ? tmp.last : &first;
139 return *this;
140 }
141 base_list(bool) { }
142 void push_back(void *info)
143 {
144 *last = new list_node(info, &end_of_list);
145 last= &(*last)->next;
146 elements++;
147 }
148 void push_back(void *info, memory::Root& mem)
149 {
150 *last = new (mem) list_node(info, &end_of_list);
151 last= &(*last)->next;
152 elements++;
153 }
154 void push_front(void *info)
155 {
156 list_node *node=new list_node(info,first);
157 if (last == &first)
158 last= &node->next;
159 first=node;
160 elements++;
161 }
162 void remove(list_node **prev)
163 {
164 list_node *node=(*prev)->next;
165 if (!--elements)
166 last= &first;
167 else if (last == &(*prev)->next)
168 last= prev;
169 delete *prev;
170 *prev=node;
171 }
172 void concat(base_list *list)
173 {
174 if (!list->is_empty())
175 {
176 *last= list->first;
177 last= list->last;
178 elements+= list->elements;
179 }
180 }
181 void *pop()
182 {
183 if (first == &end_of_list) return 0;
184 list_node *tmp=first;
185 first=first->next;
186 if (!--elements)
187 last= &first;
188 return tmp->info;
189 }
190 void disjoin(base_list *list)
191 {
192 list_node **prev= &first;
193 list_node *node= first;
194 list_node *list_first= list->first;
195 elements=0;
196 while (node && node != list_first)
197 {
198 prev= &node->next;
199 node= node->next;
200 elements++;
201 }
202 *prev= *last;
203 last= prev;
204 }
205 void prepand(base_list *list)
206 {
207 if (!list->is_empty())
208 {
209 *list->last= first;
210 first= list->first;
211 elements+= list->elements;
212 }
213 }
217 void swap(base_list &rhs)
218 {
219 std::swap(first, rhs.first);
220 std::swap(last, rhs.last);
221 std::swap(elements, rhs.elements);
222 }
223 bool is_empty() { return first == &end_of_list ; }
224 friend class base_list_iterator;
225
226#ifdef LIST_EXTRA_DEBUG
227 /*
228 Check list invariants and print results into trace. Invariants are:
229 - (*last) points to end_of_list
230 - There are no NULLs in the list.
231 - base_list::elements is the number of elements in the list.
232
233 SYNOPSIS
234 check_list()
235 name Name to print to trace file
236
237 RETURN
238 1 The list is Ok.
239 0 List invariants are not met.
240 */
241
242 bool check_list(const char *name)
243 {
244 list_node *node= first;
245 uint32_t cnt= 0;
246
247 while (node->next != &end_of_list)
248 {
249 if (!node->info)
250 {
251 return false;
252 }
253 node= node->next;
254 cnt++;
255 }
256 if (last != &(node->next))
257 {
258 return false;
259 }
260 if (cnt+1 != elements)
261 {
262 return false;
263 }
264 return true;
265 }
266#endif // LIST_EXTRA_DEBUG
267
268protected:
269 void after(void *info,list_node *node)
270 {
271 list_node *new_node=new list_node(info,node->next);
272 node->next=new_node;
273 elements++;
274 if (last == &(node->next))
275 last= &new_node->next;
276 }
277};
278
279
280class base_list_iterator
281{
282protected:
283 base_list *list;
284 list_node **el,**prev,*current;
285public:
286 void sublist(base_list &ls, uint32_t elm) const
287 {
288 ls.first= *el;
289 ls.last= list->last;
290 ls.elements= elm;
291 }
292 base_list_iterator()
293 :list(0), el(0), prev(0), current(0)
294 {}
295
296 base_list_iterator(base_list &list_par, list_node** el0)
297 :list(&list_par), el(el0), prev(0), current(0)
298 {
299 }
300
301 void *replace(base_list &new_list)
302 {
303 void *ret_value=current->info;
304 if (!new_list.is_empty())
305 {
306 *new_list.last=current->next;
307 current->info=new_list.first->info;
308 current->next=new_list.first->next;
309 if (list->last == &current->next && new_list.elements > 1)
310 list->last= new_list.last;
311 list->elements+=new_list.elements-1;
312 }
313 return ret_value; // return old element
314 }
315 void remove() // Remove current
316 {
317 list->remove(prev);
318 el=prev;
319 current=0; // Safeguard
320 }
321 void after(void *element) // Insert element after current
322 {
323 list->after(element,current);
324 current=current->next;
325 el= &current->next;
326 }
327};
328
329template <class T> class List_iterator;
330
331template <class T> class List : public base_list
332{
333public:
334 typedef List_iterator<T> iterator;
335
336 friend class List_iterator<T>;
337
338 List() {}
339 List(const List<T> &tmp) : base_list(tmp) {}
340 List<T>& operator=(const List<T> &tmp)
341 {
342 base_list::operator=(tmp);
343 return *this;
344 }
345 List(const List<T> &tmp, memory::Root *mem_root) : base_list(tmp, mem_root) {}
346 T& front() {return *static_cast<T*>(first->info); }
347 T* pop() {return static_cast<T*>(base_list::pop()); }
348 void concat(List<T> *list) { base_list::concat(list); }
349 void disjoin(List<T> *list) { base_list::disjoin(list); }
350 void prepand(List<T> *list) { base_list::prepand(list); }
351 void delete_elements()
352 {
353 list_node *element,*next;
354 for (element=first; element != &end_of_list; element=next)
355 {
356 next=element->next;
357 delete (T*) element->info;
358 }
359 clear();
360 }
361
362 iterator begin()
363 {
364 return iterator(*this, &first);
365 }
366
367 size_t size() const
368 {
369 return elements;
370 }
371
372 void set_size(size_t v)
373 {
374 elements = v;
375 }
376};
377
378template <class T> class List_iterator : public base_list_iterator
379{
380public:
381 List_iterator(List<T>& a, list_node** b) : base_list_iterator(a, b) {};
382 List_iterator() {};
383 T *operator++(int) { prev=el; current= *el; el= &current->next; return (T*)current->info; }
384 T *replace(T *a) { T* old = (T*) current->info; current->info= a; return old; }
385 void replace(List<T> &a) { base_list_iterator::replace(a); }
386 T** ref() { return (T**) &current->info; }
387
388 T& operator*()
389 {
390 return *(T*)current->info;
391 }
392
393 T* operator->()
394 {
395 return (T*)current->info;
396 }
397};
398
399} /* namespace drizzled */
base_list(const base_list &tmp)
Definition sql_list.h:128
void swap(base_list &rhs)
Definition sql_list.h:217
TODO: Rename this file - func.h is stupid.
Visibility Control Macros.
#define DRIZZLED_API
Definition visibility.h:38