1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
/* -*- 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_dom_FastFrontRemovableArray_h
#define mozilla_dom_FastFrontRemovableArray_h
// An nsTArray of pointers where removing from the front is amortized constant
// time.
#include "mozilla/Span.h"
#include "nsTArray.h"
namespace mozilla::dom {
template <typename T, size_t InlineCapacity = 0>
class FastFrontRemovableArray {
using InternalList = AutoTArray<T, InlineCapacity>;
public:
static const size_t NoIndex = InternalList::NoIndex;
operator Span<const T>() const { return AsSpan(); }
operator Span<T>() { return AsSpan(); }
Span<const T> AsSpan() const {
return Span<const T>(mList).From(mIndexOfFirstElement);
}
Span<T> AsSpan() { return Span<T>(mList).From(mIndexOfFirstElement); }
size_t Length() const { return mList.Length() - mIndexOfFirstElement; }
bool IsEmpty() const { return Length() == 0; }
void RemoveElementAt(size_t aIndex) {
if (aIndex == 0) {
mList[mIndexOfFirstElement++] = nullptr;
if (mIndexOfFirstElement > std::max(size_t(4), mList.Length() / 4)) {
// Compact the list if it gets too big. This shifts all the elements,
// which is expensive, so only do it if we have more than 4 elements
// wasted at the front, and more than a quarter of the list is wasted
// space in the front.
mList.RemoveElementsAt(0, mIndexOfFirstElement);
mIndexOfFirstElement = 0;
}
return;
}
mList.RemoveElementAt(aIndex + mIndexOfFirstElement);
if (IsEmpty()) {
Clear();
}
}
template <typename U>
void InsertElementAt(size_t aIndex, U* aElem) {
if (mIndexOfFirstElement && aIndex == 0) {
mList[--mIndexOfFirstElement] = aElem;
return;
}
mList.InsertElementAt(aIndex + mIndexOfFirstElement, aElem);
}
T& operator[](size_t aIndex) { return mList[aIndex + mIndexOfFirstElement]; }
const T& operator[](size_t aIndex) const {
return mList[aIndex + mIndexOfFirstElement];
}
T& ElementAt(size_t aIndex) { return mList[aIndex + mIndexOfFirstElement]; }
const T& ElementAt(size_t aIndex) const {
return mList[aIndex + mIndexOfFirstElement];
}
T& SafeElementAt(size_t aIndex, T& aDef) {
return mList.SafeElementAt(aIndex + mIndexOfFirstElement, aDef);
}
const T& SafeElementAt(size_t aIndex, const T& aDef) const {
return mList.SafeElementAt(aIndex + mIndexOfFirstElement, aDef);
}
const T& FirstElement() const { return ElementAt(0); }
const T& LastElement() const { return mList.LastElement(); }
T& FirstElement() { return ElementAt(0); }
T& LastElement() { return mList.LastElement(); }
template <typename U>
void AppendElement(U* aElem) {
mList.AppendElement(aElem);
}
template <typename Item>
bool RemoveElement(const Item& aItem) {
auto i = IndexOf(aItem);
if (i == NoIndex) {
return false;
}
RemoveElementAt(i);
return true;
}
template <typename Item>
bool Contains(const Item& aItem) const {
return IndexOf(aItem) != NoIndex;
}
void Clear() {
mList.Clear();
mIndexOfFirstElement = 0;
}
template <typename Item>
size_t IndexOf(const Item& aItem) const {
auto index = mList.IndexOf(aItem, mIndexOfFirstElement);
if (index == NoIndex || mIndexOfFirstElement == 0) {
return index;
}
return index - mIndexOfFirstElement;
}
private:
AutoTArray<T, InlineCapacity> mList;
size_t mIndexOfFirstElement = 0;
};
template <typename T, size_t InlineCap>
inline void ImplCycleCollectionUnlink(
FastFrontRemovableArray<T, InlineCap>& aField) {
aField.Clear();
}
template <typename T, size_t InlineCap, typename Callback>
inline void ImplCycleCollectionIndexedContainer(
FastFrontRemovableArray<T, InlineCap>& aField, Callback&& aCallback) {
for (auto& value : aField.AsSpan()) {
aCallback(value);
}
}
} // namespace mozilla::dom
#endif
|
