xapian-core/api/smallvector.h

   1 /** @file smallvector.h
   2  * @brief Append only vector of Xapian PIMPL objects
   3  */
   4 /* Copyright (C) 2012,2013,2014 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 <cstddef> // For std::size_t
  29
  30 namespace Xapian {
  31
  32 class SmallVector_ {
  33   public:
  34     SmallVector_() : c(0) { }
  35
  36   protected:
  37     std::size_t c;
  38     void * p[2];
  39
  40     void do_reserve(std::size_t n);
  41 };
  42
  43 /** Vector of Xapian PIMPL objects.
  44  *
  45  *  A notable feature is that if the vector holds <= 2 objects, there's no
  46  *  extra storage - the two internal pointers are held in the two
  47  *  pointers which otherwise point to the first and just after the last
  48  *  element.
  49  *
  50  *  This means that for the fairly common cases of pair-wise Query operators
  51  *  and Database objects with one or two subdatabases, we use less space than
  52  *  std::vector<Xapian::Foo> would.
  53  */
  54 template<typename T>
  55 class SmallVector : private SmallVector_ {
  56   public:
  57     typedef std::size_t size_type;
  58     class const_iterator {
  59         void * const * ptr;
  60
  61       public:
  62         const_iterator() { }
  63
  64         explicit const_iterator(void * const * ptr_) : ptr(ptr_) { }
  65
  66         const_iterator & operator++() { ++ptr; return *this; }
  67
  68         const_iterator operator++(int) { return const_iterator(ptr++); }
  69
  70         T operator*() const {
  71             return T(static_cast<typename T::Internal*>(*ptr));
  72         }
  73
  74         T operator[](size_type idx) const {
  75             return T(static_cast<typename T::Internal*>(ptr[idx]));
  76         }
  77
  78         bool operator==(const const_iterator& o) const { return ptr == o.ptr; }
  79
  80         bool operator!=(const const_iterator& o) const { return !(*this == o); }
  81
  82         const_iterator operator+(int n) { return const_iterator(ptr + n); }
  83     };
  84
  85     // Create an empty SmallVector.
  86     SmallVector() : SmallVector_() { }
  87
  88     // Create an empty SmallVector with n elements reserved.
  89     explicit SmallVector(size_type n) : SmallVector_() {
  90         reserve(n);
  91     }
  92
  93     ~SmallVector() {
  94         clear();
  95     }
  96
  97     const_iterator begin() const {
  98         return const_iterator(c > sizeof(p) / sizeof(*p) ?
  99                               static_cast<void * const *>(p[0]) :
 100                               p);
 101     }
 102
 103     const_iterator end() const {
 104         return const_iterator(c > sizeof(p) / sizeof(*p) ?
 105                               static_cast<void * const *>(p[1]) :
 106                               p + c);
 107     }
 108
 109     size_type size() const {
 110         return c > sizeof(p) / sizeof(*p) ?
 111                static_cast<void**>(p[1]) - static_cast<void**>(p[0]) : c;
 112     }
 113
 114     size_type capacity() const {
 115         return c > sizeof(p) / sizeof(*p) ? c : sizeof(p) / sizeof(*p);
 116     }
 117
 118     bool empty() const {
 119         return c > sizeof(p) / sizeof(*p) ? p[0] == p[1] : c == 0;
 120     }
 121
 122     void clear() {
 123         for (const_iterator i = begin(); i != end(); ++i)
 124             if ((*i).internal.get() && --(*i).internal->_refs == 0)
 125                 delete (*i).internal.get();
 126
 127         if (c > sizeof(p) / sizeof(*p))
 128             delete [] static_cast<typename T::Internal**>(p[0]);
 129
 130         c = 0;
 131     }
 132
 133     void reserve(size_type n) {
 134         if (n > sizeof(p) / sizeof(*p) && n > c) {
 135             do_reserve(n);
 136             c = n;
 137         }
 138     }
 139
 140     void push_back(const T & elt) {
 141         size_type cap = capacity();
 142         if (size() == cap) {
 143             cap *= 2;
 144             do_reserve(cap);
 145             c = cap;
 146         }
 147         if (elt.internal.get())
 148             ++elt.internal->_refs;
 149         if (c >= sizeof(p) / sizeof(*p)) {
 150             void ** e = static_cast<void **>(p[1]);
 151             *e++ = static_cast<void*>(elt.internal.get());
 152             p[1] = static_cast<void*>(e);
 153         } else {
 154             p[c++] = elt.internal.get();
 155         }
 156     }
 157
 158     T operator[](size_type idx) const {
 159         return begin()[idx];
 160     }
 161 };
 162
 163 }
 164
 165 #endif // XAPIAN_INCLUDED_SMALLVECTOR_H