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