src/hb-vector.hh

   1 /*
   2  * Copyright © 2017,2018  Google, Inc.
   3  *
   4  *  This is part of HarfBuzz, a text shaping library.
   5  *
   6  * Permission is hereby granted, without written agreement and without
   7  * license or royalty fees, to use, copy, modify, and distribute this
   8  * software and its documentation for any purpose, provided that the
   9  * above copyright notice and the following two paragraphs appear in
  10  * all copies of this software.
  11  *
  12  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  13  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  14  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  15  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  16  * DAMAGE.
  17  *
  18  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  19  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  20  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  21  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  22  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  23  *
  24  * Google Author(s): Behdad Esfahbod
  25  */
  26
  27 #ifndef HB_VECTOR_HH
  28 #define HB_VECTOR_HH
  29
  30 #include "hb.hh"
  31 #include "hb-array.hh"
  32 #include "hb-null.hh"
  33
  34
  35 template <typename Type>
  36 struct hb_vector_t
  37 {
  38   typedef Type item_t;
  39   static constexpr unsigned item_size = hb_static_size (Type);
  40
  41   HB_NO_COPY_ASSIGN_TEMPLATE (hb_vector_t, Type);
  42   hb_vector_t ()  { init (); }
  43   ~hb_vector_t () { fini (); }
  44
  45   unsigned int length;
  46   private:
  47   int allocated; /* == -1 means allocation failed. */
  48   Type *arrayZ_;
  49   public:
  50
  51   void init ()
  52   {
  53     allocated = length = 0;
  54     arrayZ_ = nullptr;
  55   }
  56
  57   void fini ()
  58   {
  59     if (arrayZ_)
  60       free (arrayZ_);
  61     init ();
  62   }
  63   void fini_deep ()
  64   {
  65     Type *array = arrayZ();
  66     unsigned int count = length;
  67     for (unsigned int i = 0; i < count; i++)
  68       array[i].fini ();
  69     fini ();
  70   }
  71
  72   const Type * arrayZ () const { return arrayZ_; }
  73         Type * arrayZ ()       { return arrayZ_; }
  74
  75   Type& operator [] (int i_)
  76   {
  77     unsigned int i = (unsigned int) i_;
  78     if (unlikely (i >= length))
  79       return Crap (Type);
  80     return arrayZ()[i];
  81   }
  82   const Type& operator [] (int i_) const
  83   {
  84     unsigned int i = (unsigned int) i_;
  85     if (unlikely (i >= length))
  86       return Null(Type);
  87     return arrayZ()[i];
  88   }
  89
  90   explicit_operator bool () const { return length; }
  91
  92   hb_array_t<Type> as_array ()
  93   { return hb_array (arrayZ(), length); }
  94   hb_array_t<const Type> as_array () const
  95   { return hb_array (arrayZ(), length); }
  96
  97   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
  98   { return as_array ().sub_array (start_offset, count);}
  99   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
 100   { return as_array ().sub_array (start_offset, count);}
 101   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
 102   { return as_array ().sub_array (start_offset, count);}
 103   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
 104   { return as_array ().sub_array (start_offset, count);}
 105
 106   hb_sorted_array_t<Type> as_sorted_array ()
 107   { return hb_sorted_array (arrayZ(), length); }
 108   hb_sorted_array_t<const Type> as_sorted_array () const
 109   { return hb_sorted_array (arrayZ(), length); }
 110
 111   hb_array_t<const Type> sorted_sub_array (unsigned int start_offset, unsigned int count) const
 112   { return as_sorted_array ().sorted_sub_array (start_offset, count);}
 113   hb_array_t<const Type> sorted_sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
 114   { return as_sorted_array ().sorted_sub_array (start_offset, count);}
 115   hb_array_t<Type> sorted_sub_array (unsigned int start_offset, unsigned int count)
 116   { return as_sorted_array ().sorted_sub_array (start_offset, count);}
 117   hb_array_t<Type> sorted_sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
 118   { return as_sorted_array ().sorted_sub_array (start_offset, count);}
 119
 120   template <typename T> explicit_operator T * () { return arrayZ(); }
 121   template <typename T> explicit_operator const T * () const { return arrayZ(); }
 122   operator hb_array_t<Type> ()             { return as_array (); }
 123   operator hb_array_t<const Type> () const { return as_array (); }
 124
 125   Type * operator  + (unsigned int i) { return arrayZ() + i; }
 126   const Type * operator  + (unsigned int i) const { return arrayZ() + i; }
 127
 128   Type *push ()
 129   {
 130     if (unlikely (!resize (length + 1)))
 131       return &Crap(Type);
 132     return &arrayZ()[length - 1];
 133   }
 134   Type *push (const Type& v)
 135   {
 136     Type *p = push ();
 137     *p = v;
 138     return p;
 139   }
 140
 141   bool in_error () const { return allocated < 0; }
 142
 143   /* Allocate for size but don't adjust length. */
 144   bool alloc (unsigned int size)
 145   {
 146     if (unlikely (allocated < 0))
 147       return false;
 148
 149     if (likely (size <= (unsigned) allocated))
 150       return true;
 151
 152     /* Reallocate */
 153
 154     unsigned int new_allocated = allocated;
 155     while (size >= new_allocated)
 156       new_allocated += (new_allocated >> 1) + 8;
 157
 158     Type *new_array = nullptr;
 159     bool overflows =
 160       (int) new_allocated < 0 ||
 161       (new_allocated < (unsigned) allocated) ||
 162       hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
 163     if (likely (!overflows))
 164       new_array = (Type *) realloc (arrayZ_, new_allocated * sizeof (Type));
 165
 166     if (unlikely (!new_array))
 167     {
 168       allocated = -1;
 169       return false;
 170     }
 171
 172     arrayZ_ = new_array;
 173     allocated = new_allocated;
 174
 175     return true;
 176   }
 177
 178   bool resize (int size_)
 179   {
 180     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
 181     if (!alloc (size))
 182       return false;
 183
 184     if (size > length)
 185       memset (arrayZ() + length, 0, (size - length) * sizeof (*arrayZ()));
 186
 187     length = size;
 188     return true;
 189   }
 190
 191   void pop ()
 192   {
 193     if (!length) return;
 194     length--;
 195   }
 196
 197   void remove (unsigned int i)
 198   {
 199     if (unlikely (i >= length))
 200       return;
 201     Type *array = arrayZ();
 202     memmove (static_cast<void *> (&array[i]),
 203              static_cast<void *> (&array[i + 1]),
 204              (length - i - 1) * sizeof (Type));
 205     length--;
 206   }
 207
 208   void shrink (int size_)
 209   {
 210     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
 211      if (size < length)
 212        length = size;
 213   }
 214
 215   template <typename T>
 216   Type *find (T v)
 217   {
 218     Type *array = arrayZ();
 219     for (unsigned int i = 0; i < length; i++)
 220       if (array[i] == v)
 221         return &array[i];
 222     return nullptr;
 223   }
 224   template <typename T>
 225   const Type *find (T v) const
 226   {
 227     const Type *array = arrayZ();
 228     for (unsigned int i = 0; i < length; i++)
 229       if (array[i] == v)
 230         return &array[i];
 231     return nullptr;
 232   }
 233
 234   void qsort (int (*cmp)(const void*, const void*))
 235   { as_array ().qsort (cmp); }
 236   void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
 237   { as_array ().qsort (start, end); }
 238
 239   template <typename T>
 240   Type *lsearch (const T &x, Type *not_found = nullptr)
 241   { return as_array ().lsearch (x, not_found); }
 242   template <typename T>
 243   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
 244   { return as_array ().lsearch (x, not_found); }
 245
 246   template <typename T>
 247   Type *bsearch (const T &x, Type *not_found = nullptr)
 248   { return as_sorted_array ().bsearch (x, not_found); }
 249   template <typename T>
 250   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
 251   { return as_sorted_array ().bsearch (x, not_found); }
 252   template <typename T>
 253   bool bfind (const T &x, unsigned int *i = nullptr,
 254                      hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
 255                      unsigned int to_store = (unsigned int) -1) const
 256   { return as_sorted_array ().bfind (x, i, not_found, to_store); }
 257 };
 258
 259
 260 #endif /* HB_VECTOR_HH */