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   hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
 175   {
 176     if (!start_offset && !seg_count)
 177       return *this;
 178
 179     unsigned int count = length;
 180     if (unlikely (start_offset > count))
 181       count = 0;
 182     else
 183       count -= start_offset;
 184     if (seg_count)
 185       count = *seg_count = hb_min (count, *seg_count);
 186     return hb_array_t (arrayZ + start_offset, count);
 187   }
 188   hb_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
 189   { return sub_array (start_offset, &seg_count); }
 190
 191   hb_array_t truncate (unsigned length) const { return sub_array (0, length); }
 192
 193   template <typename T,
 194             unsigned P = sizeof (Type),
 195             hb_enable_if (P == 1)>
 196   const T *as () const
 197   { return length < hb_null_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); }
 198
 199   template <typename T,
 200             unsigned P = sizeof (Type),
 201             hb_enable_if (P == 1)>
 202   bool in_range (const T *p, unsigned int size = T::static_size) const
 203   {
 204     return ((const char *) p) >= arrayZ
 205         && ((const char *) p + size) <= arrayZ + length;
 206   }
 207
 208   /* Only call if you allocated the underlying array using malloc() or similar. */
 209   void free ()
 210   { ::free ((void *) arrayZ); arrayZ = nullptr; length = 0; }
 211
 212   template <typename hb_serialize_context_t>
 213   hb_array_t copy (hb_serialize_context_t *c) const
 214   {
 215     TRACE_SERIALIZE (this);
 216     auto* out = c->start_embed (arrayZ);
 217     if (unlikely (!c->extend_size (out, get_size ()))) return_trace (hb_array_t ());
 218     for (unsigned i = 0; i < length; i++)
 219       out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */
 220     return_trace (hb_array_t (out, length));
 221   }
 222
 223   template <typename hb_sanitize_context_t>
 224   bool sanitize (hb_sanitize_context_t *c) const
 225   { return c->check_array (arrayZ, length); }
 226
 227   /*
 228    * Members
 229    */
 230
 231   public:
 232   Type *arrayZ;
 233   unsigned int length;
 234   unsigned int backwards_length;
 235 };
 236 template <typename T> inline hb_array_t<T>
 237 hb_array (T *array, unsigned int length)
 238 { return hb_array_t<T> (array, length); }
 239 template <typename T, unsigned int length_> inline hb_array_t<T>
 240 hb_array (T (&array_)[length_])
 241 { return hb_array_t<T> (array_); }
 242
 243 enum hb_bfind_not_found_t
 244 {
 245   HB_BFIND_NOT_FOUND_DONT_STORE,
 246   HB_BFIND_NOT_FOUND_STORE,
 247   HB_BFIND_NOT_FOUND_STORE_CLOSEST,
 248 };
 249
 250 template <typename Type>
 251 struct hb_sorted_array_t :
 252         hb_iter_t<hb_sorted_array_t<Type>, Type&>,
 253         hb_array_t<Type>
 254 {
 255   typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t;
 256   HB_ITER_USING (iter_base_t);
 257   static constexpr bool is_random_access_iterator = true;
 258   static constexpr bool is_sorted_iterator = true;
 259
 260   hb_sorted_array_t () : hb_array_t<Type> () {}
 261   hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {}
 262   template <unsigned int length_>
 263   hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {}
 264
 265   template <typename U,
 266             hb_enable_if (hb_is_cr_convertible(U, Type))>
 267   hb_sorted_array_t (const hb_array_t<U> &o) :
 268     hb_iter_t<hb_sorted_array_t, Type&> (),
 269     hb_array_t<Type> (o) {}
 270   template <typename U,
 271             hb_enable_if (hb_is_cr_convertible(U, Type))>
 272   hb_sorted_array_t& operator = (const hb_array_t<U> &o)
 273   { hb_array_t<Type> (*this) = o; return *this; }
 274
 275   /* Iterator implementation. */
 276   bool operator != (const hb_sorted_array_t& o) const
 277   { return this->arrayZ != o.arrayZ || this->length != o.length; }
 278
 279   hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
 280   { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
 281   hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
 282   { return sub_array (start_offset, &seg_count); }
 283
 284   hb_sorted_array_t truncate (unsigned length) const { return sub_array (0, length); }
 285
 286   template <typename T>
 287   Type *bsearch (const T &x, Type *not_found = nullptr)
 288   {
 289     unsigned int i;
 290     return bfind (x, &i) ? &this->arrayZ[i] : not_found;
 291   }
 292   template <typename T>
 293   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
 294   {
 295     unsigned int i;
 296     return bfind (x, &i) ? &this->arrayZ[i] : not_found;
 297   }
 298   template <typename T>
 299   bool bfind (const T &x, unsigned int *i = nullptr,
 300               hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
 301               unsigned int to_store = (unsigned int) -1) const
 302   {
 303     int min = 0, max = (int) this->length - 1;
 304     const Type *array = this->arrayZ;
 305     while (min <= max)
 306     {
 307       int mid = ((unsigned int) min + (unsigned int) max) / 2;
 308       int c = array[mid].cmp (x);
 309       if (c < 0)
 310         max = mid - 1;
 311       else if (c > 0)
 312         min = mid + 1;
 313       else
 314       {
 315         if (i)
 316           *i = mid;
 317         return true;
 318       }
 319     }
 320     if (i)
 321     {
 322       switch (not_found)
 323       {
 324         case HB_BFIND_NOT_FOUND_DONT_STORE:
 325           break;
 326
 327         case HB_BFIND_NOT_FOUND_STORE:
 328           *i = to_store;
 329           break;
 330
 331         case HB_BFIND_NOT_FOUND_STORE_CLOSEST:
 332           if (max < 0 || (max < (int) this->length && array[max].cmp (x) > 0))
 333             max++;
 334           *i = max;
 335           break;
 336       }
 337     }
 338     return false;
 339   }
 340 };
 341 template <typename T> inline hb_sorted_array_t<T>
 342 hb_sorted_array (T *array, unsigned int length)
 343 { return hb_sorted_array_t<T> (array, length); }
 344 template <typename T, unsigned int length_> inline hb_sorted_array_t<T>
 345 hb_sorted_array (T (&array_)[length_])
 346 { return hb_sorted_array_t<T> (array_); }
 347
 348 template <typename T>
 349 bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const
 350 {
 351   if (o.length != this->length) return false;
 352   for (unsigned int i = 0; i < this->length; i++) {
 353     if (this->arrayZ[i] != o.arrayZ[i]) return false;
 354   }
 355   return true;
 356 }
 357
 358 /* TODO Specialize opeator== for hb_bytes_t and hb_ubytes_t. */
 359
 360 template <>
 361 inline uint32_t hb_array_t<const char>::hash () const {
 362   uint32_t current = 0;
 363   for (unsigned int i = 0; i < this->length; i++)
 364     current = current * 31 + (uint32_t) (this->arrayZ[i] * 2654435761u);
 365   return current;
 366 }
 367
 368 template <>
 369 inline uint32_t hb_array_t<const unsigned char>::hash () const {
 370   uint32_t current = 0;
 371   for (unsigned int i = 0; i < this->length; i++)
 372     current = current * 31 + (uint32_t) (this->arrayZ[i] * 2654435761u);
 373   return current;
 374 }
 375
 376
 377 typedef hb_array_t<const char> hb_bytes_t;
 378 typedef hb_array_t<const unsigned char> hb_ubytes_t;
 379
 380
 381
 382 #endif /* HB_ARRAY_HH */