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 // A simple segmented vector class.
9 // This class should be used in preference to mozilla::Vector or nsTArray when
10 // you are simply gathering items in order to later iterate over them.
12 // - In the case where you don't know the final size in advance, using
13 // SegmentedVector avoids the need to repeatedly allocate increasingly large
14 // buffers and copy the data into them.
16 // - In the case where you know the final size in advance and so can set the
17 // capacity appropriately, using SegmentedVector still avoids the need for
18 // large allocations (which can trigger OOMs).
20 #ifndef mozilla_SegmentedVector_h
21 #define mozilla_SegmentedVector_h
23 #include "mozilla/Alignment.h"
24 #include "mozilla/AllocPolicy.h"
25 #include "mozilla/Array.h"
26 #include "mozilla/LinkedList.h"
27 #include "mozilla/MemoryReporting.h"
28 #include "mozilla/Move.h"
29 #include "mozilla/TypeTraits.h"
31 #include <new> // for placement new
35 // |IdealSegmentSize| specifies how big each segment will be in bytes (or as
36 // close as is possible). Use the following guidelines to choose a size.
38 // - It should be a power-of-two, to avoid slop.
40 // - It should not be too small, so that segment allocations are infrequent,
41 // and so that per-segment bookkeeping overhead is low. Typically each
42 // segment should be able to hold hundreds of elements, at least.
44 // - It should not be too large, so that OOMs are unlikely when allocating
45 // segments, and so that not too much space is wasted when the final segment
48 // The ideal size depends on how the SegmentedVector is used and the size of
49 // |T|, but reasonable sizes include 1024, 4096 (the default), 8192, and 16384.
52 size_t IdealSegmentSize
= 4096,
53 typename AllocPolicy
= MallocAllocPolicy
>
54 class SegmentedVector
: private AllocPolicy
56 template<size_t SegmentCapacity
>
58 : public mozilla::LinkedListElement
<SegmentImpl
<SegmentCapacity
>>
60 SegmentImpl() : mLength(0) {}
64 for (uint32_t i
= 0; i
< mLength
; i
++) {
69 uint32_t Length() const { return mLength
; }
71 T
* Elems() { return reinterpret_cast<T
*>(&mStorage
.mBuf
); }
73 T
& operator[](size_t aIndex
)
75 MOZ_ASSERT(aIndex
< mLength
);
76 return Elems()[aIndex
];
79 const T
& operator[](size_t aIndex
) const
81 MOZ_ASSERT(aIndex
< mLength
);
82 return Elems()[aIndex
];
88 // GCC 4.4 gives a bogus "invalid use of member" error for this
89 // assertion, so skip it in that case. Once bug 1056337 lands and GCC 4.4
90 // is no longer used we should be able to remove this condition.
91 #if !(defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ == 4))
92 MOZ_ASSERT(mLength
< SegmentCapacity
);
94 // Pre-increment mLength so that the bounds-check in operator[] passes.
96 T
* elem
= &(*this)[mLength
- 1];
97 new (elem
) T(mozilla::Forward
<U
>(aU
));
102 // The union ensures that the elements are appropriately aligned.
105 char mBuf
[sizeof(T
) * SegmentCapacity
];
106 mozilla::AlignedElem
<MOZ_ALIGNOF(T
)> mAlign
;
109 static_assert(MOZ_ALIGNOF(T
) == MOZ_ALIGNOF(Storage
),
110 "SegmentedVector provides incorrect alignment");
113 // See how many we elements we can fit in a segment of IdealSegmentSize. If
114 // IdealSegmentSize is too small, it'll be just one. The +1 is because
115 // kSingleElementSegmentSize already accounts for one element.
116 static const size_t kSingleElementSegmentSize
= sizeof(SegmentImpl
<1>);
117 static const size_t kSegmentCapacity
=
118 kSingleElementSegmentSize
<= IdealSegmentSize
119 ? (IdealSegmentSize
- kSingleElementSegmentSize
) / sizeof(T
) + 1
122 typedef SegmentImpl
<kSegmentCapacity
> Segment
;
125 // The |aIdealSegmentSize| is only for sanity checking. If it's specified, we
126 // check that the actual segment size is as close as possible to it. This
127 // serves as a sanity check for SegmentedVectorCapacity's capacity
129 explicit SegmentedVector(size_t aIdealSegmentSize
= 0)
131 // The difference between the actual segment size and the ideal segment
132 // size should be less than the size of a single element... unless the
133 // ideal size was too small, in which case the capacity should be one.
135 aIdealSegmentSize
!= 0,
136 (sizeof(Segment
) > aIdealSegmentSize
&& kSegmentCapacity
== 1) ||
137 aIdealSegmentSize
- sizeof(Segment
) < sizeof(T
));
140 ~SegmentedVector() { Clear(); }
142 bool IsEmpty() const { return !mSegments
.getFirst(); }
144 // Note that this is O(n) rather than O(1), but the constant factor is very
145 // small because it only has to do one addition per segment.
146 size_t Length() const
149 for (auto segment
= mSegments
.getFirst();
151 segment
= segment
->getNext()) {
152 n
+= segment
->Length();
157 // Returns false if the allocation failed. (If you are using an infallible
158 // allocation policy, use InfallibleAppend() instead.)
160 MOZ_WARN_UNUSED_RESULT
bool Append(U
&& aU
)
162 Segment
* last
= mSegments
.getLast();
163 if (!last
|| last
->Length() == kSegmentCapacity
) {
164 last
= this->template pod_malloc
<Segment
>(1);
168 new (last
) Segment();
169 mSegments
.insertBack(last
);
171 last
->Append(mozilla::Forward
<U
>(aU
));
175 // You should probably only use this instead of Append() if you are using an
176 // infallible allocation policy. It will crash if the allocation fails.
178 void InfallibleAppend(U
&& aU
)
180 bool ok
= Append(mozilla::Forward
<U
>(aU
));
181 MOZ_RELEASE_ASSERT(ok
);
187 while ((segment
= mSegments
.popFirst())) {
189 this->free_(segment
);
193 // Use this class to iterate over a SegmentedVector, like so:
195 // for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
196 // MyElem& elem = iter.Get();
202 friend class SegmentedVector
;
207 explicit IterImpl(SegmentedVector
* aVector
)
208 : mSegment(aVector
->mSegments
.getFirst())
213 bool Done() const { return !mSegment
; }
218 return (*mSegment
)[mIndex
];
224 return (*mSegment
)[mIndex
];
231 if (mIndex
== mSegment
->Length()) {
232 mSegment
= mSegment
->getNext();
238 IterImpl
Iter() { return IterImpl(this); }
240 // Measure the memory consumption of the vector excluding |this|. Note that
241 // it only measures the vector itself. If the vector elements contain
242 // pointers to other memory blocks, those blocks must be measured separately
243 // during a subsequent iteration over the vector.
244 size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const
246 return mSegments
.sizeOfExcludingThis(aMallocSizeOf
);
249 // Like sizeOfExcludingThis(), but measures |this| as well.
250 size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const
252 return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf
);
256 mozilla::LinkedList
<Segment
> mSegments
;
259 } // namespace mozilla
261 #endif /* mozilla_SegmentedVector_h */