diff options
Diffstat (limited to 'Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh')
-rw-r--r-- | Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh | 152 |
1 files changed, 109 insertions, 43 deletions
diff --git a/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh b/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh index f7156e51a04..26e4930a5f7 100644 --- a/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh +++ b/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh @@ -30,31 +30,39 @@ #include "hb.hh" -template <typename T> -inline uint32_t Hash (const T &v) -{ - /* Knuth's multiplicative method: */ - return (uint32_t) v * 2654435761u; -} - - /* - * hb_map_t + * hb_hashmap_t */ -struct hb_map_t +template <typename K, typename V, + K kINVALID = hb_is_pointer (K) ? 0 : hb_is_signed (K) ? hb_int_min (K) : (K) -1, + V vINVALID = hb_is_pointer (V) ? 0 : hb_is_signed (V) ? hb_int_min (V) : (V) -1> +struct hb_hashmap_t { - HB_NO_COPY_ASSIGN (hb_map_t); - hb_map_t () { init (); } - ~hb_map_t () { fini (); } + HB_DELETE_COPY_ASSIGN (hb_hashmap_t); + hb_hashmap_t () { init (); } + ~hb_hashmap_t () { fini (); } + + static_assert (hb_is_integral (K) || hb_is_pointer (K), ""); + static_assert (hb_is_integral (V) || hb_is_pointer (V), ""); + /* TODO If key type is a pointer, keep hash in item_t and use to: + * 1. avoid rehashing when resizing table, and + * 2. compare hash before comparing keys, for speed. + */ struct item_t { - hb_codepoint_t key; - hb_codepoint_t value; + K key; + V value; + + void clear () { key = kINVALID; value = vINVALID; } - bool is_unused () const { return key == INVALID; } - bool is_tombstone () const { return key != INVALID && value == INVALID; } + bool operator == (K o) { return hb_deref (key) == hb_deref (o); } + bool operator == (const item_t &o) { return *this == o.key; } + bool is_unused () const { return key == kINVALID; } + bool is_tombstone () const { return key != kINVALID && value == vINVALID; } + bool is_real () const { return key != kINVALID && value != vINVALID; } + hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } }; hb_object_header_t header; @@ -82,14 +90,22 @@ struct hb_map_t { free (items); items = nullptr; + population = occupancy = 0; } void fini () { - population = occupancy = 0; hb_object_fini (this); fini_shallow (); } + void reset () + { + if (unlikely (hb_object_is_immutable (this))) + return; + successful = true; + clear (); + } + bool in_error () const { return !successful; } bool resize () @@ -104,7 +120,9 @@ struct hb_map_t successful = false; return false; } - memset (new_items, 0xFF, (size_t) new_size * sizeof (item_t)); + + hb_iter (new_items, new_size) + | hb_apply (&item_t::clear) + ; unsigned int old_size = mask + 1; item_t *old_items = items; @@ -118,7 +136,7 @@ struct hb_map_t /* Insert back old items. */ if (old_items) for (unsigned int i = 0; i < old_size; i++) - if (old_items[i].key != INVALID && old_items[i].value != INVALID) + if (old_items[i].is_real ()) set (old_items[i].key, old_items[i].value); free (old_items); @@ -126,14 +144,14 @@ struct hb_map_t return true; } - void set (hb_codepoint_t key, hb_codepoint_t value) + void set (K key, V value) { if (unlikely (!successful)) return; - if (unlikely (key == INVALID)) return; + if (unlikely (key == kINVALID)) return; if ((occupancy + occupancy / 2) >= mask && !resize ()) return; unsigned int i = bucket_for (key); - if (value == INVALID && items[i].key != key) + if (value == vINVALID && items[i].key != key) return; /* Trying to delete non-existent key. */ if (!items[i].is_unused ()) @@ -151,26 +169,37 @@ struct hb_map_t population++; } - hb_codepoint_t get (hb_codepoint_t key) const + V get (K key) const { - if (unlikely (!items)) return INVALID; + if (unlikely (!items)) return vINVALID; unsigned int i = bucket_for (key); - return items[i].key == key ? items[i].value : INVALID; + return items[i].is_real () && items[i] == key ? items[i].value : vINVALID; } - void del (hb_codepoint_t key) { set (key, INVALID); } + void del (K key) { set (key, vINVALID); } - bool has (hb_codepoint_t key) const - { return get (key) != INVALID; } - - hb_codepoint_t operator [] (unsigned int key) const - { return get (key); } - - static constexpr hb_codepoint_t INVALID = HB_MAP_VALUE_INVALID; + /* Has interface. */ + static constexpr V SENTINEL = vINVALID; + typedef V value_t; + value_t operator [] (K k) const { return get (k); } + bool has (K k, V *vp = nullptr) const + { + V v = (*this)[k]; + if (vp) *vp = v; + return v != SENTINEL; + } + /* Projection. */ + V operator () (K k) const { return get (k); } void clear () { - if (items) memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t)); + if (unlikely (hb_object_is_immutable (this))) + return; + if (items) + + hb_iter (items, mask + 1) + | hb_apply (&item_t::clear) + ; + population = occupancy = 0; } @@ -178,22 +207,50 @@ struct hb_map_t unsigned int get_population () const { return population; } + /* + * Iterator + */ + auto iter () const HB_AUTO_RETURN + ( + + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real) + | hb_map (&item_t::get_pair) + ) + auto keys () const HB_AUTO_RETURN + ( + + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real) + | hb_map (&item_t::key) + | hb_map (hb_ridentity) + ) + auto values () const HB_AUTO_RETURN + ( + + hb_array (items, mask ? mask + 1 : 0) + | hb_filter (&item_t::is_real) + | hb_map (&item_t::value) + | hb_map (hb_ridentity) + ) + + /* Sink interface. */ + hb_hashmap_t<K, V, kINVALID, vINVALID>& operator << (const hb_pair_t<K, V>& v) + { set (v.first, v.second); return *this; } + protected: - unsigned int bucket_for (hb_codepoint_t key) const + unsigned int bucket_for (K key) const { - unsigned int i = Hash (key) % prime; + unsigned int i = hb_hash (key) % prime; unsigned int step = 0; - unsigned int tombstone = INVALID; + unsigned int tombstone = (unsigned) -1; while (!items[i].is_unused ()) { - if (items[i].key == key) - return i; - if (tombstone == INVALID && items[i].is_tombstone ()) - tombstone = i; + if (items[i] == key) + return i; + if (tombstone == (unsigned) -1 && items[i].is_tombstone ()) + tombstone = i; i = (i + ++step) & mask; } - return tombstone == INVALID ? i : tombstone; + return tombstone == (unsigned) -1 ? i : tombstone; } static unsigned int prime_for (unsigned int shift) @@ -248,5 +305,14 @@ struct hb_map_t } }; +/* + * hb_map_t + */ + +struct hb_map_t : hb_hashmap_t<hb_codepoint_t, + hb_codepoint_t, + HB_MAP_VALUE_INVALID, + HB_MAP_VALUE_INVALID> {}; + #endif /* HB_MAP_HH */ |