1 files changed, 60 insertions, 28 deletions

diff --git a/sql/sql_list.h b/sql/sql_list.h
index b86250f70b6..1486502148f 100644
--- a/sql/sql_list.h
+++ b/sql/sql_list.h
@@ -34,25 +34,40 @@ public:
 /*
 ** basic single linked list
 ** Used for item and item_buffs.
+** All list ends with a pointer to the 'end_of_list' element, which
+** data pointer is a null pointer and the next pointer points to itself.
+** This makes it very fast to traverse lists as we don't have to
+** test for a specialend condition for list that can't contain a null
+** pointer.
 */
 
+class list_node :public Sql_alloc
+{
+public:
+  list_node *next;
+  void *info;
+  list_node(void *info_par,list_node *next_par)
+    :next(next_par),info(info_par)
+    {}
+  list_node()					/* For end_of_list */
+    {
+      info=0;
+      next= this;
+    }
+  friend class base_list;
+  friend class base_list_iterator;
+};
+
+extern list_node end_of_list;
+
 class base_list :public Sql_alloc {
 protected:
-  class list_node :public Sql_alloc
-  {
-  public:
-    list_node *next;
-    void *info;
-    list_node(void *info_par,list_node *next_par) : next(next_par),info(info_par) {}
-    friend class base_list;
-    friend class base_list_iterator;
-  };
   list_node *first,**last;
 
 public:
   uint elements;
 
-  inline void empty() { elements=0; first=0; last=&first;}
+  inline void empty() { elements=0; first= &end_of_list; last=&first;}
   inline base_list() { empty(); }
   inline base_list(const base_list &tmp) :Sql_alloc()
   {
@@ -62,7 +77,7 @@ public:
   }
   inline bool push_back(void *info)
   {
-    if (((*last)=new list_node(info,0)))
+    if (((*last)=new list_node(info, &end_of_list)))
     {
       last= &(*last)->next;
       elements++;
@@ -75,7 +90,7 @@ public:
     list_node *node=new list_node(info,first);
     if (node)
     {
-      if (!first)
+      if (last == &first)
 	last= &node->next;
       first=node;
       elements++;
@@ -89,22 +104,21 @@ public:
     delete *prev;
     *prev=node;
     if (!--elements)
-    {
       last= &first;
-      first=0;
-    }
   }
   inline void *pop(void)
   {
-    if (!first) return 0;
+    if (first == &end_of_list) return 0;
     list_node *tmp=first;
     first=first->next;
     if (!--elements)
       last= &first;
     return tmp->info;
   }
-  inline void *head() { return first ? first->info : 0; }
-  inline void **head_ref() { return first ? &first->info : 0; }
+  inline void *head() { return first->info; }
+  inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
+  inline bool is_empty() { return first == &end_of_list ; }
+  inline list_node *last_ref() { return &end_of_list; }
   friend class base_list_iterator;
 
 protected:
@@ -122,7 +136,7 @@ protected:
 class base_list_iterator
 {
   base_list *list;
-  base_list::list_node **el,**prev,*current;
+  list_node **el,**prev,*current;
 public:
   base_list_iterator(base_list &list_par) :list(&list_par),el(&list_par.first),
     prev(0),current(0)
@@ -130,16 +144,22 @@ public:
   inline void *next(void)
   {
     prev=el;
-    if (!(current= *el))
-      return 0;
+    current= *el;
     el= &current->next;
     return current->info;
   }
+  inline void *next_fast(void)
+  {
+    list_node *tmp;
+    tmp= *el;
+    el= &tmp->next;
+    return tmp->info;
+  }
   inline void rewind(void)
   {
     el= &list->first;
   }
-  void *replace(void *element)
+  inline void *replace(void *element)
   {						// Return old element
     void *tmp=current->info;
     current->info=element;
@@ -148,7 +168,7 @@ public:
   void *replace(base_list &new_list)
   {
     void *ret_value=current->info;
-    if (new_list.first)
+    if (!new_list.is_empty())
     {
       *new_list.last=current->next;
       current->info=new_list.first->info;
@@ -175,7 +195,7 @@ public:
   }
   inline bool is_last(void)
   {
-    return *el == 0;
+    return el == &list->last_ref()->next;
   }
 };
 
@@ -193,7 +213,7 @@ public:
   void delete_elements(void)
   {
     list_node *element,*next;
-    for (element=first; element ; element=next)
+    for (element=first; element != &end_of_list; element=next)
     {
       next=element->next;
       delete (T*) element->info;
@@ -208,13 +228,25 @@ template <class T> class List_iterator :public base_list_iterator
 public:
   List_iterator(List<T> &a) : base_list_iterator(a) {}
   inline T* operator++(int) { return (T*) base_list_iterator::next(); }
-  inline void rewind(void)  { base_list_iterator::rewind(); }
   inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
   inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
-  inline void remove(void)  { base_list_iterator::remove(); }
   inline void after(T *a)   { base_list_iterator::after(a); }
   inline T** ref(void)	    { return (T**) base_list_iterator::ref(); }
-  inline bool is_last(void) { return base_list_iterator::is_last(); }
+};
+
+template <class T> class List_iterator_fast :public base_list_iterator
+{
+protected:
+  inline T *replace(T *a)   { return (T*) 0; }
+  inline T *replace(List<T> &a) { return (T*) 0; }
+  inline void remove(void)  { }
+  inline void after(T *a)   { }
+  inline T** ref(void)	    { return (T**) 0; }
+
+public:
+  List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
+  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
+  inline void rewind(void)  { base_list_iterator::rewind(); }
 };