X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fhb-map.hh;h=8c8db4d520b299b222ab2e107947e7e5ac05556a;hb=a280f8312cc9b27515efbab292b95b9d147a2b73;hp=f7156e51a04d449427dd54b0f27a9d6a443e7d83;hpb=610626019cd10944b76622e30b2610910bf4b2b8;p=platform%2Fupstream%2Fharfbuzz.git

diff --git a/src/hb-map.hh b/src/hb-map.hh
index f7156e5..8c8db4d 100644
--- a/src/hb-map.hh
+++ b/src/hb-map.hh
@@ -30,31 +30,36 @@
 #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), "");
 
   struct item_t
   {
-    hb_codepoint_t key;
-    hb_codepoint_t value;
-
-    bool is_unused () const    { return key == INVALID; }
-    bool is_tombstone () const { return key != INVALID && value == INVALID; }
+    K key;
+    V value;
+    uint32_t hash;
+
+    void clear () { key = kINVALID; value = vINVALID; hash = 0; }
+
+    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 +87,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 +117,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,22 +133,97 @@ 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)
-	  set (old_items[i].key, old_items[i].value);
+	if (old_items[i].is_real ())
+	  set_with_hash (old_items[i].key,
+                         old_items[i].hash,
+                         old_items[i].value);
 
     free (old_items);
 
     return true;
   }
 
-  void set (hb_codepoint_t key, hb_codepoint_t value)
+  void set (K key, V value)
+  {
+    set_with_hash (key, hb_hash (key), value);
+  }
+
+  V get (K key) const
+  {
+    if (unlikely (!items)) return vINVALID;
+    unsigned int i = bucket_for (key);
+    return items[i].is_real () && items[i] == key ? items[i].value : vINVALID;
+  }
+
+  void del (K key) { set (key, vINVALID); }
+
+  /* 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 (unlikely (hb_object_is_immutable (this)))
+      return;
+    if (items)
+      + hb_iter (items, mask + 1)
+      | hb_apply (&item_t::clear)
+      ;
+
+    population = occupancy = 0;
+  }
+
+  bool is_empty () const { return population == 0; }
+
+  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:
+
+  void set_with_hash (K key, uint32_t hash, 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);
+    unsigned int i = bucket_for_hash (key, hash);
 
-    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 ())
@@ -145,55 +235,32 @@ struct hb_map_t
 
     items[i].key = key;
     items[i].value = value;
+    items[i].hash = hash;
 
     occupancy++;
     if (!items[i].is_tombstone ())
       population++;
-
-  }
-  hb_codepoint_t get (hb_codepoint_t key) const
-  {
-    if (unlikely (!items)) return INVALID;
-    unsigned int i = bucket_for (key);
-    return items[i].key == key ? items[i].value : INVALID;
   }
 
-  void del (hb_codepoint_t key) { set (key, INVALID); }
-
-  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;
-
-  void clear ()
+  unsigned int bucket_for (K key) const
   {
-    if (items) memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t));
-    population = occupancy = 0;
+    return bucket_for_hash (key, hb_hash (key));
   }
 
-  bool is_empty () const { return population == 0; }
-
-  unsigned int get_population () const { return population; }
-
-  protected:
-
-  unsigned int bucket_for (hb_codepoint_t key) const
+  unsigned int bucket_for_hash (K key, uint32_t hash) const
   {
-    unsigned int i = Hash (key) % prime;
+    unsigned int i = hash % 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].hash == hash && 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 +315,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 */