bzr commit into mysql-6.0 branch (davi:2739)

[Davi Arnaut]

# At a local mysql-6.0 repository of davi

 2739 Davi Arnaut	2008-10-22
      o Rework the intrusive parameterized list implementation
      
      Re-implement the I_P_List class as a doubly linked list with
      sentinel nodes. Although sentinal nodes take up extra space,
      they simplify most list operations so that no special handling
      is necessary for the common operations (push_front, push_back,
      is_empty, etc). The list nodes also contain a pointer to the
      embedded data so its use is not restricted to POD types (the
      use of offsetof is restricted to POD types).
      
      Wikipedia offers a nice summary on the tradeoffs of sentinel nodes:
      
      http://en.wikipedia.org/wiki/Linked_list#Sentinel_nodes_.28header_nodes.29
modified:
  sql/mdl.cc
  sql/mdl.h
  sql/sql_base.cc
  sql/sql_plist.h
  sql/table.h

per-file messages:
  sql/mdl.cc
    Rename head() method to front(). Use join instead of swap.
  sql/mdl.h
    Use new I_P_List link node.
  sql/sql_base.cc
    Rename head() method to front()
  sql/sql_plist.h
    Introduce a special class that represents a list node.
    Re-implement the I_P_List class as a doubly linked list
    with sentinel nodes.
    Add a new template argument to the iterator class so that
    its possibly to specify the returned type (eg const pointer)
  sql/table.h
    Return pointer to list link.
=== modified file 'sql/mdl.cc'
--- a/sql/mdl.cc	2008-08-13 10:36:29 +0000
+++ b/sql/mdl.cc	2008-10-22 20:47:47 +0000
@@ -53,11 +53,11 @@ struct MDL_LOCK
   MDL_LOCK_DATA *get_key_owner()
   {
      return !active_shared.is_empty() ?
-            active_shared.head() :
+            active_shared.front() :
             (!active_shared_waiting_upgrade.is_empty() ?
-             active_shared_waiting_upgrade.head() :
+             active_shared_waiting_upgrade.front() :
              (!active_exclusive.is_empty() ?
-              active_exclusive.head() : waiting_exclusive.head()));
+              active_exclusive.front() : waiting_exclusive.front()));
   }
 
   bool has_one_lock_data()
