From cc8a4abea68f2dba26feb5785f9e518e6853c744 Mon Sep 17 00:00:00 2001 From: Behdad Esfahbod Date: Thu, 8 Jul 2010 00:40:04 -0400 Subject: [PATCH] Use bsearch where applicable --- src/hb-open-type-private.hh | 49 +++++++++++++ src/hb-ot-layout-common-private.hh | 145 +++++++++++++------------------------ 2 files changed, 100 insertions(+), 94 deletions(-) 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 @@ struct IntType inline operator Type(void) const { return v; } inline bool operator == (const IntType &o) const { return v == o.v; } inline bool operator != (const IntType &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 @@ struct HeadlessArrayOf }; +/* An array with sorted elements. Supports binary searching. */ +template +struct SortedArrayOf : ArrayOf { + + template + 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::sanitize (c) && sanitize_order (c); + } + + inline bool sanitize (hb_sanitize_context_t *c, void *base) { + TRACE_SANITIZE (); + return ArrayOf::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 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 @@ struct Record }; template -struct RecordArrayOf : ArrayOf > { +struct RecordArrayOf : SortedArrayOf > { inline const Tag& get_tag (unsigned int i) const { if (unlikely (i >= this->len)) return Null(Tag); @@ -86,21 +94,14 @@ struct RecordArrayOf : ArrayOf > { } 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 *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 RecordListOf : RecordArrayOf }; +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 { inline unsigned int get_indexes (unsigned int start_offset, @@ -318,14 +344,8 @@ struct CoverageFormat1 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 @@ struct CoverageFormat1 private: USHORT coverageFormat; /* Format identifier--format = 1 */ - ArrayOf + SortedArrayOf 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 @@ struct CoverageFormat2 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 @@ struct CoverageFormat2 private: USHORT coverageFormat; /* Format identifier--format = 2 */ - ArrayOf + SortedArrayOf rangeRecord; /* Array of glyph ranges--ordered by * Start GlyphID. rangeCount entries * long */ @@ -468,33 +457,6 @@ struct ClassDefFormat1 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 @@ struct ClassDefFormat2 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 @@ struct ClassDefFormat2 } USHORT classFormat; /* Format identifier--format = 2 */ - ArrayOf + SortedArrayOf rangeRecord; /* Array of glyph ranges--ordered by * Start GlyphID */ public: -- 2.7.4