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 36 template <typename Type, 37 bool sorted=false> 38 struct hb_vector_t 39 { 40 static constexpr bool realloc_move = true; 41 42 typedef Type item_t; 43 static constexpr unsigned item_size = hb_static_size (Type); 44 using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type; 45 using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type; 46 47 hb_vector_t () = default; hb_vector_thb_vector_t48 hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t () 49 { 50 alloc (lst.size (), true); 51 for (auto&& item : lst) 52 push (item); 53 } 54 template <typename Iterable, 55 hb_requires (hb_is_iterable (Iterable))> hb_vector_thb_vector_t56 hb_vector_t (const Iterable &o) : hb_vector_t () 57 { 58 auto iter = hb_iter (o); 59 if (iter.is_random_access_iterator || iter.has_fast_len) 60 alloc (hb_len (iter), true); 61 hb_copy (iter, *this); 62 } hb_vector_thb_vector_t63 hb_vector_t (const hb_vector_t &o) : hb_vector_t () 64 { 65 alloc (o.length, true); 66 if (unlikely (in_error ())) return; 67 copy_array (o.as_array ()); 68 } hb_vector_thb_vector_t69 hb_vector_t (array_t o) : hb_vector_t () 70 { 71 alloc (o.length, true); 72 if (unlikely (in_error ())) return; 73 copy_array (o); 74 } hb_vector_thb_vector_t75 hb_vector_t (c_array_t o) : hb_vector_t () 76 { 77 alloc (o.length, true); 78 if (unlikely (in_error ())) return; 79 copy_array (o); 80 } hb_vector_thb_vector_t81 hb_vector_t (hb_vector_t &&o) noexcept 82 { 83 allocated = o.allocated; 84 length = o.length; 85 arrayZ = o.arrayZ; 86 o.init (); 87 } ~hb_vector_thb_vector_t88 ~hb_vector_t () { fini (); } 89 90 public: 91 int allocated = 0; /* < 0 means allocation failed. */ 92 unsigned int length = 0; 93 public: 94 Type *arrayZ = nullptr; 95 inithb_vector_t96 void init () 97 { 98 allocated = length = 0; 99 arrayZ = nullptr; 100 } init0hb_vector_t101 void init0 () 102 { 103 } 104 finihb_vector_t105 void fini () 106 { 107 /* We allow a hack to make the vector point to a foreign array 108 * by the user. In that case length/arrayZ are non-zero but 109 * allocated is zero. Don't free anything. */ 110 if (allocated) 111 { 112 shrink_vector (0); 113 hb_free (arrayZ); 114 } 115 init (); 116 } 117 resethb_vector_t118 void reset () 119 { 120 if (unlikely (in_error ())) 121 reset_error (); 122 resize (0); 123 } 124 swap(hb_vector_t & a,hb_vector_t & b)125 friend void swap (hb_vector_t& a, hb_vector_t& b) noexcept 126 { 127 hb_swap (a.allocated, b.allocated); 128 hb_swap (a.length, b.length); 129 hb_swap (a.arrayZ, b.arrayZ); 130 } 131 operator =hb_vector_t132 hb_vector_t& operator = (const hb_vector_t &o) 133 { 134 reset (); 135 alloc (o.length, true); 136 if (unlikely (in_error ())) return *this; 137 138 copy_array (o.as_array ()); 139 140 return *this; 141 } operator =hb_vector_t142 hb_vector_t& operator = (hb_vector_t &&o) noexcept 143 { 144 hb_swap (*this, o); 145 return *this; 146 } 147 as_byteshb_vector_t148 hb_bytes_t as_bytes () const 149 { return hb_bytes_t ((const char *) arrayZ, get_size ()); } 150 operator ==hb_vector_t151 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); } operator !=hb_vector_t152 bool operator != (const hb_vector_t &o) const { return !(*this == o); } hashhb_vector_t153 uint32_t hash () const { return as_array ().hash (); } 154 operator []hb_vector_t155 Type& operator [] (int i_) 156 { 157 unsigned int i = (unsigned int) i_; 158 if (unlikely (i >= length)) 159 return Crap (Type); 160 return arrayZ[i]; 161 } operator []hb_vector_t162 const Type& operator [] (int i_) const 163 { 164 unsigned int i = (unsigned int) i_; 165 if (unlikely (i >= length)) 166 return Null (Type); 167 return arrayZ[i]; 168 } 169 tailhb_vector_t170 Type& tail () { return (*this)[length - 1]; } tailhb_vector_t171 const Type& tail () const { return (*this)[length - 1]; } 172 operator boolhb_vector_t173 explicit operator bool () const { return length; } get_sizehb_vector_t174 unsigned get_size () const { return length * item_size; } 175 176 /* Sink interface. */ 177 template <typename T> operator <<hb_vector_t178 hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; } 179 as_arrayhb_vector_t180 array_t as_array () { return hb_array (arrayZ, length); } as_arrayhb_vector_t181 c_array_t as_array () const { return hb_array (arrayZ, length); } 182 183 /* Iterator. */ 184 typedef c_array_t iter_t; 185 typedef array_t writer_t; iterhb_vector_t186 iter_t iter () const { return as_array (); } writerhb_vector_t187 writer_t writer () { return as_array (); } operator iter_thb_vector_t188 operator iter_t () const { return iter (); } operator writer_thb_vector_t189 operator writer_t () { return writer (); } 190 191 /* Faster range-based for loop. */ beginhb_vector_t192 Type *begin () const { return arrayZ; } endhb_vector_t193 Type *end () const { return arrayZ + length; } 194 195 as_sorted_arrayhb_vector_t196 hb_sorted_array_t<Type> as_sorted_array () 197 { return hb_sorted_array (arrayZ, length); } as_sorted_arrayhb_vector_t198 hb_sorted_array_t<const Type> as_sorted_array () const 199 { return hb_sorted_array (arrayZ, length); } 200 operator T*hb_vector_t201 template <typename T> explicit operator T * () { return arrayZ; } operator const T*hb_vector_t202 template <typename T> explicit operator const T * () const { return arrayZ; } 203 operator +hb_vector_t204 Type * operator + (unsigned int i) { return arrayZ + i; } operator +hb_vector_t205 const Type * operator + (unsigned int i) const { return arrayZ + i; } 206 pushhb_vector_t207 Type *push () 208 { 209 if (unlikely (!resize (length + 1))) 210 return std::addressof (Crap (Type)); 211 return std::addressof (arrayZ[length - 1]); 212 } pushhb_vector_t213 template <typename... Args> Type *push (Args&&... args) 214 { 215 if (unlikely ((int) length >= allocated && !alloc (length + 1))) 216 // If push failed to allocate then don't copy v, since this may cause 217 // the created copy to leak memory since we won't have stored a 218 // reference to it. 219 return std::addressof (Crap (Type)); 220 221 /* Emplace. */ 222 Type *p = std::addressof (arrayZ[length++]); 223 return new (p) Type (std::forward<Args> (args)...); 224 } 225 in_errorhb_vector_t226 bool in_error () const { return allocated < 0; } set_errorhb_vector_t227 void set_error () 228 { 229 assert (allocated >= 0); 230 allocated = -allocated - 1; 231 } reset_errorhb_vector_t232 void reset_error () 233 { 234 assert (allocated < 0); 235 allocated = -(allocated + 1); 236 } 237 238 template <typename T = Type, 239 hb_enable_if (hb_is_trivially_copy_assignable(T))> 240 Type * realloc_vectorhb_vector_t241 realloc_vector (unsigned new_allocated, hb_priority<0>) 242 { 243 if (!new_allocated) 244 { 245 hb_free (arrayZ); 246 return nullptr; 247 } 248 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); 249 } 250 template <typename T = Type, 251 hb_enable_if (!hb_is_trivially_copy_assignable(T))> 252 Type * realloc_vectorhb_vector_t253 realloc_vector (unsigned new_allocated, hb_priority<0>) 254 { 255 if (!new_allocated) 256 { 257 hb_free (arrayZ); 258 return nullptr; 259 } 260 Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type)); 261 if (likely (new_array)) 262 { 263 for (unsigned i = 0; i < length; i++) 264 { 265 new (std::addressof (new_array[i])) Type (); 266 new_array[i] = std::move (arrayZ[i]); 267 arrayZ[i].~Type (); 268 } 269 hb_free (arrayZ); 270 } 271 return new_array; 272 } 273 /* Specialization for types that can be moved using realloc(). */ 274 template <typename T = Type, 275 hb_enable_if (T::realloc_move)> 276 Type * realloc_vectorhb_vector_t277 realloc_vector (unsigned new_allocated, hb_priority<1>) 278 { 279 if (!new_allocated) 280 { 281 hb_free (arrayZ); 282 return nullptr; 283 } 284 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); 285 } 286 287 template <typename T = Type, 288 hb_enable_if (hb_is_trivially_constructible(T))> 289 void grow_vectorhb_vector_t290 grow_vector (unsigned size, hb_priority<0>) 291 { 292 hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 293 length = size; 294 } 295 template <typename T = Type, 296 hb_enable_if (!hb_is_trivially_constructible(T))> 297 void grow_vectorhb_vector_t298 grow_vector (unsigned size, hb_priority<0>) 299 { 300 for (; length < size; length++) 301 new (std::addressof (arrayZ[length])) Type (); 302 } 303 /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */ 304 template <typename T = Type, 305 hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) || 306 hb_is_same (T, hb_array_t <typename T::item_t>))> 307 void grow_vectorhb_vector_t308 grow_vector (unsigned size, hb_priority<1>) 309 { 310 hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 311 length = size; 312 } 313 314 template <typename T = Type, 315 hb_enable_if (hb_is_trivially_copyable (T))> 316 void copy_arrayhb_vector_t317 copy_array (hb_array_t<const Type> other) 318 { 319 length = other.length; 320 if (!HB_OPTIMIZE_SIZE_VAL && sizeof (T) >= sizeof (long long)) 321 /* This runs faster because of alignment. */ 322 for (unsigned i = 0; i < length; i++) 323 arrayZ[i] = other.arrayZ[i]; 324 else 325 hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size); 326 } 327 template <typename T = Type, 328 hb_enable_if (!hb_is_trivially_copyable (T) && 329 std::is_copy_constructible<T>::value)> 330 void copy_arrayhb_vector_t331 copy_array (hb_array_t<const Type> other) 332 { 333 length = 0; 334 while (length < other.length) 335 { 336 length++; 337 new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]); 338 } 339 } 340 template <typename T = Type, 341 hb_enable_if (!hb_is_trivially_copyable (T) && 342 !std::is_copy_constructible<T>::value && 343 std::is_default_constructible<T>::value && 344 std::is_copy_assignable<T>::value)> 345 void copy_arrayhb_vector_t346 copy_array (hb_array_t<const Type> other) 347 { 348 length = 0; 349 while (length < other.length) 350 { 351 length++; 352 new (std::addressof (arrayZ[length - 1])) Type (); 353 arrayZ[length - 1] = other.arrayZ[length - 1]; 354 } 355 } 356 357 void shrink_vectorhb_vector_t358 shrink_vector (unsigned size) 359 { 360 assert (size <= length); 361 if (!std::is_trivially_destructible<Type>::value) 362 { 363 unsigned count = length - size; 364 Type *p = arrayZ + length - 1; 365 while (count--) 366 p--->~Type (); 367 } 368 length = size; 369 } 370 371 void shift_down_vectorhb_vector_t372 shift_down_vector (unsigned i) 373 { 374 for (; i < length; i++) 375 arrayZ[i - 1] = std::move (arrayZ[i]); 376 } 377 378 /* Allocate for size but don't adjust length. */ allochb_vector_t379 bool alloc (unsigned int size, bool exact=false) 380 { 381 if (unlikely (in_error ())) 382 return false; 383 384 unsigned int new_allocated; 385 if (exact) 386 { 387 /* If exact was specified, we allow shrinking the storage. */ 388 size = hb_max (size, length); 389 if (size <= (unsigned) allocated && 390 size >= (unsigned) allocated >> 2) 391 return true; 392 393 new_allocated = size; 394 } 395 else 396 { 397 if (likely (size <= (unsigned) allocated)) 398 return true; 399 400 new_allocated = allocated; 401 while (size > new_allocated) 402 new_allocated += (new_allocated >> 1) + 8; 403 } 404 405 406 /* Reallocate */ 407 408 bool overflows = 409 (int) in_error () || 410 (new_allocated < size) || 411 hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 412 413 if (unlikely (overflows)) 414 { 415 set_error (); 416 return false; 417 } 418 419 Type *new_array = realloc_vector (new_allocated, hb_prioritize); 420 421 if (unlikely (new_allocated && !new_array)) 422 { 423 if (new_allocated <= (unsigned) allocated) 424 return true; // shrinking failed; it's okay; happens in our fuzzer 425 426 set_error (); 427 return false; 428 } 429 430 arrayZ = new_array; 431 allocated = new_allocated; 432 433 return true; 434 } 435 resizehb_vector_t436 bool resize (int size_, bool initialize = true, bool exact = false) 437 { 438 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 439 if (!alloc (size, exact)) 440 return false; 441 442 if (size > length) 443 { 444 if (initialize) 445 grow_vector (size, hb_prioritize); 446 } 447 else if (size < length) 448 { 449 if (initialize) 450 shrink_vector (size); 451 } 452 453 length = size; 454 return true; 455 } resize_exacthb_vector_t456 bool resize_exact (int size_, bool initialize = true) 457 { 458 return resize (size_, initialize, true); 459 } 460 pophb_vector_t461 Type pop () 462 { 463 if (!length) return Null (Type); 464 Type v (std::move (arrayZ[length - 1])); 465 arrayZ[length - 1].~Type (); 466 length--; 467 return v; 468 } 469 remove_orderedhb_vector_t470 void remove_ordered (unsigned int i) 471 { 472 if (unlikely (i >= length)) 473 return; 474 shift_down_vector (i + 1); 475 arrayZ[length - 1].~Type (); 476 length--; 477 } 478 479 template <bool Sorted = sorted, 480 hb_enable_if (!Sorted)> remove_unorderedhb_vector_t481 void remove_unordered (unsigned int i) 482 { 483 if (unlikely (i >= length)) 484 return; 485 if (i != length - 1) 486 arrayZ[i] = std::move (arrayZ[length - 1]); 487 arrayZ[length - 1].~Type (); 488 length--; 489 } 490 shrinkhb_vector_t491 void shrink (int size_, bool shrink_memory = true) 492 { 493 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 494 if (size >= length) 495 return; 496 497 shrink_vector (size); 498 499 if (shrink_memory) 500 alloc (size, true); /* To force shrinking memory if needed. */ 501 } 502 503 504 /* Sorting API. */ qsorthb_vector_t505 void qsort (int (*cmp)(const void*, const void*) = Type::cmp) 506 { as_array ().qsort (cmp); } 507 508 /* Unsorted search API. */ 509 template <typename T> lsearchhb_vector_t510 Type *lsearch (const T &x, Type *not_found = nullptr) 511 { return as_array ().lsearch (x, not_found); } 512 template <typename T> lsearchhb_vector_t513 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 514 { return as_array ().lsearch (x, not_found); } 515 template <typename T> lfindhb_vector_t516 bool lfind (const T &x, unsigned *pos = nullptr) const 517 { return as_array ().lfind (x, pos); } 518 519 /* Sorted search API. */ 520 template <typename T, 521 bool Sorted=sorted, hb_enable_if (Sorted)> bsearchhb_vector_t522 Type *bsearch (const T &x, Type *not_found = nullptr) 523 { return as_array ().bsearch (x, not_found); } 524 template <typename T, 525 bool Sorted=sorted, hb_enable_if (Sorted)> bsearchhb_vector_t526 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 527 { return as_array ().bsearch (x, not_found); } 528 template <typename T, 529 bool Sorted=sorted, hb_enable_if (Sorted)> bfindhb_vector_t530 bool bfind (const T &x, unsigned int *i = nullptr, 531 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, 532 unsigned int to_store = (unsigned int) -1) const 533 { return as_array ().bfind (x, i, not_found, to_store); } 534 }; 535 536 template <typename Type> 537 using hb_sorted_vector_t = hb_vector_t<Type, true>; 538 539 #endif /* HB_VECTOR_HH */ 540