src/hb-coretext.cc | 4 ++-- src/hb-open-type-private.hh | 4 ++-- src/hb-ot-cmap-table.hh | 14 +++++++------- src/hb-ot-layout-common-private.hh | 9 +++++---- src/hb-ot-map.cc | 4 ++-- src/hb-private.hh | 8 ++++---- src/hb-uniscribe.cc | 4 ++-- 7 files changed, 24 insertions(+), 23 deletions(-)
New commits: commit df554af99db390e42d378983bb3fcf583477a1d7 Author: Behdad Esfahbod <[email protected]> Date: Thu Jun 19 15:39:18 2014 -0400 Rename search() to bsearch() and lsearch() Such that the complexity of the algorithm used is clear at call site. diff --git a/src/hb-open-type-private.hh b/src/hb-open-type-private.hh index c4446ce..a95afc2 100644 --- a/src/hb-open-type-private.hh +++ b/src/hb-open-type-private.hh @@ -837,7 +837,7 @@ struct GenericArrayOf } template <typename SearchType> - inline int search (const SearchType &x) const + inline int lsearch (const SearchType &x) const { unsigned int count = len; for (unsigned int i = 0; i < count; i++) @@ -962,7 +962,7 @@ template <typename LenType, typename Type> struct GenericSortedArrayOf : GenericArrayOf<LenType, Type> { template <typename SearchType> - inline int search (const SearchType &x) const + inline int bsearch (const SearchType &x) const { /* Hand-coded bsearch here since this is in the hot inner loop. */ int min = 0, max = (int) this->len - 1; diff --git a/src/hb-ot-cmap-table.hh b/src/hb-ot-cmap-table.hh index e21baed..b182b53 100644 --- a/src/hb-ot-cmap-table.hh +++ b/src/hb-ot-cmap-table.hh @@ -92,7 +92,7 @@ struct CmapSubtableFormat4 glyphIdArray = idRangeOffset + segCount; glyphIdArrayLength = (this->length - 16 - 8 * segCount) / 2; - /* Custom bsearch. */ + /* Custom two-array bsearch. */ int min = 0, max = (int) segCount - 1; unsigned int i; while (min <= max) @@ -247,7 +247,7 @@ struct CmapSubtableLongSegmented private: inline bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const { - int i = groups.search (codepoint); + int i = groups.bsearch (codepoint); if (i == -1) return false; *glyph = T::group_get_glyph (groups[i], codepoint); @@ -367,7 +367,10 @@ struct cmap key.platformID.set (platform_id); key.encodingID.set (encoding_id); - int result = encodingRecord.search (key); + /* Note: We can use bsearch, but since it has no performance + * implications, we use lsearch and as such accept fonts with + * unsorted subtable list. */ + int result = encodingRecord./*bsearch*/lsearch (key); if (result == -1 || !encodingRecord[result].subtable) return NULL; @@ -382,10 +385,7 @@ struct cmap } USHORT version; /* Table version number (0). */ - /* Note: We can use the Sorted array variant, but since it - * has no performance implications, we use non-sorted array and - * as such accept fonts with unsorted subtable list. */ - /*Sorted*/ArrayOf<EncodingRecord> + SortedArrayOf<EncodingRecord> encodingRecord; /* Encoding tables. */ public: DEFINE_SIZE_ARRAY (4, encodingRecord); diff --git a/src/hb-ot-layout-common-private.hh b/src/hb-ot-layout-common-private.hh index 688bf65..3904c2d 100644 --- a/src/hb-ot-layout-common-private.hh +++ b/src/hb-ot-layout-common-private.hh @@ -103,7 +103,8 @@ struct RecordArrayOf : SortedArrayOf<Record<Type> > { } inline bool find_index (hb_tag_t tag, unsigned int *index) const { - int i = this->search (tag); + /* If we want to allow non-sorted data, we can lsearch(). */ + int i = this->/*lsearch*/bsearch (tag); if (i != -1) { if (index) *index = i; return true; @@ -631,7 +632,7 @@ struct CoverageFormat1 private: inline unsigned int get_coverage (hb_codepoint_t glyph_id) const { - int i = glyphArray.search (glyph_id); + int i = glyphArray.bsearch (glyph_id); ASSERT_STATIC (((unsigned int) -1) == NOT_COVERED); return i; } @@ -696,7 +697,7 @@ struct CoverageFormat2 private: inline unsigned int get_coverage (hb_codepoint_t glyph_id) const { - int i = rangeRecord.search (glyph_id); + int i = rangeRecord.bsearch (glyph_id); if (i != -1) { const RangeRecord &range = rangeRecord[i]; return (unsigned int) range.value + (glyph_id - range.start); @@ -992,7 +993,7 @@ struct ClassDefFormat2 private: inline unsigned int get_class (hb_codepoint_t glyph_id) const { - int i = rangeRecord.search (glyph_id); + int i = rangeRecord.bsearch (glyph_id); if (i != -1) return rangeRecord[i].value; return 0; commit fb8cc86ff99c08064ac58a559bb66cc340693b92 Author: Behdad Esfahbod <[email protected]> Date: Thu Jun 19 15:30:18 2014 -0400 Rename sort() to qsort() In an effort to make the algorithm used clear. diff --git a/src/hb-coretext.cc b/src/hb-coretext.cc index 06ccfd8..864e9e7 100644 --- a/src/hb-coretext.cc +++ b/src/hb-coretext.cc @@ -477,7 +477,7 @@ _hb_coretext_shape (hb_shape_plan_t *shape_plan, event->start = false; event->feature = feature; } - feature_events.sort (); + feature_events.qsort (); /* Add a strategic final event. */ { active_feature_t feature; @@ -512,7 +512,7 @@ _hb_coretext_shape (hb_shape_plan_t *shape_plan, CFMutableArrayRef features_array = CFArrayCreateMutable(kCFAllocatorDefault, 0, &kCFTypeArrayCallBacks); /* TODO sort and resolve conflicting features? */ - /* active_features.sort (); */ + /* active_features.qsort (); */ for (unsigned int j = 0; j < active_features.len; j++) { CFStringRef keys[2] = { diff --git a/src/hb-ot-map.cc b/src/hb-ot-map.cc index 559193c..bd2d87f 100644 --- a/src/hb-ot-map.cc +++ b/src/hb-ot-map.cc @@ -141,7 +141,7 @@ hb_ot_map_builder_t::compile (hb_ot_map_t &m) /* Sort features and merge duplicates */ { - feature_infos.sort (); + feature_infos.qsort (); unsigned int j = 0; for (unsigned int i = 1; i < feature_infos.len; i++) if (feature_infos[i].tag != feature_infos[j].tag) @@ -251,7 +251,7 @@ hb_ot_map_builder_t::compile (hb_ot_map_t &m) /* Sort lookups and merge duplicates */ if (last_num_lookups < m.lookups[table_index].len) { - m.lookups[table_index].sort (last_num_lookups, m.lookups[table_index].len); + m.lookups[table_index].qsort (last_num_lookups, m.lookups[table_index].len); unsigned int j = last_num_lookups; for (unsigned int i = j + 1; i < m.lookups[table_index].len; i++) diff --git a/src/hb-private.hh b/src/hb-private.hh index f361875..5179912 100644 --- a/src/hb-private.hh +++ b/src/hb-private.hh @@ -353,14 +353,14 @@ struct hb_prealloced_array_t return NULL; } - inline void sort (void) + inline void qsort (void) { - qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); + ::qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); } - inline void sort (unsigned int start, unsigned int end) + inline void qsort (unsigned int start, unsigned int end) { - qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp); + ::qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp); } template <typename T> diff --git a/src/hb-uniscribe.cc b/src/hb-uniscribe.cc index 6571448..f699415 100644 --- a/src/hb-uniscribe.cc +++ b/src/hb-uniscribe.cc @@ -631,7 +631,7 @@ _hb_uniscribe_shape (hb_shape_plan_t *shape_plan, event->start = false; event->feature = feature; } - feature_events.sort (); + feature_events.qsort (); /* Add a strategic final event. */ { active_feature_t feature; @@ -663,7 +663,7 @@ _hb_uniscribe_shape (hb_shape_plan_t *shape_plan, unsigned int offset = feature_records.len; - active_features.sort (); + active_features.qsort (); for (unsigned int j = 0; j < active_features.len; j++) { if (!j || active_features[j].rec.tagFeature != feature_records[feature_records.len - 1].tagFeature) _______________________________________________ HarfBuzz mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/harfbuzz
