src/hb-array.hh

   1 /*
   2  * Copyright © 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_ARRAY_HH
  28 #define HB_ARRAY_HH
  29
  30 #include "hb.hh"
  31 #include "hb-algs.hh"
  32 #include "hb-iter.hh"
  33 #include "hb-null.hh"
  34
  35
  36 template <typename Type>
  37 struct hb_sorted_array_t;
  38
  39 enum hb_not_found_t
  40 {
  41   HB_NOT_FOUND_DONT_STORE,
  42   HB_NOT_FOUND_STORE,
  43   HB_NOT_FOUND_STORE_CLOSEST,
  44 };
  45
  46
  47 template <typename Type>
  48 struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&>
  49 {
  50   /*
  51    * Constructors.
  52    */
  53   hb_array_t () = default;
  54   hb_array_t (const hb_array_t&) = default;
  55   ~hb_array_t () = default;
  56   hb_array_t& operator= (const hb_array_t&) = default;
  57   hb_array_t& operator= (hb_array_t&&) = default;
  58
  59   constexpr hb_array_t (std::nullptr_t) : hb_array_t () {}
  60   constexpr hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {}
  61   template <unsigned int length_>
  62   constexpr hb_array_t (Type (&array_)[length_]) : hb_array_t (array_, length_) {}
  63
  64   template <typename U,
  65             hb_enable_if (hb_is_cr_convertible(U, Type))>
  66   constexpr hb_array_t (const hb_array_t<U> &o) :
  67     hb_iter_with_fallback_t<hb_array_t, Type&> (),
  68     arrayZ (o.arrayZ), length (o.length), backwards_length (o.backwards_length) {}
  69   template <typename U,
  70             hb_enable_if (hb_is_cr_convertible(U, Type))>
  71   hb_array_t& operator = (const hb_array_t<U> &o)
  72   { arrayZ = o.arrayZ; length = o.length; backwards_length = o.backwards_length; return *this; }
  73
  74   /*
  75    * Iterator implementation.
  76    */
  77   typedef Type& __item_t__;
  78   static constexpr bool is_random_access_iterator = true;
  79   Type& __item_at__ (unsigned i) const
  80   {
  81     if (unlikely (i >= length)) return CrapOrNull (Type);
  82     return arrayZ[i];
  83   }
  84   void __forward__ (unsigned n)
  85   {
  86     if (unlikely (n > length))
  87       n = length;
  88     length -= n;
  89     backwards_length += n;
  90     arrayZ += n;
  91   }
  92   void __rewind__ (unsigned n)
  93   {
  94     if (unlikely (n > backwards_length))
  95       n = backwards_length;
  96     length += n;
  97     backwards_length -= n;
  98     arrayZ -= n;
  99   }
 100   unsigned __len__ () const { return length; }
 101   /* Ouch. The operator== compares the contents of the array.  For range-based for loops,
 102    * it's best if we can just compare arrayZ, though comparing contents is still fast,
 103    * but also would require that Type has operator==.  As such, we optimize this operator
 104    * for range-based for loop and just compare arrayZ.  No need to compare length, as we
 105    * assume we're only compared to .end(). */
 106   bool operator != (const hb_array_t& o) const
 107   { return arrayZ != o.arrayZ; }
 108
 109   /* Extra operators.
 110    */
 111   Type * operator & () const { return arrayZ; }
 112   operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, length); }
 113   template <typename T> operator T * () const { return arrayZ; }
 114
 115   HB_INTERNAL bool operator == (const hb_array_t &o) const;
 116
 117   uint32_t hash () const {
 118     uint32_t current = 0;
 119     for (unsigned int i = 0; i < this->length; i++) {
 120       current = current * 31 + hb_hash (this->arrayZ[i]);
 121     }
 122     return current;
 123   }
 124
 125   /*
 126    * Compare, Sort, and Search.
 127    */
 128
 129   /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
 130   int cmp (const hb_array_t &a) const
 131   {
 132     if (length != a.length)
 133       return (int) a.length - (int) length;
 134     return hb_memcmp (a.arrayZ, arrayZ, get_size ());
 135   }
 136   HB_INTERNAL static int cmp (const void *pa, const void *pb)
 137   {
 138     hb_array_t *a = (hb_array_t *) pa;
 139     hb_array_t *b = (hb_array_t *) pb;
 140     return b->cmp (*a);
 141   }
 142
 143   template <typename T>
 144   Type *lsearch (const T &x, Type *not_found = nullptr)
 145   {
 146     unsigned i;
 147     return lfind (x, &i) ? &this->arrayZ[i] : not_found;
 148   }
 149   template <typename T>
 150   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
 151   {
 152     unsigned i;
 153     return lfind (x, &i) ? &this->arrayZ[i] : not_found;
 154   }
 155   template <typename T>
 156   bool lfind (const T &x, unsigned *pos = nullptr,
 157               hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
 158               unsigned int to_store = (unsigned int) -1) const
 159   {
 160     for (unsigned i = 0; i < length; ++i)
 161       if (hb_equal (x, this->arrayZ[i]))
 162       {
 163         if (pos)
 164           *pos = i;
 165         return true;
 166       }
 167
 168     if (pos)
 169     {
 170       switch (not_found)
 171       {
 172         case HB_NOT_FOUND_DONT_STORE:
 173           break;
 174
 175         case HB_NOT_FOUND_STORE:
 176           *pos = to_store;
 177           break;
 178
 179         case HB_NOT_FOUND_STORE_CLOSEST:
 180           *pos = length;
 181           break;
 182       }
 183     }
 184     return false;
 185   }
 186
 187   hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*))
 188   {
 189     if (likely (length))
 190       hb_qsort (arrayZ, length, this->get_item_size (), cmp_);
 191     return hb_sorted_array_t<Type> (*this);
 192   }
 193   hb_sorted_array_t<Type> qsort ()
 194   {
 195     if (likely (length))
 196       hb_qsort (arrayZ, length, this->get_item_size (), Type::cmp);
 197     return hb_sorted_array_t<Type> (*this);
 198   }
 199   void qsort (unsigned int start, unsigned int end)
 200   {
 201     end = hb_min (end, length);
 202     assert (start <= end);
 203     if (likely (start < end))
 204       hb_qsort (arrayZ + start, end - start, this->get_item_size (), Type::cmp);
 205   }
 206
 207   /*
 208    * Other methods.
 209    */
 210
 211   unsigned int get_size () const { return length * this->get_item_size (); }
 212
 213   /*
 214    * Reverse the order of items in this array in the range [start, end).
 215    */
 216   void reverse (unsigned start = 0, unsigned end = -1)
 217   {
 218     start = hb_min (start, length);
 219     end = hb_min (end, length);
 220
 221     if (end < start + 2)
 222       return;
 223
 224     for (unsigned lhs = start, rhs = end - 1; lhs < rhs; lhs++, rhs--) {
 225       Type temp = arrayZ[rhs];
 226       arrayZ[rhs] = arrayZ[lhs];
 227       arrayZ[lhs] = temp;
 228     }
 229   }
 230
 231   hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
 232   {
 233     if (!start_offset && !seg_count)
 234       return *this;
 235
 236     unsigned int count = length;
 237     if (unlikely (start_offset > count))
 238       count = 0;
 239     else
 240       count -= start_offset;
 241     if (seg_count)
 242       count = *seg_count = hb_min (count, *seg_count);
 243     return hb_array_t (arrayZ + start_offset, count);
 244   }
 245   hb_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
 246   { return sub_array (start_offset, &seg_count); }
 247
 248   hb_array_t truncate (unsigned length) const { return sub_array (0, length); }
 249
 250   template <typename T,
 251             unsigned P = sizeof (Type),
 252             hb_enable_if (P == 1)>
 253   const T *as () const
 254   { return length < hb_min_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); }
 255
 256   template <typename T,
 257             unsigned P = sizeof (Type),
 258             hb_enable_if (P == 1)>
 259   bool check_range (const T *p, unsigned int size = T::static_size) const
 260   {
 261     return arrayZ <= ((const char *) p)
 262         && ((const char *) p) <= arrayZ + length
 263         && (unsigned int) (arrayZ + length - (const char *) p) >= size;
 264   }
 265
 266   /* Only call if you allocated the underlying array using hb_malloc() or similar. */
 267   void fini ()
 268   { hb_free ((void *) arrayZ); arrayZ = nullptr; length = 0; }
 269
 270   template <typename hb_serialize_context_t>
 271   hb_array_t copy (hb_serialize_context_t *c) const
 272   {
 273     TRACE_SERIALIZE (this);
 274     auto* out = c->start_embed (arrayZ);
 275     if (unlikely (!c->extend_size (out, get_size ()))) return_trace (hb_array_t ());
 276     for (unsigned i = 0; i < length; i++)
 277       out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */
 278     return_trace (hb_array_t (out, length));
 279   }
 280
 281   template <typename hb_sanitize_context_t>
 282   bool sanitize (hb_sanitize_context_t *c) const
 283   { return c->check_array (arrayZ, length); }
 284
 285   /*
 286    * Members
 287    */
 288
 289   public:
 290   Type *arrayZ = nullptr;
 291   unsigned int length = 0;
 292   unsigned int backwards_length = 0;
 293 };
 294 template <typename T> inline hb_array_t<T>
 295 hb_array (T *array, unsigned int length)
 296 { return hb_array_t<T> (array, length); }
 297 template <typename T, unsigned int length_> inline hb_array_t<T>
 298 hb_array (T (&array_)[length_])
 299 { return hb_array_t<T> (array_); }
 300
 301 template <typename Type>
 302 struct hb_sorted_array_t :
 303         hb_iter_t<hb_sorted_array_t<Type>, Type&>,
 304         hb_array_t<Type>
 305 {
 306   typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t;
 307   HB_ITER_USING (iter_base_t);
 308   static constexpr bool is_random_access_iterator = true;
 309   static constexpr bool is_sorted_iterator = true;
 310
 311   hb_sorted_array_t () = default;
 312   hb_sorted_array_t (const hb_sorted_array_t&) = default;
 313   ~hb_sorted_array_t () = default;
 314   hb_sorted_array_t& operator= (const hb_sorted_array_t&) = default;
 315   hb_sorted_array_t& operator= (hb_sorted_array_t&&) = default;
 316
 317   constexpr hb_sorted_array_t (std::nullptr_t) : hb_sorted_array_t () {}
 318   constexpr hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {}
 319   template <unsigned int length_>
 320   constexpr hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {}
 321
 322   template <typename U,
 323             hb_enable_if (hb_is_cr_convertible(U, Type))>
 324   constexpr hb_sorted_array_t (const hb_array_t<U> &o) :
 325     hb_iter_t<hb_sorted_array_t, Type&> (),
 326     hb_array_t<Type> (o) {}
 327   template <typename U,
 328             hb_enable_if (hb_is_cr_convertible(U, Type))>
 329   hb_sorted_array_t& operator = (const hb_array_t<U> &o)
 330   { hb_array_t<Type> (*this) = o; return *this; }
 331
 332   /* Iterator implementation. */
 333   bool operator != (const hb_sorted_array_t& o) const
 334   { return this->arrayZ != o.arrayZ || this->length != o.length; }
 335
 336   hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
 337   { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
 338   hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
 339   { return sub_array (start_offset, &seg_count); }
 340
 341   hb_sorted_array_t truncate (unsigned length) const { return sub_array (0, length); }
 342
 343   template <typename T>
 344   Type *bsearch (const T &x, Type *not_found = nullptr)
 345   {
 346     unsigned int i;
 347     return bfind (x, &i) ? &this->arrayZ[i] : not_found;
 348   }
 349   template <typename T>
 350   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
 351   {
 352     unsigned int i;
 353     return bfind (x, &i) ? &this->arrayZ[i] : not_found;
 354   }
 355   template <typename T>
 356   bool bfind (const T &x, unsigned int *i = nullptr,
 357               hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
 358               unsigned int to_store = (unsigned int) -1) const
 359   {
 360     unsigned pos;
 361
 362     if (bsearch_impl (x, &pos))
 363     {
 364       if (i)
 365         *i = pos;
 366       return true;
 367     }
 368
 369     if (i)
 370     {
 371       switch (not_found)
 372       {
 373         case HB_NOT_FOUND_DONT_STORE:
 374           break;
 375
 376         case HB_NOT_FOUND_STORE:
 377           *i = to_store;
 378           break;
 379
 380         case HB_NOT_FOUND_STORE_CLOSEST:
 381           *i = pos;
 382           break;
 383       }
 384     }
 385     return false;
 386   }
 387   template <typename T>
 388   bool bsearch_impl (const T &x, unsigned *pos) const
 389   {
 390     return hb_bsearch_impl (pos,
 391                             x,
 392                             this->arrayZ,
 393                             this->length,
 394                             sizeof (Type),
 395                             _hb_cmp_method<T, Type>);
 396   }
 397 };
 398 template <typename T> inline hb_sorted_array_t<T>
 399 hb_sorted_array (T *array, unsigned int length)
 400 { return hb_sorted_array_t<T> (array, length); }
 401 template <typename T, unsigned int length_> inline hb_sorted_array_t<T>
 402 hb_sorted_array (T (&array_)[length_])
 403 { return hb_sorted_array_t<T> (array_); }
 404
 405 template <typename T>
 406 bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const
 407 {
 408   if (o.length != this->length) return false;
 409   for (unsigned int i = 0; i < this->length; i++) {
 410     if (this->arrayZ[i] != o.arrayZ[i]) return false;
 411   }
 412   return true;
 413 }
 414
 415 /* TODO Specialize operator== for hb_bytes_t and hb_ubytes_t. */
 416
 417 template <>
 418 inline uint32_t hb_array_t<const char>::hash () const {
 419   uint32_t current = 0;
 420   for (unsigned int i = 0; i < this->length; i++)
 421     current = current * 31 + (uint32_t) (this->arrayZ[i] * 2654435761u);
 422   return current;
 423 }
 424
 425 template <>
 426 inline uint32_t hb_array_t<const unsigned char>::hash () const {
 427   uint32_t current = 0;
 428   for (unsigned int i = 0; i < this->length; i++)
 429     current = current * 31 + (uint32_t) (this->arrayZ[i] * 2654435761u);
 430   return current;
 431 }
 432
 433
 434 typedef hb_array_t<const char> hb_bytes_t;
 435 typedef hb_array_t<const unsigned char> hb_ubytes_t;
 436
 437
 438
 439 #endif /* HB_ARRAY_HH */