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 typedef Type item_t; 41 static constexpr unsigned item_size = hb_static_size (Type); 42 using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type; 43 using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type; 44 45 hb_vector_t () = default; hb_vector_thb_vector_t46 hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t () 47 { 48 alloc (lst.size ()); 49 for (auto&& item : lst) 50 push (item); 51 } 52 template <typename Iterable, 53 hb_requires (hb_is_iterable (Iterable))> hb_vector_thb_vector_t54 hb_vector_t (const Iterable &o) : hb_vector_t () 55 { 56 auto iter = hb_iter (o); 57 if (iter.is_random_access_iterator) 58 alloc (hb_len (iter)); 59 hb_copy (iter, *this); 60 } hb_vector_thb_vector_t61 hb_vector_t (const hb_vector_t &o) : hb_vector_t () 62 { 63 alloc (o.length); 64 if (unlikely (in_error ())) return; 65 copy_vector (o); 66 } hb_vector_thb_vector_t67 hb_vector_t (hb_vector_t &&o) 68 { 69 allocated = o.allocated; 70 length = o.length; 71 arrayZ = o.arrayZ; 72 o.init (); 73 } ~hb_vector_thb_vector_t74 ~hb_vector_t () { fini (); } 75 76 public: 77 int allocated = 0; /* == -1 means allocation failed. */ 78 unsigned int length = 0; 79 public: 80 Type *arrayZ = nullptr; 81 inithb_vector_t82 void init () 83 { 84 allocated = length = 0; 85 arrayZ = nullptr; 86 } init0hb_vector_t87 void init0 () 88 { 89 } 90 finihb_vector_t91 void fini () 92 { 93 shrink_vector (0); 94 hb_free (arrayZ); 95 init (); 96 } 97 resethb_vector_t98 void reset () 99 { 100 if (unlikely (in_error ())) 101 /* Big Hack! We don't know the true allocated size before 102 * an allocation failure happened. But we know it was at 103 * least as big as length. Restore it to that and continue 104 * as if error did not happen. */ 105 allocated = length; 106 resize (0); 107 } 108 swap(hb_vector_t & a,hb_vector_t & b)109 friend void swap (hb_vector_t& a, hb_vector_t& b) 110 { 111 hb_swap (a.allocated, b.allocated); 112 hb_swap (a.length, b.length); 113 hb_swap (a.arrayZ, b.arrayZ); 114 } 115 operator =hb_vector_t116 hb_vector_t& operator = (const hb_vector_t &o) 117 { 118 reset (); 119 alloc (o.length); 120 if (unlikely (in_error ())) return *this; 121 122 copy_vector (o); 123 124 return *this; 125 } operator =hb_vector_t126 hb_vector_t& operator = (hb_vector_t &&o) 127 { 128 hb_swap (*this, o); 129 return *this; 130 } 131 as_byteshb_vector_t132 hb_bytes_t as_bytes () const 133 { return hb_bytes_t ((const char *) arrayZ, get_size ()); } 134 operator ==hb_vector_t135 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); } operator !=hb_vector_t136 bool operator != (const hb_vector_t &o) const { return !(*this == o); } hashhb_vector_t137 uint32_t hash () const { return as_array ().hash (); } 138 operator []hb_vector_t139 Type& operator [] (int i_) 140 { 141 unsigned int i = (unsigned int) i_; 142 if (unlikely (i >= length)) 143 return Crap (Type); 144 return arrayZ[i]; 145 } operator []hb_vector_t146 const Type& operator [] (int i_) const 147 { 148 unsigned int i = (unsigned int) i_; 149 if (unlikely (i >= length)) 150 return Null (Type); 151 return arrayZ[i]; 152 } 153 tailhb_vector_t154 Type& tail () { return (*this)[length - 1]; } tailhb_vector_t155 const Type& tail () const { return (*this)[length - 1]; } 156 operator boolhb_vector_t157 explicit operator bool () const { return length; } get_sizehb_vector_t158 unsigned get_size () const { return length * item_size; } 159 160 /* Sink interface. */ 161 template <typename T> operator <<hb_vector_t162 hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; } 163 as_arrayhb_vector_t164 array_t as_array () { return hb_array (arrayZ, length); } as_arrayhb_vector_t165 c_array_t as_array () const { return hb_array (arrayZ, length); } 166 167 /* Iterator. */ 168 typedef c_array_t iter_t; 169 typedef array_t writer_t; iterhb_vector_t170 iter_t iter () const { return as_array (); } writerhb_vector_t171 writer_t writer () { return as_array (); } operator iter_thb_vector_t172 operator iter_t () const { return iter (); } operator writer_thb_vector_t173 operator writer_t () { return writer (); } 174 175 /* Faster range-based for loop. */ beginhb_vector_t176 Type *begin () const { return arrayZ; } endhb_vector_t177 Type *end () const { return arrayZ + length; } 178 179 as_sorted_arrayhb_vector_t180 hb_sorted_array_t<Type> as_sorted_array () 181 { return hb_sorted_array (arrayZ, length); } as_sorted_arrayhb_vector_t182 hb_sorted_array_t<const Type> as_sorted_array () const 183 { return hb_sorted_array (arrayZ, length); } 184 operator T*hb_vector_t185 template <typename T> explicit operator T * () { return arrayZ; } operator const T*hb_vector_t186 template <typename T> explicit operator const T * () const { return arrayZ; } 187 operator +hb_vector_t188 Type * operator + (unsigned int i) { return arrayZ + i; } operator +hb_vector_t189 const Type * operator + (unsigned int i) const { return arrayZ + i; } 190 pushhb_vector_t191 Type *push () 192 { 193 if (unlikely (!resize (length + 1))) 194 return &Crap (Type); 195 return std::addressof (arrayZ[length - 1]); 196 } 197 template <typename T, 198 typename T2 = Type, 199 hb_enable_if (!std::is_copy_constructible<T2>::value && 200 std::is_copy_assignable<T>::value)> pushhb_vector_t201 Type *push (T&& v) 202 { 203 Type *p = push (); 204 if (p == &Crap (Type)) 205 // If push failed to allocate then don't copy v, since this may cause 206 // the created copy to leak memory since we won't have stored a 207 // reference to it. 208 return p; 209 *p = std::forward<T> (v); 210 return p; 211 } 212 template <typename T, 213 typename T2 = Type, 214 hb_enable_if (std::is_copy_constructible<T2>::value)> pushhb_vector_t215 Type *push (T&& v) 216 { 217 if (unlikely (!alloc (length + 1))) 218 // If push failed to allocate then don't copy v, since this may cause 219 // the created copy to leak memory since we won't have stored a 220 // reference to it. 221 return &Crap (Type); 222 223 /* Emplace. */ 224 length++; 225 Type *p = std::addressof (arrayZ[length - 1]); 226 return new (p) Type (std::forward<T> (v)); 227 } 228 in_errorhb_vector_t229 bool in_error () const { return allocated < 0; } 230 231 template <typename T = Type, 232 hb_enable_if (hb_is_trivially_copy_assignable(T))> 233 Type * realloc_vectorhb_vector_t234 realloc_vector (unsigned new_allocated) 235 { 236 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); 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) 242 { 243 Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type)); 244 if (likely (new_array)) 245 { 246 for (unsigned i = 0; i < length; i++) 247 { 248 new (std::addressof (new_array[i])) Type (); 249 new_array[i] = std::move (arrayZ[i]); 250 arrayZ[i].~Type (); 251 } 252 hb_free (arrayZ); 253 } 254 return new_array; 255 } 256 257 template <typename T = Type, 258 hb_enable_if (hb_is_trivially_constructible(T))> 259 void grow_vectorhb_vector_t260 grow_vector (unsigned size) 261 { 262 memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 263 length = size; 264 } 265 template <typename T = Type, 266 hb_enable_if (!hb_is_trivially_constructible(T))> 267 void grow_vectorhb_vector_t268 grow_vector (unsigned size) 269 { 270 while (length < size) 271 { 272 length++; 273 new (std::addressof (arrayZ[length - 1])) Type (); 274 } 275 } 276 277 template <typename T = Type, 278 hb_enable_if (hb_is_trivially_copyable (T))> 279 void copy_vectorhb_vector_t280 copy_vector (const hb_vector_t &other) 281 { 282 length = other.length; 283 #ifndef HB_OPTIMIZE_SIZE 284 if (sizeof (T) >= sizeof (long long)) 285 /* This runs faster because of alignment. */ 286 for (unsigned i = 0; i < length; i++) 287 arrayZ[i] = other.arrayZ[i]; 288 else 289 #endif 290 hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size); 291 } 292 template <typename T = Type, 293 hb_enable_if (!hb_is_trivially_copyable (T) && 294 std::is_copy_constructible<T>::value)> 295 void copy_vectorhb_vector_t296 copy_vector (const hb_vector_t &other) 297 { 298 length = 0; 299 while (length < other.length) 300 { 301 length++; 302 new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]); 303 } 304 } 305 template <typename T = Type, 306 hb_enable_if (!hb_is_trivially_copyable (T) && 307 !std::is_copy_constructible<T>::value && 308 std::is_default_constructible<T>::value && 309 std::is_copy_assignable<T>::value)> 310 void copy_vectorhb_vector_t311 copy_vector (const hb_vector_t &other) 312 { 313 length = 0; 314 while (length < other.length) 315 { 316 length++; 317 new (std::addressof (arrayZ[length - 1])) Type (); 318 arrayZ[length - 1] = other.arrayZ[length - 1]; 319 } 320 } 321 322 void shrink_vectorhb_vector_t323 shrink_vector (unsigned size) 324 { 325 while ((unsigned) length > size) 326 { 327 arrayZ[(unsigned) length - 1].~Type (); 328 length--; 329 } 330 } 331 332 void shift_down_vectorhb_vector_t333 shift_down_vector (unsigned i) 334 { 335 for (; i < length; i++) 336 arrayZ[i - 1] = std::move (arrayZ[i]); 337 } 338 339 /* Allocate for size but don't adjust length. */ allochb_vector_t340 bool alloc (unsigned int size) 341 { 342 if (unlikely (in_error ())) 343 return false; 344 345 if (likely (size <= (unsigned) allocated)) 346 return true; 347 348 /* Reallocate */ 349 350 unsigned int new_allocated = allocated; 351 while (size >= new_allocated) 352 new_allocated += (new_allocated >> 1) + 8; 353 354 Type *new_array = nullptr; 355 bool overflows = 356 (int) in_error () || 357 (new_allocated < (unsigned) allocated) || 358 hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 359 if (likely (!overflows)) 360 new_array = realloc_vector (new_allocated); 361 362 if (unlikely (!new_array)) 363 { 364 allocated = -1; 365 return false; 366 } 367 368 arrayZ = new_array; 369 allocated = new_allocated; 370 371 return true; 372 } 373 resizehb_vector_t374 bool resize (int size_, bool initialize = true) 375 { 376 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 377 if (!alloc (size)) 378 return false; 379 380 if (size > length) 381 { 382 if (initialize) 383 grow_vector (size); 384 } 385 else if (size < length) 386 { 387 if (initialize) 388 shrink_vector (size); 389 } 390 391 length = size; 392 return true; 393 } 394 pophb_vector_t395 Type pop () 396 { 397 if (!length) return Null (Type); 398 Type v {std::move (arrayZ[length - 1])}; 399 arrayZ[length - 1].~Type (); 400 length--; 401 return v; 402 } 403 remove_orderedhb_vector_t404 void remove_ordered (unsigned int i) 405 { 406 if (unlikely (i >= length)) 407 return; 408 shift_down_vector (i + 1); 409 arrayZ[length - 1].~Type (); 410 length--; 411 } 412 413 template <bool Sorted = sorted, 414 hb_enable_if (!Sorted)> remove_unorderedhb_vector_t415 void remove_unordered (unsigned int i) 416 { 417 if (unlikely (i >= length)) 418 return; 419 if (i != length - 1) 420 arrayZ[i] = std::move (arrayZ[length - 1]); 421 arrayZ[length - 1].~Type (); 422 length--; 423 } 424 shrinkhb_vector_t425 void shrink (int size_) 426 { 427 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 428 if (size >= length) 429 return; 430 431 shrink_vector (size); 432 } 433 434 435 /* Sorting API. */ qsorthb_vector_t436 void qsort (int (*cmp)(const void*, const void*) = Type::cmp) 437 { as_array ().qsort (cmp); } 438 439 /* Unsorted search API. */ 440 template <typename T> lsearchhb_vector_t441 Type *lsearch (const T &x, Type *not_found = nullptr) 442 { return as_array ().lsearch (x, not_found); } 443 template <typename T> lsearchhb_vector_t444 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 445 { return as_array ().lsearch (x, not_found); } 446 template <typename T> lfindhb_vector_t447 bool lfind (const T &x, unsigned *pos = nullptr) const 448 { return as_array ().lfind (x, pos); } 449 450 /* Sorted search API. */ 451 template <typename T, 452 bool Sorted=sorted, hb_enable_if (Sorted)> bsearchhb_vector_t453 Type *bsearch (const T &x, Type *not_found = nullptr) 454 { return as_array ().bsearch (x, not_found); } 455 template <typename T, 456 bool Sorted=sorted, hb_enable_if (Sorted)> bsearchhb_vector_t457 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 458 { return as_array ().bsearch (x, not_found); } 459 template <typename T, 460 bool Sorted=sorted, hb_enable_if (Sorted)> bfindhb_vector_t461 bool bfind (const T &x, unsigned int *i = nullptr, 462 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, 463 unsigned int to_store = (unsigned int) -1) const 464 { return as_array ().bfind (x, i, not_found, to_store); } 465 }; 466 467 template <typename Type> 468 using hb_sorted_vector_t = hb_vector_t<Type, true>; 469 470 #endif /* HB_VECTOR_HH */ 471