D7net
Home
Console
Upload
information
Create File
Create Folder
About
Tools
:
/
proc
/
thread-self
/
root
/
proc
/
thread-self
/
root
/
usr
/
include
/
mysql
/
server
/
private
/
Filename :
ilist.h
back
Copy
/* 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 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 */ #ifndef ILIST_H #define ILIST_H #include "my_dbug.h" #include <cstddef> #include <iterator> // Derive your class from this struct to insert to a linked list. template <class Tag= void> struct ilist_node { #ifndef DBUG_OFF ilist_node() noexcept : next(NULL), prev(NULL) {} #else ilist_node() = default; #endif ilist_node(ilist_node *next, ilist_node *prev) noexcept : next(next), prev(prev) { } ilist_node *next; ilist_node *prev; }; // Modelled after std::list<T> template <class T, class Tag= void> class ilist { public: typedef ilist_node<Tag> ListNode; class Iterator; // All containers in C++ should define these types to implement generic // container interface. typedef T value_type; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef value_type &reference; typedef const value_type &const_reference; typedef T *pointer; typedef const T *const_pointer; typedef Iterator iterator; typedef Iterator const_iterator; /* FIXME */ typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const iterator> const_reverse_iterator; class Iterator { public: // All iterators in C++ should define these types to implement generic // iterator interface. typedef std::bidirectional_iterator_tag iterator_category; typedef T value_type; typedef std::ptrdiff_t difference_type; typedef T *pointer; typedef T &reference; explicit Iterator(ListNode *node) noexcept : node_(node) { DBUG_ASSERT(node_ != nullptr); } Iterator &operator++() noexcept { node_= node_->next; DBUG_ASSERT(node_ != nullptr); return *this; } Iterator operator++(int) noexcept { Iterator tmp(*this); operator++(); return tmp; } Iterator &operator--() noexcept { node_= node_->prev; DBUG_ASSERT(node_ != nullptr); return *this; } Iterator operator--(int) noexcept { Iterator tmp(*this); operator--(); return tmp; } reference operator*() noexcept { return *static_cast<pointer>(node_); } pointer operator->() noexcept { return static_cast<pointer>(node_); } friend bool operator==(const Iterator &lhs, const Iterator &rhs) noexcept { return lhs.node_ == rhs.node_; } friend bool operator!=(const Iterator &lhs, const Iterator &rhs) noexcept { return !(lhs == rhs); } private: ListNode *node_; friend class ilist; }; ilist() noexcept : sentinel_(&sentinel_, &sentinel_) {} reference front() noexcept { return *begin(); } reference back() noexcept { return *--end(); } const_reference front() const noexcept { return *begin(); } const_reference back() const noexcept { return *--end(); } iterator begin() noexcept { return iterator(sentinel_.next); } const_iterator begin() const noexcept { return iterator(const_cast<ListNode *>(sentinel_.next)); } iterator end() noexcept { return iterator(&sentinel_); } const_iterator end() const noexcept { return iterator(const_cast<ListNode *>(&sentinel_)); } reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } const_reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); } reverse_iterator rend() noexcept { return reverse_iterator(begin()); } const_reverse_iterator rend() const noexcept { return reverse_iterator(begin()); } bool empty() const noexcept { 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() noexcept { sentinel_.next= &sentinel_; sentinel_.prev= &sentinel_; } iterator insert(iterator pos, reference value) noexcept { ListNode *curr= pos.node_; ListNode *prev= pos.node_->prev; prev->next= &value; curr->prev= &value; static_cast<ListNode &>(value).prev= prev; static_cast<ListNode &>(value).next= curr; return iterator(&value); } iterator erase(iterator pos) noexcept { ListNode *prev= pos.node_->prev; ListNode *next= pos.node_->next; prev->next= next; next->prev= prev; #ifndef DBUG_OFF ListNode *curr= pos.node_; curr->prev= nullptr; curr->next= nullptr; #endif return Iterator(next); } void push_back(reference value) noexcept { insert(end(), value); } void pop_back() noexcept { erase(end()); } void push_front(reference value) noexcept { insert(begin(), value); } void pop_front() noexcept { erase(begin()); } // STL version is O(n) but this is O(1) because an element can't be inserted // several times in the same ilist. void remove(reference value) noexcept { erase(iterator(&value)); } private: ListNode sentinel_; }; // 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. typedef T value_type; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef value_type &reference; typedef const value_type &const_reference; typedef T *pointer; typedef const T *const_pointer; typedef typename BASE::Iterator iterator; typedef const typename BASE::Iterator const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const iterator> const_reverse_iterator; sized_ilist() noexcept : size_(0) {} size_type size() const noexcept { return size_; } void clear() noexcept { BASE::clear(); size_= 0; } iterator insert(iterator pos, reference value) noexcept { ++size_; return BASE::insert(pos, value); } iterator erase(iterator pos) noexcept { --size_; return BASE::erase(pos); } void push_back(reference value) noexcept { insert(BASE::end(), value); } void pop_back() noexcept { erase(BASE::end()); } void push_front(reference value) noexcept { insert(BASE::begin(), value); } void pop_front() noexcept { erase(BASE::begin()); } void remove(reference value) noexcept { erase(iterator(&value)); } private: size_type size_; }; #endif