gfx/2d/IterableArena.h

   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
  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
  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>
  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.
 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>
 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:
 139     Iterator() : mCursor(0) {}
 140
 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:
 157   Header* GetHeader(ptrdiff_t offset) { return (Header*)(mStorage + offset); }
 158
 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