xpcom/threads/Queue.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_Queue_h
   8 #define mozilla_Queue_h
   9
  10 #include <algorithm>
  11 #include <utility>
  12 #include <stdint.h>
  13 #include "mozilla/MemoryReporting.h"
  14 #include "mozilla/Assertions.h"
  15 #include "mozalloc.h"
  16
  17 namespace mozilla {
  18
  19 // A queue implements a singly linked list of pages, each of which contains some
  20 // number of elements. Since the queue needs to store a "next" pointer, the
  21 // actual number of elements per page won't be quite as many as were requested.
  22 //
  23 // Each page consists of N entries.  We use the head buffer as a circular buffer
  24 // if it's the only buffer; if we have more than one buffer when the head is
  25 // empty we release it.  This avoids occasional freeing and reallocating buffers
  26 // every N entries.  We'll still allocate and free every N if the normal queue
  27 // depth is greated than N.  A fancier solution would be to move an empty Head
  28 // buffer to be an empty tail buffer, freeing if we have multiple empty tails,
  29 // but that probably isn't worth it.
  30 //
  31 // Cases:
  32 //   a) single buffer, circular
  33 //      Push: if not full:
  34 //              Add to tail, increase count
  35 //            full:
  36 //              Add new page, insert there and increase count.
  37 //      Pop:
  38 //            take entry, bump head and decrease count
  39 //   b) multiple buffers:
  40 //      Push: if not full:
  41 //              Add to tail, increase count
  42 //            full:
  43 //              Add new page, insert there and increase count.
  44 //      Pop:
  45 //            take entry, bump head and decrease count
  46 //            if buffer is empty, free head buffer and promote next to head
  47 //
  48 template <class T, size_t RequestedItemsPerPage = 256>
  49 class Queue {
  50  public:
  51   Queue() = default;
  52
  53   Queue(Queue&& aOther) noexcept
  54       : mHead(std::exchange(aOther.mHead, nullptr)),
  55         mTail(std::exchange(aOther.mTail, nullptr)),
  56         mCount(std::exchange(aOther.mCount, 0)),
  57         mOffsetHead(std::exchange(aOther.mOffsetHead, 0)),
  58         mHeadLength(std::exchange(aOther.mHeadLength, 0)) {}
  59
  60   Queue& operator=(Queue&& aOther) noexcept {
  61     Clear();
  62
  63     mHead = std::exchange(aOther.mHead, nullptr);
  64     mTail = std::exchange(aOther.mTail, nullptr);
  65     mCount = std::exchange(aOther.mCount, 0);
  66     mOffsetHead = std::exchange(aOther.mOffsetHead, 0);
  67     mHeadLength = std::exchange(aOther.mHeadLength, 0);
  68     return *this;
  69   }
  70
  71   ~Queue() { Clear(); }
  72
  73   // Discard all elements form the queue, clearing it to be empty.
  74   void Clear() {
  75     while (!IsEmpty()) {
  76       Pop();
  77     }
  78     if (mHead) {
  79       free(mHead);
  80       mHead = nullptr;
  81     }
  82   }
  83
  84   T& Push(T&& aElement) {
  85     MOZ_ASSERT(mCount < std::numeric_limits<uint32_t>::max());
  86
  87     if (!mHead) {
  88       // First page
  89       mHead = NewPage();
  90       MOZ_ASSERT(mHead);
  91
  92       mTail = mHead;
  93       T* eltPtr = &mTail->mEvents[0];
  94       new (eltPtr) T(std::move(aElement));
  95       mOffsetHead = 0;
  96       mCount = 1;
  97       mHeadLength = 1;
  98       return *eltPtr;
  99     }
 100     if (mHead == mTail && mCount < ItemsPerPage) {
 101       // Single buffer, circular
 102       uint16_t offsetTail = (mOffsetHead + mCount) % ItemsPerPage;
 103       T* eltPtr = &mHead->mEvents[offsetTail];
 104       new (eltPtr) T(std::move(aElement));
 105       ++mCount;
 106       ++mHeadLength;
 107       MOZ_ASSERT(mCount == mHeadLength);
 108       return *eltPtr;
 109     }
 110
 111     // Multiple buffers
 112     uint16_t offsetTail = (mCount - mHeadLength) % ItemsPerPage;
 113     if (offsetTail == 0) {
 114       // Tail buffer is full
 115       Page* page = NewPage();
 116       MOZ_ASSERT(page);
 117
 118       mTail->mNext = page;
 119       mTail = page;
 120       T* eltPtr = &page->mEvents[0];
 121       new (eltPtr) T(std::move(aElement));
 122       ++mCount;
 123       return *eltPtr;
 124     }
 125
 126     MOZ_ASSERT(mHead != mTail, "can't have a non-circular single buffer");
 127     T* eltPtr = &mTail->mEvents[offsetTail];
 128     new (eltPtr) T(std::move(aElement));
 129     ++mCount;
 130     return *eltPtr;
 131   }
 132
 133   bool IsEmpty() const { return !mCount; }
 134
 135   T Pop() {
 136     MOZ_ASSERT(!IsEmpty());
 137
 138     T result = std::move(mHead->mEvents[mOffsetHead]);
 139     mHead->mEvents[mOffsetHead].~T();
 140     // Could be circular buffer, or not.
 141     mOffsetHead = (mOffsetHead + 1) % ItemsPerPage;
 142     mCount -= 1;
 143     mHeadLength -= 1;
 144
 145     // Check if the head page is empty and we have more pages.
 146     if (mHead != mTail && mHeadLength == 0) {
 147       Page* dead = mHead;
 148       mHead = mHead->mNext;
 149       free(dead);
 150       // Non-circular buffer
 151       mOffsetHead = 0;
 152       mHeadLength =
 153           static_cast<uint16_t>(std::min<uint32_t>(mCount, ItemsPerPage));
 154       // if there are still >1 pages, the new head is full.
 155     }
 156
 157     return result;
 158   }
 159
 160   T& FirstElement() {
 161     MOZ_ASSERT(!IsEmpty());
 162     return mHead->mEvents[mOffsetHead];
 163   }
 164
 165   const T& FirstElement() const {
 166     MOZ_ASSERT(!IsEmpty());
 167     return mHead->mEvents[mOffsetHead];
 168   }
 169
 170   size_t Count() const { return mCount; }
 171
 172   size_t ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
 173     size_t n = 0;
 174     if (mHead) {
 175       for (Page* page = mHead; page != mTail; page = page->mNext) {
 176         n += aMallocSizeOf(page);
 177       }
 178     }
 179     return n;
 180   }
 181
 182   size_t ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
 183     return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
 184   }
 185
 186  private:
 187   static_assert(
 188       (RequestedItemsPerPage & (RequestedItemsPerPage - 1)) == 0,
 189       "RequestedItemsPerPage should be a power of two to avoid heap slop.");
 190
 191   // Since a Page must also contain a "next" pointer, we use one of the items to
 192   // store this pointer. If sizeof(T) > sizeof(Page*), then some space will be
 193   // wasted. So be it.
 194   static constexpr size_t ItemsPerPage = RequestedItemsPerPage - 1;
 195
 196   // Page objects are linked together to form a simple deque.
 197   struct Page {
 198     struct Page* mNext;
 199     T mEvents[ItemsPerPage];
 200   };
 201
 202   static Page* NewPage() {
 203     return static_cast<Page*>(moz_xcalloc(1, sizeof(Page)));
 204   }
 205
 206   Page* mHead = nullptr;
 207   Page* mTail = nullptr;
 208
 209   uint32_t mCount = 0;       // Number of items in the queue
 210   uint16_t mOffsetHead = 0;  // Read position in head page
 211   uint16_t mHeadLength = 0;  // Number of items in the circular head page
 212 };
 213
 214 }  // namespace mozilla
 215
 216 #endif  // mozilla_Queue_h