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 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 : : #include <algorithm>
29 : : #include <cstddef> // For std::size_t
30 : : #include <cstring> // For std::memcpy
31 : : #include <type_traits>
32 : :
33 : : namespace Xapian {
34 : :
35 : : /** Suitable for "simple" type T.
36 : : *
37 : : * If sizeof(T) > 2 * sizeof(T*) this isn't going to work, and it's not very
38 : : * useful when sizeof(T) == 2 * sizeof(T*) as you can only store a single
39 : : * element inline.
40 : : *
41 : : * Offers optional Copy-On-Write functionality - if COW is true, then copying
42 : : * a Vec with external data only makes a copy of that data if you attempt
43 : : * to modify it. Current COW is only supported for integral types T.
44 : : */
45 : : template<typename T,
46 : : bool COW = false,
47 : : typename = typename std::enable_if<
48 : : (COW ?
49 : : std::is_integral<T>::value :
50 : : #ifdef HAVE_STD_IS_TRIVIALLY_COPYABLE
51 : : std::is_trivially_copyable<T>::value
52 : : #else
53 : : // std::is_trivially_copyable<T> is C++11, but for example GCC
54 : : // didn't support it until version 6. Assume "true" if it's not
55 : : // available - we'll have to rely on newer compiler versions to
56 : : // catch attempts to use unsuitable types here.
57 : : true
58 : : #endif
59 : : )>::type>
60 : : class Vec {
61 : : std::size_t c;
62 : :
63 : : static constexpr std::size_t INTERNAL_CAPACITY = 2 * sizeof(T*) / sizeof(T);
64 : :
65 : : union {
66 : : T v[INTERNAL_CAPACITY];
67 : : struct {
68 : : T* b;
69 : : T* e;
70 : : };
71 : : } u;
72 : :
73 : : struct Vec_to_copy {
74 : : const Vec& ref;
75 : 1564879 : explicit Vec_to_copy(const Vec& o) : ref(o) {}
76 : : };
77 : :
78 : : public:
79 : : typedef std::size_t size_type;
80 : :
81 : : typedef const T* const_iterator;
82 : :
83 : : typedef T* iterator;
84 : :
85 : 14795777 : Vec() : c(0) { }
86 : :
87 : : // Prevent inadvertent copying.
88 : : Vec(const Vec&) = delete;
89 : :
90 : 1564879 : Vec(const Vec_to_copy& o) {
91 : 1564879 : do_copy_from(o.ref);
92 : 1564879 : }
93 : :
94 : : // Prevent inadvertent copying.
95 : : void operator=(const Vec&) = delete;
96 : :
97 : : void operator=(const Vec_to_copy& o) {
98 : : clear();
99 : : do_copy_from(o.ref);
100 : : }
101 : :
102 : 1564879 : Vec_to_copy copy() const {
103 : 1564879 : return Vec_to_copy(*this);
104 : : }
105 : :
106 : 17210296 : Vec(Vec&& o) noexcept : Vec() {
107 : 8605148 : std::memcpy(&u, &o.u, sizeof(u));
108 : 8605148 : std::swap(c, o.c);
109 : 8605148 : }
110 : :
111 : 837 : void operator=(Vec&& o) {
112 : 837 : clear();
113 : 837 : u = o.u;
114 : 837 : std::swap(c, o.c);
115 : 837 : }
116 : :
117 : 0 : explicit Vec(size_type n) : c(0) {
118 : 0 : reserve(n);
119 : 0 : }
120 : :
121 : 16360656 : ~Vec() {
122 : 16360656 : clear();
123 : 16360656 : }
124 : :
125 : 16091780 : size_type size() const {
126 [ + + ]: 16091780 : return is_external() ? u.e - u.b : c;
127 : : }
128 : :
129 : 8470056 : size_type capacity() const {
130 [ + + ]: 8470056 : return is_external() ? c : INTERNAL_CAPACITY;
131 : : }
132 : :
133 : 10042675 : bool empty() const {
134 [ + + ]: 10042675 : return is_external() ? u.b == u.e : c == 0;
135 : : }
136 : :
137 : 743128 : void reserve(size_type n) {
138 [ + + ]: 743128 : if (n > capacity()) {
139 : 189328 : do_reserve(n);
140 : : }
141 : 743128 : }
142 : :
143 : 5026534 : const_iterator cbegin() const {
144 [ + + ]: 5026534 : return is_external() ? u.b : u.v;
145 : : }
146 : :
147 : 3727306 : const_iterator cend() const {
148 [ + + ]: 3727306 : return is_external() ? u.e : u.v + c;
149 : : }
150 : :
151 : 5026460 : const_iterator begin() const {
152 : 5026460 : return cbegin();
153 : : }
154 : :
155 : 3727275 : const_iterator end() const {
156 : 3727275 : return cend();
157 : : }
158 : :
159 : 1486760 : iterator begin() {
160 : : // FIXME: This is a bit eager - non-const begin() is often invoked when
161 : : // no modification is needed, but doing it lazily is a bit tricky as
162 : : // the pointer will change when we COW.
163 [ + + ][ + + ]: 1486760 : if (COW && is_external() && u.b[-1] > 0) {
[ + + ]
164 : 12 : do_cow();
165 : : }
166 [ + + ]: 1486760 : return is_external() ? u.b : u.v;
167 : : }
168 : :
169 : 743636 : iterator end() {
170 [ + + ][ - + ]: 743636 : if (COW && is_external() && u.b[-1] > 0) {
[ - + ]
171 : 0 : do_cow();
172 : : }
173 [ + + ]: 743636 : return is_external() ? u.e : u.v + c;
174 : : }
175 : :
176 : 7726928 : void push_back(T elt) {
177 : 7726928 : auto cap = capacity();
178 [ + + ]: 7726928 : if (size() == cap) {
179 : 92234 : do_reserve(cap * 2);
180 : : }
181 [ + + ]: 7726928 : if (c >= INTERNAL_CAPACITY) {
182 [ - + ]: 567321 : if (COW && u.b[-1] > 0)
183 : 0 : do_cow();
184 : 567321 : *(u.e++) = elt;
185 : : } else {
186 : 7159607 : u.v[c++] = elt;
187 : : }
188 : 7726928 : }
189 : :
190 : 5 : void pop_back() {
191 [ - + ]: 5 : if (is_external()) {
192 : 0 : --u.e;
193 : : } else {
194 : 5 : --c;
195 : : }
196 : 5 : }
197 : :
198 : 16361580 : void clear() {
199 [ + + ]: 16361580 : if (is_external())
200 : 140598 : do_free();
201 : 16361580 : c = 0;
202 : 16361580 : }
203 : :
204 : 4 : void erase(const_iterator it) {
205 : 4 : T* p = const_cast<T*>(it);
206 : 4 : std::memmove(p, p + 1, (end() - it - 1) * sizeof(T));
207 [ - + ]: 4 : if (is_external()) {
208 : 0 : --u.e;
209 : : } else {
210 : 4 : --c;
211 : : }
212 : 4 : }
213 : :
214 : 3 : void erase(const_iterator b, const_iterator e) {
215 : 3 : auto n_erased = e - b;
216 [ - + ]: 3 : if (n_erased == 0) return;
217 : 3 : std::memmove(const_cast<T*>(b), const_cast<T*>(e),
218 : 3 : (end() - e) * sizeof(T));
219 [ + - ]: 3 : if (is_external()) {
220 : 3 : u.e -= n_erased;
221 : : } else {
222 : 0 : c -= n_erased;
223 : : }
224 : : }
225 : :
226 : : void insert(const_iterator pos, const T& elt) {
227 : : push_back(T());
228 : : T* p = const_cast<T*>(end());
229 : : while (--p != pos) {
230 : : *p = p[-1];
231 : : }
232 : : *(const_cast<T*>(pos)) = elt;
233 : : }
234 : :
235 : 4283334 : const T& operator[](size_type idx) const {
236 : 4283334 : return begin()[idx];
237 : : }
238 : :
239 : : T& operator[](size_type idx) {
240 : : if (COW && is_external() && u.b[-1] > 0) {
241 : : do_cow();
242 : : }
243 : : return const_cast<T&>(begin()[idx]);
244 : : }
245 : :
246 : : const T& front() const {
247 : : return *(begin());
248 : : }
249 : :
250 : 2984149 : const T& back() const {
251 : 2984149 : return end()[-1];
252 : : }
253 : :
254 : : protected:
255 : 306572 : void do_free() {
256 [ + + ]: 306572 : if (!COW || u.b[-1] == 0)
257 [ + - ]: 281574 : delete [] (u.b - COW);
258 : : else
259 : 24998 : --u.b[-1];
260 : 306572 : }
261 : :
262 : 281562 : void do_reserve(size_type n) {
263 : : // Logic error or size_t wrapping.
264 [ - + ]: 281562 : if (rare(COW ? n < c : n <= c))
265 : 0 : throw std::bad_alloc();
266 [ + - ]: 281562 : T* blk = new T[n + COW];
267 : : if (COW)
268 : 281562 : *blk++ = 0;
269 [ + + ]: 281562 : if (is_external()) {
270 : 165974 : u.e = std::copy(u.b, u.e, blk);
271 : 165974 : do_free();
272 : : } else {
273 : 115588 : u.e = std::copy(u.v, u.v + c, blk);
274 : : }
275 : 281562 : u.b = blk;
276 : 281562 : c = n;
277 : 281562 : }
278 : :
279 : 12 : void do_cow() {
280 [ + - ]: 12 : T* blk = new T[c + 1];
281 : 12 : *blk++ = 0;
282 : 12 : u.e = std::copy(u.b, u.e, blk);
283 : 12 : --u.b[-1];
284 : 12 : u.b = blk;
285 : 12 : }
286 : :
287 : 1564879 : void do_copy_from(const Vec& o) {
288 [ + + ]: 1564879 : if (!o.is_external()) {
289 : 1539869 : u = o.u;
290 : 1564879 : c = o.c;
291 : : } else if (COW) {
292 : 25010 : u = o.u;
293 : 25010 : c = o.c;
294 : 25010 : ++u.b[-1];
295 : : } else {
296 : : T* blk = new T[o.c];
297 : : u.e = std::copy(o.u.b, o.u.e, blk);
298 : : u.b = blk;
299 : : c = o.c;
300 : : }
301 : 1564879 : }
302 : :
303 : : /// Return true if storage is external to the object.
304 : 66027176 : bool is_external() const noexcept {
305 : 66027176 : return c > INTERNAL_CAPACITY;
306 : : }
307 : : };
308 : :
309 : : template<typename T>
310 : : using VecCOW = Vec<T, true>;
311 : :
312 : : class SmallVector_ {
313 : : std::size_t c;
314 : :
315 : : static constexpr std::size_t INTERNAL_CAPACITY = 2;
316 : :
317 : : void * p[INTERNAL_CAPACITY];
318 : :
319 : : public:
320 : : SmallVector_() : c(0) { }
321 : :
322 : : // Prevent inadvertent copying.
323 : : SmallVector_(const SmallVector_&) = delete;
324 : :
325 : : // Prevent inadvertent copying.
326 : : void operator=(const SmallVector_&) = delete;
327 : :
328 : : SmallVector_(SmallVector_&& o) noexcept : SmallVector_() {
329 : : std::memcpy(p, o.p, sizeof(p));
330 : : std::swap(c, o.c);
331 : : }
332 : :
333 : 623334 : explicit SmallVector_(std::size_t n) : c(0) {
334 : 623334 : reserve(n);
335 : 623334 : }
336 : :
337 : 11967671 : std::size_t size() const {
338 [ + + ]: 11967671 : if (!is_external())
339 : 11872333 : return c;
340 : 95338 : void * const * b = static_cast<void * const *>(p[0]);
341 : 95338 : void * const * e = static_cast<void * const *>(p[1]);
342 : 95338 : return e - b;
343 : : }
344 : :
345 : 1301980 : std::size_t capacity() const {
346 [ + + ]: 1301980 : return is_external() ? c : INTERNAL_CAPACITY;
347 : : }
348 : :
349 : 622706 : bool empty() const {
350 [ + + ]: 622706 : return is_external() ? p[0] == p[1] : c == 0;
351 : : }
352 : :
353 : 623372 : void reserve(std::size_t n) {
354 [ + + ][ + - ]: 623372 : if (n > INTERNAL_CAPACITY && n > c) {
355 : 1398 : do_reserve(n);
356 : : }
357 : 623372 : }
358 : :
359 : : protected:
360 : : void do_free();
361 : :
362 : : void do_reserve(std::size_t n);
363 : :
364 : 623388 : void do_clear() {
365 [ + + ]: 623388 : if (is_external())
366 : 1625 : do_free();
367 : 623388 : c = 0;
368 : 623388 : }
369 : :
370 : : /// Return true if storage is external to the object.
371 : 29272050 : bool is_external() const {
372 : 29272050 : return c > INTERNAL_CAPACITY;
373 : : }
374 : :
375 : 11248595 : void * const * do_begin() const {
376 [ + + ]: 11248595 : return is_external() ? static_cast<void * const *>(p[0]) : p;
377 : : }
378 : :
379 : 3505932 : void * const * do_end() const {
380 [ + + ]: 3505932 : return is_external() ? static_cast<void * const *>(p[1]) : p + c;
381 : : }
382 : :
383 : 1301980 : void do_push_back(void* elt) {
384 : 1301980 : std::size_t cap = capacity();
385 [ + + ]: 1301980 : if (size() == cap) {
386 : 380 : do_reserve(cap * 2);
387 : : }
388 [ + + ]: 1301980 : if (c >= INTERNAL_CAPACITY) {
389 : 89508 : void ** e = static_cast<void **>(p[1]);
390 : 89508 : *e++ = elt;
391 : 89508 : p[1] = static_cast<void*>(e);
392 : : } else {
393 : 1212472 : p[c++] = elt;
394 : : }
395 : 1301980 : }
396 : : };
397 : :
398 : : /** Vector of Xapian PIMPL internal objects.
399 : : *
400 : : * A notable feature is that if the vector holds <= 2 objects, there's no
401 : : * extra storage - the two internal pointers are held in the two
402 : : * pointers which otherwise point to the first and just after the last
403 : : * element.
404 : : *
405 : : * This means that for the fairly common cases of pair-wise Query operators
406 : : * and Database objects with one or two subdatabases, we use less space than
407 : : * std::vector<Xapian::Foo::Internal*> would.
408 : : */
409 : : template<typename TI>
410 : : class SmallVectorI : public SmallVector_ {
411 : : public:
412 : : typedef std::size_t size_type;
413 : :
414 : : typedef TI*const* const_iterator;
415 : :
416 : : // Create an empty SmallVectorI.
417 : : SmallVectorI() : SmallVector_() { }
418 : :
419 : : // Create an empty SmallVectorI with n elements reserved.
420 : 1246668 : explicit SmallVectorI(size_type n) : SmallVector_(n) { }
421 : :
422 : : SmallVectorI(SmallVectorI&& o) noexcept : SmallVector_(o) { }
423 : :
424 : 623334 : ~SmallVectorI() {
425 : 623334 : clear();
426 : 623334 : }
427 : :
428 : 11248595 : const_iterator begin() const {
429 : 11248595 : return const_iterator(do_begin());
430 : : }
431 : :
432 : 3505932 : const_iterator end() const {
433 : 3505932 : return const_iterator(do_end());
434 : : }
435 : :
436 : 623388 : void clear() {
437 [ + + ]: 1925368 : for (const_iterator i = begin(); i != end(); ++i)
438 [ + + ][ + + ]: 1301980 : if ((*i) && --(*i)->_refs == 0)
[ + + ]
439 [ + - ]: 1229819 : delete *i;
440 : :
441 : 623388 : do_clear();
442 : 623388 : }
443 : :
444 : 1301980 : void push_back(TI* elt) {
445 : : // Cast away potential const-ness in TI. We can only try to modify an
446 : : // element after casting to TI*, so this is const-safe overall.
447 : 1301980 : do_push_back(const_cast<void*>(static_cast<const void*>(elt)));
448 [ + + ]: 1301980 : if (elt)
449 : 1301920 : ++elt->_refs;
450 : 1301980 : }
451 : :
452 : 9784044 : TI* operator[](size_type idx) const {
453 : 9784044 : return begin()[idx];
454 : : }
455 : :
456 : : TI* front() const {
457 : : return *(begin());
458 : : }
459 : :
460 : : TI* back() const {
461 : : return end()[-1];
462 : : }
463 : : };
464 : :
465 : : /** Vector of Xapian PIMPL objects.
466 : : *
467 : : * A notable feature is that if the vector holds <= 2 objects, there's no
468 : : * extra storage - the two internal pointers are held in the two
469 : : * pointers which otherwise point to the first and just after the last
470 : : * element.
471 : : *
472 : : * This means that for the fairly common cases of pair-wise Query operators
473 : : * and Database objects with one or two subdatabases, we use less space than
474 : : * std::vector<Xapian::Foo> would.
475 : : */
476 : : template<typename T>
477 : 1245324 : class SmallVector : public SmallVectorI<typename T::Internal> {
478 : : typedef SmallVectorI<typename T::Internal> super;
479 : :
480 : : public:
481 : : typedef std::size_t size_type;
482 : :
483 : : class const_iterator {
484 : : typename super::const_iterator ptr;
485 : :
486 : : public:
487 : 386880 : const_iterator() : ptr(nullptr) { }
488 : :
489 : 1767864 : explicit const_iterator(typename super::const_iterator ptr_)
490 : 1767864 : : ptr(ptr_) { }
491 : :
492 : 1595202 : const_iterator & operator++() { ++ptr; return *this; }
493 : :
494 : : const_iterator operator++(int) { return const_iterator(ptr++); }
495 : :
496 : 800041 : T operator*() const {
497 : 800041 : return T(*ptr);
498 : : }
499 : :
500 : 55238 : T operator[](size_type idx) const {
501 : 55238 : return T(ptr[idx]);
502 : : }
503 : :
504 : 2371402 : bool operator==(const const_iterator& o) const { return ptr == o.ptr; }
505 : :
506 : 2371402 : bool operator!=(const const_iterator& o) const { return !(*this == o); }
507 : :
508 : 281166 : const_iterator operator+(int n) { return const_iterator(ptr + n); }
509 : :
510 : : const_iterator operator-(int n) { return const_iterator(ptr - n); }
511 : : };
512 : :
513 : : // Create an empty SmallVector.
514 : : SmallVector() { }
515 : :
516 : : // Create an empty SmallVector with n elements reserved.
517 : 1245324 : explicit SmallVector(size_type n) : super(n) { }
518 : :
519 : 443940 : const_iterator begin() const {
520 : 443940 : return const_iterator(super::begin());
521 : : }
522 : :
523 : 1183341 : const_iterator end() const {
524 : 1183341 : return const_iterator(super::end());
525 : : }
526 : :
527 : : using super::push_back;
528 : :
529 : 1300578 : void push_back(const T & elt) {
530 : 1300578 : push_back(elt.internal.get());
531 : 1300578 : }
532 : :
533 : 55238 : T operator[](size_type idx) const {
534 [ + - ]: 55238 : return begin()[idx];
535 : : }
536 : :
537 : 602 : T front() const {
538 [ + - ]: 602 : return *(begin());
539 : : }
540 : :
541 : : T back() const {
542 : : return end()[-1];
543 : : }
544 : : };
545 : :
546 : : }
547 : :
548 : : #endif // XAPIAN_INCLUDED_SMALLVECTOR_H
|
