Drizzled Public API Documentation

sql_list.h
00001 /* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  *
00004  *  Copyright (C) 2008 Sun Microsystems, Inc.
00005  *
00006  *  This program is free software; you can redistribute it and/or modify
00007  *  it under the terms of the GNU General Public License as published by
00008  *  the Free Software Foundation; version 2 of the License.
00009  *
00010  *  This program is distributed in the hope that it will be useful,
00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  *  GNU General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU General Public License
00016  *  along with this program; if not, write to the Free Software
00017  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
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;       /* link current list last */
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   Basic single linked list
00080   Used for item and item_buffs.
00081   All list ends with a pointer to the 'end_of_list' element, which
00082   data pointer is a null pointer and the next pointer points to itself.
00083   This makes it very fast to traverse lists as we don't have to
00084   test for a specialend condition for list that can't contain a null
00085   pointer.
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()         /* For end_of_list */
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     Check list invariants and print results into trace. Invariants are:
00235       - (*last) points to end_of_list
00236       - There are no NULLs in the list.
00237       - base_list::elements is the number of elements in the list.
00238 
00239     SYNOPSIS
00240       check_list()
00241         name  Name to print to trace file
00242 
00243     RETURN
00244       1  The list is Ok.
00245       0  List invariants are not met.
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 == &current->next && new_list.elements > 1)
00317         list->last= new_list.last;
00318       list->elements+=new_list.elements-1;
00319     }
00320     return ret_value;       // return old element
00321   }
00322   void remove()     // Remove current
00323   {
00324     list->remove(prev);
00325     el=prev;
00326     current=0;          // Safeguard
00327   }
00328   void after(void *element)     // Insert element after current
00329   {
00330     list->after(element,current);
00331     current=current->next;
00332     el= &current->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= &current->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**) &current->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 } /* namespace drizzled */
00405