Edit
kc3-lang/harfbuzz/src/hb-vector.hh
Behdad Esfahbod
- src/hb-vector.hh
-
/* * Copyright © 2017,2018 Google, Inc. * * This is part of HarfBuzz, a text shaping library. * * Permission is hereby granted, without written agreement and without * license or royalty fees, to use, copy, modify, and distribute this * software and its documentation for any purpose, provided that the * above copyright notice and the following two paragraphs appear in * all copies of this software. * * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH * DAMAGE. * * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. * * Google Author(s): Behdad Esfahbod */ #ifndef HB_VECTOR_HH #define HB_VECTOR_HH #include "hb.hh" #include "hb-array.hh" #include "hb-meta.hh" #include "hb-null.hh" template <typename Type, bool sorted=false> struct hb_vector_t { typedef Type item_t; static constexpr unsigned item_size = hb_static_size (Type); using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type; using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type; hb_vector_t () = default; hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t () { alloc (lst.size (), true); for (auto&& item : lst) push (item); } template <typename Iterable, hb_requires (hb_is_iterable (Iterable))> hb_vector_t (const Iterable &o) : hb_vector_t () { auto iter = hb_iter (o); if (iter.is_random_access_iterator) alloc (hb_len (iter), true); hb_copy (iter, *this); } hb_vector_t (const hb_vector_t &o) : hb_vector_t () { alloc (o.length, true); if (unlikely (in_error ())) return; copy_vector (o); } hb_vector_t (hb_vector_t &&o) { allocated = o.allocated; length = o.length; arrayZ = o.arrayZ; o.init (); } ~hb_vector_t () { fini (); } public: int allocated = 0; /* == -1 means allocation failed. */ unsigned int length = 0; public: Type *arrayZ = nullptr; void init () { allocated = length = 0; arrayZ = nullptr; } void init0 () { } void fini () { shrink_vector (0); hb_free (arrayZ); init (); } void reset () { if (unlikely (in_error ())) /* Big Hack! We don't know the true allocated size before * an allocation failure happened. But we know it was at * least as big as length. Restore it to that and continue * as if error did not happen. */ allocated = length; resize (0); } friend void swap (hb_vector_t& a, hb_vector_t& b) { hb_swap (a.allocated, b.allocated); hb_swap (a.length, b.length); hb_swap (a.arrayZ, b.arrayZ); } hb_vector_t& operator = (const hb_vector_t &o) { reset (); alloc (o.length, true); if (unlikely (in_error ())) return *this; copy_vector (o); return *this; } hb_vector_t& operator = (hb_vector_t &&o) { hb_swap (*this, o); return *this; } hb_bytes_t as_bytes () const { return hb_bytes_t ((const char *) arrayZ, get_size ()); } bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); } bool operator != (const hb_vector_t &o) const { return !(*this == o); } uint32_t hash () const { return as_array ().hash (); } Type& operator [] (int i_) { unsigned int i = (unsigned int) i_; if (unlikely (i >= length)) return Crap (Type); return arrayZ[i]; } const Type& operator [] (int i_) const { unsigned int i = (unsigned int) i_; if (unlikely (i >= length)) return Null (Type); return arrayZ[i]; } Type& tail () { return (*this)[length - 1]; } const Type& tail () const { return (*this)[length - 1]; } explicit operator bool () const { return length; } unsigned get_size () const { return length * item_size; } /* Sink interface. */ template <typename T> hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; } array_t as_array () { return hb_array (arrayZ, length); } c_array_t as_array () const { return hb_array (arrayZ, length); } /* Iterator. */ typedef c_array_t iter_t; typedef array_t writer_t; iter_t iter () const { return as_array (); } writer_t writer () { return as_array (); } operator iter_t () const { return iter (); } operator writer_t () { return writer (); } /* Faster range-based for loop. */ Type *begin () const { return arrayZ; } Type *end () const { return arrayZ + length; } hb_sorted_array_t<Type> as_sorted_array () { return hb_sorted_array (arrayZ, length); } hb_sorted_array_t<const Type> as_sorted_array () const { return hb_sorted_array (arrayZ, length); } template <typename T> explicit operator T * () { return arrayZ; } template <typename T> explicit operator const T * () const { return arrayZ; } Type * operator + (unsigned int i) { return arrayZ + i; } const Type * operator + (unsigned int i) const { return arrayZ + i; } Type *push () { if (unlikely (!resize (length + 1))) return &Crap (Type); return std::addressof (arrayZ[length - 1]); } template <typename T, typename T2 = Type, hb_enable_if (!std::is_copy_constructible<T2>::value && std::is_copy_assignable<T>::value)> Type *push (T&& v) { Type *p = push (); if (p == &Crap (Type)) // If push failed to allocate then don't copy v, since this may cause // the created copy to leak memory since we won't have stored a // reference to it. return p; *p = std::forward<T> (v); return p; } template <typename T, typename T2 = Type, hb_enable_if (std::is_copy_constructible<T2>::value)> Type *push (T&& v) { if (unlikely (!alloc (length + 1))) // If push failed to allocate then don't copy v, since this may cause // the created copy to leak memory since we won't have stored a // reference to it. return &Crap (Type); /* Emplace. */ length++; Type *p = std::addressof (arrayZ[length - 1]); return new (p) Type (std::forward<T> (v)); } bool in_error () const { return allocated < 0; } template <typename T = Type, hb_enable_if (hb_is_trivially_copy_assignable(T))> Type * realloc_vector (unsigned new_allocated) { if (!new_allocated) { hb_free (arrayZ); return nullptr; } return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); } template <typename T = Type, hb_enable_if (!hb_is_trivially_copy_assignable(T))> Type * realloc_vector (unsigned new_allocated) { if (!new_allocated) { hb_free (arrayZ); return nullptr; } Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type)); if (likely (new_array)) { for (unsigned i = 0; i < length; i++) { new (std::addressof (new_array[i])) Type (); new_array[i] = std::move (arrayZ[i]); arrayZ[i].~Type (); } hb_free (arrayZ); } return new_array; } template <typename T = Type, hb_enable_if (hb_is_trivially_constructible(T))> void grow_vector (unsigned size) { memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); length = size; } template <typename T = Type, hb_enable_if (!hb_is_trivially_constructible(T))> void grow_vector (unsigned size) { while (length < size) { length++; new (std::addressof (arrayZ[length - 1])) Type (); } } template <typename T = Type, hb_enable_if (hb_is_trivially_copyable (T))> void copy_vector (const hb_vector_t &other) { length = other.length; #ifndef HB_OPTIMIZE_SIZE if (sizeof (T) >= sizeof (long long)) /* This runs faster because of alignment. */ for (unsigned i = 0; i < length; i++) arrayZ[i] = other.arrayZ[i]; else #endif hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size); } template <typename T = Type, hb_enable_if (!hb_is_trivially_copyable (T) && std::is_copy_constructible<T>::value)> void copy_vector (const hb_vector_t &other) { length = 0; while (length < other.length) { length++; new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]); } } template <typename T = Type, hb_enable_if (!hb_is_trivially_copyable (T) && !std::is_copy_constructible<T>::value && std::is_default_constructible<T>::value && std::is_copy_assignable<T>::value)> void copy_vector (const hb_vector_t &other) { length = 0; while (length < other.length) { length++; new (std::addressof (arrayZ[length - 1])) Type (); arrayZ[length - 1] = other.arrayZ[length - 1]; } } void shrink_vector (unsigned size) { while ((unsigned) length > size) { arrayZ[(unsigned) length - 1].~Type (); length--; } } void shift_down_vector (unsigned i) { for (; i < length; i++) arrayZ[i - 1] = std::move (arrayZ[i]); } /* Allocate for size but don't adjust length. */ bool alloc (unsigned int size, bool exact=false) { if (unlikely (in_error ())) return false; unsigned int new_allocated; if (exact) { /* If exact was specified, we allow shrinking the storage. */ size = hb_max (size, length); if (size <= (unsigned) allocated && size >= (unsigned) allocated >> 2) return true; new_allocated = size; } else { if (likely (size <= (unsigned) allocated)) return true; new_allocated = allocated; while (size > new_allocated) new_allocated += (new_allocated >> 1) + 8; } /* Reallocate */ bool overflows = (int) in_error () || (new_allocated < size) || hb_unsigned_mul_overflows (new_allocated, sizeof (Type)); if (unlikely (overflows)) { allocated = -1; return false; } Type *new_array = realloc_vector (new_allocated); if (unlikely (new_allocated && !new_array)) { if (new_allocated <= (unsigned) allocated) return true; // shrinking failed; it's okay; happens in our fuzzer allocated = -1; return false; } arrayZ = new_array; allocated = new_allocated; return true; } bool resize (int size_, bool initialize = true, bool exact = false) { unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; if (!alloc (size, exact)) return false; if (size > length) { if (initialize) grow_vector (size); } else if (size < length) { if (initialize) shrink_vector (size); } length = size; return true; } bool resize_exact (int size_, bool initialize = true) { return resize (size_, initialize, true); } Type pop () { if (!length) return Null (Type); Type v {std::move (arrayZ[length - 1])}; arrayZ[length - 1].~Type (); length--; return v; } void remove_ordered (unsigned int i) { if (unlikely (i >= length)) return; shift_down_vector (i + 1); arrayZ[length - 1].~Type (); length--; } template <bool Sorted = sorted, hb_enable_if (!Sorted)> void remove_unordered (unsigned int i) { if (unlikely (i >= length)) return; if (i != length - 1) arrayZ[i] = std::move (arrayZ[length - 1]); arrayZ[length - 1].~Type (); length--; } void shrink (int size_) { unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; if (size >= length) return; shrink_vector (size); alloc (size, true); /* To force shrinking memory if needed. */ } /* Sorting API. */ void qsort (int (*cmp)(const void*, const void*) = Type::cmp) { as_array ().qsort (cmp); } /* Unsorted search API. */ template <typename T> Type *lsearch (const T &x, Type *not_found = nullptr) { return as_array ().lsearch (x, not_found); } template <typename T> const Type *lsearch (const T &x, const Type *not_found = nullptr) const { return as_array ().lsearch (x, not_found); } template <typename T> bool lfind (const T &x, unsigned *pos = nullptr) const { return as_array ().lfind (x, pos); } /* Sorted search API. */ template <typename T, bool Sorted=sorted, hb_enable_if (Sorted)> Type *bsearch (const T &x, Type *not_found = nullptr) { return as_array ().bsearch (x, not_found); } template <typename T, bool Sorted=sorted, hb_enable_if (Sorted)> const Type *bsearch (const T &x, const Type *not_found = nullptr) const { return as_array ().bsearch (x, not_found); } template <typename T, bool Sorted=sorted, hb_enable_if (Sorted)> bool bfind (const T &x, unsigned int *i = nullptr, hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, unsigned int to_store = (unsigned int) -1) const { return as_array ().bfind (x, i, not_found, to_store); } }; template <typename Type> using hb_sorted_vector_t = hb_vector_t<Type, true>; #endif /* HB_VECTOR_HH */