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