Drizzled Public API Documentation

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 
29 namespace drizzled {
30 
31 struct 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 
94 struct 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 
108 extern DRIZZLED_API list_node end_of_list;
109 
111 {
112 protected:
113  list_node *first,**last;
114  uint32_t elements;
115 public:
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(bool) { }
135  void push_back(void *info)
136  {
137  *last = new list_node(info, &end_of_list);
138  last= &(*last)->next;
139  elements++;
140  }
141  void push_back(void *info, memory::Root& mem)
142  {
143  *last = new (mem) list_node(info, &end_of_list);
144  last= &(*last)->next;
145  elements++;
146  }
147  void push_front(void *info)
148  {
149  list_node *node=new list_node(info,first);
150  if (last == &first)
151  last= &node->next;
152  first=node;
153  elements++;
154  }
155  void remove(list_node **prev)
156  {
157  list_node *node=(*prev)->next;
158  if (!--elements)
159  last= &first;
160  else if (last == &(*prev)->next)
161  last= prev;
162  delete *prev;
163  *prev=node;
164  }
165  void concat(base_list *list)
166  {
167  if (!list->is_empty())
168  {
169  *last= list->first;
170  last= list->last;
171  elements+= list->elements;
172  }
173  }
174  void *pop()
175  {
176  if (first == &end_of_list) return 0;
177  list_node *tmp=first;
178  first=first->next;
179  if (!--elements)
180  last= &first;
181  return tmp->info;
182  }
183  void disjoin(base_list *list)
184  {
185  list_node **prev= &first;
186  list_node *node= first;
187  list_node *list_first= list->first;
188  elements=0;
189  while (node && node != list_first)
190  {
191  prev= &node->next;
192  node= node->next;
193  elements++;
194  }
195  *prev= *last;
196  last= prev;
197  }
198  void prepand(base_list *list)
199  {
200  if (!list->is_empty())
201  {
202  *list->last= first;
203  first= list->first;
204  elements+= list->elements;
205  }
206  }
210  void swap(base_list &rhs)
211  {
212  std::swap(first, rhs.first);
213  std::swap(last, rhs.last);
214  std::swap(elements, rhs.elements);
215  }
216  bool is_empty() { return first == &end_of_list ; }
217  friend class base_list_iterator;
218 
219 #ifdef LIST_EXTRA_DEBUG
220  /*
221  Check list invariants and print results into trace. Invariants are:
222  - (*last) points to end_of_list
223  - There are no NULLs in the list.
224  - base_list::elements is the number of elements in the list.
225 
226  SYNOPSIS
227  check_list()
228  name Name to print to trace file
229 
230  RETURN
231  1 The list is Ok.
232  0 List invariants are not met.
233  */
234 
235  bool check_list(const char *name)
236  {
237  list_node *node= first;
238  uint32_t cnt= 0;
239 
240  while (node->next != &end_of_list)
241  {
242  if (!node->info)
243  {
244  return false;
245  }
246  node= node->next;
247  cnt++;
248  }
249  if (last != &(node->next))
250  {
251  return false;
252  }
253  if (cnt+1 != elements)
254  {
255  return false;
256  }
257  return true;
258  }
259 #endif // LIST_EXTRA_DEBUG
260 
261 protected:
262  void after(void *info,list_node *node)
263  {
264  list_node *new_node=new list_node(info,node->next);
265  node->next=new_node;
266  elements++;
267  if (last == &(node->next))
268  last= &new_node->next;
269  }
270 };
271 
272 
274 {
275 protected:
276  base_list *list;
277  list_node **el,**prev,*current;
278 public:
279  void sublist(base_list &ls, uint32_t elm) const
280  {
281  ls.first= *el;
282  ls.last= list->last;
283  ls.elements= elm;
284  }
286  :list(0), el(0), prev(0), current(0)
287  {}
288 
289  base_list_iterator(base_list &list_par, list_node** el0)
290  :list(&list_par), el(el0), prev(0), current(0)
291  {
292  }
293 
294  void *replace(base_list &new_list)
295  {
296  void *ret_value=current->info;
297  if (!new_list.is_empty())
298  {
299  *new_list.last=current->next;
300  current->info=new_list.first->info;
301  current->next=new_list.first->next;
302  if (list->last == &current->next && new_list.elements > 1)
303  list->last= new_list.last;
304  list->elements+=new_list.elements-1;
305  }
306  return ret_value; // return old element
307  }
308  void remove() // Remove current
309  {
310  list->remove(prev);
311  el=prev;
312  current=0; // Safeguard
313  }
314  void after(void *element) // Insert element after current
315  {
316  list->after(element,current);
317  current=current->next;
318  el= &current->next;
319  }
320 };
321 
322 template <class T> class List_iterator;
323 
324 template <class T> class List : public base_list
325 {
326 public:
327  typedef List_iterator<T> iterator;
328 
329  friend class List_iterator<T>;
330 
331  List() {}
332  List(const List<T> &tmp) : base_list(tmp) {}
333  List(const List<T> &tmp, memory::Root *mem_root) : base_list(tmp, mem_root) {}
334  T& front() {return *static_cast<T*>(first->info); }
335  T* pop() {return static_cast<T*>(base_list::pop()); }
336  void concat(List<T> *list) { base_list::concat(list); }
337  void disjoin(List<T> *list) { base_list::disjoin(list); }
338  void prepand(List<T> *list) { base_list::prepand(list); }
339  void delete_elements()
340  {
341  list_node *element,*next;
342  for (element=first; element != &end_of_list; element=next)
343  {
344  next=element->next;
345  delete (T*) element->info;
346  }
347  clear();
348  }
349 
350  iterator begin()
351  {
352  return iterator(*this, &first);
353  }
354 
355  size_t size() const
356  {
357  return elements;
358  }
359 
360  void set_size(size_t v)
361  {
362  elements = v;
363  }
364 };
365 
366 template <class T> class List_iterator : public base_list_iterator
367 {
368 public:
370  List_iterator() {};
371  T *operator++(int) { prev=el; current= *el; el= &current->next; return (T*)current->info; }
372  T *replace(T *a) { T* old = (T*) current->info; current->info= a; return old; }
373  void replace(List<T> &a) { base_list_iterator::replace(a); }
374  T** ref() { return (T**) &current->info; }
375 
376  T& operator*()
377  {
378  return *(T*)current->info;
379  }
380 
381  T* operator->()
382  {
383  return (T*)current->info;
384  }
385 };
386 
387 } /* namespace drizzled */
388 
void swap(base_list &rhs)
Definition: sql_list.h:210
TODO: Rename this file - func.h is stupid.
#define DRIZZLED_API
Definition: visibility.h:62
Visibility Control Macros.
base_list(const base_list &tmp)
Definition: sql_list.h:128