Branch data Line data Source code
1 : : /** @file smallvector.h
2 : : * @brief Custom vector implementations using small vector optimisation
3 : : */
4 : : /* Copyright (C) 2012,2013,2014,2017,2018,2019 Olly Betts
5 : : *
6 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
7 : : * of this software and associated documentation files (the "Software"), to
8 : : * deal in the Software without restriction, including without limitation the
9 : : * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 : : * sell copies of the Software, and to permit persons to whom the Software is
11 : : * furnished to do so, subject to the following conditions:
12 : : *
13 : : * The above copyright notice and this permission notice shall be included in
14 : : * all copies or substantial portions of the Software.
15 : : *
16 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 : : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 : : * IN THE SOFTWARE.
23 : : */
24 : :
25 : : #ifndef XAPIAN_INCLUDED_SMALLVECTOR_H
26 : : #define XAPIAN_INCLUDED_SMALLVECTOR_H
27 : :
28 : : #ifndef PACKAGE
29 : : # error config.h must be included first in each C++ source file
30 : : #endif
31 : :
32 : : #include <algorithm>
33 : : #include <cstddef> // For std::size_t
34 : : #include <cstring> // For std::memcpy
35 : : #include <type_traits>
36 : :
37 : : namespace Xapian {
38 : :
39 : : /** Suitable for "simple" type T.
40 : : *
41 : : * If sizeof(T) > 2 * sizeof(T*) this isn't going to work, and it's not very
42 : : * useful when sizeof(T) == 2 * sizeof(T*) as you can only store a single
43 : : * element inline.
44 : : *
45 : : * Offers optional Copy-On-Write functionality - if COW is true, then copying
46 : : * a Vec with external data only makes a copy of that data if you attempt
47 : : * to modify it. Current COW is only supported for integral types T.
48 : : */
49 : : template<typename T,
50 : : bool COW = false,
51 : : typename = typename std::enable_if<
52 : : (COW ?
53 : : std::is_integral<T>::value :
54 : : #ifdef HAVE_STD_IS_TRIVIALLY_COPYABLE
55 : : std::is_trivially_copyable<T>::value
56 : : #else
57 : : // std::is_trivially_copyable<T> is C++11, but for example GCC
58 : : // didn't support it until version 6. Assume "true" if it's not
59 : : // available - we'll have to rely on newer compiler versions to
60 : : // catch attempts to use unsuitable types here.
61 : : true
62 : : #endif
63 : : )>::type>
64 : : class Vec {
65 : : std::size_t c;
66 : :
67 : : static constexpr std::size_t INTERNAL_CAPACITY = 2 * sizeof(T*) / sizeof(T);
68 : :
69 : : union {
70 : : T v[INTERNAL_CAPACITY];
71 : : struct {
72 : : T* b;
73 : : T* e;
74 : : } p;
75 : : } u;
76 : :
77 : : struct Vec_to_copy {
78 : : const Vec& ref;
79 : 1607516 : explicit Vec_to_copy(const Vec& o) : ref(o) {}
80 : : };
81 : :
82 : : public:
83 : : typedef std::size_t size_type;
84 : :
85 : : typedef const T* const_iterator;
86 : :
87 : : typedef T* iterator;
88 : :
89 : 15296874 : Vec() : c(0) { }
90 : :
91 : : // Prevent inadvertent copying.
92 : : Vec(const Vec&) = delete;
93 : :
94 : 1607516 : Vec(const Vec_to_copy& o) {
95 : 1607516 : do_copy_from(o.ref);
96 : 1607516 : }
97 : :
98 : : // Prevent inadvertent copying.
99 : : void operator=(const Vec&) = delete;
100 : :
101 : : void operator=(const Vec_to_copy& o) {
102 : : clear();
103 : : do_copy_from(o.ref);
104 : : }
105 : :
106 : 1607516 : Vec_to_copy copy() const {
107 : 1607516 : return Vec_to_copy(*this);
108 : : }
109 : :
110 : 17784764 : Vec(Vec&& o) noexcept : Vec() {
111 : 8892382 : std::memcpy(&u, &o.u, sizeof(u));
112 : 8892382 : std::swap(c, o.c);
113 : 8892382 : }
114 : :
115 : 836 : void operator=(Vec&& o) {
116 : 836 : clear();
117 : 836 : u = o.u;
118 : 836 : std::swap(c, o.c);
119 : 836 : }
120 : :
121 : 0 : explicit Vec(size_type n) : c(0) {
122 : 0 : reserve(n);
123 : 0 : }
124 : :
125 : 16904390 : ~Vec() {
126 : 16904390 : clear();
127 : 16904390 : }
128 : :
129 : 16678281 : size_type size() const {
130 [ + + ]: 16678281 : return is_external() ? u.p.e - u.p.b : c;
131 : : }
132 : :
133 : 8808351 : size_type capacity() const {
134 [ + + ]: 8808351 : return is_external() ? c : INTERNAL_CAPACITY;
135 : : }
136 : :
137 : 10331532 : bool empty() const {
138 [ + + ]: 10331532 : return is_external() ? u.p.b == u.p.e : c == 0;
139 : : }
140 : :
141 : 782894 : void reserve(size_type n) {
142 [ + + ]: 782894 : if (n > capacity()) {
143 : 198820 : do_reserve(n);
144 : : }
145 : 782894 : }
146 : :
147 : 5216606 : const_iterator cbegin() const {
148 [ + + ]: 5216606 : return is_external() ? u.p.b : u.v;
149 : : }
150 : :
151 : 3869472 : const_iterator cend() const {
152 [ + + ]: 3869472 : return is_external() ? u.p.e : u.v + c;
153 : : }
154 : :
155 : 5216530 : const_iterator begin() const {
156 : 5216530 : return cbegin();
157 : : }
158 : :
159 : 3869435 : const_iterator end() const {
160 : 3869435 : return cend();
161 : : }
162 : :
163 : 1566458 : iterator begin() {
164 : : // FIXME: This is a bit eager - non-const begin() is often invoked when
165 : : // no modification is needed, but doing it lazily is a bit tricky as
166 : : // the pointer will change when we COW.
167 [ + + ][ + + ]: 1566458 : if (COW && is_external() && u.p.b[-1] > 0) {
[ + + ]
168 : 12 : do_cow();
169 : : }
170 [ + + ]: 1566458 : return is_external() ? u.p.b : u.v;
171 : : }
172 : :
173 : 783570 : iterator end() {
174 [ + + ][ - + ]: 783570 : if (COW && is_external() && u.p.b[-1] > 0) {
[ - + ]
175 : 0 : do_cow();
176 : : }
177 [ + + ]: 783570 : return is_external() ? u.p.e : u.v + c;
178 : : }
179 : :
180 : 8025457 : void push_back(T elt) {
181 : 8025457 : auto cap = capacity();
182 [ + + ]: 8025457 : if (size() == cap) {
183 : 96797 : do_reserve(cap * 2);
184 : : }
185 [ + + ]: 8025457 : if (c >= INTERNAL_CAPACITY) {
186 [ - + ]: 591722 : if (COW && u.p.b[-1] > 0)
187 : 0 : do_cow();
188 : 591722 : *(u.p.e++) = elt;
189 : : } else {
190 : 7433735 : u.v[c++] = elt;
191 : : }
192 : 8025457 : }
193 : :
194 : 10 : void pop_back() {
195 [ - + ]: 10 : if (is_external()) {
196 : 0 : --u.p.e;
197 : : } else {
198 : 10 : --c;
199 : : }
200 : 10 : }
201 : :
202 : 16905313 : void clear() {
203 [ + + ]: 16905313 : if (is_external())
204 : 147966 : do_free();
205 : 16905313 : c = 0;
206 : 16905313 : }
207 : :
208 : 4 : void erase(const_iterator it) {
209 : 4 : T* p = const_cast<T*>(it);
210 : 4 : std::memmove(p, p + 1, (end() - it - 1) * sizeof(T));
211 [ - + ]: 4 : if (is_external()) {
212 : 0 : --u.p.e;
213 : : } else {
214 : 4 : --c;
215 : : }
216 : 4 : }
217 : :
218 : 5 : void erase(const_iterator b, const_iterator e) {
219 : 5 : auto n_erased = e - b;
220 [ - + ]: 5 : if (n_erased == 0) return;
221 : 5 : std::memmove(const_cast<T*>(b), const_cast<T*>(e),
222 : 5 : (end() - e) * sizeof(T));
223 [ + - ]: 5 : if (is_external()) {
224 : 5 : u.p.e -= n_erased;
225 : : } else {
226 : 0 : c -= n_erased;
227 : : }
228 : : }
229 : :
230 : : void insert(const_iterator pos, const T& elt) {
231 : : push_back(T());
232 : : T* p = const_cast<T*>(end());
233 : : while (--p != pos) {
234 : : *p = p[-1];
235 : : }
236 : : *(const_cast<T*>(pos)) = elt;
237 : : }
238 : :
239 : 4433638 : const T& operator[](size_type idx) const {
240 : 4433638 : return begin()[idx];
241 : : }
242 : :
243 : : T& operator[](size_type idx) {
244 : : if (COW && is_external() && u.p.b[-1] > 0) {
245 : : do_cow();
246 : : }
247 : : return const_cast<T&>(begin()[idx]);
248 : : }
249 : :
250 : : const T& front() const {
251 : : return *(begin());
252 : : }
253 : :
254 : 3086543 : const T& back() const {
255 : 3086543 : return end()[-1];
256 : : }
257 : :
258 : : protected:
259 : 321992 : void do_free() {
260 [ + + ]: 321992 : if (!COW || u.p.b[-1] == 0)
261 [ + - ]: 295629 : delete [] (u.p.b - COW);
262 : : else
263 : 26363 : --u.p.b[-1];
264 : 321992 : }
265 : :
266 : 295617 : void do_reserve(size_type n) {
267 : : // Logic error or size_t wrapping.
268 [ - + ]: 295617 : if (rare(COW ? n < c : n <= c))
269 : 0 : throw std::bad_alloc();
270 [ + - ]: 295617 : T* blk = new T[n + COW];
271 : : if (COW)
272 : 295617 : *blk++ = 0;
273 [ + + ]: 295617 : if (is_external()) {
274 : 174026 : u.p.e = std::copy(u.p.b, u.p.e, blk);
275 : 174026 : do_free();
276 : : } else {
277 : 121591 : u.p.e = std::copy(u.v, u.v + c, blk);
278 : : }
279 : 295617 : u.p.b = blk;
280 : 295617 : c = n;
281 : 295617 : }
282 : :
283 : 12 : void do_cow() {
284 [ + - ]: 12 : T* blk = new T[c + 1];
285 : 12 : *blk++ = 0;
286 : 12 : u.p.e = std::copy(u.p.b, u.p.e, blk);
287 : 12 : --u.p.b[-1];
288 : 12 : u.p.b = blk;
289 : 12 : }
290 : :
291 : 1607516 : void do_copy_from(const Vec& o) {
292 [ + + ]: 1607516 : if (!o.is_external()) {
293 : 1581141 : u = o.u;
294 : 1607516 : c = o.c;
295 : : } else if (COW) {
296 : 26375 : u = o.u;
297 : 26375 : c = o.c;
298 : 26375 : ++u.p.b[-1];
299 : : } else {
300 : : T* blk = new T[o.c];
301 : : u.p.e = std::copy(o.u.p.b, o.u.p.e, blk);
302 : : u.p.b = blk;
303 : : c = o.c;
304 : : }
305 : 1607516 : }
306 : :
307 : : /// Return true if storage is external to the object.
308 : 68412763 : bool is_external() const noexcept {
309 : 68412763 : return c > INTERNAL_CAPACITY;
310 : : }
311 : : };
312 : :
313 : : template<typename T>
314 : : using VecCOW = Vec<T, true>;
315 : :
316 : : class SmallVector_ {
317 : : std::size_t c;
318 : :
319 : : static constexpr std::size_t INTERNAL_CAPACITY = 2;
320 : :
321 : : void * p[INTERNAL_CAPACITY];
322 : :
323 : : public:
324 : : SmallVector_() : c(0) { }
325 : :
326 : : // Prevent inadvertent copying.
327 : : SmallVector_(const SmallVector_&) = delete;
328 : :
329 : : // Prevent inadvertent copying.
330 : : void operator=(const SmallVector_&) = delete;
331 : :
332 : : SmallVector_(SmallVector_&& o) noexcept : SmallVector_() {
333 : : std::memcpy(p, o.p, sizeof(p));
334 : : std::swap(c, o.c);
335 : : }
336 : :
337 : 123913 : explicit SmallVector_(std::size_t n) : c(0) {
338 : 123913 : reserve(n);
339 : 123913 : }
340 : :
341 : 10329839 : std::size_t size() const {
342 [ + + ]: 10329839 : if (!is_external())
343 : 10234519 : return c;
344 : 95320 : void * const * b = static_cast<void * const *>(p[0]);
345 : 95320 : void * const * e = static_cast<void * const *>(p[1]);
346 : 95320 : return e - b;
347 : : }
348 : :
349 : 303128 : std::size_t capacity() const {
350 [ + + ]: 303128 : return is_external() ? c : INTERNAL_CAPACITY;
351 : : }
352 : :
353 : 123243 : bool empty() const {
354 [ + + ]: 123243 : return is_external() ? p[0] == p[1] : c == 0;
355 : : }
356 : :
357 : 123954 : void reserve(std::size_t n) {
358 [ + + ][ + - ]: 123954 : if (n > INTERNAL_CAPACITY && n > c) {
359 : 1481 : do_reserve(n);
360 : : }
361 : 123954 : }
362 : :
363 : : protected:
364 : : void do_free();
365 : :
366 : : void do_reserve(std::size_t n);
367 : :
368 : 123967 : void do_clear() {
369 [ + + ]: 123967 : if (is_external())
370 : 1708 : do_free();
371 : 123967 : c = 0;
372 : 123967 : }
373 : :
374 : : /// Return true if storage is external to the object.
375 : 23589461 : bool is_external() const {
376 : 23589461 : return c > INTERNAL_CAPACITY;
377 : : }
378 : :
379 : 10723315 : void * const * do_begin() const {
380 [ + + ]: 10723315 : return is_external() ? static_cast<void * const *>(p[0]) : p;
381 : : }
382 : :
383 : 1984107 : void * const * do_end() const {
384 [ + + ]: 1984107 : return is_external() ? static_cast<void * const *>(p[1]) : p + c;
385 : : }
386 : :
387 : 303128 : void do_push_back(void* elt) {
388 : 303128 : std::size_t cap = capacity();
389 [ + + ]: 303128 : if (size() == cap) {
390 : 381 : do_reserve(cap * 2);
391 : : }
392 [ + + ]: 303128 : if (c >= INTERNAL_CAPACITY) {
393 : 89785 : void ** e = static_cast<void **>(p[1]);
394 : 89785 : *e++ = elt;
395 : 89785 : p[1] = static_cast<void*>(e);
396 : : } else {
397 : 213343 : p[c++] = elt;
398 : : }
399 : 303128 : }
400 : : };
401 : :
402 : : /** Vector of Xapian PIMPL internal objects.
403 : : *
404 : : * A notable feature is that if the vector holds <= 2 objects, there's no
405 : : * extra storage - the two internal pointers are held in the two
406 : : * pointers which otherwise point to the first and just after the last
407 : : * element.
408 : : *
409 : : * This means that for the fairly common cases of pair-wise Query operators
410 : : * and Database objects with one or two subdatabases, we use less space than
411 : : * std::vector<Xapian::Foo::Internal*> would.
412 : : */
413 : : template<typename TI>
414 : : class SmallVectorI : public SmallVector_ {
415 : : public:
416 : : typedef std::size_t size_type;
417 : :
418 : : typedef TI*const* const_iterator;
419 : :
420 : : // Create an empty SmallVectorI.
421 : : SmallVectorI() : SmallVector_() { }
422 : :
423 : : // Create an empty SmallVectorI with n elements reserved.
424 : 247826 : explicit SmallVectorI(size_type n) : SmallVector_(n) { }
425 : :
426 : : SmallVectorI(SmallVectorI&& o) noexcept : SmallVector_(o) { }
427 : :
428 : 123913 : ~SmallVectorI() {
429 : 123913 : clear();
430 : 123913 : }
431 : :
432 : 10723315 : const_iterator begin() const {
433 : 10723315 : return const_iterator(do_begin());
434 : : }
435 : :
436 : 1984107 : const_iterator end() const {
437 : 1984107 : return const_iterator(do_end());
438 : : }
439 : :
440 : 123967 : void clear() {
441 [ + + ]: 427095 : for (const_iterator i = begin(); i != end(); ++i)
442 [ + + ][ + + ]: 303128 : if ((*i) && --(*i)->_refs == 0)
[ + + ]
443 [ + - ]: 230737 : delete *i;
444 : :
445 : 123967 : do_clear();
446 : 123967 : }
447 : :
448 : 303128 : void push_back(TI* elt) {
449 : : // Cast away potential const-ness in TI. We can only try to modify an
450 : : // element after casting to TI*, so this is const-safe overall.
451 : 303128 : do_push_back(const_cast<void*>(static_cast<const void*>(elt)));
452 [ + + ]: 303128 : if (elt)
453 : 303068 : ++elt->_refs;
454 : 303128 : }
455 : :
456 : 9784475 : TI* operator[](size_type idx) const {
457 : 9784475 : return begin()[idx];
458 : : }
459 : :
460 : : TI* front() const {
461 : : return *(begin());
462 : : }
463 : :
464 : : TI* back() const {
465 : : return end()[-1];
466 : : }
467 : : };
468 : :
469 : : /** Vector of Xapian PIMPL objects.
470 : : *
471 : : * A notable feature is that if the vector holds <= 2 objects, there's no
472 : : * extra storage - the two internal pointers are held in the two
473 : : * pointers which otherwise point to the first and just after the last
474 : : * element.
475 : : *
476 : : * This means that for the fairly common cases of pair-wise Query operators
477 : : * and Database objects with one or two subdatabases, we use less space than
478 : : * std::vector<Xapian::Foo> would.
479 : : */
480 : : template<typename T>
481 : 246382 : class SmallVector : public SmallVectorI<typename T::Internal> {
482 : : typedef SmallVectorI<typename T::Internal> super;
483 : :
484 : : public:
485 : : typedef std::size_t size_type;
486 : :
487 : : class const_iterator {
488 : : typename super::const_iterator ptr;
489 : :
490 : : public:
491 : 388338 : const_iterator() : ptr(nullptr) { }
492 : :
493 : 1775009 : explicit const_iterator(typename super::const_iterator ptr_)
494 : 1775009 : : ptr(ptr_) { }
495 : :
496 : 1602016 : const_iterator & operator++() { ++ptr; return *this; }
497 : :
498 : : const_iterator operator++(int) { return const_iterator(ptr++); }
499 : :
500 : 803542 : T operator*() const {
501 : 803542 : return T(*ptr);
502 : : }
503 : :
504 : 55847 : T operator[](size_type idx) const {
505 : 55847 : return T(ptr[idx]);
506 : : }
507 : :
508 : 2381168 : bool operator==(const const_iterator& o) const { return ptr == o.ptr; }
509 : :
510 : 2381168 : bool operator!=(const const_iterator& o) const { return !(*this == o); }
511 : :
512 : 281592 : const_iterator operator+(int n) { return const_iterator(ptr + n); }
513 : :
514 : : const_iterator operator-(int n) { return const_iterator(ptr - n); }
515 : : };
516 : :
517 : : // Create an empty SmallVector.
518 : : SmallVector() { }
519 : :
520 : : // Create an empty SmallVector with n elements reserved.
521 : 246382 : explicit SmallVector(size_type n) : super(n) { }
522 : :
523 : 446037 : const_iterator begin() const {
524 : 446037 : return const_iterator(super::begin());
525 : : }
526 : :
527 : 1188176 : const_iterator end() const {
528 : 1188176 : return const_iterator(super::end());
529 : : }
530 : :
531 : : using super::push_back;
532 : :
533 : 301622 : void push_back(const T & elt) {
534 : 301622 : push_back(elt.internal.get());
535 : 301622 : }
536 : :
537 : 55847 : T operator[](size_type idx) const {
538 [ + - ]: 55847 : return begin()[idx];
539 : : }
540 : :
541 : 614 : T front() const {
542 [ + - ]: 614 : return *(begin());
543 : : }
544 : :
545 : : T back() const {
546 : : return end()[-1];
547 : : }
548 : : };
549 : :
550 : : }
551 : :
552 : : #endif // XAPIAN_INCLUDED_SMALLVECTOR_H
|
