Lets add another intrusive double linked list!

Features:
* STL-like interface
* Fast modification: no branches on insertion or deletion
* Fast iteration: one pointer dereference and one pointer comparison
* Your class can be a part of several lists

Modeled after std::list<T> but currently has fewer methods (not complete yet)

For even more performance it's possible to customize list with templates so
it won't have size counter variable or won't NULLify unlinked node.

How existing lists differ?

No existing lists support STL-like interface.

I_List:
* slower iteration (one more branch on iteration)
* element can't be a part of two lists simultaneously

I_P_List:
* slower modification (branches, except for the fastest push_back() case)
* slower iteration (one more branch on iteration)

UT_LIST_BASE_NODE_T:
* slower modification (branches)

Three UT_LISTs were replaced: two in fil_system_t and one in dyn_buf_t.

4 files changed, 127 insertions, 141 deletions

diff --git a/storage/innobase/fil/fil0crypt.cc b/storage/innobase/fil/fil0crypt.cc
index d1aca92ef62..2211370ada1 100644
--- a/storage/innobase/fil/fil0crypt.cc
+++ b/storage/innobase/fil/fil0crypt.cc
@@ -2346,7 +2346,7 @@ static void fil_crypt_rotation_list_fill()
 			}
 		}
 
-		UT_LIST_ADD_LAST(fil_system->rotation_list, space);
+		fil_system->rotation_list.push_back(*space);
 	}
 }
 
diff --git a/storage/innobase/fil/fil0fil.cc b/storage/innobase/fil/fil0fil.cc
index e37cb963c28..64c2834a635 100644
--- a/storage/innobase/fil/fil0fil.cc
+++ b/storage/innobase/fil/fil0fil.cc
@@ -898,9 +898,7 @@ skip_flush:
 			if (space->is_in_unflushed_spaces()
 			    && fil_space_is_flushed(space)) {
 
-				UT_LIST_REMOVE(
-					fil_system->unflushed_spaces,
-					space);
+				fil_system->unflushed_spaces.remove(*space);
 			}
 		}
 
@@ -1201,7 +1199,7 @@ fil_node_close_to_free(
 		} else if (space->is_in_unflushed_spaces()
 			   && fil_space_is_flushed(space)) {
 
-			UT_LIST_REMOVE(fil_system->unflushed_spaces, space);
+			fil_system->unflushed_spaces.remove(*space);
 		}
 
 		fil_node_close_file(node);
@@ -1232,12 +1230,12 @@ fil_space_detach(
 
 		ut_ad(!fil_buffering_disabled(space));
 
-		UT_LIST_REMOVE(fil_system->unflushed_spaces, space);
+		fil_system->unflushed_spaces.remove(*space);
 	}
 
 	if (space->is_in_rotation_list()) {
 
-		UT_LIST_REMOVE(fil_system->rotation_list, space);
+		fil_system->rotation_list.remove(*space);
 	}
 
 	UT_LIST_REMOVE(fil_system->space_list, space);
