intrusive::list fixes

namespace intrusive: removed

split class into two: ilist<T> and sized_ilist<T> which has a size field.

ilist<T> no more NULLify pointers to bring a slignly better performance.
As a consequence, fil_space_t::is_in_unflushed_spaces and
fil_space_t::is_in_rotation_list boolean members are needed now.

1 files changed, 78 insertions, 23 deletions

diff --git a/include/intrusive_list.h b/include/ilist.h
index 23534596b93..a94f878f49b 100644
--- a/include/intrusive_list.h
+++ b/include/ilist.h
@@ -1,5 +1,5 @@
 /*
-   Copyright (c) 2019, MariaDB
+   Copyright (c) 2019, 2020, MariaDB
 
    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
@@ -21,26 +21,28 @@
 #include <cstddef>
 #include <iterator>
 
-namespace intrusive
-{
-
 // Derive your class from this struct to insert to a linked list.
-template <class Tag= void> struct list_node
+template <class Tag= void> struct ilist_node
 {
-  list_node(list_node *next= NULL, list_node *prev= NULL)
-      : next(next), prev(prev)
+  ilist_node()
+      :
+#ifndef DBUG_OFF
+        next(NULL), prev(NULL)
+#endif
   {
   }
 
-  list_node *next;
-  list_node *prev;
+  ilist_node(ilist_node *next, ilist_node *prev) : next(next), prev(prev) {}
+
+  ilist_node *next;
+  ilist_node *prev;
 };
 
 // Modelled after std::list<T>
-template <class T, class Tag= void> class list
+template <class T, class Tag= void> class ilist
 {
 public:
-  typedef list_node<Tag> ListNode;
+  typedef ilist_node<Tag> ListNode;
   class Iterator;
 
   // All containers in C++ should define these types to implement generic
@@ -103,10 +105,10 @@ public:
   private:
     ListNode *node_;
 
-    friend class list;
+    friend class ilist;
   };
 
-  list() : sentinel_(&sentinel_, &sentinel_), size_(0) {}
+  ilist() : sentinel_(&sentinel_, &sentinel_) {}
 
   reference front() { return *begin(); }
   reference back() { return *--end(); }
@@ -127,14 +129,18 @@ public:
   reverse_iterator rend() { return reverse_iterator(begin()); }
   const_reverse_iterator rend() const { return reverse_iterator(begin()); }
 
-  bool empty() const { return size_ == 0; }
-  size_type size() const { return size_; }
+  bool empty() const { return sentinel_.next == &sentinel_; }
+
+  // Not implemented because it's O(N)
+  // size_type size() const
+  // {
+  //   return static_cast<size_type>(std::distance(begin(), end()));
+  // }
 
   void clear()
   {
     sentinel_.next= &sentinel_;
     sentinel_.prev= &sentinel_;
-    size_= 0;
   }
 
   iterator insert(iterator pos, reference value)
@@ -148,7 +154,6 @@ public:
     static_cast<ListNode &>(value).prev= prev;
     static_cast<ListNode &>(value).next= curr;
 
-    ++size_;
     return iterator(&value);
   }
 
@@ -160,13 +165,12 @@ public:
     prev->next= next;
     next->prev= prev;
 
-    // This is not required for list functioning. But maybe it'll prevent bugs
-    // and ease debugging.
+#ifndef DBUG_OFF
     ListNode *curr= pos.node_;
     curr->prev= NULL;
     curr->next= NULL;
+#endif
 
-    --size_;
     return next;
   }
 
@@ -177,12 +181,63 @@ public:
   void pop_front() { erase(begin()); }
 
   // STL version is O(n) but this is O(1) because an element can't be inserted
-  // several times in the same intrusive list.
+  // several times in the same ilist.
   void remove(reference value) { erase(iterator(&value)); }
 
 private:
   ListNode sentinel_;
-  size_type size_;
 };
 
-} // namespace intrusive
+// Similar to ilist but also has O(1) size() method.
+template <class T, class Tag= void> class sized_ilist : public ilist<T, Tag>
+{
+  typedef ilist<T, Tag> BASE;
+
+public:
+  // All containers in C++ should define these types to implement generic
+  // container interface.
+  using typename BASE::const_iterator;
+  using typename BASE::const_pointer;
+  using typename BASE::const_reference;
+  using typename BASE::const_reverse_iterator;
+  using typename BASE::difference_type;
+  using typename BASE::iterator;
+  using typename BASE::pointer;
+  using typename BASE::reference;
+  using typename BASE::reverse_iterator;
+  using typename BASE::size_type;
+  using typename BASE::value_type;
+
+  sized_ilist() : size_(0) {}
+
+  size_type size() const { return size_; }
+
+  void clear()
+  {
+    BASE::clear();
+    size_= 0;
+  }
+
+  iterator insert(iterator pos, reference value)
+  {
+    ++size_;
+    return BASE::insert(pos, value);
+  }
+
+  iterator erase(iterator pos)
+  {
+    --size_;
+    return BASE::erase(pos);
+  }
+
+  void push_back(reference value) { insert(BASE::end(), value); }
+  void pop_back() { erase(BASE::end()); }
+
+  void push_front(reference value) { insert(BASE::begin(), value); }
+  void pop_front() { erase(BASE::begin()); }
+
+  void remove(reference value) { erase(iterator(&value)); }
+
+private:
+  size_t size_;
+};