diff options
Diffstat (limited to 'thirdparty/harfbuzz/src/hb-map.hh')
| -rw-r--r-- | thirdparty/harfbuzz/src/hb-map.hh | 225 |
1 files changed, 151 insertions, 74 deletions
diff --git a/thirdparty/harfbuzz/src/hb-map.hh b/thirdparty/harfbuzz/src/hb-map.hh index 9341637eac..8302e3f8c7 100644 --- a/thirdparty/harfbuzz/src/hb-map.hh +++ b/thirdparty/harfbuzz/src/hb-map.hh @@ -34,19 +34,18 @@ * hb_hashmap_t */ +extern HB_INTERNAL const hb_codepoint_t minus_1; + template <typename K, typename V, - typename k_invalid_t = K, - typename v_invalid_t = V, - k_invalid_t kINVALID = std::is_pointer<K>::value ? 0 : std::is_signed<K>::value ? hb_int_min (K) : (K) -1, - v_invalid_t vINVALID = std::is_pointer<V>::value ? 0 : std::is_signed<V>::value ? hb_int_min (V) : (V) -1> + bool minus_one = false> struct hb_hashmap_t { hb_hashmap_t () { init (); } ~hb_hashmap_t () { fini (); } - hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { hb_copy (o, *this); } + hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { resize (population); hb_copy (o, *this); } hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); } - hb_hashmap_t& operator= (const hb_hashmap_t& o) { hb_copy (o, *this); return *this; } + hb_hashmap_t& operator= (const hb_hashmap_t& o) { resize (population); hb_copy (o, *this); return *this; } hb_hashmap_t& operator= (hb_hashmap_t&& o) { hb_swap (*this, o); return *this; } hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t () @@ -58,44 +57,53 @@ struct hb_hashmap_t hb_requires (hb_is_iterable (Iterable))> hb_hashmap_t (const Iterable &o) : hb_hashmap_t () { - hb_copy (o, *this); + auto iter = hb_iter (o); + if (iter.is_random_access_iterator) + resize (hb_len (iter)); + hb_copy (iter, *this); } struct item_t { K key; + uint32_t hash : 30; + uint32_t is_used_ : 1; + uint32_t is_tombstone_ : 1; V value; - uint32_t hash; + + bool is_used () const { return is_used_; } + void set_used (bool is_used) { is_used_ = is_used; } + bool is_tombstone () const { return is_tombstone_; } + void set_tombstone (bool is_tombstone) { is_tombstone_ = is_tombstone; } + bool is_real () const { return is_used_ && !is_tombstone_; } + + template <bool v = minus_one, + hb_enable_if (v == false)> + static inline const V& default_value () { return Null(V); }; + template <bool v = minus_one, + hb_enable_if (v == true)> + static inline const V& default_value () + { + static_assert (hb_is_same (V, hb_codepoint_t), ""); + return minus_1; + }; void clear () { new (std::addressof (key)) K (); - key = hb_coerce<K> (kINVALID); new (std::addressof (value)) V (); - value = hb_coerce<V> (vINVALID); hash = 0; + is_used_ = false; + is_tombstone_ = false; } bool operator == (const K &o) { return hb_deref (key) == hb_deref (o); } bool operator == (const item_t &o) { return *this == o.key; } - bool is_unused () const - { - const K inv = hb_coerce<K> (kINVALID); - return key == inv; - } - bool is_tombstone () const - { - const K kinv = hb_coerce<K> (kINVALID); - const V vinv = hb_coerce<V> (vINVALID); - return key != kinv && value == vinv; - } - bool is_real () const - { - const K kinv = hb_coerce<K> (kINVALID); - const V vinv = hb_coerce<V> (vINVALID); - return key != kinv && value != vinv; - } hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } + hb_pair_t<const K &, const V &> get_pair_ref() const { return hb_pair_t<const K &, const V &> (key, value); } + + uint32_t total_hash () const + { return (hash * 31) + hb_hash (value); } }; hb_object_header_t header; @@ -116,21 +124,20 @@ struct hb_hashmap_t hb_swap (a.prime, b.prime); hb_swap (a.items, b.items); } - void init_shallow () + void init () { + hb_object_init (this); + successful = true; population = occupancy = 0; mask = 0; prime = 0; items = nullptr; } - void init () - { - hb_object_init (this); - init_shallow (); - } - void fini_shallow () + void fini () { + hb_object_fini (this); + if (likely (items)) { unsigned size = mask + 1; for (unsigned i = 0; i < size; i++) @@ -140,11 +147,6 @@ struct hb_hashmap_t } population = occupancy = 0; } - void fini () - { - hb_object_fini (this); - fini_shallow (); - } void reset () { @@ -154,11 +156,11 @@ struct hb_hashmap_t bool in_error () const { return !successful; } - bool resize () + bool resize (unsigned new_population = 0) { if (unlikely (!successful)) return false; - unsigned int power = hb_bit_storage (population * 2 + 8); + unsigned int power = hb_bit_storage (hb_max (population, new_population) * 2 + 8); unsigned int new_size = 1u << power; item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t)); if (unlikely (!new_items)) @@ -196,27 +198,34 @@ struct hb_hashmap_t return true; } - bool set (K key, const V& value) { return set_with_hash (key, hb_hash (key), value); } - bool set (K key, V&& value) { return set_with_hash (key, hb_hash (key), std::move (value)); } + template <typename VV> + bool set (K key, VV&& value) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value)); } - V get (K key) const + const V& get (K key) const { - if (unlikely (!items)) return hb_coerce<V> (vINVALID); + if (unlikely (!items)) return item_t::default_value (); unsigned int i = bucket_for (key); - return items[i].is_real () && items[i] == key ? items[i].value : hb_coerce<V> (vINVALID); + return items[i].is_real () && items[i] == key ? items[i].value : item_t::default_value (); } - void del (K key) { set (key, hb_coerce<V> (vINVALID)); } + void del (K key) { set_with_hash (key, hb_hash (key), item_t::default_value (), true); } /* Has interface. */ - typedef V value_t; + typedef const V& value_t; value_t operator [] (K k) const { return get (k); } - bool has (K k, V *vp = nullptr) const + template <typename VV=V> + bool has (K key, VV **vp = nullptr) const { - V v = (*this)[k]; - if (vp) *vp = v; - const V vinv = hb_coerce<V> (vINVALID); - return v != vinv; + if (unlikely (!items)) + return false; + unsigned int i = bucket_for (key); + if (items[i].is_real () && items[i] == key) + { + if (vp) *vp = &items[i].value; + return true; + } + else + return false; } /* Projection. */ V operator () (K k) const { return get (k); } @@ -235,6 +244,28 @@ struct hb_hashmap_t bool is_empty () const { return population == 0; } explicit operator bool () const { return !is_empty (); } + uint32_t hash () const + { + uint32_t h = 0; + for (const auto &item : + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real)) + h ^= item.total_hash (); + return h; + } + + bool is_equal (const hb_hashmap_t &other) const + { + if (population != other.population) return false; + + for (auto pair : iter ()) + if (get (pair.first) != pair.second) + return false; + + return true; + } + bool operator == (const hb_hashmap_t &other) const { return is_equal (other); } + bool operator != (const hb_hashmap_t &other) const { return !is_equal (other); } + unsigned int get_population () const { return population; } /* @@ -246,6 +277,12 @@ struct hb_hashmap_t | hb_filter (&item_t::is_real) | hb_map (&item_t::get_pair) ) + auto iter_ref () const HB_AUTO_RETURN + ( + + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real) + | hb_map (&item_t::get_pair_ref) + ) auto keys () const HB_AUTO_RETURN ( + hb_array (items, mask ? mask + 1 : 0) @@ -253,6 +290,12 @@ struct hb_hashmap_t | hb_map (&item_t::key) | hb_map (hb_ridentity) ) + auto keys_ref () const HB_AUTO_RETURN + ( + + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real) + | hb_map (&item_t::key) + ) auto values () const HB_AUTO_RETURN ( + hb_array (items, mask ? mask + 1 : 0) @@ -260,6 +303,12 @@ struct hb_hashmap_t | hb_map (&item_t::value) | hb_map (hb_ridentity) ) + auto values_ref () const HB_AUTO_RETURN + ( + + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real) + | hb_map (&item_t::value) + ) /* Sink interface. */ hb_hashmap_t& operator << (const hb_pair_t<K, V>& v) @@ -268,19 +317,16 @@ struct hb_hashmap_t protected: template <typename VV> - bool set_with_hash (K key, uint32_t hash, VV&& value) + bool set_with_hash (K key, uint32_t hash, VV&& value, bool is_delete=false) { if (unlikely (!successful)) return false; - const K kinv = hb_coerce<K> (kINVALID); - if (unlikely (key == kinv)) return true; if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false; unsigned int i = bucket_for_hash (key, hash); - const V vinv = hb_coerce<V> (vINVALID); - if (value == vinv && items[i].key != key) + if (is_delete && items[i].key != key) return true; /* Trying to delete non-existent key. */ - if (!items[i].is_unused ()) + if (items[i].is_used ()) { occupancy--; if (!items[i].is_tombstone ()) @@ -288,27 +334,30 @@ struct hb_hashmap_t } items[i].key = key; - items[i].value = value; + items[i].value = std::forward<VV> (value); items[i].hash = hash; + items[i].set_used (true); + items[i].set_tombstone (is_delete); occupancy++; - if (!items[i].is_tombstone ()) + if (!is_delete) population++; return true; } - unsigned int bucket_for (K key) const + unsigned int bucket_for (const K &key) const { return bucket_for_hash (key, hb_hash (key)); } - unsigned int bucket_for_hash (K key, uint32_t hash) const + unsigned int bucket_for_hash (const K &key, uint32_t hash) const { + hash &= 0x3FFFFFFF; // We only store lower 30bit of hash unsigned int i = hash % prime; unsigned int step = 0; unsigned int tombstone = (unsigned) -1; - while (!items[i].is_unused ()) + while (items[i].is_used ()) { if (items[i].hash == hash && items[i] == key) return i; @@ -377,21 +426,16 @@ struct hb_hashmap_t struct hb_map_t : hb_hashmap_t<hb_codepoint_t, hb_codepoint_t, - hb_codepoint_t, - hb_codepoint_t, - HB_MAP_VALUE_INVALID, - HB_MAP_VALUE_INVALID> + true> { using hashmap = hb_hashmap_t<hb_codepoint_t, hb_codepoint_t, - hb_codepoint_t, - hb_codepoint_t, - HB_MAP_VALUE_INVALID, - HB_MAP_VALUE_INVALID>; + true>; - hb_map_t () = default; ~hb_map_t () = default; - hb_map_t (hb_map_t&) = default; + hb_map_t () : hashmap () {} + hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {} + hb_map_t (hb_map_t &&o) : hashmap (std::move ((hashmap &) o)) {} hb_map_t& operator= (const hb_map_t&) = default; hb_map_t& operator= (hb_map_t&&) = default; hb_map_t (std::initializer_list<hb_pair_t<hb_codepoint_t, hb_codepoint_t>> lst) : hashmap (lst) {} @@ -400,4 +444,37 @@ struct hb_map_t : hb_hashmap_t<hb_codepoint_t, hb_map_t (const Iterable &o) : hashmap (o) {} }; +template <typename K, typename V> +static inline +hb_hashmap_t<K, V>* hb_hashmap_create () +{ + using hashmap = hb_hashmap_t<K, V>; + hashmap* map; + if (!(map = hb_object_create<hashmap> ())) + return nullptr; + + return map; +} + +template <typename K, typename V> +static inline +void hb_hashmap_destroy (hb_hashmap_t<K, V>* map) +{ + if (!hb_object_destroy (map)) + return; + + hb_free (map); +} + +namespace hb { + +template <typename K, typename V> +struct vtable<hb_hashmap_t<K, V>> +{ + static constexpr auto destroy = hb_hashmap_destroy<K,V>; +}; + +} + + #endif /* HB_MAP_HH */ |