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-null.hh" 33 34 35 template <typename Type> 36 struct hb_vector_t 37 { 38 typedef Type item_t; 39 static constexpr unsigned item_size = hb_static_size (Type); 40 41 hb_vector_t () = default; hb_vector_thb_vector_t42 hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t () 43 { 44 alloc (lst.size ()); 45 for (auto&& item : lst) 46 push (item); 47 } 48 template <typename Iterable, 49 hb_requires (hb_is_iterable (Iterable))> hb_vector_thb_vector_t50 hb_vector_t (const Iterable &o) : hb_vector_t () 51 { 52 if (hb_iter (o).is_random_access_iterator) 53 alloc (hb_len (hb_iter (o))); 54 hb_copy (o, *this); 55 } hb_vector_thb_vector_t56 hb_vector_t (const hb_vector_t &o) : hb_vector_t () 57 { 58 alloc (o.length); 59 hb_copy (o, *this); 60 } hb_vector_thb_vector_t61 hb_vector_t (hb_vector_t &&o) 62 { 63 allocated = o.allocated; 64 length = o.length; 65 arrayZ = o.arrayZ; 66 o.init (); 67 } ~hb_vector_thb_vector_t68 ~hb_vector_t () { fini (); } 69 70 private: 71 int allocated = 0; /* == -1 means allocation failed. */ 72 public: 73 unsigned int length = 0; 74 public: 75 Type *arrayZ = nullptr; 76 inithb_vector_t77 void init () 78 { 79 allocated = length = 0; 80 arrayZ = nullptr; 81 } 82 finihb_vector_t83 void fini () 84 { 85 hb_free (arrayZ); 86 init (); 87 } fini_deephb_vector_t88 void fini_deep () 89 { 90 unsigned int count = length; 91 for (unsigned int i = 0; i < count; i++) 92 arrayZ[i].fini (); 93 fini (); 94 } 95 resethb_vector_t96 void reset () 97 { 98 if (unlikely (in_error ())) 99 allocated = length; // Big hack! 100 resize (0); 101 } 102 swap(hb_vector_t & a,hb_vector_t & b)103 friend void swap (hb_vector_t& a, hb_vector_t& b) 104 { 105 hb_swap (a.allocated, b.allocated); 106 hb_swap (a.length, b.length); 107 hb_swap (a.arrayZ, b.arrayZ); 108 } 109 operator =hb_vector_t110 hb_vector_t& operator = (const hb_vector_t &o) 111 { 112 reset (); 113 alloc (o.length); 114 hb_copy (o, *this); 115 return *this; 116 } operator =hb_vector_t117 hb_vector_t& operator = (hb_vector_t &&o) 118 { 119 hb_swap (*this, o); 120 return *this; 121 } 122 as_byteshb_vector_t123 hb_bytes_t as_bytes () const 124 { return hb_bytes_t ((const char *) arrayZ, length * item_size); } 125 operator ==hb_vector_t126 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); } operator !=hb_vector_t127 bool operator != (const hb_vector_t &o) const { return !(*this == o); } hashhb_vector_t128 uint32_t hash () const { return as_array ().hash (); } 129 operator []hb_vector_t130 Type& operator [] (int i_) 131 { 132 unsigned int i = (unsigned int) i_; 133 if (unlikely (i >= length)) 134 return Crap (Type); 135 return arrayZ[i]; 136 } operator []hb_vector_t137 const Type& operator [] (int i_) const 138 { 139 unsigned int i = (unsigned int) i_; 140 if (unlikely (i >= length)) 141 return Null (Type); 142 return arrayZ[i]; 143 } 144 tailhb_vector_t145 Type& tail () { return (*this)[length - 1]; } tailhb_vector_t146 const Type& tail () const { return (*this)[length - 1]; } 147 operator boolhb_vector_t148 explicit operator bool () const { return length; } get_sizehb_vector_t149 unsigned get_size () const { return length * item_size; } 150 151 /* Sink interface. */ 152 template <typename T> operator <<hb_vector_t153 hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; } 154 as_arrayhb_vector_t155 hb_array_t< Type> as_array () { return hb_array (arrayZ, length); } as_arrayhb_vector_t156 hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); } 157 158 /* Iterator. */ 159 typedef hb_array_t<const Type> iter_t; 160 typedef hb_array_t< Type> writer_t; iterhb_vector_t161 iter_t iter () const { return as_array (); } writerhb_vector_t162 writer_t writer () { return as_array (); } operator iter_thb_vector_t163 operator iter_t () const { return iter (); } operator writer_thb_vector_t164 operator writer_t () { return writer (); } 165 sub_arrayhb_vector_t166 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const 167 { return as_array ().sub_array (start_offset, count); } sub_arrayhb_vector_t168 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const 169 { return as_array ().sub_array (start_offset, count); } sub_arrayhb_vector_t170 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) 171 { return as_array ().sub_array (start_offset, count); } sub_arrayhb_vector_t172 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) 173 { return as_array ().sub_array (start_offset, count); } 174 as_sorted_arrayhb_vector_t175 hb_sorted_array_t<Type> as_sorted_array () 176 { return hb_sorted_array (arrayZ, length); } as_sorted_arrayhb_vector_t177 hb_sorted_array_t<const Type> as_sorted_array () const 178 { return hb_sorted_array (arrayZ, length); } 179 operator T*hb_vector_t180 template <typename T> explicit operator T * () { return arrayZ; } operator const T*hb_vector_t181 template <typename T> explicit operator const T * () const { return arrayZ; } 182 operator +hb_vector_t183 Type * operator + (unsigned int i) { return arrayZ + i; } operator +hb_vector_t184 const Type * operator + (unsigned int i) const { return arrayZ + i; } 185 pushhb_vector_t186 Type *push () 187 { 188 if (unlikely (!resize (length + 1))) 189 return &Crap (Type); 190 return &arrayZ[length - 1]; 191 } 192 template <typename T> pushhb_vector_t193 Type *push (T&& v) 194 { 195 Type *p = push (); 196 if (p == &Crap (Type)) 197 // If push failed to allocate then don't copy v, since this may cause 198 // the created copy to leak memory since we won't have stored a 199 // reference to it. 200 return p; 201 *p = std::forward<T> (v); 202 return p; 203 } 204 in_errorhb_vector_t205 bool in_error () const { return allocated < 0; } 206 207 /* Allocate for size but don't adjust length. */ allochb_vector_t208 bool alloc (unsigned int size) 209 { 210 if (unlikely (in_error ())) 211 return false; 212 213 if (likely (size <= (unsigned) allocated)) 214 return true; 215 216 /* Reallocate */ 217 218 unsigned int new_allocated = allocated; 219 while (size >= new_allocated) 220 new_allocated += (new_allocated >> 1) + 8; 221 222 Type *new_array = nullptr; 223 bool overflows = 224 (int) in_error () || 225 (new_allocated < (unsigned) allocated) || 226 hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 227 if (likely (!overflows)) 228 new_array = (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); 229 230 if (unlikely (!new_array)) 231 { 232 allocated = -1; 233 return false; 234 } 235 236 arrayZ = new_array; 237 allocated = new_allocated; 238 239 return true; 240 } 241 resizehb_vector_t242 bool resize (int size_) 243 { 244 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 245 if (!alloc (size)) 246 return false; 247 248 if (size > length) 249 memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 250 251 length = size; 252 return true; 253 } 254 pophb_vector_t255 Type pop () 256 { 257 if (!length) return Null (Type); 258 return std::move (arrayZ[--length]); /* Does this move actually work? */ 259 } 260 removehb_vector_t261 void remove (unsigned int i) 262 { 263 if (unlikely (i >= length)) 264 return; 265 memmove (static_cast<void *> (&arrayZ[i]), 266 static_cast<void *> (&arrayZ[i + 1]), 267 (length - i - 1) * sizeof (Type)); 268 length--; 269 } 270 shrinkhb_vector_t271 void shrink (int size_) 272 { 273 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 274 if (size < length) 275 length = size; 276 } 277 278 template <typename T> findhb_vector_t279 Type *find (T v) 280 { 281 for (unsigned int i = 0; i < length; i++) 282 if (arrayZ[i] == v) 283 return &arrayZ[i]; 284 return nullptr; 285 } 286 template <typename T> findhb_vector_t287 const Type *find (T v) const 288 { 289 for (unsigned int i = 0; i < length; i++) 290 if (arrayZ[i] == v) 291 return &arrayZ[i]; 292 return nullptr; 293 } 294 qsorthb_vector_t295 void qsort (int (*cmp)(const void*, const void*)) 296 { as_array ().qsort (cmp); } qsorthb_vector_t297 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1) 298 { as_array ().qsort (start, end); } 299 300 template <typename T> lsearchhb_vector_t301 Type *lsearch (const T &x, Type *not_found = nullptr) 302 { return as_array ().lsearch (x, not_found); } 303 template <typename T> lsearchhb_vector_t304 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 305 { return as_array ().lsearch (x, not_found); } 306 template <typename T> lfindhb_vector_t307 bool lfind (const T &x, unsigned *pos = nullptr) const 308 { return as_array ().lfind (x, pos); } 309 }; 310 311 template <typename Type> 312 struct hb_sorted_vector_t : hb_vector_t<Type> 313 { 314 hb_sorted_vector_t () = default; 315 ~hb_sorted_vector_t () = default; 316 hb_sorted_vector_t (hb_sorted_vector_t& o) = default; 317 hb_sorted_vector_t (hb_sorted_vector_t &&o) = default; hb_sorted_vector_thb_sorted_vector_t318 hb_sorted_vector_t (std::initializer_list<Type> lst) : hb_vector_t<Type> (lst) {} 319 template <typename Iterable, 320 hb_requires (hb_is_iterable (Iterable))> hb_sorted_vector_thb_sorted_vector_t321 hb_sorted_vector_t (const Iterable &o) : hb_vector_t<Type> (o) {} 322 hb_sorted_vector_t& operator = (const hb_sorted_vector_t &o) = default; 323 hb_sorted_vector_t& operator = (hb_sorted_vector_t &&o) = default; swap(hb_sorted_vector_t & a,hb_sorted_vector_t & b)324 friend void swap (hb_sorted_vector_t& a, hb_sorted_vector_t& b) 325 { hb_swap ((hb_vector_t<Type>&) (a), (hb_vector_t<Type>&) (b)); } 326 as_arrayhb_sorted_vector_t327 hb_sorted_array_t< Type> as_array () { return hb_sorted_array (this->arrayZ, this->length); } as_arrayhb_sorted_vector_t328 hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); } 329 330 /* Iterator. */ 331 typedef hb_sorted_array_t<const Type> const_iter_t; 332 typedef hb_sorted_array_t< Type> iter_t; iterhb_sorted_vector_t333 const_iter_t iter () const { return as_array (); } citerhb_sorted_vector_t334 const_iter_t citer () const { return as_array (); } iterhb_sorted_vector_t335 iter_t iter () { return as_array (); } operator iter_thb_sorted_vector_t336 operator iter_t () { return iter (); } operator const_iter_thb_sorted_vector_t337 operator const_iter_t () const { return iter (); } 338 339 template <typename T> bsearchhb_sorted_vector_t340 Type *bsearch (const T &x, Type *not_found = nullptr) 341 { return as_array ().bsearch (x, not_found); } 342 template <typename T> bsearchhb_sorted_vector_t343 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 344 { return as_array ().bsearch (x, not_found); } 345 template <typename T> bfindhb_sorted_vector_t346 bool bfind (const T &x, unsigned int *i = nullptr, 347 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, 348 unsigned int to_store = (unsigned int) -1) const 349 { return as_array ().bfind (x, i, not_found, to_store); } 350 }; 351 352 #endif /* HB_VECTOR_HH */ 353