Imported Upstream version 1.2.7

[platform/upstream/harfbuzz.git] / src / hb-set-private.hh

diff --git a/src/hb-set-private.hh b/src/hb-set-private.hh
index 705f554..3c302b1 100644 (file)
--- a/src/hb-set-private.hh
+++ b/src/hb-set-private.hh
@@ -36,7 +36,15 @@
  * "approximate member query".  Conceptually these are like Bloom
  * Filter and Quotient Filter, however, much smaller, faster, and
  * designed to fit the requirements of our uses for glyph coverage
- * queries.  As a result, our filters have much higher.
+ * queries.
+ *
+ * Our filters are highly accurate if the lookup covers fairly local
+ * set of glyphs, but fully flooded and ineffective if coverage is
+ * all over the place.
+ *
+ * The frozen-set can be used instead of a digest, to trade more
+ * memory for 100% accuracy, but in practice, that doesn't look like
+ * an attractive trade-off.
  */
 
 template <typename mask_t, unsigned int shift>
@@ -145,12 +153,14 @@ typedef hb_set_digest_combiner_t
 
 struct hb_set_t
 {
+  friend struct hb_frozen_set_t;
+
   hb_object_header_t header;
   ASSERT_POD ();
   bool in_error;
 
   inline void init (void) {
-    header.init ();
+    hb_object_init (this);
     clear ();
   }
   inline void fini (void) {
@@ -326,7 +336,7 @@ struct hb_set_t
   static  const hb_codepoint_t INVALID = HB_SET_VALUE_INVALID;
 
   elt_t &elt (hb_codepoint_t g) { return elts[g >> SHIFT]; }
-  elt_t elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; }
+  elt_t const &elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; }
   elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); }
 
   elt_t elts[ELTS]; /* XXX 8kb */
@@ -335,6 +345,58 @@ struct hb_set_t
   ASSERT_STATIC (sizeof (elt_t) * 8 * ELTS > MAX_G);
 };
 
+struct hb_frozen_set_t
+{
+  static const unsigned int SHIFT = hb_set_t::SHIFT;
+  static const unsigned int BITS = hb_set_t::BITS;
+  static const unsigned int MASK = hb_set_t::MASK;
+  typedef hb_set_t::elt_t elt_t;
+
+  inline void init (const hb_set_t &set)
+  {
+    start = count = 0;
+    elts = NULL;
+
+    unsigned int max = set.get_max ();
+    if (max == set.INVALID)
+      return;
+    unsigned int min = set.get_min ();
+    const elt_t &min_elt = set.elt (min);
+
+    start = min & ~MASK;
+    count = max - start + 1;
+    unsigned int num_elts = (count + BITS - 1) / BITS;
+    unsigned int elts_size = num_elts * sizeof (elt_t);
+    elts = (elt_t *) malloc (elts_size);
+    if (unlikely (!elts))
+    {
+      start = count = 0;
+      return;
+    }
+    memcpy (elts, &min_elt, elts_size);
+  }
+
+  inline void fini (void)
+  {
+    if (elts)
+      free (elts);
+  }
+
+  inline bool has (hb_codepoint_t g) const
+  {
+    /* hb_codepoint_t is unsigned. */
+    g -= start;
+    if (unlikely (g > count)) return false;
+    return !!(elt (g) & mask (g));
+  }
+
+  elt_t const &elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; }
+  elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); }
+
+  private:
+  hb_codepoint_t start, count;
+  elt_t *elts;
+};
 
 
 #endif /* HB_SET_PRIVATE_HH */