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_ */