hb-vector.hh (18675B)
1 /* 2 * Copyright © 2017,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_VECTOR_HH 28 #define HB_VECTOR_HH 29 30 #include "hb.hh" 31 #include "hb-array.hh" 32 #include "hb-meta.hh" 33 #include "hb-null.hh" 34 35 // Change to 1 to force inline vector allocs, to see callsite in malloc-stats tool. 36 #if 0 37 #define HB_ALWAYS_INLINE_VECTOR_ALLOCS HB_ALWAYS_INLINE 38 #else 39 #define HB_ALWAYS_INLINE_VECTOR_ALLOCS 40 #endif 41 42 template <typename Type, 43 bool sorted=false> 44 struct hb_vector_t 45 { 46 static constexpr bool realloc_move = true; 47 48 typedef Type item_t; 49 static constexpr unsigned item_size = hb_static_size (Type); 50 using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type; 51 using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type; 52 53 hb_vector_t () = default; 54 HB_ALWAYS_INLINE_VECTOR_ALLOCS 55 hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t () 56 { 57 alloc (lst.size (), true); 58 for (auto&& item : lst) 59 push (item); 60 } 61 template <typename Iterable, 62 hb_requires (hb_is_iterable (Iterable))> 63 explicit hb_vector_t (const Iterable &o) : hb_vector_t () 64 { 65 extend (o); 66 } 67 HB_ALWAYS_INLINE_VECTOR_ALLOCS 68 hb_vector_t (const hb_vector_t &o) : hb_vector_t () 69 { 70 alloc_exact (o.length); 71 if (unlikely (in_error ())) return; 72 copy_array (o.as_array ()); 73 } 74 HB_ALWAYS_INLINE_VECTOR_ALLOCS 75 hb_vector_t (array_t o) : hb_vector_t () 76 { 77 alloc_exact (o.length); 78 if (unlikely (in_error ())) return; 79 copy_array (o); 80 } 81 HB_ALWAYS_INLINE_VECTOR_ALLOCS 82 hb_vector_t (c_array_t o) : hb_vector_t () 83 { 84 alloc_exact (o.length); 85 if (unlikely (in_error ())) return; 86 copy_array (o); 87 } 88 hb_vector_t (hb_vector_t &&o) noexcept 89 { 90 allocated = o.allocated; 91 length = o.length; 92 arrayZ = o.arrayZ; 93 o.init (); 94 } 95 ~hb_vector_t () { fini (); } 96 97 template <unsigned n> 98 void 99 set_storage (Type (&array)[n]) 100 { set_storage (array, n); } 101 void 102 set_storage (hb_array_t<Type> array) 103 { set_storage (array.arrayZ, array.length); } 104 template <typename T = Type, 105 hb_enable_if (hb_is_trivially_constructible(T) && 106 hb_is_trivially_destructible(T))> 107 void 108 set_storage (Type *array, unsigned n) 109 { 110 assert (allocated == 0); 111 assert (length == 0); 112 113 arrayZ = array; 114 length = n; 115 } 116 117 template <typename Iterable, 118 hb_requires (hb_is_iterable (Iterable))> 119 HB_ALWAYS_INLINE_VECTOR_ALLOCS 120 void extend (const Iterable &o) 121 { 122 auto iter = hb_iter (o); 123 if (iter.is_random_access_iterator || iter.has_fast_len) 124 { 125 if (unlikely (!alloc (hb_len (iter), true))) 126 return; 127 unsigned count = hb_len (iter); 128 for (unsigned i = 0; i < count; i++) 129 push_has_room (*iter++); 130 } 131 while (iter) 132 { 133 if (unlikely (!alloc (length + 1))) 134 return; 135 unsigned room = allocated - length; 136 for (unsigned i = 0; i < room && iter; i++) 137 push_has_room (*iter++); 138 } 139 } 140 HB_ALWAYS_INLINE_VECTOR_ALLOCS 141 void extend (array_t o) 142 { 143 alloc (length + o.length); 144 if (unlikely (in_error ())) return; 145 copy_array (o); 146 } 147 HB_ALWAYS_INLINE_VECTOR_ALLOCS 148 void extend (c_array_t o) 149 { 150 alloc (length + o.length); 151 if (unlikely (in_error ())) return; 152 copy_array (o); 153 } 154 155 public: 156 int allocated = 0; /* < 0 means allocation failed. */ 157 unsigned int length = 0; 158 public: 159 Type *arrayZ = nullptr; 160 161 void init () 162 { 163 allocated = length = 0; 164 arrayZ = nullptr; 165 } 166 void init0 () 167 { 168 } 169 170 void fini () 171 { 172 if (is_owned ()) 173 { 174 shrink_vector (0); 175 hb_free (arrayZ); 176 } 177 init (); 178 } 179 180 HB_ALWAYS_INLINE_VECTOR_ALLOCS 181 hb_vector_t &reset () 182 { 183 if (unlikely (in_error ())) 184 reset_error (); 185 resize (0); 186 return *this; 187 } 188 189 friend void swap (hb_vector_t& a, hb_vector_t& b) noexcept 190 { 191 hb_swap (a.allocated, b.allocated); 192 hb_swap (a.length, b.length); 193 hb_swap (a.arrayZ, b.arrayZ); 194 } 195 196 hb_vector_t& operator = (const hb_vector_t &o) 197 { 198 reset (); 199 alloc_exact (o.length); 200 if (unlikely (in_error ())) return *this; 201 202 length = 0; 203 copy_array (o.as_array ()); 204 205 return *this; 206 } 207 hb_vector_t& operator = (hb_vector_t &&o) noexcept 208 { 209 hb_swap (*this, o); 210 return *this; 211 } 212 213 hb_bytes_t as_bytes () const 214 { return hb_bytes_t ((const char *) arrayZ, get_size ()); } 215 216 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); } 217 bool operator != (const hb_vector_t &o) const { return !(*this == o); } 218 uint32_t hash () const { return as_array ().hash (); } 219 220 Type& operator [] (int i_) 221 { 222 unsigned int i = (unsigned int) i_; 223 if (unlikely (i >= length)) 224 return Crap (Type); 225 return arrayZ[i]; 226 } 227 const Type& operator [] (int i_) const 228 { 229 unsigned int i = (unsigned int) i_; 230 if (unlikely (i >= length)) 231 return Null (Type); 232 return arrayZ[i]; 233 } 234 235 Type& tail () { return (*this)[length - 1]; } 236 const Type& tail () const { return (*this)[length - 1]; } 237 238 explicit operator bool () const { return length; } 239 unsigned get_size () const { return length * item_size; } 240 241 /* Sink interface. */ 242 template <typename T> 243 hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; } 244 245 array_t as_array () { return hb_array (arrayZ, length); } 246 c_array_t as_array () const { return hb_array (arrayZ, length); } 247 248 /* Iterator. */ 249 typedef c_array_t iter_t; 250 typedef array_t writer_t; 251 iter_t iter () const { return as_array (); } 252 writer_t writer () { return as_array (); } 253 operator iter_t () const { return iter (); } 254 operator writer_t () { return writer (); } 255 256 /* Faster range-based for loop. */ 257 Type *begin () const { return arrayZ; } 258 Type *end () const { return arrayZ + length; } 259 260 261 hb_sorted_array_t<Type> as_sorted_array () 262 { return hb_sorted_array (arrayZ, length); } 263 hb_sorted_array_t<const Type> as_sorted_array () const 264 { return hb_sorted_array (arrayZ, length); } 265 266 template <typename T> explicit operator T * () { return arrayZ; } 267 template <typename T> explicit operator const T * () const { return arrayZ; } 268 269 Type * operator + (unsigned int i) { return arrayZ + i; } 270 const Type * operator + (unsigned int i) const { return arrayZ + i; } 271 272 HB_ALWAYS_INLINE_VECTOR_ALLOCS 273 Type *push () 274 { 275 if (unlikely (!resize (length + 1))) 276 return std::addressof (Crap (Type)); 277 return std::addressof (arrayZ[length - 1]); 278 } 279 template <typename... Args> 280 HB_ALWAYS_INLINE_VECTOR_ALLOCS 281 Type *push (Args&&... args) 282 { 283 if (unlikely ((int) length >= allocated && !alloc (length + 1))) 284 // If push failed to allocate then don't copy v, since this may cause 285 // the created copy to leak memory since we won't have stored a 286 // reference to it. 287 return std::addressof (Crap (Type)); 288 289 return push_has_room (std::forward<Args> (args)...); 290 } 291 template <typename... Args> 292 HB_ALWAYS_INLINE_VECTOR_ALLOCS 293 Type *push_has_room (Args&&... args) 294 { 295 /* Emplace. */ 296 Type *p = std::addressof (arrayZ[length++]); 297 return new (p) Type (std::forward<Args> (args)...); 298 } 299 300 bool is_owned () const 301 { 302 return allocated != 0 && allocated != -1; 303 } 304 305 bool in_error () const { return allocated < 0; } 306 void set_error () 307 { 308 assert (allocated >= 0); 309 allocated = -allocated - 1; 310 } 311 void reset_error () 312 { 313 assert (allocated < 0); 314 allocated = -(allocated + 1); 315 } 316 void ensure_error () 317 { 318 if (!in_error ()) 319 set_error (); 320 } 321 322 Type * 323 _realloc (unsigned new_allocated) 324 { 325 if (!new_allocated) 326 { 327 if (is_owned ()) 328 hb_free (arrayZ); 329 return nullptr; 330 } 331 if (!allocated && arrayZ) 332 { 333 /* If we have a non-null arrayZ but allocated is 0, then we are 334 * reallocating from a foreign array. */ 335 Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type)); 336 if (unlikely (!new_array)) 337 return nullptr; 338 hb_memcpy ((void *) new_array, (const void *) arrayZ, length * sizeof (Type)); 339 return new_array; 340 } 341 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); 342 } 343 Type * 344 _malloc_move (unsigned new_allocated) 345 { 346 if (!new_allocated) 347 { 348 if (is_owned ()) 349 hb_free (arrayZ); 350 return nullptr; 351 } 352 Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type)); 353 if (likely (new_array)) 354 { 355 for (unsigned i = 0; i < length; i++) 356 { 357 new (std::addressof (new_array[i])) Type (); 358 new_array[i] = std::move (arrayZ[i]); 359 arrayZ[i].~Type (); 360 } 361 if (is_owned ()) 362 hb_free (arrayZ); 363 } 364 return new_array; 365 } 366 367 template <typename T = Type, 368 hb_enable_if (hb_is_trivially_copy_assignable(T))> 369 Type * 370 realloc_vector (unsigned new_allocated, hb_priority<0>) 371 { 372 return _realloc (new_allocated); 373 } 374 template <typename T = Type, 375 hb_enable_if (!hb_is_trivially_copy_assignable(T))> 376 Type * 377 realloc_vector (unsigned new_allocated, hb_priority<0>) 378 { 379 return _malloc_move (new_allocated); 380 } 381 /* Specialization for types that can be moved using realloc(). */ 382 template <typename T = Type, 383 hb_enable_if (T::realloc_move)> 384 Type * 385 realloc_vector (unsigned new_allocated, hb_priority<1>) 386 { 387 return _realloc (new_allocated); 388 } 389 390 template <typename T = Type, 391 hb_enable_if (hb_is_trivially_constructible(T))> 392 void 393 grow_vector (unsigned size, hb_priority<0>) 394 { 395 hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 396 length = size; 397 } 398 template <typename T = Type, 399 hb_enable_if (!hb_is_trivially_constructible(T))> 400 void 401 grow_vector (unsigned size, hb_priority<0>) 402 { 403 for (; length < size; length++) 404 new (std::addressof (arrayZ[length])) Type (); 405 } 406 /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */ 407 template <typename T = Type, 408 hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) || 409 hb_is_same (T, hb_array_t <typename T::item_t>))> 410 void 411 grow_vector (unsigned size, hb_priority<1>) 412 { 413 hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 414 length = size; 415 } 416 417 template <typename T = Type, 418 hb_enable_if (hb_is_trivially_copyable (T))> 419 void 420 copy_array (hb_array_t<Type> other) 421 { 422 hb_memcpy ((void *) (arrayZ + length), (const void *) other.arrayZ, other.length * item_size); 423 length += other.length; 424 } 425 template <typename T = Type, 426 hb_enable_if (hb_is_trivially_copyable (T))> 427 void 428 copy_array (hb_array_t<const Type> other) 429 { 430 hb_memcpy ((void *) (arrayZ + length), (const void *) other.arrayZ, other.length * item_size); 431 length += other.length; 432 } 433 template <typename T = Type, 434 hb_enable_if (!hb_is_trivially_copyable (T) && 435 std::is_copy_constructible<T>::value)> 436 void 437 copy_array (hb_array_t<const Type> other) 438 { 439 for (unsigned i = 0; i < other.length; i++) 440 new (std::addressof (arrayZ[length + i])) Type (other.arrayZ[i]); 441 length += other.length; 442 } 443 template <typename T = Type, 444 hb_enable_if (!hb_is_trivially_copyable (T) && 445 !std::is_copy_constructible<T>::value && 446 std::is_default_constructible<T>::value && 447 std::is_copy_assignable<T>::value)> 448 void 449 copy_array (hb_array_t<const Type> other) 450 { 451 for (unsigned i = 0; i < other.length; i++) 452 { 453 new (std::addressof (arrayZ[length + i])) Type (); 454 arrayZ[length + i] = other.arrayZ[i]; 455 } 456 length += other.length; 457 } 458 459 void 460 shrink_vector (unsigned size) 461 { 462 assert (size <= length); 463 if (!hb_is_trivially_destructible(Type)) 464 { 465 unsigned count = length - size; 466 Type *p = arrayZ + length; 467 while (count--) 468 (--p)->~Type (); 469 } 470 length = size; 471 } 472 473 void 474 shift_down_vector (unsigned i) 475 { 476 for (; i < length; i++) 477 arrayZ[i - 1] = std::move (arrayZ[i]); 478 } 479 480 /* Allocate for size but don't adjust length. */ 481 HB_ALWAYS_INLINE_VECTOR_ALLOCS 482 bool alloc (unsigned int size, bool exact=false) 483 { 484 if (unlikely (in_error ())) 485 return false; 486 487 unsigned int new_allocated; 488 if (exact) 489 { 490 /* If exact was specified, we allow shrinking the storage. */ 491 size = hb_max (size, length); 492 if (size <= (unsigned) allocated && 493 size >= (unsigned) allocated >> 2) 494 return true; 495 496 new_allocated = size; 497 } 498 else 499 { 500 if (likely (size <= (unsigned) allocated)) 501 return true; 502 503 new_allocated = allocated; 504 while (size > new_allocated) 505 new_allocated += (new_allocated >> 1) + 8; 506 } 507 508 /* Reallocate */ 509 510 bool overflows = 511 (int) in_error () || 512 (new_allocated < size) || 513 hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 514 515 if (unlikely (overflows)) 516 { 517 set_error (); 518 return false; 519 } 520 521 Type *new_array = realloc_vector (new_allocated, hb_prioritize); 522 523 if (unlikely (new_allocated && !new_array)) 524 { 525 if (new_allocated <= (unsigned) allocated) 526 return true; // shrinking failed; it's okay; happens in our fuzzer 527 528 set_error (); 529 return false; 530 } 531 532 arrayZ = new_array; 533 allocated = new_allocated; 534 535 return true; 536 } 537 HB_ALWAYS_INLINE_VECTOR_ALLOCS 538 bool alloc_exact (unsigned int size) 539 { 540 return alloc (size, true); 541 } 542 543 HB_ALWAYS_INLINE_VECTOR_ALLOCS 544 void clear () 545 { 546 resize (0); 547 } 548 549 template <typename allocator_t> 550 HB_ALWAYS_INLINE_VECTOR_ALLOCS 551 bool allocate_from_pool (allocator_t *allocator, unsigned size, unsigned int initialize = true) 552 { 553 if (allocator) 554 { 555 assert (!length && !allocated); 556 arrayZ = (Type *) allocator->alloc (size * sizeof (Type), alignof (Type)); 557 if (unlikely (!arrayZ)) 558 { 559 set_error (); 560 return false; 561 } 562 if (initialize) 563 grow_vector (size, hb_prioritize); 564 else 565 length = size; 566 return true; 567 } 568 return resize_full ((int) size, initialize, true); 569 } 570 571 template <typename allocator_t> 572 HB_ALWAYS_INLINE_VECTOR_ALLOCS 573 bool allocate_from_pool (allocator_t *allocator, const hb_vector_t &other) 574 { 575 if (unlikely (!allocate_from_pool (allocator, other.length, false))) 576 return false; 577 length = 0; 578 copy_array (other.as_array ()); 579 return true; 580 } 581 582 template <typename allocator_t> 583 void shrink_back_to_pool (allocator_t *allocator, int size) 584 { 585 unsigned orig_length = length; 586 587 shrink (size, false); 588 589 if (allocator && !is_owned ()) 590 allocator->discard (arrayZ + length, (orig_length - length) * sizeof (Type)); 591 } 592 593 HB_ALWAYS_INLINE_VECTOR_ALLOCS 594 bool resize_full (int size_, bool initialize, bool exact) 595 { 596 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 597 if (!alloc (size, exact)) 598 return false; 599 600 if (size > length) 601 { 602 if (initialize) 603 grow_vector (size, hb_prioritize); 604 } 605 else if (size < length) 606 { 607 if (initialize) 608 shrink_vector (size); 609 } 610 611 length = size; 612 return true; 613 } 614 HB_ALWAYS_INLINE_VECTOR_ALLOCS 615 bool resize (int size_) 616 { 617 return resize_full (size_, true, false); 618 } 619 HB_ALWAYS_INLINE_VECTOR_ALLOCS 620 bool resize_dirty (int size_) 621 { 622 return resize_full (size_, false, false); 623 } 624 HB_ALWAYS_INLINE_VECTOR_ALLOCS 625 bool resize_exact (int size_) 626 { 627 return resize_full (size_, true, true); 628 } 629 630 Type pop () 631 { 632 if (!length) return Null (Type); 633 Type v (std::move (arrayZ[length - 1])); 634 arrayZ[length - 1].~Type (); 635 length--; 636 return v; 637 } 638 639 void remove_ordered (unsigned int i) 640 { 641 if (unlikely (i >= length)) 642 return; 643 shift_down_vector (i + 1); 644 arrayZ[length - 1].~Type (); 645 length--; 646 } 647 648 template <bool Sorted = sorted, 649 hb_enable_if (!Sorted)> 650 void remove_unordered (unsigned int i) 651 { 652 if (unlikely (i >= length)) 653 return; 654 if (i != length - 1) 655 arrayZ[i] = std::move (arrayZ[length - 1]); 656 arrayZ[length - 1].~Type (); 657 length--; 658 } 659 660 void shrink (int size_, bool shrink_memory = true) 661 { 662 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 663 if (size >= length) 664 return; 665 666 shrink_vector (size); 667 668 if (is_owned () && shrink_memory) 669 alloc_exact (size); /* To force shrinking memory if needed. */ 670 } 671 672 673 /* Sorting API. */ 674 void qsort (int (*cmp)(const void*, const void*) = Type::cmp) 675 { as_array ().qsort (cmp); } 676 677 /* Unsorted search API. */ 678 template <typename T> 679 Type *lsearch (const T &x, Type *not_found = nullptr) 680 { return as_array ().lsearch (x, not_found); } 681 template <typename T> 682 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 683 { return as_array ().lsearch (x, not_found); } 684 template <typename T> 685 bool lfind (const T &x, unsigned *pos = nullptr) const 686 { return as_array ().lfind (x, pos); } 687 688 /* Sorted search API. */ 689 template <typename T, 690 bool Sorted=sorted, hb_enable_if (Sorted)> 691 Type *bsearch (const T &x, Type *not_found = nullptr) 692 { return as_array ().bsearch (x, not_found); } 693 template <typename T, 694 bool Sorted=sorted, hb_enable_if (Sorted)> 695 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 696 { return as_array ().bsearch (x, not_found); } 697 template <typename T, 698 bool Sorted=sorted, hb_enable_if (Sorted)> 699 bool bfind (const T &x, unsigned int *i = nullptr, 700 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, 701 unsigned int to_store = (unsigned int) -1) const 702 { return as_array ().bfind (x, i, not_found, to_store); } 703 }; 704 705 template <typename Type> 706 using hb_sorted_vector_t = hb_vector_t<Type, true>; 707 708 #endif /* HB_VECTOR_HH */