home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / sql / sql_list.h < prev    next >
C/C++ Source or Header  |  2000-09-13  |  8KB  |  311 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This program is free software; you can redistribute it and/or modify
  4.    it under the terms of the GNU General Public License as published by
  5.    the Free Software Foundation; either version 2 of the License, or
  6.    (at your option) any later version.
  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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  16.  
  17.  
  18. /* mysql standard open memoryallocator */
  19.  
  20. #ifdef __GNUC__
  21. #pragma interface            /* gcc class implementation */
  22. #endif
  23.  
  24.  
  25. class Sql_alloc
  26. {
  27. public:
  28.   static void *operator new(size_t size) {return (void*) sql_alloc((uint) size); }
  29.   static void operator delete(void *ptr, size_t size) {} /*lint -e715 */
  30.   inline Sql_alloc() {};
  31.   inline ~Sql_alloc() {};
  32. };
  33.  
  34. /*
  35. ** basic single linked list
  36. ** Used for item and item_buffs.
  37. */
  38.  
  39. class base_list :public Sql_alloc {
  40. protected:
  41.   class list_node :public Sql_alloc
  42.   {
  43.   public:
  44.     list_node *next;
  45.     void *info;
  46.     list_node(void *info_par,list_node *next_par) : next(next_par),info(info_par) {}
  47.     friend class base_list;
  48.     friend class base_list_iterator;
  49.   };
  50.   list_node *first,**last;
  51.  
  52. public:
  53.   uint elements;
  54.  
  55.   inline void empty() { elements=0; first=0; last=&first;}
  56.   inline base_list() { empty(); }
  57.   inline base_list(const base_list &tmp) :Sql_alloc()
  58.   {
  59.     elements=tmp.elements;
  60.     first=tmp.first;
  61.     last=tmp.last;
  62.   }
  63.   inline bool push_back(void *info)
  64.   {
  65.     if (((*last)=new list_node(info,0)))
  66.     {
  67.       last= &(*last)->next;
  68.       elements++;
  69.       return 0;
  70.     }
  71.     return 1;
  72.   }
  73.   inline bool push_front(void *info)
  74.   {
  75.     list_node *node=new list_node(info,first);
  76.     if (node)
  77.     {
  78.       if (!first)
  79.     last= &node->next;
  80.       first=node;
  81.       elements++;
  82.       return 0;
  83.     }
  84.     return 1;
  85.   }
  86.   void remove(list_node **prev)
  87.   {
  88.     list_node *node=(*prev)->next;
  89.     delete *prev;
  90.     *prev=node;
  91.     if (!--elements)
  92.     {
  93.       last= &first;
  94.       first=0;
  95.     }
  96.   }
  97.   inline void *pop(void)
  98.   {
  99.     if (!first) return 0;
  100.     list_node *tmp=first;
  101.     first=first->next;
  102.     if (!--elements)
  103.       last= &first;
  104.     return tmp->info;
  105.   }
  106.   inline void *head() { return first ? first->info : 0; }
  107.   inline void **head_ref() { return first ? &first->info : 0; }
  108.   friend class base_list_iterator;
  109.  
  110. protected:
  111.   void after(void *info,list_node *node)
  112.   {
  113.     list_node *new_node=new list_node(info,node->next);
  114.     node->next=new_node;
  115.     elements++;
  116.     if (last == &(node->next))
  117.       last= &new_node->next;
  118.   }
  119. };
  120.  
  121.  
  122. class base_list_iterator
  123. {
  124.   base_list *list;
  125.   base_list::list_node **el,**prev,*current;
  126. public:
  127.   base_list_iterator(base_list &list_par) :list(&list_par),el(&list_par.first),
  128.     prev(0),current(0)
  129.   {}
  130.   inline void *next(void)
  131.   {
  132.     prev=el;
  133.     if (!(current= *el))
  134.       return 0;
  135.     el= ¤t->next;
  136.     return current->info;
  137.   }
  138.   inline void rewind(void)
  139.   {
  140.     el= &list->first;
  141.   }
  142.   void *replace(void *element)
  143.   {                        // Return old element
  144.     void *tmp=current->info;
  145.     current->info=element;
  146.     return tmp;
  147.   }
  148.   void *replace(base_list &new_list)
  149.   {
  150.     void *ret_value=current->info;
  151.     if (new_list.first)
  152.     {
  153.       *new_list.last=current->next;
  154.       current->info=new_list.first->info;
  155.       current->next=new_list.first->next;
  156.       list->elements+=new_list.elements-1;
  157.     }
  158.     return ret_value;                // return old element
  159.   }
  160.   inline void remove(void)            // Remove current
  161.   {
  162.     list->remove(prev);
  163.     el=prev;
  164.     current=0;                    // Safeguard
  165.   }
  166.   void after(void *element)            // Insert element after current
  167.   {
  168.     list->after(element,current);
  169.     current=current->next;
  170.     el= ¤t->next;
  171.   }
  172.   inline void **ref(void)            // Get reference pointer
  173.   {
  174.     return ¤t->info;
  175.   }
  176.   inline bool is_last(void)
  177.   {
  178.     return *el == 0;
  179.   }
  180. };
  181.  
  182.  
  183. template <class T> class List :public base_list
  184. {
  185. public:
  186.   inline List() :base_list() {}
  187.   inline List(const List<T> &tmp) :base_list(tmp) {}
  188.   inline bool push_back(T *a) { return base_list::push_back(a); }
  189.   inline bool push_front(T *a) { return base_list::push_front(a); }
  190.   inline T* head() {return (T*) base_list::head(); }
  191.   inline T** head_ref() {return (T**) base_list::head_ref(); }
  192.   inline T* pop()  {return (T*) base_list::pop(); }
  193.   void delete_elements(void)
  194.   {
  195.     list_node *element,*next;
  196.     for (element=first; element ; element=next)
  197.     {
  198.       next=element->next;
  199.       delete (T*) element->info;
  200.     }
  201.     empty();
  202.   }
  203. };
  204.  
  205.  
  206. template <class T> class List_iterator :public base_list_iterator
  207. {
  208. public:
  209.   List_iterator(List<T> &a) : base_list_iterator(a) {}
  210.   inline T* operator++(int) { return (T*) base_list_iterator::next(); }
  211.   inline void rewind(void)  { base_list_iterator::rewind(); }
  212.   inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
  213.   inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
  214.   inline void remove(void)  { base_list_iterator::remove(); }
  215.   inline void after(T *a)   { base_list_iterator::after(a); }
  216.   inline T** ref(void)        { return (T**) base_list_iterator::ref(); }
  217.   inline bool is_last(void) { return base_list_iterator::is_last(); }
  218. };
  219.  
  220.  
  221. /*
  222. ** An simple intrusive list with automaticly removes element from list
  223. ** on delete (for THD element)
  224. */
  225.  
  226. struct ilink {
  227.   struct ilink **prev,*next;
  228.   inline ilink()
  229.   {
  230.     prev=0; next=0;
  231.   }
  232.   inline void unlink()
  233.   {
  234.     /* Extra tests because element doesn't have to be linked */
  235.     if (prev) *prev= next;
  236.     if (next) next->prev=prev;
  237.     prev=0 ; next=0;
  238.   }
  239.   virtual ~ilink() { unlink(); }        /*lint -e1740 */
  240. };
  241.  
  242. template <class T> class I_List_iterator;
  243.  
  244. class base_ilist {
  245.   public:
  246.   struct ilink *first,last;
  247.   base_ilist() { first= &last; last.prev= &first; }
  248.   inline bool is_empty() {  return first == &last; }
  249.   inline void append(ilink *a)
  250.   {
  251.     first->prev= &a->next;
  252.     a->next=first; a->prev= &first; first=a;
  253.   }
  254.   inline void push_back(ilink *a)
  255.   {
  256.     *last.prev= a;
  257.     a->next= &last;
  258.     a->prev= last.prev;
  259.     last.prev= &a->next;
  260.   }
  261.   inline struct ilink *get()
  262.   {
  263.     struct ilink *first_link=first;
  264.     if (first_link == &last)
  265.       return 0;
  266.     first_link->unlink();            // Unlink from list
  267.     return first_link;
  268.   }
  269.   friend class base_list_iterator;
  270. };
  271.  
  272.  
  273. class base_ilist_iterator
  274. {
  275.   base_ilist *list;
  276.   struct ilink **el,*current;
  277. public:
  278.   base_ilist_iterator(base_ilist &list_par) :list(&list_par),
  279.     el(&list_par.first),current(0) {}
  280.   void *next(void)
  281.   {
  282.     /* This is coded to allow push_back() while iterating */
  283.     current= *el;
  284.     if (current == &list->last) return 0;
  285.     el= ¤t->next;
  286.     return current;
  287.   }
  288. };
  289.  
  290.  
  291. template <class T>
  292. class I_List :private base_ilist {
  293. public:
  294.   I_List() :base_ilist()    {}
  295.   inline bool is_empty()        { return base_ilist::is_empty(); } 
  296.   inline void append(T* a)    { base_ilist::append(a); }
  297.   inline void push_back(T* a)    { base_ilist::push_back(a); }
  298.   inline T* get()        { return (T*) base_ilist::get(); }
  299. #ifndef _lint
  300.   friend class I_List_iterator<T>;
  301. #endif
  302. };
  303.  
  304.  
  305. template <class T> class I_List_iterator :public base_ilist_iterator
  306. {
  307. public:
  308.   I_List_iterator(I_List<T> &a) : base_ilist_iterator(a) {}
  309.   inline T* operator++(int) { return (T*) base_ilist_iterator::next(); }
  310. };
  311.