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
36template <typename Type,
37 bool sorted=false>
38struct 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;
46 hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
47 {
48 alloc (lst.size (), true);
49 for (auto&& item : lst)
50 push (item);
51 }
52 template <typename Iterable,
53 hb_requires (hb_is_iterable (Iterable))>
54 hb_vector_t (const Iterable &o) : hb_vector_t ()
55 {
56 auto iter = hb_iter (o);
57 if (iter.is_random_access_iterator || iter.has_fast_len)
58 alloc (hb_len (iter), true);
59 hb_copy (iter, *this);
60 }
61 hb_vector_t (const hb_vector_t &o) : hb_vector_t ()
62 {
63 alloc (o.length, true);
64 if (unlikely (in_error ())) return;
65 copy_array (o.as_array ());
66 }
67 hb_vector_t (array_t o) : hb_vector_t ()
68 {
69 alloc (o.length, true);
70 if (unlikely (in_error ())) return;
71 copy_array (o);
72 }
73 hb_vector_t (c_array_t o) : hb_vector_t ()
74 {
75 alloc (o.length, true);
76 if (unlikely (in_error ())) return;
77 copy_array (o);
78 }
79 hb_vector_t (hb_vector_t &&o)
80 {
81 allocated = o.allocated;
82 length = o.length;
83 arrayZ = o.arrayZ;
84 o.init ();
85 }
86 ~hb_vector_t () { fini (); }
87
88 public:
89 int allocated = 0; /* < 0 means allocation failed. */
90 unsigned int length = 0;
91 public:
92 Type *arrayZ = nullptr;
93
94 void init ()
95 {
96 allocated = length = 0;
97 arrayZ = nullptr;
98 }
99 void init0 ()
100 {
101 }
102
103 void fini ()
104 {
105 /* We allow a hack to make the vector point to a foriegn array
106 * by the user. In that case length/arrayZ are non-zero but
107 * allocated is zero. Don't free anything. */
108 if (allocated)
109 {
110 shrink_vector (0);
111 hb_free (arrayZ);
112 }
113 init ();
114 }
115
116 void reset ()
117 {
118 if (unlikely (in_error ()))
119 reset_error ();
120 resize (0);
121 }
122
123 friend void swap (hb_vector_t& a, hb_vector_t& b)
124 {
125 hb_swap (a.allocated, b.allocated);
126 hb_swap (a.length, b.length);
127 hb_swap (a.arrayZ, b.arrayZ);
128 }
129
130 hb_vector_t& operator = (const hb_vector_t &o)
131 {
132 reset ();
133 alloc (o.length, true);
134 if (unlikely (in_error ())) return *this;
135
136 copy_array (o.as_array ());
137
138 return *this;
139 }
140 hb_vector_t& operator = (hb_vector_t &&o)
141 {
142 hb_swap (*this, o);
143 return *this;
144 }
145
146 hb_bytes_t as_bytes () const
147 { return hb_bytes_t ((const char *) arrayZ, get_size ()); }
148
149 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
150 bool operator != (const hb_vector_t &o) const { return !(*this == o); }
151 uint32_t hash () const { return as_array ().hash (); }
152
153 Type& operator [] (int i_)
154 {
155 unsigned int i = (unsigned int) i_;
156 if (unlikely (i >= length))
157 return Crap (Type);
158 return arrayZ[i];
159 }
160 const Type& operator [] (int i_) const
161 {
162 unsigned int i = (unsigned int) i_;
163 if (unlikely (i >= length))
164 return Null (Type);
165 return arrayZ[i];
166 }
167
168 Type& tail () { return (*this)[length - 1]; }
169 const Type& tail () const { return (*this)[length - 1]; }
170
171 explicit operator bool () const { return length; }
172 unsigned get_size () const { return length * item_size; }
173
174 /* Sink interface. */
175 template <typename T>
176 hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; }
177
178 array_t as_array () { return hb_array (arrayZ, length); }
179 c_array_t as_array () const { return hb_array (arrayZ, length); }
180
181 /* Iterator. */
182 typedef c_array_t iter_t;
183 typedef array_t writer_t;
184 iter_t iter () const { return as_array (); }
185 writer_t writer () { return as_array (); }
186 operator iter_t () const { return iter (); }
187 operator writer_t () { return writer (); }
188
189 /* Faster range-based for loop. */
190 Type *begin () const { return arrayZ; }
191 Type *end () const { return arrayZ + length; }
192
193
194 hb_sorted_array_t<Type> as_sorted_array ()
195 { return hb_sorted_array (arrayZ, length); }
196 hb_sorted_array_t<const Type> as_sorted_array () const
197 { return hb_sorted_array (arrayZ, length); }
198
199 template <typename T> explicit operator T * () { return arrayZ; }
200 template <typename T> explicit operator const T * () const { return arrayZ; }
201
202 Type * operator + (unsigned int i) { return arrayZ + i; }
203 const Type * operator + (unsigned int i) const { return arrayZ + i; }
204
205 Type *push ()
206 {
207 if (unlikely (!resize (length + 1)))
208 return std::addressof (Crap (Type));
209 return std::addressof (arrayZ[length - 1]);
210 }
211 template <typename T,
212 typename T2 = Type,
213 hb_enable_if (!std::is_copy_constructible<T2>::value &&
214 std::is_copy_assignable<T>::value)>
215 Type *push (T&& v)
216 {
217 Type *p = push ();
218 if (p == std::addressof (Crap (Type)))
219 // If push failed to allocate then don't copy v, since this may cause
220 // the created copy to leak memory since we won't have stored a
221 // reference to it.
222 return p;
223 *p = std::forward<T> (v);
224 return p;
225 }
226 template <typename T,
227 typename T2 = Type,
228 hb_enable_if (std::is_copy_constructible<T2>::value)>
229 Type *push (T&& v)
230 {
231 if (unlikely ((int) length >= allocated && !alloc (length + 1)))
232 // If push failed to allocate then don't copy v, since this may cause
233 // the created copy to leak memory since we won't have stored a
234 // reference to it.
235 return std::addressof (Crap (Type));
236
237 /* Emplace. */
238 Type *p = std::addressof (arrayZ[length++]);
239 return new (p) Type (std::forward<T> (v));
240 }
241
242 bool in_error () const { return allocated < 0; }
243 void set_error ()
244 {
245 assert (allocated >= 0);
246 allocated = -allocated - 1;
247 }
248 void reset_error ()
249 {
250 assert (allocated < 0);
251 allocated = -(allocated + 1);
252 }
253
254 template <typename T = Type,
255 hb_enable_if (hb_is_trivially_copy_assignable(T))>
256 Type *
257 realloc_vector (unsigned new_allocated, hb_priority<0>)
258 {
259 if (!new_allocated)
260 {
261 hb_free (arrayZ);
262 return nullptr;
263 }
264 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
265 }
266 template <typename T = Type,
267 hb_enable_if (!hb_is_trivially_copy_assignable(T))>
268 Type *
269 realloc_vector (unsigned new_allocated, hb_priority<0>)
270 {
271 if (!new_allocated)
272 {
273 hb_free (arrayZ);
274 return nullptr;
275 }
276 Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type));
277 if (likely (new_array))
278 {
279 for (unsigned i = 0; i < length; i++)
280 {
281 new (std::addressof (new_array[i])) Type ();
282 new_array[i] = std::move (arrayZ[i]);
283 arrayZ[i].~Type ();
284 }
285 hb_free (arrayZ);
286 }
287 return new_array;
288 }
289 /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */
290 template <typename T = Type,
291 hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
292 hb_is_same (T, hb_array_t <typename T::item_t>))>
293 Type *
294 realloc_vector (unsigned new_allocated, hb_priority<1>)
295 {
296 if (!new_allocated)
297 {
298 hb_free (arrayZ);
299 return nullptr;
300 }
301 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
302 }
303
304 template <typename T = Type,
305 hb_enable_if (hb_is_trivially_constructible(T))>
306 void
307 grow_vector (unsigned size, hb_priority<0>)
308 {
309 hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
310 length = size;
311 }
312 template <typename T = Type,
313 hb_enable_if (!hb_is_trivially_constructible(T))>
314 void
315 grow_vector (unsigned size, hb_priority<0>)
316 {
317 for (; length < size; length++)
318 new (std::addressof (arrayZ[length])) Type ();
319 }
320 /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */
321 template <typename T = Type,
322 hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
323 hb_is_same (T, hb_array_t <typename T::item_t>))>
324 void
325 grow_vector (unsigned size, hb_priority<1>)
326 {
327 hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
328 length = size;
329 }
330
331 template <typename T = Type,
332 hb_enable_if (hb_is_trivially_copyable (T))>
333 void
334 copy_array (hb_array_t<const Type> other)
335 {
336 length = other.length;
337 if (!HB_OPTIMIZE_SIZE_VAL && sizeof (T) >= sizeof (long long))
338 /* This runs faster because of alignment. */
339 for (unsigned i = 0; i < length; i++)
340 arrayZ[i] = other.arrayZ[i];
341 else
342 hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size);
343 }
344 template <typename T = Type,
345 hb_enable_if (!hb_is_trivially_copyable (T) &&
346 std::is_copy_constructible<T>::value)>
347 void
348 copy_array (hb_array_t<const Type> other)
349 {
350 length = 0;
351 while (length < other.length)
352 {
353 length++;
354 new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]);
355 }
356 }
357 template <typename T = Type,
358 hb_enable_if (!hb_is_trivially_copyable (T) &&
359 !std::is_copy_constructible<T>::value &&
360 std::is_default_constructible<T>::value &&
361 std::is_copy_assignable<T>::value)>
362 void
363 copy_array (hb_array_t<const Type> other)
364 {
365 length = 0;
366 while (length < other.length)
367 {
368 length++;
369 new (std::addressof (arrayZ[length - 1])) Type ();
370 arrayZ[length - 1] = other.arrayZ[length - 1];
371 }
372 }
373
374 void
375 shrink_vector (unsigned size)
376 {
377 assert (size <= length);
378 if (!std::is_trivially_destructible<Type>::value)
379 {
380 unsigned count = length - size;
381 Type *p = arrayZ + length - 1;
382 while (count--)
383 p--->~Type ();
384 }
385 length = size;
386 }
387
388 void
389 shift_down_vector (unsigned i)
390 {
391 for (; i < length; i++)
392 arrayZ[i - 1] = std::move (arrayZ[i]);
393 }
394
395 /* Allocate for size but don't adjust length. */
396 bool alloc (unsigned int size, bool exact=false)
397 {
398 if (unlikely (in_error ()))
399 return false;
400
401 unsigned int new_allocated;
402 if (exact)
403 {
404 /* If exact was specified, we allow shrinking the storage. */
405 size = hb_max (size, length);
406 if (size <= (unsigned) allocated &&
407 size >= (unsigned) allocated >> 2)
408 return true;
409
410 new_allocated = size;
411 }
412 else
413 {
414 if (likely (size <= (unsigned) allocated))
415 return true;
416
417 new_allocated = allocated;
418 while (size > new_allocated)
419 new_allocated += (new_allocated >> 1) + 8;
420 }
421
422
423 /* Reallocate */
424
425 bool overflows =
426 (int) in_error () ||
427 (new_allocated < size) ||
428 hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
429
430 if (unlikely (overflows))
431 {
432 set_error ();
433 return false;
434 }
435
436 Type *new_array = realloc_vector (new_allocated, hb_prioritize);
437
438 if (unlikely (new_allocated && !new_array))
439 {
440 if (new_allocated <= (unsigned) allocated)
441 return true; // shrinking failed; it's okay; happens in our fuzzer
442
443 set_error ();
444 return false;
445 }
446
447 arrayZ = new_array;
448 allocated = new_allocated;
449
450 return true;
451 }
452
453 bool resize (int size_, bool initialize = true, bool exact = false)
454 {
455 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
456 if (!alloc (size, exact))
457 return false;
458
459 if (size > length)
460 {
461 if (initialize)
462 grow_vector (size, hb_prioritize);
463 }
464 else if (size < length)
465 {
466 if (initialize)
467 shrink_vector (size);
468 }
469
470 length = size;
471 return true;
472 }
473 bool resize_exact (int size_, bool initialize = true)
474 {
475 return resize (size_, initialize, true);
476 }
477
478 Type pop ()
479 {
480 if (!length) return Null (Type);
481 Type v {std::move (arrayZ[length - 1])};
482 arrayZ[length - 1].~Type ();
483 length--;
484 return v;
485 }
486
487 void remove_ordered (unsigned int i)
488 {
489 if (unlikely (i >= length))
490 return;
491 shift_down_vector (i + 1);
492 arrayZ[length - 1].~Type ();
493 length--;
494 }
495
496 template <bool Sorted = sorted,
497 hb_enable_if (!Sorted)>
498 void remove_unordered (unsigned int i)
499 {
500 if (unlikely (i >= length))
501 return;
502 if (i != length - 1)
503 arrayZ[i] = std::move (arrayZ[length - 1]);
504 arrayZ[length - 1].~Type ();
505 length--;
506 }
507
508 void shrink (int size_, bool shrink_memory = true)
509 {
510 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
511 if (size >= length)
512 return;
513
514 shrink_vector (size);
515
516 if (shrink_memory)
517 alloc (size, true); /* To force shrinking memory if needed. */
518 }
519
520
521 /* Sorting API. */
522 void qsort (int (*cmp)(const void*, const void*) = Type::cmp)
523 { as_array ().qsort (cmp); }
524
525 /* Unsorted search API. */
526 template <typename T>
527 Type *lsearch (const T &x, Type *not_found = nullptr)
528 { return as_array ().lsearch (x, not_found); }
529 template <typename T>
530 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
531 { return as_array ().lsearch (x, not_found); }
532 template <typename T>
533 bool lfind (const T &x, unsigned *pos = nullptr) const
534 { return as_array ().lfind (x, pos); }
535
536 /* Sorted search API. */
537 template <typename T,
538 bool Sorted=sorted, hb_enable_if (Sorted)>
539 Type *bsearch (const T &x, Type *not_found = nullptr)
540 { return as_array ().bsearch (x, not_found); }
541 template <typename T,
542 bool Sorted=sorted, hb_enable_if (Sorted)>
543 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
544 { return as_array ().bsearch (x, not_found); }
545 template <typename T,
546 bool Sorted=sorted, hb_enable_if (Sorted)>
547 bool bfind (const T &x, unsigned int *i = nullptr,
548 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
549 unsigned int to_store = (unsigned int) -1) const
550 { return as_array ().bfind (x, i, not_found, to_store); }
551};
552
553template <typename Type>
554using hb_sorted_vector_t = hb_vector_t<Type, true>;
555
556#endif /* HB_VECTOR_HH */
557