00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #pragma once
00021
00022 #include <cstdlib>
00023 #include <cassert>
00024 #include <utility>
00025 #include <algorithm>
00026 #include <drizzled/memory/sql_alloc.h>
00027 #include <drizzled/visibility.h>
00028
00029 namespace drizzled {
00030
00031 typedef struct st_sql_list
00032 {
00033 uint32_t elements;
00034 unsigned char *first;
00035 unsigned char **next;
00036
00037 void clear()
00038 {
00039 elements=0;
00040 first=0;
00041 next= &first;
00042 }
00043
00044 size_t size() const
00045 {
00046 return elements;
00047 }
00048
00049 void link_in_list(unsigned char *element,unsigned char **next_ptr)
00050 {
00051 elements++;
00052 (*next)=element;
00053 next= next_ptr;
00054 *next=0;
00055 }
00056 void save_and_clear(struct st_sql_list *save)
00057 {
00058 *save= *this;
00059 clear();
00060 }
00061 void push_front(struct st_sql_list *save)
00062 {
00063 *save->next= first;
00064 first= save->first;
00065 elements+= save->elements;
00066 }
00067 void push_back(struct st_sql_list *save)
00068 {
00069 if (save->first)
00070 {
00071 *next= save->first;
00072 next= save->next;
00073 elements+= save->elements;
00074 }
00075 }
00076 } SQL_LIST;
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00094 struct list_node : public memory::SqlAlloc
00095 {
00096 list_node *next;
00097 void *info;
00098 list_node(void *info_par,list_node *next_par)
00099 :next(next_par),info(info_par)
00100 {}
00101 list_node()
00102 {
00103 info= 0;
00104 next= this;
00105 }
00106 };
00107
00108 extern DRIZZLED_API list_node end_of_list;
00109
00110 class base_list :public memory::SqlAlloc
00111 {
00112 protected:
00113 list_node *first,**last;
00114 uint32_t elements;
00115 public:
00116
00117 void clear() { elements=0; first= &end_of_list; last=&first;}
00118 base_list() { clear(); }
00128 base_list(const base_list &tmp) :memory::SqlAlloc()
00129 {
00130 elements= tmp.elements;
00131 first= tmp.first;
00132 last= elements ? tmp.last : &first;
00133 }
00134 base_list(bool) { }
00135 bool push_back(void *info)
00136 {
00137 if (((*last)=new list_node(info, &end_of_list)))
00138 {
00139 last= &(*last)->next;
00140 elements++;
00141 return 0;
00142 }
00143 return 1;
00144 }
00145 bool push_back(void *info, memory::Root *mem_root)
00146 {
00147 if (((*last)=new (mem_root) list_node(info, &end_of_list)))
00148 {
00149 last= &(*last)->next;
00150 elements++;
00151 return 0;
00152 }
00153 return 1;
00154 }
00155 bool push_front(void *info)
00156 {
00157 list_node *node=new list_node(info,first);
00158 if (node)
00159 {
00160 if (last == &first)
00161 last= &node->next;
00162 first=node;
00163 elements++;
00164 return 0;
00165 }
00166 return 1;
00167 }
00168 void remove(list_node **prev)
00169 {
00170 list_node *node=(*prev)->next;
00171 if (!--elements)
00172 last= &first;
00173 else if (last == &(*prev)->next)
00174 last= prev;
00175 delete *prev;
00176 *prev=node;
00177 }
00178 void concat(base_list *list)
00179 {
00180 if (!list->is_empty())
00181 {
00182 *last= list->first;
00183 last= list->last;
00184 elements+= list->elements;
00185 }
00186 }
00187 void *pop()
00188 {
00189 if (first == &end_of_list) return 0;
00190 list_node *tmp=first;
00191 first=first->next;
00192 if (!--elements)
00193 last= &first;
00194 return tmp->info;
00195 }
00196 void disjoin(base_list *list)
00197 {
00198 list_node **prev= &first;
00199 list_node *node= first;
00200 list_node *list_first= list->first;
00201 elements=0;
00202 while (node && node != list_first)
00203 {
00204 prev= &node->next;
00205 node= node->next;
00206 elements++;
00207 }
00208 *prev= *last;
00209 last= prev;
00210 }
00211 void prepand(base_list *list)
00212 {
00213 if (!list->is_empty())
00214 {
00215 *list->last= first;
00216 first= list->first;
00217 elements+= list->elements;
00218 }
00219 }
00223 void swap(base_list &rhs)
00224 {
00225 std::swap(first, rhs.first);
00226 std::swap(last, rhs.last);
00227 std::swap(elements, rhs.elements);
00228 }
00229 bool is_empty() { return first == &end_of_list ; }
00230 friend class base_list_iterator;
00231
00232 #ifdef LIST_EXTRA_DEBUG
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248 bool check_list(const char *name)
00249 {
00250 base_list *list= this;
00251 list_node *node= first;
00252 uint32_t cnt= 0;
00253
00254 while (node->next != &end_of_list)
00255 {
00256 if (!node->info)
00257 {
00258 return false;
00259 }
00260 node= node->next;
00261 cnt++;
00262 }
00263 if (last != &(node->next))
00264 {
00265 return false;
00266 }
00267 if (cnt+1 != elements)
00268 {
00269 return false;
00270 }
00271 return true;
00272 }
00273 #endif // LIST_EXTRA_DEBUG
00274
00275 protected:
00276 void after(void *info,list_node *node)
00277 {
00278 list_node *new_node=new list_node(info,node->next);
00279 node->next=new_node;
00280 elements++;
00281 if (last == &(node->next))
00282 last= &new_node->next;
00283 }
00284 };
00285
00286
00287 class base_list_iterator
00288 {
00289 protected:
00290 base_list *list;
00291 list_node **el,**prev,*current;
00292 public:
00293 void sublist(base_list &ls, uint32_t elm)
00294 {
00295 ls.first= *el;
00296 ls.last= list->last;
00297 ls.elements= elm;
00298 }
00299 base_list_iterator()
00300 :list(0), el(0), prev(0), current(0)
00301 {}
00302
00303 base_list_iterator(base_list &list_par, list_node** el0)
00304 :list(&list_par), el(el0), prev(0), current(0)
00305 {
00306 }
00307
00308 void *replace(base_list &new_list)
00309 {
00310 void *ret_value=current->info;
00311 if (!new_list.is_empty())
00312 {
00313 *new_list.last=current->next;
00314 current->info=new_list.first->info;
00315 current->next=new_list.first->next;
00316 if (list->last == ¤t->next && new_list.elements > 1)
00317 list->last= new_list.last;
00318 list->elements+=new_list.elements-1;
00319 }
00320 return ret_value;
00321 }
00322 void remove()
00323 {
00324 list->remove(prev);
00325 el=prev;
00326 current=0;
00327 }
00328 void after(void *element)
00329 {
00330 list->after(element,current);
00331 current=current->next;
00332 el= ¤t->next;
00333 }
00334 };
00335
00336 template <class T> class List_iterator;
00337
00338 template <class T> class List : public base_list
00339 {
00340 public:
00341 typedef List_iterator<T> iterator;
00342
00343 friend class List_iterator<T>;
00344
00345 List() {}
00346 List(const List<T> &tmp) : base_list(tmp) {}
00347 List(const List<T> &tmp, memory::Root *mem_root) : base_list(tmp, mem_root) {}
00348 bool push_back(T *a) { return base_list::push_back(a); }
00349 bool push_back(T *a, memory::Root *mem_root) { return base_list::push_back(a, mem_root); }
00350 bool push_front(T *a) { return base_list::push_front(a); }
00351 T& front() {return *static_cast<T*>(first->info); }
00352 T* pop() {return static_cast<T*>(base_list::pop()); }
00353 void concat(List<T> *list) { base_list::concat(list); }
00354 void disjoin(List<T> *list) { base_list::disjoin(list); }
00355 void prepand(List<T> *list) { base_list::prepand(list); }
00356 void delete_elements()
00357 {
00358 list_node *element,*next;
00359 for (element=first; element != &end_of_list; element=next)
00360 {
00361 next=element->next;
00362 delete (T*) element->info;
00363 }
00364 clear();
00365 }
00366
00367 iterator begin()
00368 {
00369 return iterator(*this, &first);
00370 }
00371
00372 size_t size() const
00373 {
00374 return elements;
00375 }
00376
00377 void set_size(size_t v)
00378 {
00379 elements = v;
00380 }
00381 };
00382
00383 template <class T> class List_iterator : public base_list_iterator
00384 {
00385 public:
00386 List_iterator(List<T>& a, list_node** b) : base_list_iterator(a, b) {};
00387 List_iterator() {};
00388 T *operator++(int) { prev=el; current= *el; el= ¤t->next; return (T*)current->info; }
00389 T *replace(T *a) { T* old = (T*) current->info; current->info= a; return old; }
00390 void replace(List<T> &a) { base_list_iterator::replace(a); }
00391 T** ref() { return (T**) ¤t->info; }
00392
00393 T& operator*()
00394 {
00395 return *(T*)current->info;
00396 }
00397
00398 T* operator->()
00399 {
00400 return (T*)current->info;
00401 }
00402 };
00403
00404 }
00405