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 hb_vector_thb_vector_t41 hb_vector_t () { init (); } hb_vector_thb_vector_t42 hb_vector_t (const hb_vector_t &o) 43 { 44 init (); 45 alloc (o.length); 46 hb_copy (o, *this); 47 } hb_vector_thb_vector_t48 hb_vector_t (hb_vector_t &&o) 49 { 50 allocated = o.allocated; 51 length = o.length; 52 arrayZ = o.arrayZ; 53 o.init (); 54 } ~hb_vector_thb_vector_t55 ~hb_vector_t () { fini (); } 56 57 private: 58 int allocated; /* == -1 means allocation failed. */ 59 public: 60 unsigned int length; 61 public: 62 Type *arrayZ; 63 inithb_vector_t64 void init () 65 { 66 allocated = length = 0; 67 arrayZ = nullptr; 68 } 69 finihb_vector_t70 void fini () 71 { 72 free (arrayZ); 73 init (); 74 } fini_deephb_vector_t75 void fini_deep () 76 { 77 unsigned int count = length; 78 for (unsigned int i = 0; i < count; i++) 79 arrayZ[i].fini (); 80 fini (); 81 } 82 resethb_vector_t83 void reset () 84 { 85 if (unlikely (in_error ())) 86 allocated = length; // Big hack! 87 resize (0); 88 } 89 operator =hb_vector_t90 hb_vector_t& operator = (const hb_vector_t &o) 91 { 92 reset (); 93 alloc (o.length); 94 hb_copy (o, *this); 95 return *this; 96 } operator =hb_vector_t97 hb_vector_t& operator = (hb_vector_t &&o) 98 { 99 fini (); 100 allocated = o.allocated; 101 length = o.length; 102 arrayZ = o.arrayZ; 103 o.init (); 104 return *this; 105 } 106 as_byteshb_vector_t107 hb_bytes_t as_bytes () const 108 { return hb_bytes_t ((const char *) arrayZ, length * item_size); } 109 operator ==hb_vector_t110 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); } operator !=hb_vector_t111 bool operator != (const hb_vector_t &o) const { return !(*this == o); } hashhb_vector_t112 uint32_t hash () const { return as_array ().hash (); } 113 operator []hb_vector_t114 Type& operator [] (int i_) 115 { 116 unsigned int i = (unsigned int) i_; 117 if (unlikely (i >= length)) 118 return Crap (Type); 119 return arrayZ[i]; 120 } operator []hb_vector_t121 const Type& operator [] (int i_) const 122 { 123 unsigned int i = (unsigned int) i_; 124 if (unlikely (i >= length)) 125 return Null (Type); 126 return arrayZ[i]; 127 } 128 tailhb_vector_t129 Type& tail () { return (*this)[length - 1]; } tailhb_vector_t130 const Type& tail () const { return (*this)[length - 1]; } 131 operator boolhb_vector_t132 explicit operator bool () const { return length; } get_sizehb_vector_t133 unsigned get_size () const { return length * item_size; } 134 135 /* Sink interface. */ 136 template <typename T> operator <<hb_vector_t137 hb_vector_t& operator << (T&& v) { push (hb_forward<T> (v)); return *this; } 138 as_arrayhb_vector_t139 hb_array_t< Type> as_array () { return hb_array (arrayZ, length); } as_arrayhb_vector_t140 hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); } 141 142 /* Iterator. */ 143 typedef hb_array_t<const Type> iter_t; 144 typedef hb_array_t< Type> writer_t; iterhb_vector_t145 iter_t iter () const { return as_array (); } writerhb_vector_t146 writer_t writer () { return as_array (); } operator iter_thb_vector_t147 operator iter_t () const { return iter (); } operator writer_thb_vector_t148 operator writer_t () { return writer (); } 149 sub_arrayhb_vector_t150 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const 151 { return as_array ().sub_array (start_offset, count); } sub_arrayhb_vector_t152 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const 153 { return as_array ().sub_array (start_offset, count); } sub_arrayhb_vector_t154 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) 155 { return as_array ().sub_array (start_offset, count); } sub_arrayhb_vector_t156 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) 157 { return as_array ().sub_array (start_offset, count); } 158 as_sorted_arrayhb_vector_t159 hb_sorted_array_t<Type> as_sorted_array () 160 { return hb_sorted_array (arrayZ, length); } as_sorted_arrayhb_vector_t161 hb_sorted_array_t<const Type> as_sorted_array () const 162 { return hb_sorted_array (arrayZ, length); } 163 operator T*hb_vector_t164 template <typename T> explicit operator T * () { return arrayZ; } operator const T*hb_vector_t165 template <typename T> explicit operator const T * () const { return arrayZ; } 166 operator +hb_vector_t167 Type * operator + (unsigned int i) { return arrayZ + i; } operator +hb_vector_t168 const Type * operator + (unsigned int i) const { return arrayZ + i; } 169 pushhb_vector_t170 Type *push () 171 { 172 if (unlikely (!resize (length + 1))) 173 return &Crap (Type); 174 return &arrayZ[length - 1]; 175 } 176 template <typename T> pushhb_vector_t177 Type *push (T&& v) 178 { 179 Type *p = push (); 180 if (p == &Crap (Type)) 181 // If push failed to allocate then don't copy v, since this may cause 182 // the created copy to leak memory since we won't have stored a 183 // reference to it. 184 return p; 185 *p = hb_forward<T> (v); 186 return p; 187 } 188 in_errorhb_vector_t189 bool in_error () const { return allocated < 0; } 190 191 /* Allocate for size but don't adjust length. */ allochb_vector_t192 bool alloc (unsigned int size) 193 { 194 if (unlikely (in_error ())) 195 return false; 196 197 if (likely (size <= (unsigned) allocated)) 198 return true; 199 200 /* Reallocate */ 201 202 unsigned int new_allocated = allocated; 203 while (size >= new_allocated) 204 new_allocated += (new_allocated >> 1) + 8; 205 206 Type *new_array = nullptr; 207 bool overflows = 208 (int) in_error () || 209 (new_allocated < (unsigned) allocated) || 210 hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 211 if (likely (!overflows)) 212 new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type)); 213 214 if (unlikely (!new_array)) 215 { 216 allocated = -1; 217 return false; 218 } 219 220 arrayZ = new_array; 221 allocated = new_allocated; 222 223 return true; 224 } 225 resizehb_vector_t226 bool resize (int size_) 227 { 228 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 229 if (!alloc (size)) 230 return false; 231 232 if (size > length) 233 memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); 234 235 length = size; 236 return true; 237 } 238 pophb_vector_t239 Type pop () 240 { 241 if (!length) return Null (Type); 242 return hb_move (arrayZ[--length]); /* Does this move actually work? */ 243 } 244 removehb_vector_t245 void remove (unsigned int i) 246 { 247 if (unlikely (i >= length)) 248 return; 249 memmove (static_cast<void *> (&arrayZ[i]), 250 static_cast<void *> (&arrayZ[i + 1]), 251 (length - i - 1) * sizeof (Type)); 252 length--; 253 } 254 shrinkhb_vector_t255 void shrink (int size_) 256 { 257 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 258 if (size < length) 259 length = size; 260 } 261 262 template <typename T> findhb_vector_t263 Type *find (T v) 264 { 265 for (unsigned int i = 0; i < length; i++) 266 if (arrayZ[i] == v) 267 return &arrayZ[i]; 268 return nullptr; 269 } 270 template <typename T> findhb_vector_t271 const Type *find (T v) const 272 { 273 for (unsigned int i = 0; i < length; i++) 274 if (arrayZ[i] == v) 275 return &arrayZ[i]; 276 return nullptr; 277 } 278 qsorthb_vector_t279 void qsort (int (*cmp)(const void*, const void*)) 280 { as_array ().qsort (cmp); } qsorthb_vector_t281 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1) 282 { as_array ().qsort (start, end); } 283 284 template <typename T> lsearchhb_vector_t285 Type *lsearch (const T &x, Type *not_found = nullptr) 286 { return as_array ().lsearch (x, not_found); } 287 template <typename T> lsearchhb_vector_t288 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 289 { return as_array ().lsearch (x, not_found); } 290 template <typename T> lfindhb_vector_t291 bool lfind (const T &x, unsigned *pos = nullptr) const 292 { return as_array ().lfind (x, pos); } 293 }; 294 295 template <typename Type> 296 struct hb_sorted_vector_t : hb_vector_t<Type> 297 { as_arrayhb_sorted_vector_t298 hb_sorted_array_t< Type> as_array () { return hb_sorted_array (this->arrayZ, this->length); } as_arrayhb_sorted_vector_t299 hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); } 300 301 /* Iterator. */ 302 typedef hb_sorted_array_t<const Type> const_iter_t; 303 typedef hb_sorted_array_t< Type> iter_t; iterhb_sorted_vector_t304 const_iter_t iter () const { return as_array (); } citerhb_sorted_vector_t305 const_iter_t citer () const { return as_array (); } iterhb_sorted_vector_t306 iter_t iter () { return as_array (); } operator iter_thb_sorted_vector_t307 operator iter_t () { return iter (); } operator const_iter_thb_sorted_vector_t308 operator const_iter_t () const { return iter (); } 309 310 template <typename T> bsearchhb_sorted_vector_t311 Type *bsearch (const T &x, Type *not_found = nullptr) 312 { return as_array ().bsearch (x, not_found); } 313 template <typename T> bsearchhb_sorted_vector_t314 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 315 { return as_array ().bsearch (x, not_found); } 316 template <typename T> bfindhb_sorted_vector_t317 bool bfind (const T &x, unsigned int *i = nullptr, 318 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE, 319 unsigned int to_store = (unsigned int) -1) const 320 { return as_array ().bfind (x, i, not_found, to_store); } 321 }; 322 323 #endif /* HB_VECTOR_HH */ 324