# 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;
}
};
| Thread |
|---|
| • bzr commit into mysql-6.0 branch (davi:2739) | Davi Arnaut | 22 Oct |
