Use bsearch where applicable
diff --git a/src/hb-open-type-private.hh b/src/hb-open-type-private.hh
index 59c7866..9cc0518 100644
--- a/src/hb-open-type-private.hh
+++ b/src/hb-open-type-private.hh
@@ -394,6 +394,7 @@
inline operator Type(void) const { return v; }
inline bool operator == (const IntType<Type> &o) const { return v == o.v; }
inline bool operator != (const IntType<Type> &o) const { return v != o.v; }
+ inline int cmp (Type b) const { Type a = v; return b < a ? -1 : b == a ? 0 : +1; }
inline bool sanitize (hb_sanitize_context_t *c) {
TRACE_SANITIZE ();
return likely (c->check_struct (this));
@@ -707,4 +708,52 @@
};
+/* An array with sorted elements. Supports binary searching. */
+template <typename Type>
+struct SortedArrayOf : ArrayOf<Type> {
+
+ template <typename SearchType>
+ inline int search (const SearchType &x) const {
+ class Cmp {
+ public: static int cmp (const void *p1, const void *p2) {
+ const SearchType *a = (const SearchType *) p1;
+ const Type *b = (const Type *) p2;
+ return b->cmp (*a);
+ }
+ };
+ const Type *p = (const Type *) bsearch (&x, this->array, this->len, sizeof (this->array[0]), Cmp::cmp);
+ return p ? p - this->array : -1;
+ }
+
+ inline bool sanitize_order (hb_sanitize_context_t *c) {
+ /* Make sure the list is sorted, since we bsearch in it. */
+ unsigned int count = this->len;
+ for (unsigned int i = 1; i < count; i++)
+ if (unlikely (this->array[i].cmp (this->array[i-1]) > 0)) {
+ /* We need to sort the entries. */
+ if (!c->can_edit (this, this->get_size ())) return false;
+ class Cmp {
+ public: static int cmp (const void *p1, const void *p2) {
+ const Type *a = (const Type *) p1;
+ const Type *b = (const Type *) p2;
+ return b->cmp (*a);
+ }
+ };
+ qsort (this->array, this->len, sizeof (this->array[0]), Cmp::cmp);
+ }
+ return true;
+ }
+
+ inline bool sanitize (hb_sanitize_context_t *c) {
+ TRACE_SANITIZE ();
+ return ArrayOf<Type>::sanitize (c) && sanitize_order (c);
+ }
+
+ inline bool sanitize (hb_sanitize_context_t *c, void *base) {
+ TRACE_SANITIZE ();
+ return ArrayOf<Type>::sanitize (c, base) && sanitize_order (c);
+ }
+};
+
+
#endif /* HB_OPEN_TYPE_PRIVATE_HH */
diff --git a/src/hb-ot-layout-common-private.hh b/src/hb-ot-layout-common-private.hh
index f965491..5954499 100644
--- a/src/hb-ot-layout-common-private.hh
+++ b/src/hb-ot-layout-common-private.hh
@@ -51,6 +51,14 @@
template <typename Type>
struct Record
{
+ inline int cmp (const Record &other) const {
+ return cmp (other.tag);
+ }
+ inline int cmp (hb_tag_t b) const {
+ hb_tag_t a = tag;
+ return b < a ? -1 : b == a ? 0 : -1;
+ }
+
inline bool sanitize (hb_sanitize_context_t *c, void *base) {
TRACE_SANITIZE ();
return c->check_struct (this)
@@ -66,7 +74,7 @@
};
template <typename Type>
-struct RecordArrayOf : ArrayOf<Record<Type> > {
+struct RecordArrayOf : SortedArrayOf<Record<Type> > {
inline const Tag& get_tag (unsigned int i) const
{
if (unlikely (i >= this->len)) return Null(Tag);
@@ -86,21 +94,14 @@
}
inline bool find_index (hb_tag_t tag, unsigned int *index) const
{
- Tag t;
- t.set (tag);
- /* TODO: bsearch (need to sort in sanitize) */
- const Record<Type> *a = this->array;
- unsigned int count = this->len;
- for (unsigned int i = 0; i < count; i++)
- {
- if (t == a[i].tag)
- {
+ int i = this->search (tag);
+ if (i != -1) {
if (index) *index = i;
return true;
- }
+ } else {
+ if (index) *index = Index::NOT_FOUND_INDEX;
+ return false;
}
- if (index) *index = Index::NOT_FOUND_INDEX;
- return false;
}
};
@@ -117,6 +118,31 @@
};
+struct RangeRecord
+{
+ inline int cmp (const RangeRecord &other) const {
+ hb_codepoint_t a = start, b = other.start;
+ return b < a ? -1 : b == a ? 0 : +1;
+ }
+ inline int cmp (hb_codepoint_t g) const {
+ hb_codepoint_t a = start, b = end;
+ return g < a ? -1 : g <= b ? 0 : +1 ;
+ }
+
+ inline bool sanitize (hb_sanitize_context_t *c) {
+ TRACE_SANITIZE ();
+ return c->check_struct (this);
+ }
+
+ GlyphID start; /* First GlyphID in the range */
+ GlyphID end; /* Last GlyphID in the range */
+ USHORT value; /* Value */
+ public:
+ DEFINE_SIZE_STATIC (6);
+};
+DEFINE_NULL_DATA (RangeRecord, "\000\001");
+
+
struct IndexArray : ArrayOf<Index>
{
inline unsigned int get_indexes (unsigned int start_offset,
@@ -318,14 +344,8 @@
private:
inline unsigned int get_coverage (hb_codepoint_t glyph_id) const
{
- if (unlikely (glyph_id > 0xFFFF))
- return NOT_COVERED;
- GlyphID gid;
- gid.set (glyph_id);
- /* TODO: bsearch (need to sort in sanitize) */
- unsigned int num_glyphs = glyphArray.len;
- for (unsigned int i = 0; i < num_glyphs; i++)
- if (gid == glyphArray[i])
+ int i = glyphArray.search (glyph_id);
+ if (i != -1)
return i;
return NOT_COVERED;
}
@@ -337,40 +357,12 @@
private:
USHORT coverageFormat; /* Format identifier--format = 1 */
- ArrayOf<GlyphID>
+ SortedArrayOf<GlyphID>
glyphArray; /* Array of GlyphIDs--in numerical order */
public:
DEFINE_SIZE_ARRAY (4, glyphArray);
};
-struct CoverageRangeRecord
-{
- friend struct CoverageFormat2;
-
- private:
- inline unsigned int get_coverage (hb_codepoint_t glyph_id) const
- {
- if (glyph_id >= start && glyph_id <= end)
- return (unsigned int) startCoverageIndex + (glyph_id - start);
- return NOT_COVERED;
- }
-
- public:
- inline bool sanitize (hb_sanitize_context_t *c) {
- TRACE_SANITIZE ();
- return c->check_struct (this);
- }
-
- private:
- GlyphID start; /* First GlyphID in the range */
- GlyphID end; /* Last GlyphID in the range */
- USHORT startCoverageIndex; /* Coverage Index of first GlyphID in
- * range */
- public:
- DEFINE_SIZE_STATIC (6);
-};
-DEFINE_NULL_DATA (CoverageRangeRecord, "\000\001");
-
struct CoverageFormat2
{
friend struct Coverage;
@@ -378,13 +370,10 @@
private:
inline unsigned int get_coverage (hb_codepoint_t glyph_id) const
{
- /* TODO: bsearch (need to sort in sanitize) */
- unsigned int count = rangeRecord.len;
- for (unsigned int i = 0; i < count; i++)
- {
- unsigned int coverage = rangeRecord[i].get_coverage (glyph_id);
- if (coverage != NOT_COVERED)
- return coverage;
+ int i = rangeRecord.search (glyph_id);
+ if (i != -1) {
+ const RangeRecord &range = rangeRecord[i];
+ return (unsigned int) range.value + (glyph_id - range.start);
}
return NOT_COVERED;
}
@@ -396,7 +385,7 @@
private:
USHORT coverageFormat; /* Format identifier--format = 2 */
- ArrayOf<CoverageRangeRecord>
+ SortedArrayOf<RangeRecord>
rangeRecord; /* Array of glyph ranges--ordered by
* Start GlyphID. rangeCount entries
* long */
@@ -468,33 +457,6 @@
DEFINE_SIZE_ARRAY (6, classValue);
};
-struct ClassRangeRecord
-{
- friend struct ClassDefFormat2;
-
- private:
- inline hb_ot_layout_class_t get_class (hb_codepoint_t glyph_id) const
- {
- if (glyph_id >= start && glyph_id <= end)
- return classValue;
- return 0;
- }
-
- public:
- inline bool sanitize (hb_sanitize_context_t *c) {
- TRACE_SANITIZE ();
- return c->check_struct (this);
- }
-
- private:
- GlyphID start; /* First GlyphID in the range */
- GlyphID end; /* Last GlyphID in the range */
- USHORT classValue; /* Applied to all glyphs in the range */
- public:
- DEFINE_SIZE_STATIC (6);
-};
-DEFINE_NULL_DATA (ClassRangeRecord, "\000\001");
-
struct ClassDefFormat2
{
friend struct ClassDef;
@@ -502,14 +464,9 @@
private:
inline hb_ot_layout_class_t get_class (hb_codepoint_t glyph_id) const
{
- /* TODO: bsearch (need to sort in sanitize) */
- unsigned int count = rangeRecord.len;
- for (unsigned int i = 0; i < count; i++)
- {
- int classValue = rangeRecord[i].get_class (glyph_id);
- if (classValue > 0)
- return classValue;
- }
+ int i = rangeRecord.search (glyph_id);
+ if (i != -1)
+ return rangeRecord[i].value;
return 0;
}
@@ -519,7 +476,7 @@
}
USHORT classFormat; /* Format identifier--format = 2 */
- ArrayOf<ClassRangeRecord>
+ SortedArrayOf<RangeRecord>
rangeRecord; /* Array of glyph ranges--ordered by
* Start GlyphID */
public:
