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/. */
7 #ifndef mozilla_Queue_h
8 #define mozilla_Queue_h
12 #include "mozilla/MemoryReporting.h"
13 #include "mozilla/Assertions.h"
18 // define to turn on additional (DEBUG) asserts
19 // #define EXTRA_ASSERTS 1
21 // A queue implements a singly linked list of pages, each of which contains some
22 // number of elements. Since the queue needs to store a "next" pointer, the
23 // actual number of elements per page won't be quite as many as were requested.
25 // Each page consists of N entries. We use the head buffer as a circular buffer
26 // if it's the only buffer; if we have more than one buffer when the head is
27 // empty we release it. This avoids occasional freeing and reallocating buffers
28 // every N entries. We'll still allocate and free every N if the normal queue
29 // depth is greated than N. A fancier solution would be to move an empty Head
30 // buffer to be an empty tail buffer, freeing if we have multiple empty tails,
31 // but that probably isn't worth it.
34 // a) single buffer, circular
36 // Add to tail, bump tail and reset to 0 if at end
38 // Add new page, insert there and set tail to 1
40 // take entry and bump head, reset to 0 if at end
41 // b) multiple buffers:
43 // Add to tail, bump tail
45 // Add new page, insert there and set tail to 1
47 // take entry and bump head, reset to 0 if at end
48 // if buffer is empty, free head buffer and promote next to head
50 template <class T
, size_t RequestedItemsPerPage
= 256>
55 Queue(Queue
&& aOther
) noexcept
56 : mHead(std::exchange(aOther
.mHead
, nullptr)),
57 mTail(std::exchange(aOther
.mTail
, nullptr)),
58 mOffsetHead(std::exchange(aOther
.mOffsetHead
, 0)),
59 mHeadLength(std::exchange(aOther
.mHeadLength
, 0)),
60 mTailLength(std::exchange(aOther
.mTailLength
, 0)) {}
62 Queue
& operator=(Queue
&& aOther
) noexcept
{
65 mHead
= std::exchange(aOther
.mHead
, nullptr);
66 mTail
= std::exchange(aOther
.mTail
, nullptr);
67 mOffsetHead
= std::exchange(aOther
.mOffsetHead
, 0);
68 mHeadLength
= std::exchange(aOther
.mHeadLength
, 0);
69 mTailLength
= std::exchange(aOther
.mTailLength
, 0);
75 // Discard all elements form the queue, clearing it to be empty.
86 T
& Push(T
&& aElement
) {
87 #if defined(EXTRA_ASSERTS) && DEBUG
88 size_t original_length
= Count();
95 T
* eltPtr
= &mTail
->mEvents
[0];
96 new (eltPtr
) T(std::move(aElement
));
100 MOZ_ASSERT(Count() == original_length
+ 1);
104 if ((mHead
== mTail
&& mHeadLength
== ItemsPerPage
) ||
105 (mHead
!= mTail
&& mTailLength
== ItemsPerPage
)) {
106 // either we have one (circular) buffer and it's full, or
107 // we have multiple buffers and the last buffer is full
108 Page
* page
= NewPage();
113 T
* eltPtr
= &page
->mEvents
[0];
114 new (eltPtr
) T(std::move(aElement
));
117 MOZ_ASSERT(Count() == original_length
+ 1);
121 if (mHead
== mTail
) {
122 // we have space in the (single) head buffer
123 uint16_t offset
= (mOffsetHead
+ mHeadLength
++) % ItemsPerPage
;
124 T
* eltPtr
= &mTail
->mEvents
[offset
];
125 new (eltPtr
) T(std::move(aElement
));
127 MOZ_ASSERT(Count() == original_length
+ 1);
131 // else we have space to insert into last buffer
132 T
* eltPtr
= &mTail
->mEvents
[mTailLength
++];
133 new (eltPtr
) T(std::move(aElement
));
135 MOZ_ASSERT(Count() == original_length
+ 1);
140 bool IsEmpty() const {
141 return !mHead
|| (mHead
== mTail
&& mHeadLength
== 0);
145 #if defined(EXTRA_ASSERTS) && DEBUG
146 size_t original_length
= Count();
148 MOZ_ASSERT(!IsEmpty());
150 T result
= std::move(mHead
->mEvents
[mOffsetHead
]);
151 mHead
->mEvents
[mOffsetHead
].~T();
152 mOffsetHead
= (mOffsetHead
+ 1) % ItemsPerPage
;
155 // Check if mHead points to empty (circular) Page and we have more
157 if (mHead
!= mTail
&& mHeadLength
== 0) {
159 mHead
= mHead
->mNext
;
162 // if there are still >1 pages, the new head is full.
163 if (mHead
!= mTail
) {
164 mHeadLength
= ItemsPerPage
;
166 mHeadLength
= mTailLength
;
172 MOZ_ASSERT(Count() == original_length
- 1);
178 MOZ_ASSERT(!IsEmpty());
179 return mHead
->mEvents
[mOffsetHead
];
182 const T
& FirstElement() const {
183 MOZ_ASSERT(!IsEmpty());
184 return mHead
->mEvents
[mOffsetHead
];
188 MOZ_ASSERT(!IsEmpty());
190 mHead
== mTail
? mOffsetHead
+ mHeadLength
- 1 : mTailLength
- 1;
191 return mTail
->mEvents
[offset
];
194 const T
& LastElement() const {
195 MOZ_ASSERT(!IsEmpty());
197 mHead
== mTail
? mOffsetHead
+ mHeadLength
- 1 : mTailLength
- 1;
198 return mTail
->mEvents
[offset
];
201 size_t Count() const {
202 // It is obvious count is 0 when the queue is empty.
207 // Compute full (intermediate) pages; Doesn't count first or last page
209 // 1 buffer will have mHead == mTail; 2 will have mHead->mNext == mTail
210 for (Page
* page
= mHead
; page
!= mTail
&& page
->mNext
!= mTail
;
211 page
= page
->mNext
) {
212 count
+= ItemsPerPage
;
214 // add first and last page
215 count
+= mHeadLength
+ mTailLength
;
216 MOZ_ASSERT(count
>= 0);
221 size_t ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf
) const {
224 for (Page
* page
= mHead
; page
!= mTail
; page
= page
->mNext
) {
225 n
+= aMallocSizeOf(page
);
231 size_t ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const {
232 return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf
);
237 (RequestedItemsPerPage
& (RequestedItemsPerPage
- 1)) == 0,
238 "RequestedItemsPerPage should be a power of two to avoid heap slop.");
240 // Since a Page must also contain a "next" pointer, we use one of the items to
241 // store this pointer. If sizeof(T) > sizeof(Page*), then some space will be
243 static const size_t ItemsPerPage
= RequestedItemsPerPage
- 1;
245 // Page objects are linked together to form a simple deque.
248 T mEvents
[ItemsPerPage
];
251 static Page
* NewPage() {
252 return static_cast<Page
*>(moz_xcalloc(1, sizeof(Page
)));
255 Page
* mHead
= nullptr;
256 Page
* mTail
= nullptr;
258 uint16_t mOffsetHead
= 0; // Read position in head page
259 uint16_t mHeadLength
= 0; // Number of items in the head page
260 uint16_t mTailLength
= 0; // Number of items in the tail page
263 } // namespace mozilla
265 #endif // mozilla_Queue_h