benchmark silo added
[c11concurrency-benchmarks.git] / silo / small_vector.h
1 #ifndef _SMALL_VECTOR_H_
2 #define _SMALL_VECTOR_H_
3
4 #include <algorithm>
5 #include <vector>
6 #include <type_traits>
7
8 #include "macros.h"
9 #include "ndb_type_traits.h"
10
11 /**
12  * References are not guaranteed to be stable across mutation
13  *
14  * XXX(stephentu): allow custom allocator
15  */
16 template <typename T, size_t SmallSize = SMALL_SIZE_VEC>
17 class small_vector {
18   typedef std::vector<T> large_vector_type;
19
20   static const bool is_trivially_destructible =
21     private_::is_trivially_destructible<T>::value;
22
23   // std::is_trivially_copyable not supported in g++-4.7
24   static const bool is_trivially_copyable = std::is_scalar<T>::value;
25
26 public:
27
28   typedef T value_type;
29   typedef T & reference;
30   typedef const T & const_reference;
31   typedef size_t size_type;
32
33   small_vector() : n(0), large_elems(0) {}
34   ~small_vector()
35   {
36     clearDestructive();
37   }
38
39   small_vector(const small_vector &that)
40     : n(0), large_elems(0)
41   {
42     assignFrom(that);
43   }
44
45   // not efficient, don't use in performance critical parts
46   small_vector(std::initializer_list<T> l)
47     : n(0), large_elems(nullptr)
48   {
49     if (l.size() > SmallSize) {
50       large_elems = new large_vector_type(l);
51     } else {
52       for (auto &p : l)
53         push_back(p);
54     }
55   }
56
57   small_vector &
58   operator=(const small_vector &that)
59   {
60     assignFrom(that);
61     return *this;
62   }
63
64   inline size_t
65   size() const
66   {
67     if (unlikely(large_elems))
68       return large_elems->size();
69     return n;
70   }
71
72   inline bool
73   empty() const
74   {
75     return size() == 0;
76   }
77
78   inline reference
79   front()
80   {
81     if (unlikely(large_elems))
82       return large_elems->front();
83     INVARIANT(n > 0);
84     INVARIANT(n <= SmallSize);
85     return *ptr();
86   }
87
88   inline const_reference
89   front() const
90   {
91     return const_cast<small_vector *>(this)->front();
92   }
93
94   inline reference
95   back()
96   {
97     if (unlikely(large_elems))
98       return large_elems->back();
99     INVARIANT(n > 0);
100     INVARIANT(n <= SmallSize);
101     return ptr()[n - 1];
102   }
103
104   inline const_reference
105   back() const
106   {
107     return const_cast<small_vector *>(this)->back();
108   }
109
110   inline void
111   pop_back()
112   {
113     if (unlikely(large_elems)) {
114       large_elems->pop_back();
115       return;
116     }
117     INVARIANT(n > 0);
118     if (!is_trivially_destructible)
119       ptr()[n - 1].~T();
120     n--;
121   }
122
123   inline void
124   push_back(const T &obj)
125   {
126     emplace_back(obj);
127   }
128
129   inline void
130   push_back(T &&obj)
131   {
132     emplace_back(std::move(obj));
133   }
134
135   // C++11 goodness- a strange syntax this is
136
137   template <class... Args>
138   inline void
139   emplace_back(Args &&... args)
140   {
141     if (unlikely(large_elems)) {
142       INVARIANT(!n);
143       large_elems->emplace_back(std::forward<Args>(args)...);
144       return;
145     }
146     if (unlikely(n == SmallSize)) {
147       large_elems = new large_vector_type(ptr(), ptr() + n);
148       large_elems->emplace_back(std::forward<Args>(args)...);
149       n = 0;
150       return;
151     }
152     INVARIANT(n < SmallSize);
153     new (&(ptr()[n++])) T(std::forward<Args>(args)...);
154   }
155
156   inline reference
157   operator[](int i)
158   {
159     if (unlikely(large_elems))
160       return large_elems->operator[](i);
161     return ptr()[i];
162   }
163
164   inline const_reference
165   operator[](int i) const
166   {
167     return const_cast<small_vector *>(this)->operator[](i);
168   }
169
170   void
171   clear()
172   {
173     if (unlikely(large_elems)) {
174       INVARIANT(!n);
175       large_elems->clear();
176       return;
177     }
178     if (!is_trivially_destructible)
179       for (size_t i = 0; i < n; i++)
180         ptr()[i].~T();
181     n = 0;
182   }
183
184   inline void
185   reserve(size_t n)
186   {
187     if (unlikely(large_elems))
188       large_elems->reserve(n);
189   }
190
191   // non-standard API
192   inline bool is_small_type() const { return !large_elems; }
193
194   template <typename Compare = std::less<T>>
195   inline void
196   sort(Compare c = Compare())
197   {
198     if (unlikely(large_elems))
199       std::sort(large_elems->begin(), large_elems->end(), c);
200     else
201       std::sort(small_begin(), small_end(), c);
202   }
203
204 private:
205
206   void
207   clearDestructive()
208   {
209     if (unlikely(large_elems)) {
210       INVARIANT(!n);
211       delete large_elems;
212       large_elems = NULL;
213       return;
214     }
215     if (!is_trivially_destructible)
216       for (size_t i = 0; i < n; i++)
217         ptr()[i].~T();
218     n = 0;
219   }
220
221   template <typename ObjType>
222   class small_iterator_ : public std::iterator<std::bidirectional_iterator_tag, ObjType> {
223     friend class small_vector;
224   public:
225     inline small_iterator_() : p(0) {}
226
227     template <typename O>
228     inline small_iterator_(const small_iterator_<O> &other)
229       : p(other.p)
230     {}
231
232     inline ObjType &
233     operator*() const
234     {
235       return *p;
236     }
237
238     inline ObjType *
239     operator->() const
240     {
241       return p;
242     }
243
244     inline bool
245     operator==(const small_iterator_ &o) const
246     {
247       return p == o.p;
248     }
249
250     inline bool
251     operator!=(const small_iterator_ &o) const
252     {
253       return !operator==(o);
254     }
255
256     inline bool
257     operator<(const small_iterator_ &o) const
258     {
259       return p < o.p;
260     }
261
262     inline bool
263     operator>=(const small_iterator_ &o) const
264     {
265       return !operator<(o);
266     }
267
268     inline bool
269     operator>(const small_iterator_ &o) const
270     {
271       return p > o.p;
272     }
273
274     inline bool
275     operator<=(const small_iterator_ &o) const
276     {
277       return !operator>(o);
278     }
279
280     inline small_iterator_ &
281     operator+=(int n)
282     {
283       p += n;
284       return *this;
285     }
286
287     inline small_iterator_ &
288     operator-=(int n)
289     {
290       p -= n;
291       return *this;
292     }
293
294     inline small_iterator_
295     operator+(int n) const
296     {
297       small_iterator_ cpy = *this;
298       return cpy += n;
299     }
300
301     inline small_iterator_
302     operator-(int n) const
303     {
304       small_iterator_ cpy = *this;
305       return cpy -= n;
306     }
307
308     inline intptr_t
309     operator-(const small_iterator_ &o) const
310     {
311       return p - o.p;
312     }
313
314     inline small_iterator_ &
315     operator++()
316     {
317       ++p;
318       return *this;
319     }
320
321     inline small_iterator_
322     operator++(int)
323     {
324       small_iterator_ cur = *this;
325       ++(*this);
326       return cur;
327     }
328
329     inline small_iterator_ &
330     operator--()
331     {
332       --p;
333       return *this;
334     }
335
336     inline small_iterator_
337     operator--(int)
338     {
339       small_iterator_ cur = *this;
340       --(*this);
341       return cur;
342     }
343
344   protected:
345     inline small_iterator_(ObjType *p) : p(p) {}
346
347   private:
348     ObjType *p;
349   };
350
351   template <typename ObjType, typename SmallTypeIter, typename LargeTypeIter>
352   class iterator_ : public std::iterator<std::bidirectional_iterator_tag, ObjType> {
353     friend class small_vector;
354   public:
355     inline iterator_() : large(false) {}
356
357     template <typename O, typename S, typename L>
358     inline iterator_(const iterator_<O, S, L> &other)
359       : large(other.large),
360         small_it(other.small_it),
361         large_it(other.large_it)
362     {}
363
364     inline ObjType &
365     operator*() const
366     {
367       if (unlikely(large))
368         return *large_it;
369       return *small_it;
370     }
371
372     inline ObjType *
373     operator->() const
374     {
375       if (unlikely(large))
376         return &(*large_it);
377       return &(*small_it);
378     }
379
380     inline bool
381     operator==(const iterator_ &o) const
382     {
383       if (unlikely(large))
384         return large_it == o.large_it;
385       return small_it == o.small_it;
386     }
387
388     inline bool
389     operator!=(const iterator_ &o) const
390     {
391       return !operator==(o);
392     }
393
394     inline bool
395     operator<(const iterator_ &o) const
396     {
397       if (unlikely(large))
398         return large_it < o.large_it;
399       return small_it < o.small_it;
400     }
401
402     inline bool
403     operator>=(const iterator_ &o) const
404     {
405       return !operator<(o);
406     }
407
408     inline bool
409     operator>(const iterator_ &o) const
410     {
411       if (unlikely(large))
412         return large_it > o.large_it;
413       return small_it > o.small_it;
414     }
415
416     inline bool
417     operator<=(const iterator_ &o) const
418     {
419       return !operator>(o);
420     }
421
422     inline iterator_ &
423     operator+=(int n)
424     {
425       if (unlikely(large))
426         large_it += n;
427       else
428         small_it += n;
429       return *this;
430     }
431
432     inline iterator_ &
433     operator-=(int n)
434     {
435       if (unlikely(large))
436         large_it -= n;
437       else
438         small_it -= n;
439       return *this;
440     }
441
442     inline iterator_
443     operator+(int n) const
444     {
445       iterator_ cpy = *this;
446       return cpy += n;
447     }
448
449     inline iterator_
450     operator-(int n) const
451     {
452       iterator_ cpy = *this;
453       return cpy -= n;
454     }
455
456     inline intptr_t
457     operator-(const iterator_ &o) const
458     {
459       if (unlikely(large))
460         return large_it - o.large_it;
461       else
462         return small_it - o.small_it;
463     }
464
465     inline iterator_ &
466     operator++()
467     {
468       if (unlikely(large))
469         ++large_it;
470       else
471         ++small_it;
472       return *this;
473     }
474
475     inline iterator_
476     operator++(int)
477     {
478       iterator_ cur = *this;
479       ++(*this);
480       return cur;
481     }
482
483     inline iterator_ &
484     operator--()
485     {
486       if (unlikely(large))
487         --large_it;
488       else
489         --small_it;
490       return *this;
491     }
492
493     inline iterator_
494     operator--(int)
495     {
496       iterator_ cur = *this;
497       --(*this);
498       return cur;
499     }
500
501   protected:
502     iterator_(SmallTypeIter small_it)
503       : large(false), small_it(small_it), large_it() {}
504     iterator_(LargeTypeIter large_it)
505       : large(true), small_it(), large_it(large_it) {}
506
507   private:
508     bool large;
509     SmallTypeIter small_it;
510     LargeTypeIter large_it;
511   };
512
513   typedef small_iterator_<T> small_iterator;
514   typedef small_iterator_<const T> const_small_iterator;
515   typedef typename large_vector_type::iterator large_iterator;
516   typedef typename large_vector_type::const_iterator const_large_iterator;
517
518   inline small_iterator
519   small_begin()
520   {
521     INVARIANT(!large_elems);
522     return small_iterator(ptr());
523   }
524
525   inline const_small_iterator
526   small_begin() const
527   {
528     INVARIANT(!large_elems);
529     return const_small_iterator(ptr());
530   }
531
532   inline small_iterator
533   small_end()
534   {
535     INVARIANT(!large_elems);
536     return small_iterator(ptr() + n);
537   }
538
539   inline const_small_iterator
540   small_end() const
541   {
542     INVARIANT(!large_elems);
543     return const_small_iterator(ptr() + n);
544   }
545
546 public:
547
548   typedef iterator_<T, small_iterator, large_iterator> iterator;
549   typedef iterator_<const T, const_small_iterator, const_large_iterator> const_iterator;
550
551   typedef std::reverse_iterator<iterator> reverse_iterator;
552   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
553
554   inline iterator
555   begin()
556   {
557     if (unlikely(large_elems))
558       return iterator(large_elems->begin());
559     return iterator(small_begin());
560   }
561
562   inline const_iterator
563   begin() const
564   {
565     if (unlikely(large_elems))
566       return const_iterator(large_elems->begin());
567     return const_iterator(small_begin());
568   }
569
570   inline iterator
571   end()
572   {
573     if (unlikely(large_elems))
574       return iterator(large_elems->end());
575     return iterator(small_end());
576   }
577
578   inline const_iterator
579   end() const
580   {
581     if (unlikely(large_elems))
582       return const_iterator(large_elems->end());
583     return const_iterator(small_end());
584   }
585
586   inline reverse_iterator
587   rbegin()
588   {
589     return reverse_iterator(end());
590   }
591
592   inline const_reverse_iterator
593   rbegin() const
594   {
595     return const_reverse_iterator(end());
596   }
597
598   inline reverse_iterator
599   rend()
600   {
601     return reverse_iterator(begin());
602   }
603
604   inline const_reverse_iterator
605   rend() const
606   {
607     return const_reverse_iterator(begin());
608   }
609
610 private:
611   void
612   assignFrom(const small_vector &that)
613   {
614     if (unlikely(this == &that))
615       return;
616     clearDestructive();
617     if (unlikely(that.large_elems)) {
618       large_elems = new large_vector_type(*that.large_elems);
619     } else {
620       INVARIANT(that.n <= SmallSize);
621       if (is_trivially_copyable) {
622         NDB_MEMCPY(ptr(), that.ptr(), that.n * sizeof(T));
623       } else {
624         for (size_t i = 0; i < that.n; i++)
625           new (&(ptr()[i])) T(that.ptr()[i]);
626       }
627       n = that.n;
628     }
629   }
630
631   inline ALWAYS_INLINE T *
632   ptr()
633   {
634     return reinterpret_cast<T *>(&small_elems_buf[0]);
635   }
636
637   inline ALWAYS_INLINE const T *
638   ptr() const
639   {
640     return reinterpret_cast<const T *>(&small_elems_buf[0]);
641   }
642
643   size_t n;
644   char small_elems_buf[sizeof(T) * SmallSize];
645   large_vector_type *large_elems;
646 };
647
648 #endif /* _SMALL_VECTOR_H_ */