| // Copyright (c) 2019 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_ |
| #define QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_ |
| |
| // A SpdyIntrusiveList<> is a doubly-linked list where the link pointers are |
| // embedded in the elements. They are circularly linked making insertion and |
| // removal into a known position constant time and branch-free operations. |
| // |
| // Usage is similar to an STL list<> where feasible, but there are important |
| // differences. First and foremost, the elements must derive from the |
| // SpdyIntrusiveLink<> base class: |
| // |
| // struct Foo : public SpdyIntrusiveLink<Foo> { |
| // // ... |
| // } |
| // |
| // SpdyIntrusiveList<Foo> l; |
| // l.push_back(new Foo); |
| // l.push_front(new Foo); |
| // l.erase(&l.front()); |
| // l.erase(&l.back()); |
| // |
| // Intrusive lists are primarily useful when you would have considered embedding |
| // link pointers in your class directly for space or performance reasons. An |
| // SpdyIntrusiveLink<> is the size of 2 pointers, usually 16 bytes on 64-bit |
| // systems. Intrusive lists do not perform memory allocation (unlike the STL |
| // list<> class) and thus may use less memory than list<>. In particular, if the |
| // list elements are pointers to objects, using a list<> would perform an extra |
| // memory allocation for each list node structure, while an SpdyIntrusiveList<> |
| // would not. |
| // |
| // Note that SpdyIntrusiveLink is exempt from the C++ style guide's limitations |
| // on multiple inheritance, so it's fine to inherit from both SpdyIntrusiveLink |
| // and a base class, even if the base class is not a pure interface. |
| // |
| // Because the list pointers are embedded in the objects stored in an |
| // SpdyIntrusiveList<>, erasing an item from a list is constant time. Consider |
| // the following: |
| // |
| // map<string,Foo> foo_map; |
| // list<Foo*> foo_list; |
| // |
| // foo_list.push_back(&foo_map["bar"]); |
| // foo_list.erase(&foo_map["bar"]); // Compile error! |
| // |
| // The problem here is that a Foo* doesn't know where on foo_list it resides, |
| // so removal requires iteration over the list. Various tricks can be performed |
| // to overcome this. For example, a foo_list::iterator can be stored inside of |
| // the Foo object. But at that point you'd be better off using an |
| // SpdyIntrusiveList<>: |
| // |
| // map<string,Foo> foo_map; |
| // SpdyIntrusiveList<Foo> foo_list; |
| // |
| // foo_list.push_back(&foo_map["bar"]); |
| // foo_list.erase(&foo_map["bar"]); // Yeah! |
| // |
| // Note that SpdyIntrusiveLists come with a few limitations. The primary |
| // limitation is that the SpdyIntrusiveLink<> base class is not copyable or |
| // assignable. The result is that STL algorithms which mutate the order of |
| // iterators, such as reverse() and unique(), will not work by default with |
| // SpdyIntrusiveLists. In order to allow these algorithms to work you'll need to |
| // define swap() and/or operator= for your class. |
| // |
| // Another limitation is that the SpdyIntrusiveList<> structure itself is not |
| // copyable or assignable since an item/link combination can only exist on one |
| // SpdyIntrusiveList<> at a time. This limitation is a result of the link |
| // pointers for an item being intrusive in the item itself. For example, the |
| // following will not compile: |
| // |
| // FooList a; |
| // FooList b(a); // no copy constructor |
| // b = a; // no assignment operator |
| // |
| // The similar STL code does work since the link pointers are external to the |
| // item: |
| // |
| // list<int*> a; |
| // a.push_back(new int); |
| // list<int*> b(a); |
| // QUICHE_CHECK(a.front() == b.front()); |
| // |
| // Note that SpdyIntrusiveList::size() runs in O(N) time. |
| |
| #include <stddef.h> |
| #include <iterator> |
| |
| |
| namespace spdy { |
| |
| template <typename T, typename ListID> class SpdyIntrusiveList; |
| |
| template <typename T, typename ListID = void> class SpdyIntrusiveLink { |
| protected: |
| // We declare the constructor protected so that only derived types and the |
| // befriended list can construct this. |
| SpdyIntrusiveLink() : next_(nullptr), prev_(nullptr) {} |
| |
| #ifndef SWIG |
| SpdyIntrusiveLink(const SpdyIntrusiveLink&) = delete; |
| SpdyIntrusiveLink& operator=(const SpdyIntrusiveLink&) = delete; |
| #endif // SWIG |
| |
| private: |
| // We befriend the matching list type so that it can manipulate the links |
| // while they are kept private from others. |
| friend class SpdyIntrusiveList<T, ListID>; |
| |
| // Encapsulates the logic to convert from a link to its derived type. |
| T* cast_to_derived() { return static_cast<T*>(this); } |
| const T* cast_to_derived() const { return static_cast<const T*>(this); } |
| |
| SpdyIntrusiveLink* next_; |
| SpdyIntrusiveLink* prev_; |
| }; |
| |
| template <typename T, typename ListID = void> class SpdyIntrusiveList { |
| template <typename QualifiedT, typename QualifiedLinkT> class iterator_impl; |
| |
| public: |
| typedef T value_type; |
| typedef value_type *pointer; |
| typedef const value_type *const_pointer; |
| typedef value_type &reference; |
| typedef const value_type &const_reference; |
| typedef size_t size_type; |
| typedef ptrdiff_t difference_type; |
| |
| typedef SpdyIntrusiveLink<T, ListID> link_type; |
| typedef iterator_impl<T, link_type> iterator; |
| typedef iterator_impl<const T, const link_type> const_iterator; |
| typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| typedef std::reverse_iterator<iterator> reverse_iterator; |
| |
| SpdyIntrusiveList() { clear(); } |
| // After the move constructor the moved-from list will be empty. |
| // |
| // NOTE: There is no move assign operator (for now). |
| // The reason is that at the moment 'clear()' does not unlink the nodes. |
| // It makes is_linked() return true when it should return false. |
| // If such node is removed from the list (e.g. from its destructor), or is |
| // added to another list - a memory corruption will occur. |
| // Admitedly the destructor does not unlink the nodes either, but move-assign |
| // will likely make the problem more prominent. |
| #ifndef SWIG |
| SpdyIntrusiveList(SpdyIntrusiveList&& src) noexcept { |
| clear(); |
| if (src.empty()) return; |
| sentinel_link_.next_ = src.sentinel_link_.next_; |
| sentinel_link_.prev_ = src.sentinel_link_.prev_; |
| // Fix head and tail nodes of the list. |
| sentinel_link_.prev_->next_ = &sentinel_link_; |
| sentinel_link_.next_->prev_ = &sentinel_link_; |
| src.clear(); |
| } |
| #endif // SWIG |
| |
| iterator begin() { return iterator(sentinel_link_.next_); } |
| const_iterator begin() const { return const_iterator(sentinel_link_.next_); } |
| iterator end() { return iterator(&sentinel_link_); } |
| const_iterator end() const { return const_iterator(&sentinel_link_); } |
| reverse_iterator rbegin() { return reverse_iterator(end()); } |
| const_reverse_iterator rbegin() const { |
| return const_reverse_iterator(end()); |
| } |
| reverse_iterator rend() { return reverse_iterator(begin()); } |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(begin()); |
| } |
| |
| bool empty() const { return (sentinel_link_.next_ == &sentinel_link_); } |
| // This runs in O(N) time. |
| size_type size() const { return std::distance(begin(), end()); } |
| size_type max_size() const { return size_type(-1); } |
| |
| reference front() { return *begin(); } |
| const_reference front() const { return *begin(); } |
| reference back() { return *(--end()); } |
| const_reference back() const { return *(--end()); } |
| |
| static iterator insert(iterator position, T *obj) { |
| return insert_link(position.link(), obj); |
| } |
| void push_front(T* obj) { insert(begin(), obj); } |
| void push_back(T* obj) { insert(end(), obj); } |
| |
| static iterator erase(T* obj) { |
| link_type* obj_link = obj; |
| // Fix up the next and previous links for the previous and next objects. |
| obj_link->next_->prev_ = obj_link->prev_; |
| obj_link->prev_->next_ = obj_link->next_; |
| // Zero out the next and previous links for the removed item. This will |
| // cause any future attempt to remove the item from the list to cause a |
| // crash instead of possibly corrupting the list structure. |
| link_type* next_link = obj_link->next_; |
| obj_link->next_ = nullptr; |
| obj_link->prev_ = nullptr; |
| return iterator(next_link); |
| } |
| |
| static iterator erase(iterator position) { |
| return erase(position.operator->()); |
| } |
| void pop_front() { erase(begin()); } |
| void pop_back() { erase(--end()); } |
| |
| // Check whether the given element is linked into some list. Note that this |
| // does *not* check whether it is linked into a particular list. |
| // Also, if clear() is used to clear the containing list, is_linked() will |
| // still return true even though obj is no longer in any list. |
| static bool is_linked(const T* obj) { |
| return obj->link_type::next_ != nullptr; |
| } |
| |
| void clear() { |
| sentinel_link_.next_ = sentinel_link_.prev_ = &sentinel_link_; |
| } |
| void swap(SpdyIntrusiveList& x) { |
| SpdyIntrusiveList tmp; |
| tmp.splice(tmp.begin(), *this); |
| this->splice(this->begin(), x); |
| x.splice(x.begin(), tmp); |
| } |
| |
| void splice(iterator pos, SpdyIntrusiveList& src) { |
| splice(pos, src.begin(), src.end()); |
| } |
| |
| void splice(iterator pos, iterator i) { splice(pos, i, std::next(i)); } |
| |
| void splice(iterator pos, iterator first, iterator last) { |
| if (first == last) return; |
| |
| link_type* const last_prev = last.link()->prev_; |
| |
| // Remove from the source. |
| first.link()->prev_->next_ = last.operator->(); |
| last.link()->prev_ = first.link()->prev_; |
| |
| // Attach to the destination. |
| first.link()->prev_ = pos.link()->prev_; |
| pos.link()->prev_->next_ = first.operator->(); |
| last_prev->next_ = pos.operator->(); |
| pos.link()->prev_ = last_prev; |
| } |
| |
| private: |
| static iterator insert_link(link_type* next_link, T* obj) { |
| link_type* obj_link = obj; |
| obj_link->next_ = next_link; |
| link_type* const initial_next_prev = next_link->prev_; |
| obj_link->prev_ = initial_next_prev; |
| initial_next_prev->next_ = obj_link; |
| next_link->prev_ = obj_link; |
| return iterator(obj_link); |
| } |
| |
| // The iterator implementation is parameterized on a potentially qualified |
| // variant of T and the matching qualified link type. Essentially, QualifiedT |
| // will either be 'T' or 'const T', the latter for a const_iterator. |
| template <typename QualifiedT, typename QualifiedLinkT> |
| class iterator_impl : public std::iterator<std::bidirectional_iterator_tag, |
| QualifiedT> { |
| public: |
| typedef std::iterator<std::bidirectional_iterator_tag, QualifiedT> base; |
| |
| iterator_impl() = default; |
| iterator_impl(QualifiedLinkT* link) : link_(link) {} |
| iterator_impl(const iterator_impl& x) = default; |
| iterator_impl& operator=(const iterator_impl& x) = default; |
| |
| // Allow converting and comparing across iterators where the pointer |
| // assignment and comparisons (respectively) are allowed. |
| template <typename U, typename V> |
| iterator_impl(const iterator_impl<U, V>& x) : link_(x.link_) {} |
| template <typename U, typename V> |
| bool operator==(const iterator_impl<U, V>& x) const { |
| return link_ == x.link_; |
| } |
| template <typename U, typename V> |
| bool operator!=(const iterator_impl<U, V>& x) const { |
| return link_ != x.link_; |
| } |
| |
| typename base::reference operator*() const { return *operator->(); } |
| typename base::pointer operator->() const { |
| return link_->cast_to_derived(); |
| } |
| |
| QualifiedLinkT *link() const { return link_; } |
| |
| #ifndef SWIG // SWIG can't wrap these operator overloads. |
| iterator_impl& operator++() { link_ = link_->next_; return *this; } |
| iterator_impl operator++(int /*unused*/) { |
| iterator_impl tmp = *this; |
| ++*this; |
| return tmp; |
| } |
| iterator_impl& operator--() { link_ = link_->prev_; return *this; } |
| iterator_impl operator--(int /*unused*/) { |
| iterator_impl tmp = *this; |
| --*this; |
| return tmp; |
| } |
| #endif // SWIG |
| |
| private: |
| // Ensure iterators can access other iterators node directly. |
| template <typename U, typename V> friend class iterator_impl; |
| |
| QualifiedLinkT* link_ = nullptr; |
| }; |
| |
| // This bare link acts as the sentinel node. |
| link_type sentinel_link_; |
| |
| // These are private and undefined to prevent copying and assigning. |
| SpdyIntrusiveList(const SpdyIntrusiveList&); |
| void operator=(const SpdyIntrusiveList&); |
| }; |
| |
| } // namespace spdy |
| |
| #endif // QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_ |