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 */