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 33 34 template <typename Type, unsigned int PreallocedCount=8> 35 struct hb_vector_t 36 { 37 typedef Type ItemType; 38 enum { item_size = hb_static_size (Type) }; 39 40 HB_NO_COPY_ASSIGN_TEMPLATE2 (hb_vector_t, Type, PreallocedCount); hb_vector_thb_vector_t41 hb_vector_t () { init (); } ~hb_vector_thb_vector_t42 ~hb_vector_t () { fini (); } 43 44 unsigned int len; 45 private: 46 unsigned int allocated; /* == 0 means allocation failed. */ 47 Type *arrayZ_; 48 Type static_array[PreallocedCount]; 49 public: 50 inithb_vector_t51 void init () 52 { 53 len = 0; 54 allocated = ARRAY_LENGTH (static_array); 55 arrayZ_ = nullptr; 56 } 57 finihb_vector_t58 void fini () 59 { 60 if (arrayZ_) 61 free (arrayZ_); 62 arrayZ_ = nullptr; 63 allocated = len = 0; 64 } fini_deephb_vector_t65 void fini_deep () 66 { 67 Type *array = arrayZ(); 68 unsigned int count = len; 69 for (unsigned int i = 0; i < count; i++) 70 array[i].fini (); 71 fini (); 72 } 73 arrayZhb_vector_t74 Type * arrayZ () { return arrayZ_ ? arrayZ_ : static_array; } arrayZhb_vector_t75 const Type * arrayZ () const { return arrayZ_ ? arrayZ_ : static_array; } 76 operator []hb_vector_t77 Type& operator [] (int i_) 78 { 79 unsigned int i = (unsigned int) i_; 80 if (unlikely (i >= len)) 81 return Crap (Type); 82 return arrayZ()[i]; 83 } operator []hb_vector_t84 const Type& operator [] (int i_) const 85 { 86 unsigned int i = (unsigned int) i_; 87 if (unlikely (i >= len)) 88 return Null(Type); 89 return arrayZ()[i]; 90 } 91 as_arrayhb_vector_t92 hb_array_t<Type> as_array () 93 { return hb_array (arrayZ(), len); } as_arrayhb_vector_t94 hb_array_t<const Type> as_array () const 95 { return hb_array (arrayZ(), len); } 96 sub_arrayhb_vector_t97 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const 98 { return as_array ().sub_array (start_offset, count);} sub_arrayhb_vector_t99 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const 100 { return as_array ().sub_array (start_offset, count);} sub_arrayhb_vector_t101 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) 102 { return as_array ().sub_array (start_offset, count);} sub_arrayhb_vector_t103 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) 104 { return as_array ().sub_array (start_offset, count);} 105 as_sorted_arrayhb_vector_t106 hb_sorted_array_t<Type> as_sorted_array () 107 { return hb_sorted_array (arrayZ(), len); } as_sorted_arrayhb_vector_t108 hb_sorted_array_t<const Type> as_sorted_array () const 109 { return hb_sorted_array (arrayZ(), len); } 110 sorted_sub_arrayhb_vector_t111 hb_array_t<const Type> sorted_sub_array (unsigned int start_offset, unsigned int count) const 112 { return as_sorted_array ().sorted_sub_array (start_offset, count);} sorted_sub_arrayhb_vector_t113 hb_array_t<const Type> sorted_sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const 114 { return as_sorted_array ().sorted_sub_array (start_offset, count);} sorted_sub_arrayhb_vector_t115 hb_array_t<Type> sorted_sub_array (unsigned int start_offset, unsigned int count) 116 { return as_sorted_array ().sorted_sub_array (start_offset, count);} sorted_sub_arrayhb_vector_t117 hb_array_t<Type> sorted_sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) 118 { return as_sorted_array ().sorted_sub_array (start_offset, count);} 119 120 template <typename T> explicit_operator T * () { return arrayZ(); } 121 template <typename T> explicit_operator const T * () const { return arrayZ(); } operator hb_array_t<Type>hb_vector_t122 operator hb_array_t<Type> () { return as_array (); } operator hb_array_t<const Type>hb_vector_t123 operator hb_array_t<const Type> () const { return as_array (); } 124 operator +hb_vector_t125 Type * operator + (unsigned int i) { return arrayZ() + i; } operator +hb_vector_t126 const Type * operator + (unsigned int i) const { return arrayZ() + i; } 127 pushhb_vector_t128 Type *push () 129 { 130 if (unlikely (!resize (len + 1))) 131 return &Crap(Type); 132 return &arrayZ()[len - 1]; 133 } pushhb_vector_t134 Type *push (const Type& v) 135 { 136 Type *p = push (); 137 *p = v; 138 return p; 139 } 140 in_errorhb_vector_t141 bool in_error () const { return allocated == 0; } 142 143 /* Allocate for size but don't adjust len. */ allochb_vector_t144 bool alloc (unsigned int size) 145 { 146 if (unlikely (!allocated)) 147 return false; 148 149 if (likely (size <= allocated)) 150 return true; 151 152 /* Reallocate */ 153 154 unsigned int new_allocated = allocated; 155 while (size >= new_allocated) 156 new_allocated += (new_allocated >> 1) + 8; 157 158 Type *new_array = nullptr; 159 160 if (!arrayZ_) 161 { 162 new_array = (Type *) calloc (new_allocated, sizeof (Type)); 163 if (new_array) 164 memcpy (new_array, static_array, len * sizeof (Type)); 165 } 166 else 167 { 168 bool overflows = (new_allocated < allocated) || hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 169 if (likely (!overflows)) 170 new_array = (Type *) realloc (arrayZ_, new_allocated * sizeof (Type)); 171 } 172 173 if (unlikely (!new_array)) 174 { 175 allocated = 0; 176 return false; 177 } 178 179 arrayZ_ = new_array; 180 allocated = new_allocated; 181 182 return true; 183 } 184 resizehb_vector_t185 bool resize (int size_) 186 { 187 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 188 if (!alloc (size)) 189 return false; 190 191 if (size > len) 192 memset (arrayZ() + len, 0, (size - len) * sizeof (*arrayZ())); 193 194 len = size; 195 return true; 196 } 197 pophb_vector_t198 void pop () 199 { 200 if (!len) return; 201 len--; 202 } 203 removehb_vector_t204 void remove (unsigned int i) 205 { 206 if (unlikely (i >= len)) 207 return; 208 Type *array = arrayZ(); 209 memmove (static_cast<void *> (&array[i]), 210 static_cast<void *> (&array[i + 1]), 211 (len - i - 1) * sizeof (Type)); 212 len--; 213 } 214 shrinkhb_vector_t215 void shrink (int size_) 216 { 217 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 218 if (size < len) 219 len = size; 220 } 221 222 template <typename T> findhb_vector_t223 Type *find (T v) 224 { 225 Type *array = arrayZ(); 226 for (unsigned int i = 0; i < len; i++) 227 if (array[i] == v) 228 return &array[i]; 229 return nullptr; 230 } 231 template <typename T> findhb_vector_t232 const Type *find (T v) const 233 { 234 const Type *array = arrayZ(); 235 for (unsigned int i = 0; i < len; i++) 236 if (array[i] == v) 237 return &array[i]; 238 return nullptr; 239 } 240 qsorthb_vector_t241 void qsort (int (*cmp)(const void*, const void*)) 242 { as_array ().qsort (cmp); } qsorthb_vector_t243 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1) 244 { as_array ().qsort (start, end); } 245 246 template <typename T> lsearchhb_vector_t247 Type *lsearch (const T &x, Type *not_found = nullptr) 248 { return as_array ().lsearch (x, not_found); } 249 template <typename T> lsearchhb_vector_t250 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 251 { return as_array ().lsearch (x, not_found); } 252 253 template <typename T> bsearchhb_vector_t254 Type *bsearch (const T &x, Type *not_found = nullptr) 255 { return as_sorted_array ().bsearch (x, not_found); } 256 template <typename T> bsearchhb_vector_t257 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 258 { return as_sorted_array ().bsearch (x, not_found); } 259 template <typename T> bfindhb_vector_t260 bool bfind (const T &x, unsigned int *i = nullptr, 261 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE, 262 unsigned int to_store = (unsigned int) -1) const 263 { return as_sorted_array ().bfind (x, i, not_found, to_store); } 264 }; 265 266 267 #endif /* HB_VECTOR_HH */ 268