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