@@ -1463,7 +1461,7 @@ fil_space_create(
 		    srv_encrypt_tables)) {
 		/* Key rotation is not enabled, need to inform background
 		encryption threads. */
-		UT_LIST_ADD_LAST(fil_system->rotation_list, space);
+		fil_system->rotation_list.push_back(*space);
 		mutex_exit(&fil_system->mutex);
 		mutex_enter(&fil_crypt_threads_mutex);
 		os_event_set(fil_crypt_threads_event);
@@ -1799,8 +1797,7 @@ fil_init(
 	ut_a(hash_size > 0);
 	ut_a(max_n_open > 0);
 
-	fil_system = static_cast<fil_system_t*>(
-		ut_zalloc_nokey(sizeof(*fil_system)));
+	fil_system = new fil_system_t();
 
 	mutex_create(LATCH_ID_FIL_SYSTEM, &fil_system->mutex);
 
@@ -1809,9 +1806,6 @@ fil_init(
 
 	UT_LIST_INIT(fil_system->LRU, &fil_node_t::LRU);
 	UT_LIST_INIT(fil_system->space_list, &fil_space_t::space_list);
-	UT_LIST_INIT(fil_system->rotation_list, &fil_space_t::rotation_list);
-	UT_LIST_INIT(fil_system->unflushed_spaces,
-		     &fil_space_t::unflushed_spaces);
 	UT_LIST_INIT(fil_system->named_spaces, &fil_space_t::named_spaces);
 
 	fil_system->max_n_open = max_n_open;
@@ -4768,8 +4762,8 @@ fil_node_complete_io(fil_node_t* node, const IORequest& type)
 
 			if (!node->space->is_in_unflushed_spaces()) {
 
-				UT_LIST_ADD_FIRST(fil_system->unflushed_spaces,
-						  node->space);
+				fil_system->unflushed_spaces.push_front(
+					*node->space);
 			}
 		}
 	}
@@ -5237,7 +5231,6 @@ void
 fil_flush_file_spaces(
 	fil_type_t	purpose)
 {
-	fil_space_t*	space;
 	ulint*		space_ids;
 	ulint		n_space_ids;
 
@@ -5245,30 +5238,25 @@ fil_flush_file_spaces(
 
 	mutex_enter(&fil_system->mutex);
 
-	n_space_ids = UT_LIST_GET_LEN(fil_system->unflushed_spaces);
+	n_space_ids = fil_system->unflushed_spaces.size();
 	if (n_space_ids == 0) {
 
 		mutex_exit(&fil_system->mutex);
 		return;
 	}
 
-	/* Assemble a list of space ids to flush.  Previously, we
-	traversed fil_system->unflushed_spaces and called UT_LIST_GET_NEXT()
-	on a space that was just removed from the list by fil_flush().
-	Thus, the space could be dropped and the memory overwritten. */
 	space_ids = static_cast<ulint*>(
 		ut_malloc_nokey(n_space_ids * sizeof(*space_ids)));
 
 	n_space_ids = 0;
 
-	for (space = UT_LIST_GET_FIRST(fil_system->unflushed_spaces);
-	     space;
-	     space = UT_LIST_GET_NEXT(unflushed_spaces, space)) {
-
-		if (space->purpose == purpose
-		    && !space->is_stopping()) {
+	for (intrusive::list<fil_space_t, unflushed_spaces_tag_t>::iterator it
+	     = fil_system->unflushed_spaces.begin(),
+	     end = fil_system->unflushed_spaces.end();
+	     it != end; ++it) {
 
-			space_ids[n_space_ids++] = space->id;
+		if (it->purpose == purpose && !it->is_stopping()) {
+			space_ids[n_space_ids++] = it->id;
 		}
 	}
 
@@ -5420,12 +5408,12 @@ fil_close(void)
 		hash_table_free(fil_system->name_hash);
 
 		ut_a(UT_LIST_GET_LEN(fil_system->LRU) == 0);
-		ut_a(UT_LIST_GET_LEN(fil_system->unflushed_spaces) == 0);
+		ut_a(fil_system->unflushed_spaces.size() == 0);
 		ut_a(UT_LIST_GET_LEN(fil_system->space_list) == 0);
 
 		mutex_free(&fil_system->mutex);
 
-		ut_free(fil_system);
+		delete fil_system;
 		fil_system = NULL;
 
 		fil_space_crypt_cleanup();
@@ -5990,8 +5978,8 @@ fil_space_remove_from_keyrotation(fil_space_t* space)
 	ut_ad(space);
 
 	if (space->n_pending_ops == 0 && space->is_in_rotation_list()) {
-		ut_a(UT_LIST_GET_LEN(fil_system->rotation_list) > 0);
-		UT_LIST_REMOVE(fil_system->rotation_list, space);
+		ut_a(!fil_system->rotation_list.empty());
+		fil_system->rotation_list.remove(*space);
 	}
 }
 
@@ -6008,55 +5996,56 @@ blocks a concurrent operation from dropping the tablespace.
 If NULL, use the first fil_space_t on fil_system->space_list.
 @return pointer to the next fil_space_t.
 @retval NULL if this was the last */
-fil_space_t*
-fil_system_t::keyrotate_next(
-	fil_space_t*	prev_space,
-	bool		recheck,
-	uint		key_version)
+fil_space_t *fil_system_t::keyrotate_next(fil_space_t *prev_space,
+                                          bool recheck, uint key_version)
 {
-	mutex_enter(&fil_system->mutex);
+  mutex_enter(&fil_system->mutex);
 
-	/* If one of the encryption threads already started the encryption
-	of the table then don't remove the unencrypted spaces from
-	rotation list
+  /* If one of the encryption threads already started the encryption
+  of the table then don't remove the unencrypted spaces from rotation list
 
-	If there is a change in innodb_encrypt_tables variables value then
-	don't remove the last processed tablespace from the rotation list. */
-	const bool remove = ((!recheck || prev_space->crypt_data)
-			     && (!key_version == !srv_encrypt_tables));
+  If there is a change in innodb_encrypt_tables variables value then
+  don't remove the last processed tablespace from the rotation list. */
+  const bool remove= (!recheck || prev_space->crypt_data) &&
+                     !key_version == !srv_encrypt_tables;
+  intrusive::list<fil_space_t, rotation_list_tag_t>::iterator it=
+      prev_space == NULL ? fil_system->rotation_list.end() : prev_space;
 
-	fil_space_t* space = prev_space;
+  if (it == fil_system->rotation_list.end())
+  {
+    it= fil_system->rotation_list.begin();
+  }
+  else
+  {
+    ut_ad(prev_space->n_pending_ops > 0);
 
-	if (prev_space == NULL) {
-		space = UT_LIST_GET_FIRST(fil_system->rotation_list);
+    /* Move on to the next fil_space_t */
+    prev_space->n_pending_ops--;
 
-		/* We can trust that space is not NULL because we
-		checked list length above */
-	} else {
-		ut_ad(space->n_pending_ops > 0);
+    ++it;
 
-		/* Move on to the next fil_space_t */
-		space->n_pending_ops--;
+    while (it != fil_system->rotation_list.end() &&
+           (UT_LIST_GET_LEN(it->chain) == 0 || it->is_stopping()))
+    {
+      ++it;
+    }
 
-		space = UT_LIST_GET_NEXT(rotation_list, space);
+    if (remove)
+    {
+      fil_space_remove_from_keyrotation(prev_space);
+    }
+  }
 
-		while (space != NULL
-		       && (UT_LIST_GET_LEN(space->chain) == 0
-			   || space->is_stopping())) {
-			space = UT_LIST_GET_NEXT(rotation_list, space);
-		}
+  fil_space_t *space= it == fil_system->rotation_list.end() ? NULL : &*it;
 
-		if (remove) {
-			fil_space_remove_from_keyrotation(prev_space);
-		}
-	}
+  if (space)
+  {
+    space->n_pending_ops++;
+  }
 
-	if (space != NULL) {
-		space->n_pending_ops++;
-	}
+  mutex_exit(&fil_system->mutex);
 
-	mutex_exit(&fil_system->mutex);
-	return(space);
+  return space;
 }
 
 /** Determine the block size of the data file.
@@ -6134,18 +6123,21 @@ fil_space_set_punch_hole(
 
 /** Checks that this tablespace in a list of unflushed tablespaces.
 @return true if in a list */
-bool fil_space_t::is_in_unflushed_spaces() const {
-	ut_ad(mutex_own(&fil_system->mutex));
+bool fil_space_t::is_in_unflushed_spaces() const
+{
+  ut_ad(mutex_own(&fil_system->mutex));
 
-	return fil_system->unflushed_spaces.start == this
-	       || unflushed_spaces.next || unflushed_spaces.prev;
+  return static_cast<const intrusive::list_node<unflushed_spaces_tag_t> *>(
+             this)
+      ->next;
 }
 
 /** Checks that this tablespace needs key rotation.
 @return true if in a rotation list */
-bool fil_space_t::is_in_rotation_list() const {
-	ut_ad(mutex_own(&fil_system->mutex));
+bool fil_space_t::is_in_rotation_list() const
+{
+  ut_ad(mutex_own(&fil_system->mutex));
 
-	return fil_system->rotation_list.start == this || rotation_list.next
-	       || rotation_list.prev;
+  return static_cast<const intrusive::list_node<rotation_list_tag_t> *>(this)
+      ->next;
 }
diff --git a/storage/innobase/include/dyn0buf.h b/storage/innobase/include/dyn0buf.h
index a7a8e1dea1e..311f6518943 100644
--- a/storage/innobase/include/dyn0buf.h
+++ b/storage/innobase/include/dyn0buf.h
@@ -29,7 +29,8 @@ Created 2013-03-16 Sunny Bains
 
 #include "mem0mem.h"
 #include "dyn0types.h"
-#include "ut0lst.h"
+#include "intrusive_list.h"
+
 
 /** Class that manages dynamic buffers. It uses a UT_LIST of
 dyn_buf_t::block_t instances. We don't use STL containers in
@@ -42,12 +43,7 @@ template <size_t SIZE = DYN_ARRAY_DATA_SIZE>
 class dyn_buf_t {
 public:
 
-	class block_t;
-
-	typedef UT_LIST_NODE_T(block_t) block_node_t;
-	typedef UT_LIST_BASE_NODE_T(block_t) block_list_t;
-
-	class block_t {
+	class block_t : public intrusive::list_node<> {
 	public:
 
 		block_t()
@@ -157,16 +153,13 @@ public:
 		/** SIZE - sizeof(m_node) + sizeof(m_used) */
 		enum {
 			MAX_DATA_SIZE = SIZE
-				      - sizeof(block_node_t)
+				      - sizeof(intrusive::list_node<>)
 				      + sizeof(ib_uint32_t)
 		};
 
 		/** Storage */
 		byte		m_data[MAX_DATA_SIZE];
 
-		/** Doubly linked list node. */
-		block_node_t	m_node;
-
 		/** number of data bytes used in this block;
 		DYN_BLOCK_FULL_FLAG is set when the block becomes full */
 		ib_uint32_t	m_used;
@@ -174,6 +167,8 @@ public:
 		friend class dyn_buf_t;
 	};
 
+	typedef intrusive::list<block_t> list_t;
+
 	enum { MAX_DATA_SIZE = block_t::MAX_DATA_SIZE};
 
 	/** Default constructor */
@@ -182,7 +177,6 @@ public:
 		m_heap(),
 		m_size()
 	{
-		UT_LIST_INIT(m_list, &block_t::m_node);
 		push_back(&m_first_block);
 	}
 
@@ -200,11 +194,11 @@ public:
 			m_heap = NULL;
 
 			/* Initialise the list and add the first block. */
-			UT_LIST_INIT(m_list, &block_t::m_node);
-			push_back(&m_first_block);
+			m_list.clear();
+			m_list.push_back(m_first_block);
 		} else {
 			m_first_block.init();
-			ut_ad(UT_LIST_GET_LEN(m_list) == 1);
+			ut_ad(m_list.size() == 1);
 		}
 
 		m_size = 0;
@@ -236,7 +230,7 @@ public:
 	@param ptr	end of used space */
 	void close(const byte* ptr)
 	{
-		ut_ad(UT_LIST_GET_LEN(m_list) > 0);
+		ut_ad(!m_list.empty());
 		block_t*	block = back();
 
 		m_size -= block->used();
@@ -324,11 +318,10 @@ public:
 #ifdef UNIV_DEBUG
 		ulint	total_size = 0;
 
-		for (const block_t* block = UT_LIST_GET_FIRST(m_list);
-		     block != NULL;
-		     block = UT_LIST_GET_NEXT(m_node, block)) {
-
-			total_size += block->used();
+		for (typename list_t::iterator it = m_list.begin(),
+					       end = m_list.end();
+		     it != end; ++it) {
+			total_size += it->used();
 		}
 
 		ut_ad(total_size == m_size);
@@ -342,12 +335,12 @@ public:
 	template <typename Functor>
 	bool for_each_block(Functor& functor) const
 	{
-		for (const block_t* block = UT_LIST_GET_FIRST(m_list);
-		     block != NULL;
-		     block = UT_LIST_GET_NEXT(m_node, block)) {
+		for (typename list_t::iterator it = m_list.begin(),
+					       end = m_list.end();
+		     it != end; ++it) {
 
-			if (!functor(block)) {
-				return(false);
+			if (!functor(&*it)) {
+				return false;
 			}
 		}
 
@@ -360,12 +353,12 @@ public:
 	template <typename Functor>
 	bool for_each_block_in_reverse(Functor& functor) const
 	{
-		for (block_t* block = UT_LIST_GET_LAST(m_list);
-		     block != NULL;
-		     block = UT_LIST_GET_PREV(m_node, block)) {
+		for (typename list_t::reverse_iterator it = m_list.rbegin(),
+						       end = m_list.rend();
+		     it != end; ++it) {
 
-			if (!functor(block)) {
-				return(false);
+			if (!functor(&*it)) {
+				return false;
 			}
 		}
 
@@ -378,12 +371,12 @@ public:
 	template <typename Functor>
 	bool for_each_block_in_reverse(const Functor& functor) const
 	{
-		for (block_t* block = UT_LIST_GET_LAST(m_list);
-		     block != NULL;
-		     block = UT_LIST_GET_PREV(m_node, block)) {
+		for (typename list_t::reverse_iterator it = m_list.rbegin(),
+						       end = m_list.rend();
+		     it != end; ++it) {
 
-			if (!functor(block)) {
-				return(false);
+			if (!functor(&*it)) {
+				return false;
 			}
 		}
 
@@ -395,8 +388,7 @@ public:
 	block_t* front()
 		MY_ATTRIBUTE((warn_unused_result))
 	{
-		ut_ad(UT_LIST_GET_LEN(m_list) > 0);
-		return(UT_LIST_GET_FIRST(m_list));
+		return &m_list.front();
 	}
 
 	/**
@@ -417,14 +409,13 @@ private:
 	void push_back(block_t* block)
 	{
 		block->init();
-
-		UT_LIST_ADD_LAST(m_list, block);
+		m_list.push_back(*block);
 	}
 
 	/** @return the last block in the list */
 	block_t* back()
 	{
-		return(UT_LIST_GET_LAST(m_list));
+		return &m_list.back();
 	}
 
 	/*
@@ -447,25 +438,22 @@ private:
 	@return the block containing the pos. */
 	block_t* find(ulint& pos)
 	{
-		block_t*	block;
+		ut_ad(!m_list.empty());
 
-		ut_ad(UT_LIST_GET_LEN(m_list) > 0);
+		for (typename list_t::iterator it = m_list.begin(),
+					       end = m_list.end();
+		     it != end; ++it) {
 
-		for (block = UT_LIST_GET_FIRST(m_list);
-		     block != NULL;
-		     block = UT_LIST_GET_NEXT(m_node, block)) {
+			if (pos < it->used()) {
+				ut_ad(it->used() >= pos);
 
-			if (pos < block->used()) {
-				break;
+				return &*it;
 			}
 
-			pos -= block->used();
+			pos -= it->used();
 		}
 
-		ut_ad(block != NULL);
-		ut_ad(block->used() >= pos);
-
-		return(block);
+		return NULL;
 	}
 
 	/**
@@ -491,7 +479,7 @@ private:
 	mem_heap_t*		m_heap;
 
 	/** Allocated blocks */
-	block_list_t		m_list;
+	list_t			m_list;
 
 	/** Total size used by all blocks */
 	ulint			m_size;
diff --git a/storage/innobase/include/fil0fil.h b/storage/innobase/include/fil0fil.h
index 386f574a59f..5484477d913 100644
--- a/storage/innobase/include/fil0fil.h
+++ b/storage/innobase/include/fil0fil.h
@@ -33,9 +33,13 @@ Created 10/25/1995 Heikki Tuuri
 #include "dict0types.h"
 #include "page0size.h"
 #include "ibuf0types.h"
+#include "intrusive_list.h"
 
 #include <list>
 
+struct unflushed_spaces_tag_t;
+struct rotation_list_tag_t;
+
 // Forward declaration
 extern ibool srv_use_doublewrite_buf;
 extern struct buf_dblwr_t* buf_dblwr;
@@ -78,7 +82,9 @@ fil_type_is_data(
 struct fil_node_t;
 
 /** Tablespace or log data space */
-struct fil_space_t {
+struct fil_space_t : intrusive::list_node<unflushed_spaces_tag_t>,
+                     intrusive::list_node<rotation_list_tag_t>
+{
 	ulint		id;	/*!< space id */
 	hash_node_t	hash;	/*!< hash chain node */
 	char*		name;	/*!< Tablespace name */
@@ -156,9 +162,6 @@ struct fil_space_t {
 	ulint		n_pending_ios;
 	rw_lock_t	latch;	/*!< latch protecting the file space storage
 				allocation */
-	UT_LIST_NODE_T(fil_space_t) unflushed_spaces;
-				/*!< list of spaces with at least one unflushed
-				file we have written to */
 	UT_LIST_NODE_T(fil_space_t) named_spaces;
 				/*!< list of spaces for which MLOG_FILE_NAME
 				records have been issued */
@@ -167,8 +170,6 @@ struct fil_space_t {
 	bool is_in_unflushed_spaces() const;
 	UT_LIST_NODE_T(fil_space_t) space_list;
 				/*!< list of all spaces */
-	/** other tablespaces needing key rotation */
-	UT_LIST_NODE_T(fil_space_t) rotation_list;
 	/** Checks that this tablespace needs key rotation.
 	@return true if in a rotation list */
 	bool is_in_rotation_list() const;
@@ -484,6 +485,11 @@ fil_space_get(
 data space) is stored here; below we talk about tablespaces, but also
 the ib_logfiles form a 'space' and it is handled here */
 struct fil_system_t {
+	fil_system_t()
+	    : n_open(0), max_assigned_id(0), space_id_reuse_warned(false)
+	{
+	}
+
 	ib_mutex_t	mutex;		/*!< The mutex protecting the cache */
 	hash_table_t*	spaces;		/*!< The hash table of spaces in the
 					system; they are hashed on the space
@@ -501,8 +507,8 @@ struct fil_system_t {
 					not put to this list: they are opened
 					after the startup, and kept open until
 					shutdown */
-	UT_LIST_BASE_NODE_T(fil_space_t) unflushed_spaces;
-					/*!< base node for the list of those
+	intrusive::list<fil_space_t, unflushed_spaces_tag_t> unflushed_spaces;
+					/*!< list of those
 					tablespaces whose files contain
 					unflushed writes; those spaces have
 					at least one file node where
@@ -524,11 +530,11 @@ struct fil_system_t {
 					record has been written since
 					the latest redo log checkpoint.
 					Protected only by log_sys->mutex. */
-	UT_LIST_BASE_NODE_T(fil_space_t) rotation_list;
+	intrusive::list<fil_space_t, rotation_list_tag_t> rotation_list;
 					/*!< list of all file spaces needing
 					key rotation.*/
 
-	ibool		space_id_reuse_warned;
+	bool		space_id_reuse_warned;
 					/* !< TRUE if fil_space_create()
 					has issued a warning about
 					potential space_id reuse */