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-dsalgs.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 :
  41         hb_iter_t<hb_array_t<Type>, Type>,
  42         hb_iter_mixin_t<hb_array_t<Type>, Type>
  43 {
  44   /*
  45    * Constructors.
  46    */
  47   hb_array_t () : arrayZ (nullptr), length (0) {}
  48   hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {}
  49   template <unsigned int length_> hb_array_t (Type (&array_)[length_]) : arrayZ (array_), length (length_) {}
  50
  51
  52   /*
  53    * Iterator implementation.
  54    */
  55   typedef Type __item_type__;
  56   Type& __item_at__ (unsigned i) const
  57   {
  58     if (unlikely (i >= length)) return CrapOrNull (Type);
  59     return arrayZ[i];
  60   }
  61   void __forward__ (unsigned n)
  62   {
  63     if (unlikely (n > length))
  64       n = length;
  65     length -= n;
  66     arrayZ += n;
  67   }
  68   void __rewind__ (unsigned n)
  69   {
  70     if (unlikely (n > length))
  71       n = length;
  72     length -= n;
  73   }
  74   unsigned __len__ () const { return length; }
  75   bool __random_access__ () const { return true; }
  76
  77   /* Extra operators.
  78    */
  79   Type * operator & () const { return arrayZ; }
  80   operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, length); }
  81   template <typename T> operator T * () const { return arrayZ; }
  82
  83   /*
  84    * Compare, Sort, and Search.
  85    */
  86
  87   /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
  88   int cmp (const hb_array_t<Type> &a) const
  89   {
  90     if (length != a.length)
  91       return (int) a.length - (int) length;
  92     return hb_memcmp (a.arrayZ, arrayZ, get_size ());
  93   }
  94   static int cmp (const void *pa, const void *pb)
  95   {
  96     hb_array_t<Type> *a = (hb_array_t<Type> *) pa;
  97     hb_array_t<Type> *b = (hb_array_t<Type> *) pb;
  98     return b->cmp (*a);
  99   }
 100
 101   template <typename T>
 102   Type *lsearch (const T &x, Type *not_found = nullptr)
 103   {
 104     unsigned int count = length;
 105     for (unsigned int i = 0; i < count; i++)
 106       if (!this->arrayZ[i].cmp (x))
 107         return &this->arrayZ[i];
 108     return not_found;
 109   }
 110   template <typename T>
 111   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
 112   {
 113     unsigned int count = length;
 114     for (unsigned int i = 0; i < count; i++)
 115       if (!this->arrayZ[i].cmp (x))
 116         return &this->arrayZ[i];
 117     return not_found;
 118   }
 119
 120   hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*))
 121   {
 122     if (likely (length))
 123       ::qsort (arrayZ, length, this->item_size, cmp_);
 124     return hb_sorted_array_t<Type> (*this);
 125   }
 126   hb_sorted_array_t<Type> qsort ()
 127   {
 128     if (likely (length))
 129       ::qsort (arrayZ, length, this->item_size, Type::cmp);
 130     return hb_sorted_array_t<Type> (*this);
 131   }
 132   void qsort (unsigned int start, unsigned int end)
 133   {
 134     end = MIN (end, length);
 135     assert (start <= end);
 136     if (likely (start < end))
 137       ::qsort (arrayZ + start, end - start, this->item_size, Type::cmp);
 138   }
 139
 140   /*
 141    * Other methods.
 142    */
 143
 144   unsigned int get_size () const { return length * this->item_size; }
 145
 146   hb_array_t<Type> sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
 147   {
 148     if (!start_offset && !seg_count)
 149       return *this;
 150
 151     unsigned int count = length;
 152     if (unlikely (start_offset > count))
 153       count = 0;
 154     else
 155       count -= start_offset;
 156     if (seg_count)
 157       count = *seg_count = MIN (count, *seg_count);
 158     return hb_array_t<Type> (arrayZ + start_offset, count);
 159   }
 160   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int seg_count) const
 161   { return sub_array (start_offset, &seg_count); }
 162
 163   /* Only call if you allocated the underlying array using malloc() or similar. */
 164   void free ()
 165   { ::free ((void *) arrayZ); arrayZ = nullptr; length = 0; }
 166
 167   template <typename hb_sanitize_context_t>
 168   bool sanitize (hb_sanitize_context_t *c) const
 169   { return c->check_array (arrayZ, length); }
 170
 171   /*
 172    * Members
 173    */
 174
 175   public:
 176   Type *arrayZ;
 177   unsigned int length;
 178 };
 179 template <typename T> inline hb_array_t<T>
 180 hb_array (T *array, unsigned int length)
 181 { return hb_array_t<T> (array, length); }
 182 template <typename T, unsigned int length_> inline hb_array_t<T>
 183 hb_array (T (&array_)[length_])
 184 { return hb_array_t<T> (array_); }
 185
 186
 187 enum hb_bfind_not_found_t
 188 {
 189   HB_BFIND_NOT_FOUND_DONT_STORE,
 190   HB_BFIND_NOT_FOUND_STORE,
 191   HB_BFIND_NOT_FOUND_STORE_CLOSEST,
 192 };
 193
 194 template <typename Type>
 195 struct hb_sorted_array_t :
 196         hb_sorted_iter_t<hb_sorted_array_t<Type>, Type>,
 197         hb_array_t<Type>,
 198         hb_iter_mixin_t<hb_sorted_array_t<Type>, Type>
 199 {
 200   hb_sorted_array_t () : hb_array_t<Type> () {}
 201   hb_sorted_array_t (const hb_array_t<Type> &o) : hb_array_t<Type> (o) {}
 202   hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {}
 203   template <unsigned int length_> hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {}
 204
 205   hb_sorted_array_t<Type> sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
 206   { return hb_sorted_array_t<Type> (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
 207   hb_sorted_array_t<Type> sub_array (unsigned int start_offset, unsigned int seg_count) const
 208   { return sub_array (start_offset, &seg_count); }
 209
 210   template <typename T>
 211   Type *bsearch (const T &x, Type *not_found = nullptr)
 212   {
 213     unsigned int i;
 214     return bfind (x, &i) ? &this->arrayZ[i] : not_found;
 215   }
 216   template <typename T>
 217   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
 218   {
 219     unsigned int i;
 220     return bfind (x, &i) ? &this->arrayZ[i] : not_found;
 221   }
 222   template <typename T>
 223   bool bfind (const T &x, unsigned int *i = nullptr,
 224                      hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
 225                      unsigned int to_store = (unsigned int) -1) const
 226   {
 227     int min = 0, max = (int) this->length - 1;
 228     const Type *array = this->arrayZ;
 229     while (min <= max)
 230     {
 231       int mid = ((unsigned int) min + (unsigned int) max) / 2;
 232       int c = array[mid].cmp (x);
 233       if (c < 0)
 234         max = mid - 1;
 235       else if (c > 0)
 236         min = mid + 1;
 237       else
 238       {
 239         if (i)
 240           *i = mid;
 241         return true;
 242       }
 243     }
 244     if (i)
 245     {
 246       switch (not_found)
 247       {
 248         case HB_BFIND_NOT_FOUND_DONT_STORE:
 249           break;
 250
 251         case HB_BFIND_NOT_FOUND_STORE:
 252           *i = to_store;
 253           break;
 254
 255         case HB_BFIND_NOT_FOUND_STORE_CLOSEST:
 256           if (max < 0 || (max < (int) this->length && array[max].cmp (x) > 0))
 257             max++;
 258           *i = max;
 259           break;
 260       }
 261     }
 262     return false;
 263   }
 264 };
 265 template <typename T> inline hb_sorted_array_t<T>
 266 hb_sorted_array (T *array, unsigned int length)
 267 { return hb_sorted_array_t<T> (array, length); }
 268 template <typename T, unsigned int length_> inline hb_sorted_array_t<T>
 269 hb_sorted_array (T (&array_)[length_])
 270 { return hb_sorted_array_t<T> (array_); }
 271
 272
 273 typedef hb_array_t<const char> hb_bytes_t;
 274 typedef hb_array_t<const unsigned char> hb_ubytes_t;
 275
 276
 277 #endif /* HB_ARRAY_HH */