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_NO_COPY_ASSIGN_TEMPLATE (hb_vector_t, Type); 42 hb_vector_t () { init (); } 43 ~hb_vector_t () { fini (); } 44 45 unsigned int length; 46 private: 47 int allocated; /* == -1 means allocation failed. */ 48 Type *arrayZ_; 49 public: 50 51 void init () 52 { 53 allocated = length = 0; 54 arrayZ_ = nullptr; 55 } 56 57 void fini () 58 { 59 if (arrayZ_) 60 free (arrayZ_); 61 init (); 62 } 63 void fini_deep () 64 { 65 Type *array = arrayZ(); 66 unsigned int count = length; 67 for (unsigned int i = 0; i < count; i++) 68 array[i].fini (); 69 fini (); 70 } 71 72 const Type * arrayZ () const { return arrayZ_; } 73 Type * arrayZ () { return arrayZ_; } 74 75 Type& operator [] (int i_) 76 { 77 unsigned int i = (unsigned int) i_; 78 if (unlikely (i >= length)) 79 return Crap (Type); 80 return arrayZ()[i]; 81 } 82 const Type& operator [] (int i_) const 83 { 84 unsigned int i = (unsigned int) i_; 85 if (unlikely (i >= length)) 86 return Null(Type); 87 return arrayZ()[i]; 88 } 89 90 explicit_operator bool () const { return length; } 91 92 hb_array_t<Type> as_array () 93 { return hb_array (arrayZ(), length); } 94 hb_array_t<const Type> as_array () const 95 { return hb_array (arrayZ(), length); } 96 97 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const 98 { return as_array ().sub_array (start_offset, count);} 99 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);} 101 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) 102 { return as_array ().sub_array (start_offset, count);} 103 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 106 hb_sorted_array_t<Type> as_sorted_array () 107 { return hb_sorted_array (arrayZ(), length); } 108 hb_sorted_array_t<const Type> as_sorted_array () const 109 { return hb_sorted_array (arrayZ(), length); } 110 111 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);} 113 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);} 115 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);} 117 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(); } 122 operator hb_array_t<Type> () { return as_array (); } 123 operator hb_array_t<const Type> () const { return as_array (); } 124 125 Type * operator + (unsigned int i) { return arrayZ() + i; } 126 const Type * operator + (unsigned int i) const { return arrayZ() + i; } 127 128 Type *push () 129 { 130 if (unlikely (!resize (length + 1))) 131 return &Crap(Type); 132 return &arrayZ()[length - 1]; 133 } 134 Type *push (const Type& v) 135 { 136 Type *p = push (); 137 *p = v; 138 return p; 139 } 140 141 bool in_error () const { return allocated < 0; } 142 143 /* Allocate for size but don't adjust length. */ 144 bool alloc (unsigned int size) 145 { 146 if (unlikely (allocated < 0)) 147 return false; 148 149 if (likely (size <= (unsigned) 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 bool overflows = 160 (int) new_allocated < 0 || 161 (new_allocated < (unsigned) allocated) || 162 hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); 163 if (likely (!overflows)) 164 new_array = (Type *) realloc (arrayZ_, new_allocated * sizeof (Type)); 165 166 if (unlikely (!new_array)) 167 { 168 allocated = -1; 169 return false; 170 } 171 172 arrayZ_ = new_array; 173 allocated = new_allocated; 174 175 return true; 176 } 177 178 bool resize (int size_) 179 { 180 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 181 if (!alloc (size)) 182 return false; 183 184 if (size > length) 185 memset (arrayZ() + length, 0, (size - length) * sizeof (*arrayZ())); 186 187 length = size; 188 return true; 189 } 190 191 void pop () 192 { 193 if (!length) return; 194 length--; 195 } 196 197 void remove (unsigned int i) 198 { 199 if (unlikely (i >= length)) 200 return; 201 Type *array = arrayZ(); 202 memmove (static_cast<void *> (&array[i]), 203 static_cast<void *> (&array[i + 1]), 204 (length - i - 1) * sizeof (Type)); 205 length--; 206 } 207 208 void shrink (int size_) 209 { 210 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; 211 if (size < length) 212 length = size; 213 } 214 215 template <typename T> 216 Type *find (T v) 217 { 218 Type *array = arrayZ(); 219 for (unsigned int i = 0; i < length; i++) 220 if (array[i] == v) 221 return &array[i]; 222 return nullptr; 223 } 224 template <typename T> 225 const Type *find (T v) const 226 { 227 const Type *array = arrayZ(); 228 for (unsigned int i = 0; i < length; i++) 229 if (array[i] == v) 230 return &array[i]; 231 return nullptr; 232 } 233 234 void qsort (int (*cmp)(const void*, const void*)) 235 { as_array ().qsort (cmp); } 236 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1) 237 { as_array ().qsort (start, end); } 238 239 template <typename T> 240 Type *lsearch (const T &x, Type *not_found = nullptr) 241 { return as_array ().lsearch (x, not_found); } 242 template <typename T> 243 const Type *lsearch (const T &x, const Type *not_found = nullptr) const 244 { return as_array ().lsearch (x, not_found); } 245 246 template <typename T> 247 Type *bsearch (const T &x, Type *not_found = nullptr) 248 { return as_sorted_array ().bsearch (x, not_found); } 249 template <typename T> 250 const Type *bsearch (const T &x, const Type *not_found = nullptr) const 251 { return as_sorted_array ().bsearch (x, not_found); } 252 template <typename T> 253 bool bfind (const T &x, unsigned int *i = nullptr, 254 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE, 255 unsigned int to_store = (unsigned int) -1) const 256 { return as_sorted_array ().bfind (x, i, not_found, to_store); } 257 }; 258 259 260 #endif /* HB_VECTOR_HH */