hb-array.hh (15277B)
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 static constexpr bool realloc_move = true; 51 52 /* 53 * Constructors. 54 */ 55 hb_array_t () = default; 56 hb_array_t (const hb_array_t&) = default; 57 ~hb_array_t () = default; 58 hb_array_t& operator= (const hb_array_t&) = default; 59 hb_array_t& operator= (hb_array_t&&) = default; 60 61 constexpr hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {} 62 template <unsigned int length_> 63 constexpr hb_array_t (Type (&array_)[length_]) : hb_array_t (array_, length_) {} 64 65 template <typename U, 66 hb_enable_if (hb_is_cr_convertible(U, Type))> 67 constexpr hb_array_t (const hb_array_t<U> &o) : 68 hb_iter_with_fallback_t<hb_array_t, Type&> (), 69 arrayZ (o.arrayZ), length (o.length), backwards_length (o.backwards_length) {} 70 template <typename U, 71 hb_enable_if (hb_is_cr_convertible(U, Type))> 72 hb_array_t& operator = (const hb_array_t<U> &o) 73 { arrayZ = o.arrayZ; length = o.length; backwards_length = o.backwards_length; return *this; } 74 75 /* 76 * Iterator implementation. 77 */ 78 typedef Type& __item_t__; 79 static constexpr bool is_random_access_iterator = true; 80 static constexpr bool has_fast_len = true; 81 Type& __item__ () const 82 { 83 if (unlikely (!length)) return CrapOrNull (Type); 84 return *arrayZ; 85 } 86 Type& __item_at__ (unsigned i) const 87 { 88 if (unlikely (i >= length)) return CrapOrNull (Type); 89 return arrayZ[i]; 90 } 91 void __next__ () 92 { 93 if (unlikely (!length)) 94 return; 95 length--; 96 backwards_length++; 97 arrayZ++; 98 } 99 void __forward__ (unsigned n) 100 { 101 if (unlikely (n > length)) 102 n = length; 103 length -= n; 104 backwards_length += n; 105 arrayZ += n; 106 } 107 void __prev__ () 108 { 109 if (unlikely (!backwards_length)) 110 return; 111 length++; 112 backwards_length--; 113 arrayZ--; 114 } 115 void __rewind__ (unsigned n) 116 { 117 if (unlikely (n > backwards_length)) 118 n = backwards_length; 119 length += n; 120 backwards_length -= n; 121 arrayZ -= n; 122 } 123 unsigned __len__ () const { return length; } 124 /* Ouch. The operator== compares the contents of the array. For range-based for loops, 125 * it's best if we can just compare arrayZ, though comparing contents is still fast, 126 * but also would require that Type has operator==. As such, we optimize this operator 127 * for range-based for loop and just compare arrayZ and length. 128 * 129 * The above comment is outdated now because we implemented separate begin/end to 130 * objects that were using hb_array_t for range-based loop before. */ 131 bool operator != (const hb_array_t& o) const 132 { return this->arrayZ != o.arrayZ || this->length != o.length; } 133 134 /* Faster range-based for loop without bounds-check. */ 135 Type *begin () const { return arrayZ; } 136 Type *end () const { return arrayZ + length; } 137 138 139 /* Extra operators. 140 */ 141 Type * operator & () const { return arrayZ; } 142 operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, length); } 143 template <typename T> operator T * () const { return arrayZ; } 144 145 HB_INTERNAL bool operator == (const hb_array_t &o) const; 146 147 uint32_t hash () const 148 { 149 // FNV-1a hash function 150 // https://github.com/harfbuzz/harfbuzz/pull/4228 151 uint32_t current = /*cbf29ce4*/0x84222325; 152 for (auto &v : *this) 153 { 154 current = current ^ hb_hash (v); 155 current = current * 16777619; 156 } 157 return current; 158 } 159 160 /* 161 * Compare, Sort, and Search. 162 */ 163 164 /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */ 165 int cmp (const hb_array_t &a) const 166 { 167 if (length != a.length) 168 return (int) a.length - (int) length; 169 return hb_memcmp (a.arrayZ, arrayZ, get_size ()); 170 } 171 HB_INTERNAL static int cmp (const void *pa, const void *pb) 172 { 173 hb_array_t *a = (hb_array_t *) pa; 174 hb_array_t *b = (hb_array_t *) pb; 175 return b->cmp (*a); 176 } 177 178 template <typename T> 179 Type *lsearch (const T &x, Type *not_found = nullptr) 180 { 181 unsigned i; 182 return lfind (x, &i) ? &this->arrayZ[i] : not_found; 183 } 184 template <typename T> 185 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 186 { 187 unsigned i; 188 return lfind (x, &i) ? &this->arrayZ[i] : not_found; 189 } 190 template <typename T> 191 bool lfind (const T &x, unsigned *pos = nullptr, 192 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, 193 unsigned int to_store = (unsigned int) -1) const 194 { 195 for (unsigned i = 0; i < length; ++i) 196 if (hb_equal (x, this->arrayZ[i])) 197 { 198 if (pos) 199 *pos = i; 200 return true; 201 } 202 203 if (pos) 204 { 205 switch (not_found) 206 { 207 case HB_NOT_FOUND_DONT_STORE: 208 break; 209 210 case HB_NOT_FOUND_STORE: 211 *pos = to_store; 212 break; 213 214 case HB_NOT_FOUND_STORE_CLOSEST: 215 *pos = length; 216 break; 217 } 218 } 219 return false; 220 } 221 222 hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*)) 223 { 224 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), ""); 225 if (likely (length)) 226 hb_qsort (arrayZ, length, this->get_item_size (), cmp_); 227 return hb_sorted_array_t<Type> (*this); 228 } 229 hb_sorted_array_t<Type> qsort () 230 { 231 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), ""); 232 if (likely (length)) 233 hb_qsort (arrayZ, length, this->get_item_size (), Type::cmp); 234 return hb_sorted_array_t<Type> (*this); 235 } 236 237 /* 238 * Other methods. 239 */ 240 241 unsigned int get_size () const { return length * this->get_item_size (); } 242 243 /* 244 * Reverse the order of items in this array in the range [start, end). 245 */ 246 void reverse (unsigned start = 0, unsigned end = -1) 247 { 248 start = hb_min (start, length); 249 end = hb_min (end, length); 250 251 if (end < start + 2) 252 return; 253 254 unsigned stop = start + (end - start) / 2; 255 for (unsigned lhs = start, rhs = end - 1; lhs < stop; lhs++, rhs--) 256 hb_swap (arrayZ[rhs], arrayZ[lhs]); 257 } 258 259 hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const 260 { 261 if (!start_offset && !seg_count) 262 return *this; 263 264 unsigned int count = length; 265 if (unlikely (start_offset > count)) 266 count = 0; 267 else 268 count -= start_offset; 269 if (seg_count) 270 count = *seg_count = hb_min (count, *seg_count); 271 return hb_array_t (arrayZ + start_offset, count); 272 } 273 hb_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const 274 { return sub_array (start_offset, &seg_count); } 275 276 hb_array_t truncate (unsigned length) const { return sub_array (0, length); } 277 278 template <typename T, 279 unsigned P = sizeof (Type), 280 hb_enable_if (P == 1)> 281 const T *as () const 282 { return length < hb_min_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); } 283 284 template <typename T, 285 unsigned P = sizeof (Type), 286 hb_enable_if (P == 1)> 287 bool check_range (const T *p, unsigned int size = T::static_size) const 288 { 289 return arrayZ <= ((const char *) p) 290 && ((const char *) p) <= arrayZ + length 291 && (unsigned int) (arrayZ + length - (const char *) p) >= size; 292 } 293 294 template <unsigned P = sizeof (Type), 295 hb_enable_if (P == 1)> 296 bool check_end (const void *p) const 297 { 298 return (uintptr_t) (((const char *) p) - arrayZ) <= length; 299 } 300 301 /* Only call if you allocated the underlying array using hb_malloc() or similar. */ 302 void fini () 303 { hb_free ((void *) arrayZ); arrayZ = nullptr; length = 0; } 304 305 template <typename hb_serialize_context_t, 306 typename U = Type, 307 hb_enable_if (!(sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>)))> 308 hb_array_t copy (hb_serialize_context_t *c) const 309 { 310 TRACE_SERIALIZE (this); 311 auto* out = c->start_embed (arrayZ); 312 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ()); 313 for (unsigned i = 0; i < length; i++) 314 out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */ 315 return_trace (hb_array_t (out, length)); 316 } 317 318 template <typename hb_serialize_context_t, 319 typename U = Type, 320 hb_enable_if (sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>))> 321 hb_array_t copy (hb_serialize_context_t *c) const 322 { 323 TRACE_SERIALIZE (this); 324 auto* out = c->start_embed (arrayZ); 325 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ()); 326 hb_memcpy (out, arrayZ, get_size ()); 327 return_trace (hb_array_t (out, length)); 328 } 329 330 template <typename hb_sanitize_context_t> 331 bool sanitize (hb_sanitize_context_t *c) const 332 { return c->check_array (arrayZ, length); } 333 334 /* 335 * Members 336 */ 337 338 public: 339 Type *arrayZ = nullptr; 340 unsigned int length = 0; 341 unsigned int backwards_length = 0; 342 }; 343 template <typename T> inline hb_array_t<T> 344 hb_array () 345 { return hb_array_t<T> (); } 346 template <typename T> inline hb_array_t<T> 347 hb_array (T *array, unsigned int length) 348 { return hb_array_t<T> (array, length); } 349 template <typename T, unsigned int length_> inline hb_array_t<T> 350 hb_array (T (&array_)[length_]) 351 { return hb_array_t<T> (array_); } 352 353 template <typename Type> 354 struct hb_sorted_array_t : 355 hb_array_t<Type>, 356 hb_iter_t<hb_sorted_array_t<Type>, Type&> 357 { 358 typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t; 359 HB_ITER_USING (iter_base_t); 360 static constexpr bool is_random_access_iterator = true; 361 static constexpr bool is_sorted_iterator = true; 362 static constexpr bool has_fast_len = true; 363 364 hb_sorted_array_t () = default; 365 hb_sorted_array_t (const hb_sorted_array_t&) = default; 366 ~hb_sorted_array_t () = default; 367 hb_sorted_array_t& operator= (const hb_sorted_array_t&) = default; 368 hb_sorted_array_t& operator= (hb_sorted_array_t&&) = default; 369 370 constexpr hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {} 371 template <unsigned int length_> 372 constexpr hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {} 373 374 template <typename U, 375 hb_enable_if (hb_is_cr_convertible(U, Type))> 376 constexpr hb_sorted_array_t (const hb_array_t<U> &o) : 377 hb_array_t<Type> (o), 378 hb_iter_t<hb_sorted_array_t, Type&> () {} 379 template <typename U, 380 hb_enable_if (hb_is_cr_convertible(U, Type))> 381 hb_sorted_array_t& operator = (const hb_array_t<U> &o) 382 { hb_array_t<Type> (*this) = o; return *this; } 383 384 /* Iterator implementation. */ 385 386 /* See comment in hb_array_of::operator != */ 387 bool operator != (const hb_sorted_array_t& o) const 388 { return this->arrayZ != o.arrayZ || this->length != o.length; } 389 390 /* Faster range-based for loop without bounds-check. */ 391 Type *begin () const { return this->arrayZ; } 392 Type *end () const { return this->arrayZ + this->length; } 393 394 395 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const 396 { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); } 397 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const 398 { return sub_array (start_offset, &seg_count); } 399 400 hb_sorted_array_t truncate (unsigned length) const { return sub_array (0, length); } 401 402 template <typename T> 403 Type *bsearch (const T &x, Type *not_found = nullptr) 404 { 405 unsigned int i; 406 return bfind (x, &i) ? &this->arrayZ[i] : not_found; 407 } 408 template <typename T> 409 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 410 { 411 unsigned int i; 412 return bfind (x, &i) ? &this->arrayZ[i] : not_found; 413 } 414 template <typename T> 415 bool bfind (const T &x, unsigned int *i = nullptr, 416 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, 417 unsigned int to_store = (unsigned int) -1) const 418 { 419 unsigned pos; 420 421 if (bsearch_impl (x, &pos)) 422 { 423 if (i) 424 *i = pos; 425 return true; 426 } 427 428 if (i) 429 { 430 switch (not_found) 431 { 432 case HB_NOT_FOUND_DONT_STORE: 433 break; 434 435 case HB_NOT_FOUND_STORE: 436 *i = to_store; 437 break; 438 439 case HB_NOT_FOUND_STORE_CLOSEST: 440 *i = pos; 441 break; 442 } 443 } 444 return false; 445 } 446 template <typename T, typename ...Ts> 447 bool bsearch_impl (const T &x, unsigned *pos, Ts... ds) const 448 { 449 return hb_bsearch_impl (pos, 450 x, 451 this->arrayZ, 452 this->length, 453 sizeof (Type), 454 _hb_cmp_method<T, Type, Ts...>, 455 std::forward<Ts> (ds)...); 456 } 457 }; 458 template <typename T> inline hb_sorted_array_t<T> 459 hb_sorted_array (T *array, unsigned int length) 460 { return hb_sorted_array_t<T> (array, length); } 461 template <typename T, unsigned int length_> inline hb_sorted_array_t<T> 462 hb_sorted_array (T (&array_)[length_]) 463 { return hb_sorted_array_t<T> (array_); } 464 465 template <typename T> 466 inline bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const 467 { 468 if (o.length != this->length) return false; 469 for (unsigned int i = 0; i < this->length; i++) { 470 if (this->arrayZ[i] != o.arrayZ[i]) return false; 471 } 472 return true; 473 } 474 template <> 475 inline bool hb_array_t<const char>::operator == (const hb_array_t<const char> &o) const 476 { 477 if (o.length != this->length) return false; 478 return 0 == hb_memcmp (arrayZ, o.arrayZ, length); 479 } 480 template <> 481 inline bool hb_array_t<const unsigned char>::operator == (const hb_array_t<const unsigned char> &o) const 482 { 483 if (o.length != this->length) return false; 484 return 0 == hb_memcmp (arrayZ, o.arrayZ, length); 485 } 486 487 488 /* Specialize hash() for byte arrays. */ 489 490 #ifndef HB_OPTIMIZE_SIZE_MORE 491 template <> 492 inline uint32_t hb_array_t<const char>::hash () const 493 { 494 // https://github.com/harfbuzz/harfbuzz/pull/4228 495 return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */); 496 } 497 498 template <> 499 inline uint32_t hb_array_t<const unsigned char>::hash () const 500 { 501 // https://github.com/harfbuzz/harfbuzz/pull/4228 502 return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */); 503 } 504 #endif 505 506 507 typedef hb_array_t<const char> hb_bytes_t; 508 typedef hb_array_t<const unsigned char> hb_ubytes_t; 509 510 511 512 #endif /* HB_ARRAY_HH */