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_vector_t ()  { init (); }
  42   hb_vector_t (const hb_vector_t &o)
  43   {
  44     init ();
  45     alloc (o.length);
  46     hb_copy (o, *this);
  47   }
  48   hb_vector_t (hb_vector_t &&o)
  49   {
  50     allocated = o.allocated;
  51     length = o.length;
  52     arrayZ = o.arrayZ;
  53     o.init ();
  54   }
  55   ~hb_vector_t () { fini (); }
  56
  57   private:
  58   int allocated; /* == -1 means allocation failed. */
  59   public:
  60   unsigned int length;
  61   public:
  62   Type *arrayZ;
  63
  64   void init ()
  65   {
  66     allocated = length = 0;
  67     arrayZ = nullptr;
  68   }
  69
  70   void fini ()
  71   {
  72     free (arrayZ);
  73     init ();
  74   }
  75   void fini_deep ()
  76   {
  77     unsigned int count = length;
  78     for (unsigned int i = 0; i < count; i++)
  79       arrayZ[i].fini ();
  80     fini ();
  81   }
  82
  83   void reset () { resize (0); }
  84
  85   hb_vector_t& operator = (const hb_vector_t &o)
  86   {
  87     reset ();
  88     alloc (o.length);
  89     hb_copy (o, *this);
  90     return *this;
  91   }
  92   hb_vector_t& operator = (hb_vector_t &&o)
  93   {
  94     fini ();
  95     allocated = o.allocated;
  96     length = o.length;
  97     arrayZ = o.arrayZ;
  98     o.init ();
  99     return *this;
 100   }
 101
 102   hb_bytes_t as_bytes () const
 103   { return hb_bytes_t ((const char *) arrayZ, length * item_size); }
 104
 105   bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
 106   bool operator != (const hb_vector_t &o) const { return !(*this == o); }
 107   uint32_t hash () const { return as_array ().hash (); }
 108
 109   Type& operator [] (int i_)
 110   {
 111     unsigned int i = (unsigned int) i_;
 112     if (unlikely (i >= length))
 113       return Crap (Type);
 114     return arrayZ[i];
 115   }
 116   const Type& operator [] (int i_) const
 117   {
 118     unsigned int i = (unsigned int) i_;
 119     if (unlikely (i >= length))
 120       return Null (Type);
 121     return arrayZ[i];
 122   }
 123
 124   Type& tail () { return (*this)[length - 1]; }
 125   const Type& tail () const { return (*this)[length - 1]; }
 126
 127   explicit operator bool () const { return length; }
 128   unsigned get_size () const { return length * item_size; }
 129
 130   /* Sink interface. */
 131   template <typename T>
 132   hb_vector_t& operator << (T&& v) { push (hb_forward<T> (v)); return *this; }
 133
 134   hb_array_t<      Type> as_array ()       { return hb_array (arrayZ, length); }
 135   hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); }
 136
 137   /* Iterator. */
 138   typedef hb_array_t<const Type>   iter_t;
 139   typedef hb_array_t<      Type> writer_t;
 140     iter_t   iter () const { return as_array (); }
 141   writer_t writer ()       { return as_array (); }
 142   operator   iter_t () const { return   iter (); }
 143   operator writer_t ()       { return writer (); }
 144
 145   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
 146   { return as_array ().sub_array (start_offset, count); }
 147   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
 148   { return as_array ().sub_array (start_offset, count); }
 149   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
 150   { return as_array ().sub_array (start_offset, count); }
 151   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
 152   { return as_array ().sub_array (start_offset, count); }
 153
 154   hb_sorted_array_t<Type> as_sorted_array ()
 155   { return hb_sorted_array (arrayZ, length); }
 156   hb_sorted_array_t<const Type> as_sorted_array () const
 157   { return hb_sorted_array (arrayZ, length); }
 158
 159   template <typename T> explicit operator T * () { return arrayZ; }
 160   template <typename T> explicit operator const T * () const { return arrayZ; }
 161
 162   Type * operator  + (unsigned int i) { return arrayZ + i; }
 163   const Type * operator  + (unsigned int i) const { return arrayZ + i; }
 164
 165   Type *push ()
 166   {
 167     if (unlikely (!resize (length + 1)))
 168       return &Crap (Type);
 169     return &arrayZ[length - 1];
 170   }
 171   template <typename T>
 172   Type *push (T&& v)
 173   {
 174     Type *p = push ();
 175     *p = hb_forward<T> (v);
 176     return p;
 177   }
 178
 179   bool in_error () const { return allocated < 0; }
 180
 181   /* Allocate for size but don't adjust length. */
 182   bool alloc (unsigned int size)
 183   {
 184     if (unlikely (allocated < 0))
 185       return false;
 186
 187     if (likely (size <= (unsigned) allocated))
 188       return true;
 189
 190     /* Reallocate */
 191
 192     unsigned int new_allocated = allocated;
 193     while (size >= new_allocated)
 194       new_allocated += (new_allocated >> 1) + 8;
 195
 196     Type *new_array = nullptr;
 197     bool overflows =
 198       (int) new_allocated < 0 ||
 199       (new_allocated < (unsigned) allocated) ||
 200       hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
 201     if (likely (!overflows))
 202       new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type));
 203
 204     if (unlikely (!new_array))
 205     {
 206       allocated = -1;
 207       return false;
 208     }
 209
 210     arrayZ = new_array;
 211     allocated = new_allocated;
 212
 213     return true;
 214   }
 215
 216   bool resize (int size_)
 217   {
 218     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
 219     if (!alloc (size))
 220       return false;
 221
 222     if (size > length)
 223       memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
 224
 225     length = size;
 226     return true;
 227   }
 228
 229   Type pop ()
 230   {
 231     if (!length) return Null (Type);
 232     return hb_move (arrayZ[--length]); /* Does this move actually work? */
 233   }
 234
 235   void remove (unsigned int i)
 236   {
 237     if (unlikely (i >= length))
 238       return;
 239     memmove (static_cast<void *> (&arrayZ[i]),
 240              static_cast<void *> (&arrayZ[i + 1]),
 241              (length - i - 1) * sizeof (Type));
 242     length--;
 243   }
 244
 245   void shrink (int size_)
 246   {
 247     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
 248      if (size < length)
 249        length = size;
 250   }
 251
 252   template <typename T>
 253   Type *find (T v)
 254   {
 255     for (unsigned int i = 0; i < length; i++)
 256       if (arrayZ[i] == v)
 257         return &arrayZ[i];
 258     return nullptr;
 259   }
 260   template <typename T>
 261   const Type *find (T v) const
 262   {
 263     for (unsigned int i = 0; i < length; i++)
 264       if (arrayZ[i] == v)
 265         return &arrayZ[i];
 266     return nullptr;
 267   }
 268
 269   void qsort (int (*cmp)(const void*, const void*))
 270   { as_array ().qsort (cmp); }
 271   void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
 272   { as_array ().qsort (start, end); }
 273
 274   template <typename T>
 275   Type *lsearch (const T &x, Type *not_found = nullptr)
 276   { return as_array ().lsearch (x, not_found); }
 277   template <typename T>
 278   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
 279   { return as_array ().lsearch (x, not_found); }
 280 };
 281
 282 template <typename Type>
 283 struct hb_sorted_vector_t : hb_vector_t<Type>
 284 {
 285   hb_sorted_array_t<      Type> as_array ()       { return hb_sorted_array (this->arrayZ, this->length); }
 286   hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); }
 287
 288   /* Iterator. */
 289   typedef hb_sorted_array_t<const Type> const_iter_t;
 290   typedef hb_sorted_array_t<      Type>       iter_t;
 291   const_iter_t  iter () const { return as_array (); }
 292   const_iter_t citer () const { return as_array (); }
 293         iter_t  iter ()       { return as_array (); }
 294   operator       iter_t ()       { return iter (); }
 295   operator const_iter_t () const { return iter (); }
 296
 297   template <typename T>
 298   Type *bsearch (const T &x, Type *not_found = nullptr)
 299   { return as_array ().bsearch (x, not_found); }
 300   template <typename T>
 301   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
 302   { return as_array ().bsearch (x, not_found); }
 303   template <typename T>
 304   bool bfind (const T &x, unsigned int *i = nullptr,
 305               hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
 306               unsigned int to_store = (unsigned int) -1) const
 307   { return as_array ().bfind (x, i, not_found, to_store); }
 308 };
 309
 310 #endif /* HB_VECTOR_HH */