From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- xpcom/threads/Queue.h | 265 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 265 insertions(+) create mode 100644 xpcom/threads/Queue.h (limited to 'xpcom/threads/Queue.h') diff --git a/xpcom/threads/Queue.h b/xpcom/threads/Queue.h new file mode 100644 index 0000000000..fa36433fdf --- /dev/null +++ b/xpcom/threads/Queue.h @@ -0,0 +1,265 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef mozilla_Queue_h +#define mozilla_Queue_h + +#include +#include +#include "mozilla/MemoryReporting.h" +#include "mozilla/Assertions.h" +#include "mozalloc.h" + +namespace mozilla { + +// define to turn on additional (DEBUG) asserts +// #define EXTRA_ASSERTS 1 + +// A queue implements a singly linked list of pages, each of which contains some +// number of elements. Since the queue needs to store a "next" pointer, the +// actual number of elements per page won't be quite as many as were requested. +// +// Each page consists of N entries. We use the head buffer as a circular buffer +// if it's the only buffer; if we have more than one buffer when the head is +// empty we release it. This avoids occasional freeing and reallocating buffers +// every N entries. We'll still allocate and free every N if the normal queue +// depth is greated than N. A fancier solution would be to move an empty Head +// buffer to be an empty tail buffer, freeing if we have multiple empty tails, +// but that probably isn't worth it. +// +// Cases: +// a) single buffer, circular +// Push: if not full: +// Add to tail, bump tail and reset to 0 if at end +// full: +// Add new page, insert there and set tail to 1 +// Pop: +// take entry and bump head, reset to 0 if at end +// b) multiple buffers: +// Push: if not full: +// Add to tail, bump tail +// full: +// Add new page, insert there and set tail to 1 +// Pop: +// take entry and bump head, reset to 0 if at end +// if buffer is empty, free head buffer and promote next to head +// +template +class Queue { + public: + Queue() = default; + + Queue(Queue&& aOther) noexcept + : mHead(std::exchange(aOther.mHead, nullptr)), + mTail(std::exchange(aOther.mTail, nullptr)), + mOffsetHead(std::exchange(aOther.mOffsetHead, 0)), + mHeadLength(std::exchange(aOther.mHeadLength, 0)), + mTailLength(std::exchange(aOther.mTailLength, 0)) {} + + Queue& operator=(Queue&& aOther) noexcept { + Clear(); + + mHead = std::exchange(aOther.mHead, nullptr); + mTail = std::exchange(aOther.mTail, nullptr); + mOffsetHead = std::exchange(aOther.mOffsetHead, 0); + mHeadLength = std::exchange(aOther.mHeadLength, 0); + mTailLength = std::exchange(aOther.mTailLength, 0); + return *this; + } + + ~Queue() { Clear(); } + + // Discard all elements form the queue, clearing it to be empty. + void Clear() { + while (!IsEmpty()) { + Pop(); + } + if (mHead) { + free(mHead); + mHead = nullptr; + } + } + + T& Push(T&& aElement) { +#if defined(EXTRA_ASSERTS) && DEBUG + size_t original_length = Count(); +#endif + if (!mHead) { + mHead = NewPage(); + MOZ_ASSERT(mHead); + + mTail = mHead; + T* eltPtr = &mTail->mEvents[0]; + new (eltPtr) T(std::move(aElement)); + mOffsetHead = 0; + mHeadLength = 1; +#ifdef EXTRA_ASSERTS + MOZ_ASSERT(Count() == original_length + 1); +#endif + return *eltPtr; + } + if ((mHead == mTail && mHeadLength == ItemsPerPage) || + (mHead != mTail && mTailLength == ItemsPerPage)) { + // either we have one (circular) buffer and it's full, or + // we have multiple buffers and the last buffer is full + Page* page = NewPage(); + MOZ_ASSERT(page); + + mTail->mNext = page; + mTail = page; + T* eltPtr = &page->mEvents[0]; + new (eltPtr) T(std::move(aElement)); + mTailLength = 1; +#ifdef EXTRA_ASSERTS + MOZ_ASSERT(Count() == original_length + 1); +#endif + return *eltPtr; + } + if (mHead == mTail) { + // we have space in the (single) head buffer + uint16_t offset = (mOffsetHead + mHeadLength++) % ItemsPerPage; + T* eltPtr = &mTail->mEvents[offset]; + new (eltPtr) T(std::move(aElement)); +#ifdef EXTRA_ASSERTS + MOZ_ASSERT(Count() == original_length + 1); +#endif + return *eltPtr; + } + // else we have space to insert into last buffer + T* eltPtr = &mTail->mEvents[mTailLength++]; + new (eltPtr) T(std::move(aElement)); +#ifdef EXTRA_ASSERTS + MOZ_ASSERT(Count() == original_length + 1); +#endif + return *eltPtr; + } + + bool IsEmpty() const { + return !mHead || (mHead == mTail && mHeadLength == 0); + } + + T Pop() { +#if defined(EXTRA_ASSERTS) && DEBUG + size_t original_length = Count(); +#endif + MOZ_ASSERT(!IsEmpty()); + + T result = std::move(mHead->mEvents[mOffsetHead]); + mHead->mEvents[mOffsetHead].~T(); + mOffsetHead = (mOffsetHead + 1) % ItemsPerPage; + mHeadLength -= 1; + + // Check if mHead points to empty (circular) Page and we have more + // pages + if (mHead != mTail && mHeadLength == 0) { + Page* dead = mHead; + mHead = mHead->mNext; + free(dead); + mOffsetHead = 0; + // if there are still >1 pages, the new head is full. + if (mHead != mTail) { + mHeadLength = ItemsPerPage; + } else { + mHeadLength = mTailLength; + mTailLength = 0; + } + } + +#ifdef EXTRA_ASSERTS + MOZ_ASSERT(Count() == original_length - 1); +#endif + return result; + } + + T& FirstElement() { + MOZ_ASSERT(!IsEmpty()); + return mHead->mEvents[mOffsetHead]; + } + + const T& FirstElement() const { + MOZ_ASSERT(!IsEmpty()); + return mHead->mEvents[mOffsetHead]; + } + + T& LastElement() { + MOZ_ASSERT(!IsEmpty()); + uint16_t offset = + mHead == mTail ? mOffsetHead + mHeadLength - 1 : mTailLength - 1; + return mTail->mEvents[offset]; + } + + const T& LastElement() const { + MOZ_ASSERT(!IsEmpty()); + uint16_t offset = + mHead == mTail ? mOffsetHead + mHeadLength - 1 : mTailLength - 1; + return mTail->mEvents[offset]; + } + + size_t Count() const { + // It is obvious count is 0 when the queue is empty. + if (!mHead) { + return 0; + } + + // Compute full (intermediate) pages; Doesn't count first or last page + int count = 0; + // 1 buffer will have mHead == mTail; 2 will have mHead->mNext == mTail + for (Page* page = mHead; page != mTail && page->mNext != mTail; + page = page->mNext) { + count += ItemsPerPage; + } + // add first and last page + count += mHeadLength + mTailLength; + MOZ_ASSERT(count >= 0); + + return count; + } + + size_t ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const { + size_t n = 0; + if (mHead) { + for (Page* page = mHead; page != mTail; page = page->mNext) { + n += aMallocSizeOf(page); + } + } + return n; + } + + size_t ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const { + return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf); + } + + private: + static_assert( + (RequestedItemsPerPage & (RequestedItemsPerPage - 1)) == 0, + "RequestedItemsPerPage should be a power of two to avoid heap slop."); + + // Since a Page must also contain a "next" pointer, we use one of the items to + // store this pointer. If sizeof(T) > sizeof(Page*), then some space will be + // wasted. So be it. + static const size_t ItemsPerPage = RequestedItemsPerPage - 1; + + // Page objects are linked together to form a simple deque. + struct Page { + struct Page* mNext; + T mEvents[ItemsPerPage]; + }; + + static Page* NewPage() { + return static_cast(moz_xcalloc(1, sizeof(Page))); + } + + Page* mHead = nullptr; + Page* mTail = nullptr; + + uint16_t mOffsetHead = 0; // Read position in head page + uint16_t mHeadLength = 0; // Number of items in the head page + uint16_t mTailLength = 0; // Number of items in the tail page +}; + +} // namespace mozilla + +#endif // mozilla_Queue_h -- cgit v1.2.3