sql_list.h
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:12k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2000-2003 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. #ifdef USE_PRAGMA_INTERFACE
  14. #pragma interface /* gcc class implementation */
  15. #endif
  16. /* mysql standard class memory allocator */
  17. #ifdef SAFEMALLOC
  18. #define TRASH(XX,YY) bfill((XX), (YY), 0x8F)
  19. #else
  20. #define TRASH(XX,YY) /* no-op */
  21. #endif
  22. class Sql_alloc
  23. {
  24. public:
  25.   static void *operator new(size_t size)
  26.   {
  27.     return (void*) sql_alloc((uint) size);
  28.   }
  29.   static void *operator new[](size_t size)
  30.   {
  31.     return (void*) sql_alloc((uint) size);
  32.   }
  33.   static void *operator new(size_t size, MEM_ROOT *mem_root)
  34.   { return (void*) alloc_root(mem_root, (uint) size); }
  35.   static void operator delete(void *ptr, size_t size) { TRASH(ptr, size); }
  36.   static void operator delete(void *ptr, MEM_ROOT *mem_root)
  37.   { /* never called */ }
  38.   static void operator delete[](void *ptr, size_t size) { TRASH(ptr, size); }
  39. #ifdef HAVE_purify
  40.   bool dummy;
  41.   inline Sql_alloc() :dummy(0) {}
  42.   inline ~Sql_alloc() {}
  43. #else
  44.   inline Sql_alloc() {}
  45.   inline ~Sql_alloc() {}
  46. #endif
  47. };
  48. /*
  49.   Basic single linked list
  50.   Used for item and item_buffs.
  51.   All list ends with a pointer to the 'end_of_list' element, which
  52.   data pointer is a null pointer and the next pointer points to itself.
  53.   This makes it very fast to traverse lists as we don't have to
  54.   test for a specialend condition for list that can't contain a null
  55.   pointer.
  56. */
  57. class list_node :public Sql_alloc
  58. {
  59. public:
  60.   list_node *next;
  61.   void *info;
  62.   list_node(void *info_par,list_node *next_par)
  63.     :next(next_par),info(info_par)
  64.     {}
  65.   list_node() /* For end_of_list */
  66.     {
  67.       info=0;
  68.       next= this;
  69.     }
  70.   friend class base_list;
  71.   friend class base_list_iterator;
  72. };
  73. extern list_node end_of_list;
  74. class base_list :public Sql_alloc
  75. {
  76. protected:
  77.   list_node *first,**last;
  78. public:
  79.   uint elements;
  80.   inline void empty() { elements=0; first= &end_of_list; last=&first;}
  81.   inline base_list() { empty(); }
  82.   inline base_list(const base_list &tmp) :Sql_alloc()
  83.   {
  84.     elements=tmp.elements;
  85.     first=tmp.first;
  86.     last=tmp.last;
  87.   }
  88.   inline base_list(bool error) { }
  89.   inline bool push_back(void *info)
  90.   {
  91.     if (((*last)=new list_node(info, &end_of_list)))
  92.     {
  93.       last= &(*last)->next;
  94.       elements++;
  95.       return 0;
  96.     }
  97.     return 1;
  98.   }
  99.   inline bool push_front(void *info)
  100.   {
  101.     list_node *node=new list_node(info,first);
  102.     if (node)
  103.     {
  104.       if (last == &first)
  105. last= &node->next;
  106.       first=node;
  107.       elements++;
  108.       return 0;
  109.     }
  110.     return 1;
  111.   }
  112.   void remove(list_node **prev)
  113.   {
  114.     list_node *node=(*prev)->next;
  115.     if (&(*prev)->next == last)
  116.     {
  117.       /*
  118.         We're removing the last element from the list. Adjust "last" to point
  119.         to the previous element.
  120.         The other way to fix this would be to change this function to
  121.         remove_next() and have base_list_iterator save ptr to previous node
  122.         (one extra assignment in iterator++) but as the remove() of the last
  123.         element isn't a common operation it's faster to just walk through the
  124.         list from the beginning here.
  125.       */
  126.       list_node *cur= first;
  127.       if (cur == *prev)
  128.       {
  129.         last= &first;
  130.       }
  131.       else
  132.       {
  133.         while (cur->next != *prev)
  134.           cur= cur->next;
  135.         last= &(cur->next);
  136.       }
  137.     }
  138.     delete *prev;
  139.     *prev=node;
  140.     elements--;
  141.   }
  142.   inline void concat(base_list *list)
  143.   {
  144.     if (!list->is_empty())
  145.     {
  146.       *last= list->first;
  147.       last= list->last;
  148.       elements+= list->elements;
  149.     }
  150.   }
  151.   inline void *pop(void)
  152.   {
  153.     if (first == &end_of_list) return 0;
  154.     list_node *tmp=first;
  155.     first=first->next;
  156.     if (!--elements)
  157.       last= &first;
  158.     return tmp->info;
  159.   }
  160.   inline list_node* last_node() { return *last; }
  161.   inline list_node* first_node() { return first;}
  162.   inline void *head() { return first->info; }
  163.   inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
  164.   inline bool is_empty() { return first == &end_of_list ; }
  165.   inline list_node *last_ref() { return &end_of_list; }
  166.   friend class base_list_iterator;
  167.   friend class error_list;
  168.   friend class error_list_iterator;
  169. #ifdef LIST_EXTRA_DEBUG
  170.   /*
  171.     Check list invariants and print results into trace. Invariants are:
  172.       - (*last) points to end_of_list
  173.       - There are no NULLs in the list.
  174.       - base_list::elements is the number of elements in the list.
  175.     SYNOPSIS
  176.       check_list()
  177.         name  Name to print to trace file
  178.     RETURN 
  179.       1  The list is Ok.
  180.       0  List invariants are not met.
  181.   */
  182.   bool check_list(const char *name)
  183.   {
  184.     base_list *list= this;
  185.     list_node *node= first;
  186.     uint cnt= 0;
  187.     while (node->next != &end_of_list)
  188.     {
  189.       if (!node->info)
  190.       {
  191.         DBUG_PRINT("list_invariants",("%s: error: NULL element in the list", 
  192.                                       name));
  193.         return FALSE;
  194.       }
  195.       node= node->next;
  196.       cnt++;
  197.     }
  198.     if (last != &(node->next))
  199.     {
  200.       DBUG_PRINT("list_invariants", ("%s: error: wrong last pointer", name));
  201.       return FALSE;
  202.     }
  203.     if (cnt+1 != elements)
  204.     {
  205.       DBUG_PRINT("list_invariants", ("%s: error: wrong element count", name));
  206.       return FALSE;
  207.     }
  208.     DBUG_PRINT("list_invariants", ("%s: list is ok", name));
  209.     return TRUE;
  210.   }
  211. #endif // LIST_EXTRA_DEBUG
  212. protected:
  213.   void after(void *info,list_node *node)
  214.   {
  215.     list_node *new_node=new list_node(info,node->next);
  216.     node->next=new_node;
  217.     elements++;
  218.     if (last == &(node->next))
  219.       last= &new_node->next;
  220.   }
  221. };
  222. class base_list_iterator
  223. {
  224. protected:
  225.   base_list *list;
  226.   list_node **el,**prev,*current;
  227.   void sublist(base_list &ls, uint elm)
  228.   {
  229.     ls.first= *el;
  230.     ls.last= list->last;
  231.     ls.elements= elm;
  232.   }
  233. public:
  234.   base_list_iterator(base_list &list_par) 
  235.     :list(&list_par), el(&list_par.first), prev(0), current(0)
  236.   {}
  237.   inline void *next(void)
  238.   {
  239.     prev=el;
  240.     current= *el;
  241.     el= &current->next;
  242.     return current->info;
  243.   }
  244.   inline void *next_fast(void)
  245.   {
  246.     list_node *tmp;
  247.     tmp= *el;
  248.     el= &tmp->next;
  249.     return tmp->info;
  250.   }
  251.   inline void rewind(void)
  252.   {
  253.     el= &list->first;
  254.   }
  255.   inline void *replace(void *element)
  256.   { // Return old element
  257.     void *tmp=current->info;
  258.     DBUG_ASSERT(current->info != 0);
  259.     current->info=element;
  260.     return tmp;
  261.   }
  262.   void *replace(base_list &new_list)
  263.   {
  264.     void *ret_value=current->info;
  265.     if (!new_list.is_empty())
  266.     {
  267.       *new_list.last=current->next;
  268.       current->info=new_list.first->info;
  269.       current->next=new_list.first->next;
  270.       if ((list->last == &current->next) && (new_list.elements > 1))
  271. list->last= new_list.last;
  272.       list->elements+=new_list.elements-1;
  273.     }
  274.     return ret_value; // return old element
  275.   }
  276.   inline void remove(void) // Remove current
  277.   {
  278.     list->remove(prev);
  279.     el=prev;
  280.     current=0; // Safeguard
  281.   }
  282.   void after(void *element) // Insert element after current
  283.   {
  284.     list->after(element,current);
  285.     current=current->next;
  286.     el= &current->next;
  287.   }
  288.   inline void **ref(void) // Get reference pointer
  289.   {
  290.     return &current->info;
  291.   }
  292.   inline bool is_last(void)
  293.   {
  294.     return el == &list->last_ref()->next;
  295.   }
  296.   friend class error_list_iterator;
  297. };
  298. template <class T> class List :public base_list
  299. {
  300. public:
  301.   inline List() :base_list() {}
  302.   inline List(const List<T> &tmp) :base_list(tmp) {}
  303.   inline bool push_back(T *a) { return base_list::push_back(a); }
  304.   inline bool push_front(T *a) { return base_list::push_front(a); }
  305.   inline T* head() {return (T*) base_list::head(); }
  306.   inline T** head_ref() {return (T**) base_list::head_ref(); }
  307.   inline T* pop()  {return (T*) base_list::pop(); }
  308.   void delete_elements(void)
  309.   {
  310.     list_node *element,*next;
  311.     for (element=first; element != &end_of_list; element=next)
  312.     {
  313.       next=element->next;
  314.       delete (T*) element->info;
  315.     }
  316.     empty();
  317.   }
  318. };
  319. template <class T> class List_iterator :public base_list_iterator
  320. {
  321. public:
  322.   List_iterator(List<T> &a) : base_list_iterator(a) {}
  323.   inline T* operator++(int) { return (T*) base_list_iterator::next(); }
  324.   inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
  325.   inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
  326.   inline void after(T *a)   { base_list_iterator::after(a); }
  327.   inline T** ref(void)     { return (T**) base_list_iterator::ref(); }
  328. };
  329. template <class T> class List_iterator_fast :public base_list_iterator
  330. {
  331. protected:
  332.   inline T *replace(T *a)   { return (T*) 0; }
  333.   inline T *replace(List<T> &a) { return (T*) 0; }
  334.   inline void remove(void)  { }
  335.   inline void after(T *a)   { }
  336.   inline T** ref(void)     { return (T**) 0; }
  337. public:
  338.   inline List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
  339.   inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
  340.   inline void rewind(void)  { base_list_iterator::rewind(); }
  341.   void sublist(List<T> &list_arg, uint el_arg)
  342.   {
  343.     base_list_iterator::sublist(list_arg, el_arg);
  344.   }
  345. };
  346. /*
  347.   A simple intrusive list which automaticly removes element from list
  348.   on delete (for THD element)
  349. */
  350. struct ilink
  351. {
  352.   struct ilink **prev,*next;
  353.   static void *operator new(size_t size)
  354.   {
  355.     return (void*)my_malloc((uint)size, MYF(MY_WME | MY_FAE));
  356.   }
  357.   static void operator delete(void* ptr_arg, size_t size)
  358.   {
  359.      my_free((gptr)ptr_arg, MYF(MY_WME|MY_ALLOW_ZERO_PTR));
  360.   }
  361.   inline ilink()
  362.   {
  363.     prev=0; next=0;
  364.   }
  365.   inline void unlink()
  366.   {
  367.     /* Extra tests because element doesn't have to be linked */
  368.     if (prev) *prev= next;
  369.     if (next) next->prev=prev;
  370.     prev=0 ; next=0;
  371.   }
  372.   virtual ~ilink() { unlink(); } /*lint -e1740 */
  373. };
  374. template <class T> class I_List_iterator;
  375. class base_ilist
  376. {
  377.   public:
  378.   struct ilink *first,last;
  379.   inline void empty() { first= &last; last.prev= &first; }
  380.   base_ilist() { empty(); }
  381.   inline bool is_empty() {  return first == &last; }
  382.   inline void append(ilink *a)
  383.   {
  384.     first->prev= &a->next;
  385.     a->next=first; a->prev= &first; first=a;
  386.   }
  387.   inline void push_back(ilink *a)
  388.   {
  389.     *last.prev= a;
  390.     a->next= &last;
  391.     a->prev= last.prev;
  392.     last.prev= &a->next;
  393.   }
  394.   inline struct ilink *get()
  395.   {
  396.     struct ilink *first_link=first;
  397.     if (first_link == &last)
  398.       return 0;
  399.     first_link->unlink(); // Unlink from list
  400.     return first_link;
  401.   }
  402.   inline struct ilink *head()
  403.   {
  404.     return (first != &last) ? first : 0;
  405.   }
  406.   friend class base_list_iterator;
  407. };
  408. class base_ilist_iterator
  409. {
  410.   base_ilist *list;
  411.   struct ilink **el,*current;
  412. public:
  413.   base_ilist_iterator(base_ilist &list_par) :list(&list_par),
  414.     el(&list_par.first),current(0) {}
  415.   void *next(void)
  416.   {
  417.     /* This is coded to allow push_back() while iterating */
  418.     current= *el;
  419.     if (current == &list->last) return 0;
  420.     el= &current->next;
  421.     return current;
  422.   }
  423. };
  424. template <class T>
  425. class I_List :private base_ilist
  426. {
  427. public:
  428.   I_List() :base_ilist() {}
  429.   inline void empty() { base_ilist::empty(); }
  430.   inline bool is_empty()        { return base_ilist::is_empty(); } 
  431.   inline void append(T* a) { base_ilist::append(a); }
  432.   inline void push_back(T* a) { base_ilist::push_back(a); }
  433.   inline T* get() { return (T*) base_ilist::get(); }
  434.   inline T* head() { return (T*) base_ilist::head(); }
  435. #ifndef _lint
  436.   friend class I_List_iterator<T>;
  437. #endif
  438. };
  439. template <class T> class I_List_iterator :public base_ilist_iterator
  440. {
  441. public:
  442.   I_List_iterator(I_List<T> &a) : base_ilist_iterator(a) {}
  443.   inline T* operator++(int) { return (T*) base_ilist_iterator::next(); }
  444. };