1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef MOZILLA_GFX_ITERABLEARENA_H_ 8 #define MOZILLA_GFX_ITERABLEARENA_H_ 9 10 #include <stdint.h> 11 #include <stdio.h> 12 #include <string.h> 13 14 #include <utility> 15 #include <vector> 16 17 #include "mozilla/Assertions.h" 18 #include "mozilla/gfx/Logging.h" 19 20 namespace mozilla { 21 namespace gfx { 22 23 /// A simple pool allocator for plain data structures. 24 /// 25 /// Beware that the pool will not attempt to run the destructors. It is the 26 /// responsibility of the user of this class to either use objects with no 27 /// destructor or to manually call the allocated objects destructors. 28 /// If the pool is growable, its allocated objects must be safely moveable in 29 /// in memory (through memcpy). 30 class IterableArena { 31 protected: 32 struct Header { 33 size_t mBlocSize; 34 }; 35 36 public: 37 enum ArenaType { FIXED_SIZE, GROWABLE }; 38 IterableArena(ArenaType aType,size_t aStorageSize)39 IterableArena(ArenaType aType, size_t aStorageSize) 40 : mSize(aStorageSize), mCursor(0), mIsGrowable(aType == GROWABLE) { 41 if (mSize == 0) { 42 mSize = 128; 43 } 44 45 mStorage = (uint8_t*)malloc(mSize); 46 if (mStorage == nullptr) { 47 gfxCriticalError() << "Not enough Memory allocate a memory pool of size " 48 << aStorageSize; 49 MOZ_CRASH("GFX: Out of memory IterableArena"); 50 } 51 } 52 ~IterableArena()53 ~IterableArena() { free(mStorage); } 54 55 /// Constructs a new item in the pool and returns a positive offset in case of 56 /// success. 57 /// 58 /// The offset never changes even if the storage is reallocated, so users 59 /// of this class should prefer storing offsets rather than direct pointers 60 /// to the allocated objects. 61 /// Alloc can cause the storage to be reallocated if the pool was initialized 62 /// with IterableArena::GROWABLE. 63 /// If for any reason the pool fails to allocate enough space for the new item 64 /// Alloc returns a negative offset and the object's constructor is not 65 /// called. 66 template <typename T, typename... Args> Alloc(Args &&...aArgs)67 ptrdiff_t Alloc(Args&&... aArgs) { 68 void* storage = nullptr; 69 auto offset = AllocRaw(sizeof(T), &storage); 70 if (offset < 0) { 71 return offset; 72 } 73 new (storage) T(std::forward<Args>(aArgs)...); 74 return offset; 75 } 76 77 ptrdiff_t AllocRaw(size_t aSize, void** aOutPtr = nullptr) { 78 const size_t blocSize = AlignedSize(sizeof(Header) + aSize); 79 80 if (AlignedSize(mCursor + blocSize) > mSize) { 81 if (!mIsGrowable) { 82 return -1; 83 } 84 85 size_t newSize = mSize * 2; 86 while (AlignedSize(mCursor + blocSize) > newSize) { 87 newSize *= 2; 88 } 89 90 uint8_t* newStorage = (uint8_t*)realloc(mStorage, newSize); 91 if (!newStorage) { 92 gfxCriticalError() 93 << "Not enough Memory to grow the memory pool, size: " << newSize; 94 return -1; 95 } 96 97 mStorage = newStorage; 98 mSize = newSize; 99 } 100 ptrdiff_t offset = mCursor; 101 GetHeader(offset)->mBlocSize = blocSize; 102 mCursor += blocSize; 103 if (aOutPtr) { 104 *aOutPtr = GetStorage(offset); 105 } 106 return offset; 107 } 108 109 /// Get access to an allocated item at a given offset (only use offsets 110 /// returned by Alloc or AllocRaw). 111 /// 112 /// If the pool is growable, the returned pointer is only valid temporarily. 113 /// The underlying storage can be reallocated in Alloc or AllocRaw, so do not 114 /// keep these pointers around and store the offset instead. 115 void* GetStorage(ptrdiff_t offset = 0) { 116 MOZ_ASSERT(offset >= 0); 117 MOZ_ASSERT(offset < mCursor); 118 return offset >= 0 ? mStorage + offset + sizeof(Header) : nullptr; 119 } 120 121 /// Clears the storage without running any destructor and without deallocating 122 /// it. Clear()123 void Clear() { mCursor = 0; } 124 125 /// Iterate over the elements allocated in this pool. 126 /// 127 /// Takes a lambda or function object accepting a void* as parameter. 128 template <typename Func> ForEach(Func cb)129 void ForEach(Func cb) { 130 Iterator it; 131 while (void* ptr = it.Next(this)) { 132 cb(ptr); 133 } 134 } 135 136 /// A simple iterator over an arena. 137 class Iterator { 138 public: Iterator()139 Iterator() : mCursor(0) {} 140 Next(IterableArena * aArena)141 void* Next(IterableArena* aArena) { 142 if (mCursor >= aArena->mCursor) { 143 return nullptr; 144 } 145 void* result = aArena->GetStorage(mCursor); 146 const size_t blocSize = aArena->GetHeader(mCursor)->mBlocSize; 147 MOZ_ASSERT(blocSize != 0); 148 mCursor += blocSize; 149 return result; 150 } 151 152 private: 153 ptrdiff_t mCursor; 154 }; 155 156 protected: GetHeader(ptrdiff_t offset)157 Header* GetHeader(ptrdiff_t offset) { return (Header*)(mStorage + offset); } 158 AlignedSize(size_t aSize)159 size_t AlignedSize(size_t aSize) const { 160 const size_t alignment = sizeof(uintptr_t); 161 return aSize + (alignment - (aSize % alignment)) % alignment; 162 } 163 164 uint8_t* mStorage; 165 uint32_t mSize; 166 ptrdiff_t mCursor; 167 bool mIsGrowable; 168 169 friend class Iterator; 170 }; 171 172 } // namespace gfx 173 } // namespace mozilla 174 175 #endif 176