WL#6456: Get rid of IB_OFFSETOF() macro. Allow non-POD types in UT_LIST_*

Affects: Benchmarks-3.0   —   Status: Complete   —   Priority: Medium

Allow lists of non-POD (Plain Old Data structure) types. POD is any non-scalar 
type that maps strictly to a C struct or union. The current implementation limits 
their use in C++.

When I did the switch from C to C++ I had to hack a macro to get at the list node 
field using an IB_OFFSETOF() macro.

/*******************************************************************//**
Return offset of F in POD T.
@param T        - POD pointer
@param F        - Field in T */
#define IB_OFFSETOF(T, F)                                               \
        (reinterpret_cast<byte*>(&(T)->F) - reinterpret_cast<byte*>(T))

This assumes a simple POD layout. This style access of struct fields limits the 
use of InnoDB's list to simple structs and unions.
By using point to member we can generalise the InnoDB list code to be used by all 
types. The main aim of this WL is to make the list self contained so that we don't 
need to explicitly pass the offset of the data member when adding, removing, 
accessing and traversing the list. Once that is accomplished we can write STL 
compliant iterators over our list implementation and use the STL algorithms over 
our lists. The long term aim is to restrict the use of this home-brew list type to  
where it is required. The main advantage of our homebrew list implementation is 
that node pointers are embedded in the list element. This avoids explicit memory 
allocation and deallocation of memory when adding/removing from the lists. Also 
the same embedded node pointer can be used to put the element on different lists 
e.g., a page in the buffer pool can be in the free list and LRU list (not 
simultaneously). The critical point here is that pages are not dynamically 
allocated in the buffer pool and we want to avoid making calls to reserve space  
for the list nodes each time we move them around.
This is the current implementation, the field offset has to be passed in 
explicitly each time we want to do any operation on the list.

/*******************************************************************//**
Return offset of F in POD T.
@param T        - POD pointer
@param F        - Field in T */
#define IB_OFFSETOF(T, F)                                               \
        (reinterpret_cast<byte*>(&(T)->F) - reinterpret_cast<byte*>(T))

/* This module implements the two-way linear list which should be used
if a list is used in the database. Note that a single struct may belong
to two or more lists, provided that the list are given different names.
An example of the usage of the lists can be found in fil0fil.cc. */

/*******************************************************************//**
This macro expands to the unnamed type definition of a struct which acts
as the two-way list base node. The base node contains pointers
to both ends of the list and a count of nodes in the list (excluding
the base node from the count).
@param TYPE     the name of the list node data type */
template <typename TYPE>
struct ut_list_base {
        typedef TYPE elem_type;

        ulint   count;  /*!< count of nodes in list */
        TYPE*   start;  /*!< pointer to list start, NULL if empty */
        TYPE*   end;    /*!< pointer to list end, NULL if empty */
};

#define UT_LIST_BASE_NODE_T(TYPE)       ut_list_base<TYPE>

The new proposed design:


/* This module implements the two-way linear list. Note that a single
list node may belong to two or more lists, but is only on one list
at a time. */

/*******************************************************************//**
The two way list node.
@param TYPE     the list node type name */
template <typename Type>
struct ut_list_node {
        Type*           prev;                   /*!< pointer to the previous
                                                node, NULL if start of list */
        Type*           next;                   /*!< pointer to next node,
                                                NULL if end of list */
};

/** Macro used for legacy reasons */
#define UT_LIST_NODE_T(t)               ut_list_node<t>

/*******************************************************************//**
The two-way list base node. The base node contains pointers to both ends
of the list and a count of nodes in the list (excluding the base node
from the count). We also store a pointer to the member field so that it
doesn't have to be specified when doing list operations.
@param Type     the type of the list element
@param NodePtr  field member pointer that points to the list node */
template <typename Type, typename NodePtr>
struct ut_list_base {
        typedef Type elem_type;
        typedef NodePtr node_ptr;
        typedef ut_list_node<Type> node_type;

        ulint           count;                  /*!< count of nodes in list */
        elem_type*      start;                  /*!< pointer to list start,
                                                NULL if empty */
        elem_type*      end;                    /*!< pointer to list end,
                                                NULL if empty */
        node_ptr        node;                   /*!< Pointer to member field
                                                that is used as a link node */
#ifdef UNIV_DEBUG
        ulint           init;                   /*!< UT_LIST_INITIALISED if
                                                the list was initialised with
                                                UT_LIST_INIT() */
#endif /* UNIV_DEBUG */
};

The pointer to member field is stored in the list base node. The main complication 
in the new design is where the pointer to member is in an embedded struct/union 
e.g., in the locking code. For that we need to write an accessor to get at the 
node pointer.

/** Functor for accessing the embedded node within a table lock. */
struct TableLockGetNode {
        ut_list_node<lock_t>& operator() (lock_t& elem)
        {
                return(elem.un_member.tab_lock.locks);
        }
};

ut_list_remove(table->locks, lock, TableLockGetNode());

For the default case this is not required.