#pragma once #include "list/ListItem.hpp" #include "iterator/ListIterator.hpp" #include "../memory/PoolAllocator.hpp" namespace sprawl { namespace collections { template<typename T> class List; } } template<typename T> class sprawl::collections::List { public: typedef detail::ListItem<T> ItemType; typedef ListIterator<T, ItemType, std::bidirectional_iterator_tag> iterator; typedef ListIterator<T, ItemType, std::bidirectional_iterator_tag> const const_iterator; typedef sprawl::memory::PoolAllocator<sizeof(ItemType)> allocator; List() : m_first(nullptr) , m_last(nullptr) , m_size(0) { // } List(List const& other) : m_first(nullptr) , m_last(nullptr) , m_size(0) { ItemType* item = other.m_first; while(item) { PushBack(item->m_value); item = item->next; } } List(List&& other) : m_first(other.m_first) , m_last(other.m_last) , m_size(other.m_size) { other.m_first = nullptr; other.m_last = nullptr; other.m_size = 0; } ~List() { Clear(); } void PushBack(T const& item) { ItemType* newItem = (ItemType*)allocator::alloc(); new(newItem) ItemType(item); if(m_first == nullptr) { m_first = newItem; m_last = newItem; ++m_size; } else { insertAfter_(newItem, m_last); } } void PushBack(T&& item) { ItemType* newItem = (ItemType*)allocator::alloc(); new(newItem) ItemType(std::move(item)); if(m_first == nullptr) { m_first = newItem; m_last = newItem; ++m_size; } else { insertAfter_(newItem, m_last); } } void PushFront(T const& item) { ItemType* newItem = (ItemType*)allocator::alloc(); new(newItem) ItemType(item); if(m_first == nullptr) { m_first = newItem; m_last = newItem; ++m_size; } else { insertBefore_(newItem, m_first); } } void PushFront(T&& item) { ItemType* newItem = (ItemType*)allocator::alloc(); new(newItem) ItemType(std::move(item)); if(m_first == nullptr) { m_first = newItem; m_last = newItem; ++m_size; } else { insertBefore_(newItem, m_first); } } void PopFront() { ItemType* item = m_first; m_first = item->next; m_first->prev = nullptr; item->~ItemType(); allocator::free(item); --m_size; } void PopBack() { ItemType* item = m_last; m_last = item->prev; m_last->next = nullptr; item->~ItemType(); allocator::free(item); --m_size; } void Insert(const_iterator& insertAfter, T const& item) { ItemType* newItem = (ItemType*)allocator::alloc(); new(newItem) ItemType(item); ItemType* insertItem = insertAfter.m_currentItem; insertBefore_(newItem, insertItem); } void Insert(const_iterator& insertAfter, T&& item) { ItemType* newItem = (ItemType*)allocator::alloc(); new(newItem) ItemType(std::move(item)); ItemType* insertItem = insertAfter.m_currentItem; insertBefore_(newItem, insertItem); } void Erase(const_iterator& iter) { ItemType* item = iter.m_currentItem; if(!item) { return; } if(item == m_first) { m_first = item->next; } if(item == m_last) { m_last = item->prev; } if(item->next) { item->next->prev = item->prev; } if(item->prev) { item->prev->next = item->next; } item->~ItemType(); allocator::free(item); --m_size; } size_t Size() { return m_size; } bool Empty() { return m_size == 0; } T& Front() { return m_first->m_value; } T& Back() { return m_last->m_value; } T const& Front() const { return m_first->m_value; } T const& Back() const { return m_last->m_value; } void Clear() { ItemType* item = m_first; while(item) { ItemType* del = item; item = item->next; del->~ItemType(); allocator::free(del); } m_first = nullptr; m_last = nullptr; m_size = 0; } iterator begin() { return iterator(m_first); } iterator end() { return iterator(nullptr); } const_iterator begin() const { return const_iterator(m_first); } const_iterator end() const { return const_iterator(nullptr); } const_iterator cbegin() { return const_iterator(m_first); } const_iterator cend() { return const_iterator(nullptr); } private: void insertAfter_(ItemType* newItem, ItemType* insertAfter) { if(insertAfter->next) { newItem->next = insertAfter->next; insertAfter->next->prev = newItem; } insertAfter->next = newItem; newItem->prev = insertAfter; if(newItem->prev == m_last) { m_last = newItem; } ++m_size; } void insertBefore_(ItemType* newItem, ItemType* insertBefore) { if(insertBefore->prev) { newItem->prev = insertBefore->prev; insertBefore->prev->next = newItem; } insertBefore->prev = newItem; newItem->next = insertBefore; if(newItem->next == m_first) { m_first = newItem; } ++m_size; } ItemType* m_first; ItemType* m_last; size_t m_size; };
# | Change | User | Description | Committed | |
---|---|---|---|---|---|
#2 | 18645 | brandon_m_bare | Integrated latest version of libsprawl. | ||
#1 | 15089 | brandon_m_bare | First integration of sprawl. | ||
//guest/ShadauxCat/Sprawl/Mainline/collections/List.hpp | |||||
#5 | 14163 | ShadauxCat |
-Renamed HashMap functions to follow coding style. Only begin, end, find, and variants are left lowercase, in keeping with C++ algorithm and range-based for support. -Fixed some accounting issues with list and forwardlist; size wasn't properly being maintained. -Made a small pedantic change to ThreadManager to ensure that m_numThreadsSynced got reset to 0 before the NotifyAll() to eliminate the miniscule potential for deadlock it would cause if it happened after another thread had already woken up. #review-14164 |
||
#4 | 14100 | ShadauxCat |
-Added Deque implementation using circular buffer. -Fixed List::Insert() and ForwardList::Insert() inserting after the iterator instead of before it. Adjusted the unit tests to compensate. -Fixed a couple of small vector bugs #review-14101 |
||
#3 | 14091 | ShadauxCat |
-Created Vector class, iterator, and unit test -Made list iterator a bidirectional iterator when created from a doubly-linked list. (It still has operator-- when created from singly-linked list, but it won't compile if it's used.) -Changed front() and back() in list classes to Front() and Back() #review-14083 |
||
#2 | 12508 | ShadauxCat |
-Added threading library. Currently only functional for Linux; Windows will fail to link. (I will fix this soon.) -Fixed missing move and copy constructors in List and ForwardList -Fixed broken move constructor in HashMap -Fixed missing const get() in HashMap -Fixed broken operator-> in ListIterator -Added sprawl::noncopyable -Added sketch headers for filesystem library -Made StringLiteral hashable, added special hashes for pointers and integers in murmur3 -Fixed compiler warning in async_network -Updated memory allocators to use new threading library for mutexes -Added accessibility to sprawl::StringLiteral to be able toa ccess its pointer and length and perform pointer comparisons #review-12504 |
||
#1 | 11496 | ShadauxCat | Initial checkin: Current states for csbuild and libSprawl |