From e59cf7b09e7388d369e8d2bf73501cde79c28708 Mon Sep 17 00:00:00 2001 From: Toni Uhlig Date: Thu, 8 Apr 2021 16:43:58 +0200 Subject: Squashed 'EASTL/' content from commit fad5471 git-subtree-dir: EASTL git-subtree-split: fad54717f8e4ebb13b20095da7efd07a53af0f10 --- include/EASTL/segmented_vector.h | 523 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 523 insertions(+) create mode 100644 include/EASTL/segmented_vector.h (limited to 'include/EASTL/segmented_vector.h') diff --git a/include/EASTL/segmented_vector.h b/include/EASTL/segmented_vector.h new file mode 100644 index 0000000..d46a942 --- /dev/null +++ b/include/EASTL/segmented_vector.h @@ -0,0 +1,523 @@ +/////////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +/////////////////////////////////////////////////////////////////////////////// + +#ifndef EASTL_SEGMENTED_VECTOR_H +#define EASTL_SEGMENTED_VECTOR_H + +#if defined(EA_PRAGMA_ONCE_SUPPORTED) + #pragma once +#endif + +#include + +namespace eastl +{ + template + class segment + { + public: + typedef eastl_size_t size_type; + typedef segment this_type; + typedef T* iterator; + typedef const T* const_iterator; + + const this_type* next_segment() const; + this_type* next_segment(); + + const_iterator begin() const; + iterator begin(); + + const_iterator end() const; + iterator end(); + + private: + static const uintptr_t kIsLastSegment = 1 << 0; + uintptr_t mPrev; + + union + { + this_type* mNext; + size_type mSize; + }; + T mData[Count]; + template friend class segmented_vector; + template friend struct segmented_vector_iterator; + }; + + + template + struct segmented_vector_iterator + { + public: + typedef segmented_vector_iterator this_type; + typedef segment segment_type; + + T* operator->() const; + T& operator*() const; + + this_type& operator++(); + this_type operator++(int); + + public: + T* mCurrent; + T* mEnd; + segment_type* mSegment; + }; + + + template + class segmented_vector + { + public: + typedef eastl_size_t size_type; + typedef segmented_vector this_type; + typedef segment segment_type; + typedef Allocator allocator_type; + typedef segmented_vector_iterator const_iterator; + typedef segmented_vector_iterator iterator; + + + segmented_vector(const Allocator& allocator = Allocator()); + ~segmented_vector(); + + allocator_type& get_allocator(); + + const segment_type* first_segment() const; + segment_type* first_segment(); + const_iterator begin() const; + iterator begin(); + + const_iterator end() const; + iterator end(); + + size_type size() const; + size_type segment_count() const; + T& front(); + T& back(); + + bool empty() const; + void clear(); + + T& push_back(); + T& push_back(const T& value); + void* push_back_uninitialized(); + + void pop_back(); + + void erase_unsorted(segment_type& segment, typename segment_type::iterator it); + iterator erase_unsorted(const iterator& i); + + void swap(this_type& other); + + protected: + segment_type* DoAllocSegment(segment_type* prevSegment); + void* DoPushBack(); + + allocator_type mAllocator; + segment_type* mFirstSegment; + segment_type* mLastSegment; + size_type mSegmentCount; + }; + + + template + inline const segment* + segment::next_segment() const + { + if (mPrev & kIsLastSegment) + return 0; + else + return mNext; + } + + template + inline segment* + segment::next_segment() + { + if (mPrev & kIsLastSegment) + return 0; + else + return mNext; + } + + template + inline typename segment::const_iterator + segment::begin() const + { + return mData; + } + + template + inline typename segment::iterator + segment::begin() + { + return mData; + } + + template + inline typename segment::const_iterator + segment::end() const + { + if (mPrev & kIsLastSegment) + return mData + mSize; + else + return mData + Count; + } + + template + inline typename segment::iterator + segment::end() + { + if (mPrev & kIsLastSegment) + return mData + mSize; + else + return mData + Count; + } + + template + T* + segmented_vector_iterator::operator->() const + { + return mCurrent; + } + + template + T& + segmented_vector_iterator::operator*() const + { + return *mCurrent; + } + + template + segmented_vector_iterator& + segmented_vector_iterator::operator++() + { + ++mCurrent; + if(EASTL_UNLIKELY(mCurrent == mEnd)) + { + if (!(mSegment->mPrev & segment_type::kIsLastSegment)) + { + mSegment = mSegment->mNext; + mCurrent = mSegment->begin(); + mEnd = mSegment->end(); + } + else + mCurrent = 0; + } + return *this; + } + + template + segmented_vector_iterator + segmented_vector_iterator::operator++(int) + { + this_type i(*this); + operator++(); + return i; + } + + + template + inline segmented_vector::segmented_vector(const Allocator& allocator) + : mAllocator(allocator) + , mFirstSegment(0) + , mLastSegment(0) + , mSegmentCount(0) + { + } + + template + inline segmented_vector::~segmented_vector() + { + clear(); + } + + template + inline typename segmented_vector::allocator_type& + segmented_vector::get_allocator() + { + return mAllocator; + } + + template + inline const typename segmented_vector::segment_type* + segmented_vector::first_segment() const + { + return mFirstSegment; + } + + template + inline typename segmented_vector::segment_type* + segmented_vector::first_segment() + { + return mFirstSegment; + } + + template + inline typename segmented_vector::const_iterator + segmented_vector::begin() const + { + iterator i; + i.mSegment = mFirstSegment; + if (mFirstSegment) + { + i.mCurrent = mFirstSegment->begin(); + i.mEnd = mFirstSegment->end(); + } + else + i.mCurrent = 0; + return (const_iterator&)i; + } + + template + inline typename segmented_vector::iterator + segmented_vector::begin() + { + iterator i; + i.mSegment = mFirstSegment; + if (mFirstSegment) + { + i.mCurrent = mFirstSegment->begin(); + i.mEnd = mFirstSegment->end(); + } + else + i.mCurrent = 0; + return i; + } + + template + inline typename segmented_vector::const_iterator + segmented_vector::end() const + { + iterator i; + i.mCurrent = 0; + return (const_iterator&)i; + } + + template + inline typename segmented_vector::iterator + segmented_vector::end() + { + iterator i; + i.mCurrent = 0; + return i; + } + + template + inline typename segmented_vector::size_type + segmented_vector::size() const + { + if (segment_type* segment = mLastSegment) + return (mSegmentCount-1)*Count + segment->mSize; + return 0; + } + + template + inline typename segmented_vector::size_type + segmented_vector::segment_count() const + { + return mSegmentCount; + } + + template + inline T& + segmented_vector::front() + { + return mFirstSegment->mData[0]; + } + + template + inline T& + segmented_vector::back() + { + segment_type* lastSegment = mLastSegment; + return lastSegment->mData[lastSegment->mSize-1]; + } + + template + inline bool + segmented_vector::empty() const + { + return mFirstSegment == 0; + } + + template + inline void + segmented_vector::clear() + { + if (segment_type* segment = mFirstSegment) + { + while (segment != mLastSegment) + { + segment_type* nextSegment = segment->mNext; + segment->~segment_type(); + EASTLFree(mAllocator, segment, sizeof(segment_type)); + segment = nextSegment; + } + for (T* i = segment->mData, *e = segment->mData + segment->mSize; i!=e; ++i) + i->~T(); + EASTLFree(mAllocator, segment, sizeof(segment_type)); + mFirstSegment = 0; + mLastSegment = 0; + mSegmentCount = 0; + } + } + + template + inline T& + segmented_vector::push_back() + { + return *(new (DoPushBack()) T()); + } + + template + inline T& + segmented_vector::push_back(const T& value) + { + return *(new (DoPushBack()) T(value)); + } + + template + inline void* + segmented_vector::push_back_uninitialized() + { + return DoPushBack(); + } + + template + inline void + segmented_vector::pop_back() + { + segment_type* lastSegment = mLastSegment; + #if EASTL_ASSERT_ENABLED + if(EASTL_UNLIKELY(!lastSegment)) + EASTL_FAIL_MSG("segmented_vector::pop_back -- segmented vector is empty"); + #endif + --lastSegment->mSize; + (lastSegment->mData + lastSegment->mSize)->T::~T(); + + if (!lastSegment->mSize) + { + --mSegmentCount; + mLastSegment = (segment_type*)(lastSegment->mPrev & (~segment_type::kIsLastSegment)); + EASTLFree(mAllocator, lastSegment, sizeof(segment_type)); + if (mLastSegment) + { + mLastSegment->mPrev |= segment_type::kIsLastSegment; + mLastSegment->mSize = Count; + } + else + mFirstSegment = 0; + } + } + + template + inline void + segmented_vector::erase_unsorted(segment_type& segment, typename segment_type::iterator it) + { + EA_UNUSED(segment); + + *it = back(); + pop_back(); + } + + template + inline typename segmented_vector::iterator + segmented_vector::erase_unsorted(const iterator& i) + { + iterator ret(i); + *i = back(); + if (i.mSegment == mLastSegment && mLastSegment->mSize == 1) + ret.mCurrent = 0; + pop_back(); + return ret; + } + + template + void + segmented_vector::swap(this_type& other) + { + allocator_type tempAllocator(mAllocator); + segment_type* tempFirstSegment = mFirstSegment; + segment_type* tempLastSegment = mLastSegment; + size_type tempSegmentCount = mSegmentCount; + + mAllocator = other.mAllocator; + mFirstSegment = other.mFirstSegment; + mLastSegment = other.mLastSegment; + mSegmentCount = other.mSegmentCount; + + other.mAllocator = tempAllocator; + other.mFirstSegment = tempFirstSegment; + other.mLastSegment = tempLastSegment; + other.mSegmentCount = tempSegmentCount; + } + + template + segment* + segmented_vector::DoAllocSegment(segment_type* prevSegment) + { + ++mSegmentCount; + segment_type* segment = (segment_type*)allocate_memory(mAllocator, sizeof(segment_type), EASTL_ALIGN_OF(segment_type), 0); + segment->mPrev = uintptr_t(prevSegment) | segment_type::kIsLastSegment; + segment->mSize = 1; + return segment; + } + + template + inline void* + segmented_vector::DoPushBack() + { + if (segment_type* segment = mLastSegment) + { + size_type size = segment->mSize; + if (size < Count) + { + ++segment->mSize; + return segment->mData + size; + } + else + { + segment_type* lastSegment = mLastSegment; + segment_type* newSegment = mLastSegment = DoAllocSegment(mLastSegment); + lastSegment->mPrev &= ~segment_type::kIsLastSegment; + lastSegment->mNext = newSegment; + return newSegment->mData; + } + } + else + { + segment = mFirstSegment = mLastSegment = DoAllocSegment(0); + return segment->mData; + } + } + + template + inline bool operator==(const segmented_vector_iterator& a, const segmented_vector_iterator& b) + { + return a.mCurrent == b.mCurrent; + } + + + template + inline bool operator!=(const segmented_vector_iterator& a, const segmented_vector_iterator& b) + { + return a.mCurrent != b.mCurrent; + } + + template + inline bool operator==(const segmented_vector_iterator& a, const segmented_vector_iterator& b) + { + return a.mCurrent == b.mCurrent; + } + + + template + inline bool operator!=(const segmented_vector_iterator& a, const segmented_vector_iterator& b) + { + return a.mCurrent != b.mCurrent; + } +} + +#endif -- cgit v1.2.3