@@ -192,7 +192,7 @@ void mdl_context_destroy(MDL_CONTEXT *co
 void mdl_context_backup_and_reset(MDL_CONTEXT *ctx, MDL_CONTEXT *backup)
 {
   backup->locks.empty();
-  ctx->locks.swap(backup->locks);
+  backup->locks.join(ctx->locks);
 }
 
 
@@ -203,7 +203,7 @@ void mdl_context_backup_and_reset(MDL_CO
 void mdl_context_restore(MDL_CONTEXT *ctx, MDL_CONTEXT *backup)
 {
   DBUG_ASSERT(ctx->locks.is_empty());
-  ctx->locks.swap(backup->locks);
+  ctx->locks.join(backup->locks);
 }
 
 
@@ -630,7 +630,7 @@ static bool can_grant_lock(MDL_LOCK *loc
           lock->waiting_exclusive.is_empty() &&
           lock->active_shared_waiting_upgrade.is_empty())) ||
         (!lock->active_exclusive.is_empty() &&
-         lock->active_exclusive.head()->ctx == lock_data->ctx))
+         lock->active_exclusive.front()->ctx == lock_data->ctx))
     {
       /*
         When exclusive lock comes from the same context we can satisfy our
@@ -655,7 +655,7 @@ static bool can_grant_lock(MDL_LOCK *loc
         on the object.
       */
       DBUG_ASSERT(lock->active_exclusive.is_empty() &&
-                  lock->active_shared_waiting_upgrade.head() == lock_data);
+                  lock->active_shared_waiting_upgrade.front() == lock_data);
 
       while ((conf_lock_data= it++))
       {

=== modified file 'sql/mdl.h'
--- a/sql/mdl.h	2008-06-20 13:11:20 +0000
+++ b/sql/mdl.h	2008-10-22 20:47:47 +0000
@@ -66,16 +66,14 @@ struct MDL_LOCK_DATA
 
 private:
   /**
-     Pointers for participating in the list of lock requests for this context.
+     Link for participating in the list of lock requests for this context.
   */
-  MDL_LOCK_DATA *next_context;
-  MDL_LOCK_DATA **prev_context;
+  I_P_List_Link link_context;
   /**
-     Pointers for participating in the list of satisfied/pending requests
+     Link for participating in the list of satisfied/pending requests
      for the lock.
   */
-  MDL_LOCK_DATA *next_lock;
-  MDL_LOCK_DATA **prev_lock;
+  I_P_List_Link link_lock;
 
   friend struct MDL_LOCK_DATA_context;
   friend struct MDL_LOCK_DATA_lock;
@@ -98,13 +96,9 @@ public:
 
 struct MDL_LOCK_DATA_context
 {
-  static inline MDL_LOCK_DATA **next_ptr(MDL_LOCK_DATA *l)
+  static inline I_P_List_Link *link(MDL_LOCK_DATA *l)
   {
-    return &l->next_context;
-  }
-  static inline MDL_LOCK_DATA ***prev_ptr(MDL_LOCK_DATA *l)
-  {
-    return &l->prev_context;
+    return &l->link_context;
   }
 };
 
@@ -116,13 +110,9 @@ struct MDL_LOCK_DATA_context
 
 struct MDL_LOCK_DATA_lock
 {
-  static inline MDL_LOCK_DATA **next_ptr(MDL_LOCK_DATA *l)
-  {
-    return &l->next_lock;
-  }
-  static inline MDL_LOCK_DATA ***prev_ptr(MDL_LOCK_DATA *l)
+  static inline I_P_List_Link *link(MDL_LOCK_DATA *l)
   {
-    return &l->prev_lock;
+    return &l->link_lock;
   }
 };
 

=== modified file 'sql/sql_base.cc'
--- a/sql/sql_base.cc	2008-10-08 09:27:11 +0000
+++ b/sql/sql_base.cc	2008-10-22 20:47:47 +0000
@@ -2686,7 +2686,7 @@ bool open_table(THD *thd, TABLE_LIST *ta
 
   if (!share->free_tables.is_empty())
   {
-    table= share->free_tables.head();
+    table= share->free_tables.front();
     table_def_use_table(thd, table);
     /* We need to release share as we have EXTRA reference to it in our hands. */
     release_table_share(share);

=== modified file 'sql/sql_plist.h'
--- a/sql/sql_plist.h	2008-05-27 09:45:34 +0000
+++ b/sql/sql_plist.h	2008-10-22 20:47:47 +0000
@@ -18,8 +18,23 @@
 
 #include <my_global.h>
 
-template <typename T, typename B> class I_P_List_iterator;
+template <typename T, typename B> class I_P_List;
+template <typename T, typename B, typename P = T> class I_P_List_iterator;
 
+class I_P_List_Link
+{
+  void *obj;
+  I_P_List_Link *next, *prev;
+public:
+  I_P_List_Link() { init(); }
+  inline void init()
+  {
+    obj= NULL;
+    next= prev= this;
+  }
+  template <typename, typename> friend class I_P_List;
+  template <typename, typename, typename> friend class I_P_List_iterator;
+};
 
 /**
    Intrusive parameterized list.
@@ -32,19 +47,15 @@ template <typename T, typename B> class 
    of element without iterator.
 
    @param T  Type of elements which will belong to list.
-   @param B  Class which via its methods specifies which members
+   @param B  Class which via its method specifies which member
              of T should be used for participating in this list.
              Here is typical layout of such class:
 
              struct B
              {
-               static inline T **next_ptr(T *el)
-               {
-                 return &el->next;
-               }
-               static inline T ***prev_ptr(T *el)
+               static inline I_P_List_Link *link(T *el)
                {
-                 return &el->prev;
+                 return &el->link;
                }
              };
 */
@@ -52,7 +63,32 @@ template <typename T, typename B> class 
 template <typename T, typename B>
 class I_P_List
 {
-  T *first;
+  I_P_List_Link head;
+  typedef I_P_List_Link Link;
+
+  /** Insert a node between two consecutive nodes. */
+  void add(Link *prev, Link *next, Link *node)
+  {
+    next->prev = node;
+    node->next = next;
+    node->prev = prev;
+    prev->next = node;
+  }
+
+  /** Remove a node by linking its neighboring nodes. */
+  void rem(Link *prev, Link *next)
+  {
+    next->prev = prev;
+    prev->next = next;
+  }
+
+  /** Link a list after a node -- link two lists together. */
+  void lnk(Link *node, Link *list)
+  {
+    Link *head= list->next, *tail= list->prev, *pos= node->next;
+    head->prev= node; node->next= head;
+    tail->next= pos; pos->prev= tail;
+  }
 
   /*
     Do not prohibit copying of I_P_List object to simplify their usage in
@@ -60,65 +96,83 @@ class I_P_List
     is a bad idea.
   */
 public:
-  I_P_List() : first(NULL) { };
-  inline void empty()      { first= NULL; }
-  inline bool is_empty() const { return (first == NULL); }
+  I_P_List() { empty(); }
+
+  /** Removes all elements from the list. */
+  inline void empty() { head.init(); }
+
+  /** Returns true if list is empty. */
+  inline bool is_empty() const { return &head == head.next; }
+
+  /** Returns first element of the list. */
+  inline T *front() const { return (T*) head.next->obj; }
+
+  /** Returns the last element of the list. */
+  inline T *back() const { return (T*) head.prev->obj; }
+
+  /** Add an element to the front of the list. */
   inline void push_front(T* a)
   {
-    *B::next_ptr(a)= first;
-    if (first)
-      *B::prev_ptr(first)= B::next_ptr(a);
-    first= a;
-    *B::prev_ptr(a)= &first;
+    Link *node= B::link(a);
+    node->obj= a;
+    add(&head, head.next, node);
+  }
+
+  /** Add an element to the end of the list. */
+  inline void push_back(T *a)
+  {
+    Link *node= B::link(a);
+    node->obj= a;
+    add(head.prev, &head, node);
   }
+
+  /** Removes an element from the list. */
   inline void remove(T *a)
   {
-    T *next= *B::next_ptr(a);
-    if (next)
-      *B::prev_ptr(next)= *B::prev_ptr(a);
-    **B::prev_ptr(a)= next;
-  }
-  inline T* head() { return first; }
-  void swap(I_P_List<T,B> &rhs)
-  {
-    swap_variables(T *, first, rhs.first);
-    if (first)
-      *B::prev_ptr(first)= &first;
-    if (rhs.first)
-      *B::prev_ptr(rhs.first)= &rhs.first;
+    Link *node= B::link(a);
+    rem(node->prev, node->next);
+  }
+
+  /** Concatenate a list to the front of the list.*/
+  void join(I_P_List<T,B> &list)
+  {
+    if (!list.is_empty())
+    {
+      lnk(&head, &list.head);
+      list.empty();
+    }
   }
 #ifndef _lint
-  friend class I_P_List_iterator<T, B>;
+  template <typename, typename, typename> friend class I_P_List_iterator;
 #endif
 };
 
 
 /**
    Iterator for I_P_List.
+   Permits safe removal of the current element.
 */
 
-template <typename T, typename B>
+template <typename T, typename B, typename P>
 class I_P_List_iterator
 {
-  I_P_List<T, B> *list;
-  T *current;
+  I_P_List_Link *head, *pos;
 public:
-  I_P_List_iterator(I_P_List<T, B> &a) : list(&a), current(a.first) {}
+  I_P_List_iterator(I_P_List<T, B> &a) { init(a); }
   inline void init(I_P_List<T, B> &a)
   {
-    list= &a;
-    current= a.first;
+    head= &a.head;
+    pos= head->next;
   }
-  inline T* operator++(int)
+  inline P* operator++(int)
   {
-    T *result= current;
-    if (result)
-      current= *B::next_ptr(current);
-    return result;
+    P *obj= (P*) pos->obj;
+    pos= pos->next;
+    return obj;
   }
   inline void rewind()
   {
-    current= list->first;
+    pos= head->next;
   }
 };
 

=== modified file 'sql/table.h'
--- a/sql/table.h	2008-10-07 22:05:23 +0000
+++ b/sql/table.h	2008-10-22 20:47:47 +0000
@@ -626,7 +626,7 @@ private:
      Declared as private to avoid direct manipulation with those objects.
      One should use methods of I_P_List template instead.
   */
-  TABLE *share_next, **share_prev;
+  I_P_List_Link share_link;
 
   friend struct TABLE_share;
 public:
@@ -840,13 +840,9 @@ public:
 
 struct TABLE_share
 {
-  static inline TABLE **next_ptr(TABLE *l)
+  static inline I_P_List_Link *link(TABLE *l)
   {
-    return &l->share_next;
-  }
-  static inline TABLE ***prev_ptr(TABLE *l)
-  {
-    return &l->share_prev;
+    return &l->share_link;
   }
 };