/**************************************************************************/ /* list.h */ /**************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ /* https://godotengine.org */ /**************************************************************************/ /* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */ /* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ /* "Software"), to deal in the Software without restriction, including */ /* without limitation the rights to use, copy, modify, merge, publish, */ /* distribute, sublicense, and/or sell copies of the Software, and to */ /* permit persons to whom the Software is furnished to do so, subject to */ /* the following conditions: */ /* */ /* The above copyright notice and this permission notice shall be */ /* included in all copies or substantial portions of the Software. */ /* */ /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */ /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /**************************************************************************/ #pragma once #include "core/error/error_macros.h" #include "core/os/memory.h" #include "core/templates/sort_list.h" #include /** * Ordered storage implemented as a doubly linked list. * * Elements are pointer stable. * * Core container guidance: * https://docs.godotengine.org/en/latest/engine_details/architecture/core_types.html#containers */ template class _WARN_UNUSED_ List { struct _Data; public: class Element { private: friend class List; T value; Element *next_ptr = nullptr; Element *prev_ptr = nullptr; _Data *data = nullptr; public: /** * Get NEXT Element iterator, for constant lists. */ _FORCE_INLINE_ const Element *next() const { return next_ptr; } /** * Get NEXT Element iterator, */ _FORCE_INLINE_ Element *next() { return next_ptr; } /** * Get PREV Element iterator, for constant lists. */ _FORCE_INLINE_ const Element *prev() const { return prev_ptr; } /** * Get PREV Element iterator, */ _FORCE_INLINE_ Element *prev() { return prev_ptr; } /** * * operator, for using as *iterator, when iterators are defined on stack. */ _FORCE_INLINE_ const T &operator*() const { return value; } /** * operator->, for using as iterator->, when iterators are defined on stack, for constant lists. */ _FORCE_INLINE_ const T *operator->() const { return &value; } /** * * operator, for using as *iterator, when iterators are defined on stack, */ _FORCE_INLINE_ T &operator*() { return value; } /** * operator->, for using as iterator->, when iterators are defined on stack, for constant lists. */ _FORCE_INLINE_ T *operator->() { return &value; } /** * get the value stored in this element. */ _FORCE_INLINE_ T &get() { return value; } /** * get the value stored in this element, for constant lists */ _FORCE_INLINE_ const T &get() const { return value; } /** * set the value stored in this element. */ _FORCE_INLINE_ void set(const T &p_value) { value = (T &)p_value; } void erase() { data->erase(this); } void transfer_to_back(List *p_dst_list); }; typedef T ValueType; struct ConstIterator { _FORCE_INLINE_ const T &operator*() const { return E->get(); } _FORCE_INLINE_ const T *operator->() const { return &E->get(); } _FORCE_INLINE_ ConstIterator &operator++() { E = E->next(); return *this; } _FORCE_INLINE_ ConstIterator &operator--() { E = E->prev(); return *this; } _FORCE_INLINE_ bool operator==(const ConstIterator &p_other) const { return E == p_other.E; } _FORCE_INLINE_ bool operator!=(const ConstIterator &p_other) const { return E != p_other.E; } _FORCE_INLINE_ ConstIterator(const Element *p_element) { E = p_element; } _FORCE_INLINE_ ConstIterator() {} _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; } private: const Element *E = nullptr; }; struct Iterator { _FORCE_INLINE_ T &operator*() const { return E->get(); } _FORCE_INLINE_ T *operator->() const { return &E->get(); } _FORCE_INLINE_ Iterator &operator++() { E = E->next(); return *this; } _FORCE_INLINE_ Iterator &operator--() { E = E->prev(); return *this; } _FORCE_INLINE_ bool operator==(const Iterator &p_other) const { return E == p_other.E; } _FORCE_INLINE_ bool operator!=(const Iterator &p_other) const { return E != p_other.E; } Iterator(Element *p_element) { E = p_element; } Iterator() {} Iterator(const Iterator &p_it) { E = p_it.E; } operator ConstIterator() const { return ConstIterator(E); } private: Element *E = nullptr; }; _FORCE_INLINE_ Iterator begin() { return Iterator(front()); } _FORCE_INLINE_ Iterator end() { return Iterator(nullptr); } #if 0 //to use when replacing find() _FORCE_INLINE_ Iterator find(const K &p_key) { return Iterator(find(p_key)); } #endif _FORCE_INLINE_ ConstIterator begin() const { return ConstIterator(front()); } _FORCE_INLINE_ ConstIterator end() const { return ConstIterator(nullptr); } #if 0 //to use when replacing find() _FORCE_INLINE_ ConstIterator find(const K &p_key) const { return ConstIterator(find(p_key)); } #endif private: struct _Data { Element *first = nullptr; Element *last = nullptr; int size_cache = 0; bool erase(Element *p_element) { ERR_FAIL_NULL_V(p_element, false); ERR_FAIL_COND_V(p_element->data != this, false); if (first == p_element) { first = p_element->next_ptr; } if (last == p_element) { last = p_element->prev_ptr; } if (p_element->prev_ptr) { p_element->prev_ptr->next_ptr = p_element->next_ptr; } if (p_element->next_ptr) { p_element->next_ptr->prev_ptr = p_element->prev_ptr; } memdelete_allocator(p_element); size_cache--; return true; } }; _Data *_data = nullptr; public: /** * return a const iterator to the beginning of the list. */ _FORCE_INLINE_ const Element *front() const _LIFETIME_BOUND_ { return _data ? _data->first : nullptr; } /** * return an iterator to the beginning of the list. */ _FORCE_INLINE_ Element *front() _LIFETIME_BOUND_ { return _data ? _data->first : nullptr; } /** * return a const iterator to the last member of the list. */ _FORCE_INLINE_ const Element *back() const _LIFETIME_BOUND_ { return _data ? _data->last : nullptr; } /** * return an iterator to the last member of the list. */ _FORCE_INLINE_ Element *back() _LIFETIME_BOUND_ { return _data ? _data->last : nullptr; } /** * store a new element at the end of the list */ Element *push_back(const T &p_value) _LIFETIME_BOUND_ { if (!_data) { _data = memnew_allocator(_Data, A); _data->first = nullptr; _data->last = nullptr; _data->size_cache = 0; } Element *n = memnew_allocator(Element, A); n->value = (T &)p_value; n->prev_ptr = _data->last; n->next_ptr = nullptr; n->data = _data; if (_data->last) { _data->last->next_ptr = n; } _data->last = n; if (!_data->first) { _data->first = n; } _data->size_cache++; return n; } void pop_back() { if (_data && _data->last) { erase(_data->last); } } /** * store a new element at the beginning of the list */ Element *push_front(const T &p_value) _LIFETIME_BOUND_ { if (!_data) { _data = memnew_allocator(_Data, A); _data->first = nullptr; _data->last = nullptr; _data->size_cache = 0; } Element *n = memnew_allocator(Element, A); n->value = (T &)p_value; n->prev_ptr = nullptr; n->next_ptr = _data->first; n->data = _data; if (_data->first) { _data->first->prev_ptr = n; } _data->first = n; if (!_data->last) { _data->last = n; } _data->size_cache++; return n; } void pop_front() { if (_data && _data->first) { erase(_data->first); } } Element *insert_after(Element *p_element, const T &p_value) _LIFETIME_BOUND_ { CRASH_COND(p_element && (!_data || p_element->data != _data)); if (!p_element) { return push_back(p_value); } Element *n = memnew_allocator(Element, A); n->value = (T &)p_value; n->prev_ptr = p_element; n->next_ptr = p_element->next_ptr; n->data = _data; if (!p_element->next_ptr) { _data->last = n; } else { p_element->next_ptr->prev_ptr = n; } p_element->next_ptr = n; _data->size_cache++; return n; } Element *insert_before(Element *p_element, const T &p_value) _LIFETIME_BOUND_ { CRASH_COND(p_element && (!_data || p_element->data != _data)); if (!p_element) { return push_back(p_value); } Element *n = memnew_allocator(Element, A); n->value = (T &)p_value; n->prev_ptr = p_element->prev_ptr; n->next_ptr = p_element; n->data = _data; if (!p_element->prev_ptr) { _data->first = n; } else { p_element->prev_ptr->next_ptr = n; } p_element->prev_ptr = n; _data->size_cache++; return n; } /** * find an element in the list, */ template const Element *find(const T_v &p_val) const _LIFETIME_BOUND_ { const Element *it = front(); while (it) { if (it->value == p_val) { return it; } it = it->next(); } return nullptr; } template Element *find(const T_v &p_val) _LIFETIME_BOUND_ { Element *it = front(); while (it) { if (it->value == p_val) { return it; } it = it->next(); } return nullptr; } /** * erase an element in the list, by iterator pointing to it. Return true if it was found/erased. */ bool erase(Element *p_element) { if (_data && p_element) { bool ret = _data->erase(p_element); if (_data->size_cache == 0) { memdelete_allocator<_Data, A>(_data); _data = nullptr; } return ret; } return false; } /** * erase the first element in the list, that contains value */ bool erase(const T &p_value) { Element *I = find(p_value); return erase(I); } /** * return whether the list is empty */ _FORCE_INLINE_ bool is_empty() const { return (!_data || !_data->size_cache); } /** * clear the list */ void clear() { while (front()) { erase(front()); } } _FORCE_INLINE_ int size() const { return _data ? _data->size_cache : 0; } void swap(Element *p_left, Element *p_right) { ERR_FAIL_COND(!p_left || !p_right); ERR_FAIL_COND(p_left->data != _data); ERR_FAIL_COND(p_right->data != _data); if (p_left == p_right) { return; } Element *A_prev = p_left->prev_ptr; Element *A_next = p_left->next_ptr; Element *B_prev = p_right->prev_ptr; Element *B_next = p_right->next_ptr; if (A_prev) { A_prev->next_ptr = p_right; } else { _data->first = p_right; } if (B_prev) { B_prev->next_ptr = p_left; } else { _data->first = p_left; } if (A_next) { A_next->prev_ptr = p_right; } else { _data->last = p_right; } if (B_next) { B_next->prev_ptr = p_left; } else { _data->last = p_left; } p_left->prev_ptr = A_next == p_right ? p_right : B_prev; p_left->next_ptr = B_next == p_left ? p_right : B_next; p_right->prev_ptr = B_next == p_left ? p_left : A_prev; p_right->next_ptr = A_next == p_right ? p_left : A_next; } /** * copy the list */ void operator=(const List &p_list) { clear(); const Element *it = p_list.front(); while (it) { push_back(it->get()); it = it->next(); } } void operator=(List &&p_list) { if (unlikely(this == &p_list)) { return; } clear(); _data = p_list._data; p_list._data = nullptr; } // Random access to elements, use with care, // do not use for iteration. T &get(int p_index) _LIFETIME_BOUND_ { CRASH_BAD_INDEX(p_index, size()); Element *I = front(); int c = 0; while (c < p_index) { I = I->next(); c++; } return I->get(); } // Random access to elements, use with care, // do not use for iteration. const T &get(int p_index) const _LIFETIME_BOUND_ { CRASH_BAD_INDEX(p_index, size()); const Element *I = front(); int c = 0; while (c < p_index) { I = I->next(); c++; } return I->get(); } void move_to_back(Element *p_element) { ERR_FAIL_COND(p_element->data != _data); if (!p_element->next_ptr) { return; } if (_data->first == p_element) { _data->first = p_element->next_ptr; } if (_data->last == p_element) { _data->last = p_element->prev_ptr; } if (p_element->prev_ptr) { p_element->prev_ptr->next_ptr = p_element->next_ptr; } p_element->next_ptr->prev_ptr = p_element->prev_ptr; _data->last->next_ptr = p_element; p_element->prev_ptr = _data->last; p_element->next_ptr = nullptr; _data->last = p_element; } void reverse() { int s = size() / 2; Element *F = front(); Element *B = back(); for (int i = 0; i < s; i++) { SWAP(F->value, B->value); F = F->next(); B = B->prev(); } } void move_to_front(Element *p_element) { ERR_FAIL_COND(p_element->data != _data); if (!p_element->prev_ptr) { return; } if (_data->first == p_element) { _data->first = p_element->next_ptr; } if (_data->last == p_element) { _data->last = p_element->prev_ptr; } p_element->prev_ptr->next_ptr = p_element->next_ptr; if (p_element->next_ptr) { p_element->next_ptr->prev_ptr = p_element->prev_ptr; } _data->first->prev_ptr = p_element; p_element->next_ptr = _data->first; p_element->prev_ptr = nullptr; _data->first = p_element; } void move_before(Element *p_value, Element *p_where) { if (p_value->prev_ptr) { p_value->prev_ptr->next_ptr = p_value->next_ptr; } else { _data->first = p_value->next_ptr; } if (p_value->next_ptr) { p_value->next_ptr->prev_ptr = p_value->prev_ptr; } else { _data->last = p_value->prev_ptr; } p_value->next_ptr = p_where; if (!p_where) { p_value->prev_ptr = _data->last; _data->last = p_value; return; } p_value->prev_ptr = p_where->prev_ptr; if (p_where->prev_ptr) { p_where->prev_ptr->next_ptr = p_value; } else { _data->first = p_value; } p_where->prev_ptr = p_value; } void sort() { sort_custom>(); } template void sort_custom() { if (size() < 2) { return; } SortList sorter; sorter.sort(_data->first, _data->last); } const void *id() const { return (void *)_data; } explicit List(const List &p_list) { const Element *it = p_list.front(); while (it) { push_back(it->get()); it = it->next(); } } List(List &&p_list) { _data = p_list._data; p_list._data = nullptr; } List() {} List(std::initializer_list p_init) { for (const T &E : p_init) { push_back(E); } } ~List() { clear(); if (_data) { ERR_FAIL_COND(_data->size_cache); memdelete_allocator<_Data, A>(_data); } } }; template void List::Element::transfer_to_back(List *p_dst_list) { // Detach from current. if (data->first == this) { data->first = data->first->next_ptr; } if (data->last == this) { data->last = data->last->prev_ptr; } if (prev_ptr) { prev_ptr->next_ptr = next_ptr; } if (next_ptr) { next_ptr->prev_ptr = prev_ptr; } data->size_cache--; // Attach to the back of the new one. if (!p_dst_list->_data) { p_dst_list->_data = memnew_allocator(_Data, A); p_dst_list->_data->first = this; p_dst_list->_data->last = nullptr; p_dst_list->_data->size_cache = 0; prev_ptr = nullptr; } else { p_dst_list->_data->last->next_ptr = this; prev_ptr = p_dst_list->_data->last; } p_dst_list->_data->last = this; next_ptr = nullptr; data = p_dst_list->_data; p_dst_list->_data->size_cache++; }