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