gfx/harfbuzz/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-meta.hh"
  33 #include "hb-null.hh"
  34
  35
  36 template <typename Type,
  37           bool sorted=false>
  38 struct hb_vector_t
  39 {
  40   typedef Type item_t;
  41   static constexpr unsigned item_size = hb_static_size (Type);
  42   using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type;
  43   using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type;
  44
  45   hb_vector_t () = default;
  46   hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
  47   {
  48     alloc (lst.size (), true);
  49     for (auto&& item : lst)
  50       push (item);
  51   }
  52   template <typename Iterable,
  53             hb_requires (hb_is_iterable (Iterable))>
  54   hb_vector_t (const Iterable &o) : hb_vector_t ()
  55   {
  56     auto iter = hb_iter (o);
  57     if (iter.is_random_access_iterator || iter.has_fast_len)
  58       alloc (hb_len (iter), true);
  59     hb_copy (iter, *this);
  60   }
  61   hb_vector_t (const hb_vector_t &o) : hb_vector_t ()
  62   {
  63     alloc (o.length, true);
  64     if (unlikely (in_error ())) return;
  65     copy_array (o.as_array ());
  66   }
  67   hb_vector_t (array_t o) : hb_vector_t ()
  68   {
  69     alloc (o.length, true);
  70     if (unlikely (in_error ())) return;
  71     copy_array (o);
  72   }
  73   hb_vector_t (c_array_t o) : hb_vector_t ()
  74   {
  75     alloc (o.length, true);
  76     if (unlikely (in_error ())) return;
  77     copy_array (o);
  78   }
  79   hb_vector_t (hb_vector_t &&o)
  80   {
  81     allocated = o.allocated;
  82     length = o.length;
  83     arrayZ = o.arrayZ;
  84     o.init ();
  85   }
  86   ~hb_vector_t () { fini (); }
  87
  88   public:
  89   int allocated = 0; /* < 0 means allocation failed. */
  90   unsigned int length = 0;
  91   public:
  92   Type *arrayZ = nullptr;
  93
  94   void init ()
  95   {
  96     allocated = length = 0;
  97     arrayZ = nullptr;
  98   }
  99   void init0 ()
 100   {
 101   }
 102
 103   void fini ()
 104   {
 105     /* We allow a hack to make the vector point to a foriegn array
 106      * by the user. In that case length/arrayZ are non-zero but
 107      * allocated is zero. Don't free anything. */
 108     if (allocated)
 109     {
 110       shrink_vector (0);
 111       hb_free (arrayZ);
 112     }
 113     init ();
 114   }
 115
 116   void reset ()
 117   {
 118     if (unlikely (in_error ()))
 119       reset_error ();
 120     resize (0);
 121   }
 122
 123   friend void swap (hb_vector_t& a, hb_vector_t& b)
 124   {
 125     hb_swap (a.allocated, b.allocated);
 126     hb_swap (a.length, b.length);
 127     hb_swap (a.arrayZ, b.arrayZ);
 128   }
 129
 130   hb_vector_t& operator = (const hb_vector_t &o)
 131   {
 132     reset ();
 133     alloc (o.length, true);
 134     if (unlikely (in_error ())) return *this;
 135
 136     copy_array (o.as_array ());
 137
 138     return *this;
 139   }
 140   hb_vector_t& operator = (hb_vector_t &&o)
 141   {
 142     hb_swap (*this, o);
 143     return *this;
 144   }
 145
 146   hb_bytes_t as_bytes () const
 147   { return hb_bytes_t ((const char *) arrayZ, get_size ()); }
 148
 149   bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
 150   bool operator != (const hb_vector_t &o) const { return !(*this == o); }
 151   uint32_t hash () const { return as_array ().hash (); }
 152
 153   Type& operator [] (int i_)
 154   {
 155     unsigned int i = (unsigned int) i_;
 156     if (unlikely (i >= length))
 157       return Crap (Type);
 158     return arrayZ[i];
 159   }
 160   const Type& operator [] (int i_) const
 161   {
 162     unsigned int i = (unsigned int) i_;
 163     if (unlikely (i >= length))
 164       return Null (Type);
 165     return arrayZ[i];
 166   }
 167
 168   Type& tail () { return (*this)[length - 1]; }
 169   const Type& tail () const { return (*this)[length - 1]; }
 170
 171   explicit operator bool () const { return length; }
 172   unsigned get_size () const { return length * item_size; }
 173
 174   /* Sink interface. */
 175   template <typename T>
 176   hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; }
 177
 178   array_t   as_array ()       { return hb_array (arrayZ, length); }
 179   c_array_t as_array () const { return hb_array (arrayZ, length); }
 180
 181   /* Iterator. */
 182   typedef c_array_t   iter_t;
 183   typedef array_t   writer_t;
 184     iter_t   iter () const { return as_array (); }
 185   writer_t writer ()       { return as_array (); }
 186   operator   iter_t () const { return   iter (); }
 187   operator writer_t ()       { return writer (); }
 188
 189   /* Faster range-based for loop. */
 190   Type *begin () const { return arrayZ; }
 191   Type *end () const { return arrayZ + length; }
 192
 193
 194   hb_sorted_array_t<Type> as_sorted_array ()
 195   { return hb_sorted_array (arrayZ, length); }
 196   hb_sorted_array_t<const Type> as_sorted_array () const
 197   { return hb_sorted_array (arrayZ, length); }
 198
 199   template <typename T> explicit operator T * () { return arrayZ; }
 200   template <typename T> explicit operator const T * () const { return arrayZ; }
 201
 202   Type * operator  + (unsigned int i) { return arrayZ + i; }
 203   const Type * operator  + (unsigned int i) const { return arrayZ + i; }
 204
 205   Type *push ()
 206   {
 207     if (unlikely (!resize (length + 1)))
 208       return std::addressof (Crap (Type));
 209     return std::addressof (arrayZ[length - 1]);
 210   }
 211   template <typename T,
 212             typename T2 = Type,
 213             hb_enable_if (!std::is_copy_constructible<T2>::value &&
 214                           std::is_copy_assignable<T>::value)>
 215   Type *push (T&& v)
 216   {
 217     Type *p = push ();
 218     if (p == std::addressof (Crap (Type)))
 219       // If push failed to allocate then don't copy v, since this may cause
 220       // the created copy to leak memory since we won't have stored a
 221       // reference to it.
 222       return p;
 223     *p = std::forward<T> (v);
 224     return p;
 225   }
 226   template <typename T,
 227             typename T2 = Type,
 228             hb_enable_if (std::is_copy_constructible<T2>::value)>
 229   Type *push (T&& v)
 230   {
 231     if (unlikely ((int) length >= allocated && !alloc (length + 1)))
 232       // If push failed to allocate then don't copy v, since this may cause
 233       // the created copy to leak memory since we won't have stored a
 234       // reference to it.
 235       return std::addressof (Crap (Type));
 236
 237     /* Emplace. */
 238     Type *p = std::addressof (arrayZ[length++]);
 239     return new (p) Type (std::forward<T> (v));
 240   }
 241
 242   bool in_error () const { return allocated < 0; }
 243   void set_error ()
 244   {
 245     assert (allocated >= 0);
 246     allocated = -allocated - 1;
 247   }
 248   void reset_error ()
 249   {
 250     assert (allocated < 0);
 251     allocated = -(allocated + 1);
 252   }
 253
 254   template <typename T = Type,
 255             hb_enable_if (hb_is_trivially_copy_assignable(T))>
 256   Type *
 257   realloc_vector (unsigned new_allocated, hb_priority<0>)
 258   {
 259     if (!new_allocated)
 260     {
 261       hb_free (arrayZ);
 262       return nullptr;
 263     }
 264     return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
 265   }
 266   template <typename T = Type,
 267             hb_enable_if (!hb_is_trivially_copy_assignable(T))>
 268   Type *
 269   realloc_vector (unsigned new_allocated, hb_priority<0>)
 270   {
 271     if (!new_allocated)
 272     {
 273       hb_free (arrayZ);
 274       return nullptr;
 275     }
 276     Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type));
 277     if (likely (new_array))
 278     {
 279       for (unsigned i = 0; i < length; i++)
 280       {
 281         new (std::addressof (new_array[i])) Type ();
 282         new_array[i] = std::move (arrayZ[i]);
 283         arrayZ[i].~Type ();
 284       }
 285       hb_free (arrayZ);
 286     }
 287     return new_array;
 288   }
 289   /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */
 290   template <typename T = Type,
 291             hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
 292                           hb_is_same (T, hb_array_t <typename T::item_t>))>
 293   Type *
 294   realloc_vector (unsigned new_allocated, hb_priority<1>)
 295   {
 296     if (!new_allocated)
 297     {
 298       hb_free (arrayZ);
 299       return nullptr;
 300     }
 301     return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
 302   }
 303
 304   template <typename T = Type,
 305             hb_enable_if (hb_is_trivially_constructible(T))>
 306   void
 307   grow_vector (unsigned size, hb_priority<0>)
 308   {
 309     hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
 310     length = size;
 311   }
 312   template <typename T = Type,
 313             hb_enable_if (!hb_is_trivially_constructible(T))>
 314   void
 315   grow_vector (unsigned size, hb_priority<0>)
 316   {
 317     for (; length < size; length++)
 318       new (std::addressof (arrayZ[length])) Type ();
 319   }
 320   /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */
 321   template <typename T = Type,
 322             hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
 323                           hb_is_same (T, hb_array_t <typename T::item_t>))>
 324   void
 325   grow_vector (unsigned size, hb_priority<1>)
 326   {
 327     hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
 328     length = size;
 329   }
 330
 331   template <typename T = Type,
 332             hb_enable_if (hb_is_trivially_copyable (T))>
 333   void
 334   copy_array (hb_array_t<const Type> other)
 335   {
 336     length = other.length;
 337     if (!HB_OPTIMIZE_SIZE_VAL && sizeof (T) >= sizeof (long long))
 338       /* This runs faster because of alignment. */
 339       for (unsigned i = 0; i < length; i++)
 340         arrayZ[i] = other.arrayZ[i];
 341     else
 342        hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size);
 343   }
 344   template <typename T = Type,
 345             hb_enable_if (!hb_is_trivially_copyable (T) &&
 346                            std::is_copy_constructible<T>::value)>
 347   void
 348   copy_array (hb_array_t<const Type> other)
 349   {
 350     length = 0;
 351     while (length < other.length)
 352     {
 353       length++;
 354       new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]);
 355     }
 356   }
 357   template <typename T = Type,
 358             hb_enable_if (!hb_is_trivially_copyable (T) &&
 359                           !std::is_copy_constructible<T>::value &&
 360                           std::is_default_constructible<T>::value &&
 361                           std::is_copy_assignable<T>::value)>
 362   void
 363   copy_array (hb_array_t<const Type> other)
 364   {
 365     length = 0;
 366     while (length < other.length)
 367     {
 368       length++;
 369       new (std::addressof (arrayZ[length - 1])) Type ();
 370       arrayZ[length - 1] = other.arrayZ[length - 1];
 371     }
 372   }
 373
 374   void
 375   shrink_vector (unsigned size)
 376   {
 377     assert (size <= length);
 378     if (!std::is_trivially_destructible<Type>::value)
 379     {
 380       unsigned count = length - size;
 381       Type *p = arrayZ + length - 1;
 382       while (count--)
 383         p--->~Type ();
 384     }
 385     length = size;
 386   }
 387
 388   void
 389   shift_down_vector (unsigned i)
 390   {
 391     for (; i < length; i++)
 392       arrayZ[i - 1] = std::move (arrayZ[i]);
 393   }
 394
 395   /* Allocate for size but don't adjust length. */
 396   bool alloc (unsigned int size, bool exact=false)
 397   {
 398     if (unlikely (in_error ()))
 399       return false;
 400
 401     unsigned int new_allocated;
 402     if (exact)
 403     {
 404       /* If exact was specified, we allow shrinking the storage. */
 405       size = hb_max (size, length);
 406       if (size <= (unsigned) allocated &&
 407           size >= (unsigned) allocated >> 2)
 408         return true;
 409
 410       new_allocated = size;
 411     }
 412     else
 413     {
 414       if (likely (size <= (unsigned) allocated))
 415         return true;
 416
 417       new_allocated = allocated;
 418       while (size > new_allocated)
 419         new_allocated += (new_allocated >> 1) + 8;
 420     }
 421
 422
 423     /* Reallocate */
 424
 425     bool overflows =
 426       (int) in_error () ||
 427       (new_allocated < size) ||
 428       hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
 429
 430     if (unlikely (overflows))
 431     {
 432       set_error ();
 433       return false;
 434     }
 435
 436     Type *new_array = realloc_vector (new_allocated, hb_prioritize);
 437
 438     if (unlikely (new_allocated && !new_array))
 439     {
 440       if (new_allocated <= (unsigned) allocated)
 441         return true; // shrinking failed; it's okay; happens in our fuzzer
 442
 443       set_error ();
 444       return false;
 445     }
 446
 447     arrayZ = new_array;
 448     allocated = new_allocated;
 449
 450     return true;
 451   }
 452
 453   bool resize (int size_, bool initialize = true, bool exact = false)
 454   {
 455     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
 456     if (!alloc (size, exact))
 457       return false;
 458
 459     if (size > length)
 460     {
 461       if (initialize)
 462         grow_vector (size, hb_prioritize);
 463     }
 464     else if (size < length)
 465     {
 466       if (initialize)
 467         shrink_vector (size);
 468     }
 469
 470     length = size;
 471     return true;
 472   }
 473   bool resize_exact (int size_, bool initialize = true)
 474   {
 475     return resize (size_, initialize, true);
 476   }
 477
 478   Type pop ()
 479   {
 480     if (!length) return Null (Type);
 481     Type v {std::move (arrayZ[length - 1])};
 482     arrayZ[length - 1].~Type ();
 483     length--;
 484     return v;
 485   }
 486
 487   void remove_ordered (unsigned int i)
 488   {
 489     if (unlikely (i >= length))
 490       return;
 491     shift_down_vector (i + 1);
 492     arrayZ[length - 1].~Type ();
 493     length--;
 494   }
 495
 496   template <bool Sorted = sorted,
 497             hb_enable_if (!Sorted)>
 498   void remove_unordered (unsigned int i)
 499   {
 500     if (unlikely (i >= length))
 501       return;
 502     if (i != length - 1)
 503       arrayZ[i] = std::move (arrayZ[length - 1]);
 504     arrayZ[length - 1].~Type ();
 505     length--;
 506   }
 507
 508   void shrink (int size_, bool shrink_memory = true)
 509   {
 510     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
 511     if (size >= length)
 512       return;
 513
 514     shrink_vector (size);
 515
 516     if (shrink_memory)
 517       alloc (size, true); /* To force shrinking memory if needed. */
 518   }
 519
 520
 521   /* Sorting API. */
 522   void qsort (int (*cmp)(const void*, const void*) = Type::cmp)
 523   { as_array ().qsort (cmp); }
 524
 525   /* Unsorted search API. */
 526   template <typename T>
 527   Type *lsearch (const T &x, Type *not_found = nullptr)
 528   { return as_array ().lsearch (x, not_found); }
 529   template <typename T>
 530   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
 531   { return as_array ().lsearch (x, not_found); }
 532   template <typename T>
 533   bool lfind (const T &x, unsigned *pos = nullptr) const
 534   { return as_array ().lfind (x, pos); }
 535
 536   /* Sorted search API. */
 537   template <typename T,
 538             bool Sorted=sorted, hb_enable_if (Sorted)>
 539   Type *bsearch (const T &x, Type *not_found = nullptr)
 540   { return as_array ().bsearch (x, not_found); }
 541   template <typename T,
 542             bool Sorted=sorted, hb_enable_if (Sorted)>
 543   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
 544   { return as_array ().bsearch (x, not_found); }
 545   template <typename T,
 546             bool Sorted=sorted, hb_enable_if (Sorted)>
 547   bool bfind (const T &x, unsigned int *i = nullptr,
 548               hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
 549               unsigned int to_store = (unsigned int) -1) const
 550   { return as_array ().bfind (x, i, not_found, to_store); }
 551 };
 552
 553 template <typename Type>
 554 using hb_sorted_vector_t = hb_vector_t<Type, true>;
 555
 556 #endif /* HB_VECTOR_HH */