summaryrefslogtreecommitdiff
path: root/Build/source/libs/harfbuzz/harfbuzz-src/src/hb-map.hh
diff options
context:
space:
mode:
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.hh152
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 */