diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 18:07:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 18:07:14 +0000 |
commit | a175314c3e5827eb193872241446f2f8f5c9d33c (patch) | |
tree | cd3d60ca99ae00829c52a6ca79150a5b6e62528b /sql/sql_plist.h | |
parent | Initial commit. (diff) | |
download | mariadb-10.5-upstream/1%10.5.12.tar.xz mariadb-10.5-upstream/1%10.5.12.zip |
Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | sql/sql_plist.h | 297 |
1 files changed, 297 insertions, 0 deletions
diff --git a/sql/sql_plist.h b/sql/sql_plist.h new file mode 100644 index 00000000..7f75208c --- /dev/null +++ b/sql/sql_plist.h @@ -0,0 +1,297 @@ +#ifndef SQL_PLIST_H +#define SQL_PLIST_H +/* Copyright (c) 2008, 2011, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ + + +template <typename T, typename L> +class I_P_List_iterator; +class I_P_List_null_counter; +template <typename T> class I_P_List_no_push_back; + + +/** + Intrusive parameterized list. + + Unlike I_List does not require its elements to be descendant of ilink + class and therefore allows them to participate in several such lists + simultaneously. + + Unlike List is doubly-linked list and thus supports efficient deletion + of element without iterator. + + @param T Type of elements which will belong to list. + @param B Class which via its methods specifies which members + 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) + { + return &el->prev; + } + }; + @param C Policy class specifying how counting of elements in the list + should be done. Instance of this class is also used as a place + where information about number of list elements is stored. + @sa I_P_List_null_counter, I_P_List_counter + @param I Policy class specifying whether I_P_List should support + efficient push_back() operation. Instance of this class + is used as place where we store information to support + this operation. + @sa I_P_List_no_push_back, I_P_List_fast_push_back. +*/ + +template <typename T, typename B, + typename C = I_P_List_null_counter, + typename I = I_P_List_no_push_back<T> > +class I_P_List : public C, public I +{ + T *m_first; + + /* + Do not prohibit copying of I_P_List object to simplify their usage in + backup/restore scenarios. Note that performing any operations on such + is a bad idea. + */ +public: + I_P_List() : I(&m_first), m_first(NULL) {}; + /* + empty() is used in many places in the code instead of a constructor, to + initialize a bzero-ed I_P_List instance. + */ + + inline void empty() { m_first= NULL; C::reset(); I::set_last(&m_first); } + inline bool is_empty() const { return (m_first == NULL); } + inline void push_front(T* a) + { + *B::next_ptr(a)= m_first; + if (m_first) + *B::prev_ptr(m_first)= B::next_ptr(a); + else + I::set_last(B::next_ptr(a)); + m_first= a; + *B::prev_ptr(a)= &m_first; + C::inc(); + } + inline void push_back(T *a) + { + T **last= I::get_last(); + *B::next_ptr(a)= *last; + *last= a; + *B::prev_ptr(a)= last; + I::set_last(B::next_ptr(a)); + C::inc(); + } + inline void insert_after(T *pos, T *a) + { + if (pos == NULL) + push_front(a); + else + { + *B::next_ptr(a)= *B::next_ptr(pos); + *B::prev_ptr(a)= B::next_ptr(pos); + *B::next_ptr(pos)= a; + if (*B::next_ptr(a)) + { + T *old_next= *B::next_ptr(a); + *B::prev_ptr(old_next)= B::next_ptr(a); + } + else + I::set_last(B::next_ptr(a)); + C::inc(); + } + } + inline void remove(T *a) + { + T *next= *B::next_ptr(a); + if (next) + *B::prev_ptr(next)= *B::prev_ptr(a); + else + I::set_last(*B::prev_ptr(a)); + **B::prev_ptr(a)= next; + C::dec(); + } + inline T* front() { return m_first; } + inline const T *front() const { return m_first; } + inline T* pop_front() + { + T *result= front(); + + if (result) + remove(result); + + return result; + } + void swap(I_P_List<T, B, C> &rhs) + { + swap_variables(T *, m_first, rhs.m_first); + I::swap(rhs); + if (m_first) + *B::prev_ptr(m_first)= &m_first; + else + I::set_last(&m_first); + if (rhs.m_first) + *B::prev_ptr(rhs.m_first)= &rhs.m_first; + else + I::set_last(&rhs.m_first); + C::swap(rhs); + } + typedef B Adapter; + typedef I_P_List<T, B, C, I> Base; + typedef I_P_List_iterator<T, Base> Iterator; + typedef I_P_List_iterator<const T, Base> Const_Iterator; +#ifndef _lint + friend class I_P_List_iterator<T, Base>; + friend class I_P_List_iterator<const T, Base>; +#endif +}; + + +/** + Iterator for I_P_List. +*/ + +template <typename T, typename L> +class I_P_List_iterator +{ + const L *list; + T *current; +public: + I_P_List_iterator(const L &a) + : list(&a), current(a.m_first) {} + I_P_List_iterator(const L &a, T* current_arg) + : list(&a), current(current_arg) {} + inline void init(const L &a) + { + list= &a; + current= a.m_first; + } + /** + Operator for it++ + + @note since we save next element pointer, caller may remove current element. + Such modification doesn't invalidate iterator. + */ + inline T* operator++(int) + { + T *result= current; + if (result) + current= *L::Adapter::next_ptr(current); + return result; + } + /* Operator for ++it */ + inline T* operator++() + { + current= *L::Adapter::next_ptr(current); + return current; + } + inline void rewind() + { + current= list->m_first; + } +}; + + +/** + Hook class which via its methods specifies which members + of T should be used for participating in a intrusive list. +*/ + +template <typename T, T* T::*next, T** T::*prev> +struct I_P_List_adapter +{ + static inline T **next_ptr(T *el) { return &(el->*next); } + static inline const T* const* next_ptr(const T *el) { return &(el->*next); } + static inline T ***prev_ptr(T *el) { return &(el->*prev); } +}; + + +/** + Element counting policy class for I_P_List to be used in + cases when no element counting should be done. +*/ + +class I_P_List_null_counter +{ +protected: + void reset() {} + void inc() {} + void dec() {} + void swap(I_P_List_null_counter &) {} +}; + + +/** + Element counting policy class for I_P_List which provides + basic element counting. +*/ + +class I_P_List_counter +{ + uint m_counter; +protected: + I_P_List_counter() : m_counter (0) {} + void reset() {m_counter= 0;} + void inc() {m_counter++;} + void dec() {m_counter--;} + void swap(I_P_List_counter &rhs) + { swap_variables(uint, m_counter, rhs.m_counter); } +public: + uint elements() const { return m_counter; } +}; + + +/** + A null insertion policy class for I_P_List to be used + in cases when push_back() operation is not necessary. +*/ + +template <typename T> class I_P_List_no_push_back +{ +protected: + I_P_List_no_push_back(T **) {} + void set_last(T **) {} + /* + T** get_last() const method is intentionally left unimplemented + in order to prohibit usage of push_back() method in lists which + use this policy. + */ + void swap(I_P_List_no_push_back<T> &) {} +}; + + +/** + An insertion policy class for I_P_List which can + be used when fast push_back() operation is required. +*/ + +template <typename T> class I_P_List_fast_push_back +{ + T **m_last; +protected: + I_P_List_fast_push_back(T **a) : m_last(a) { }; + void set_last(T **a) { m_last= a; } + T** get_last() const { return m_last; } + void swap(I_P_List_fast_push_back<T> &rhs) + { swap_variables(T**, m_last, rhs.m_last); } +}; + +#endif |