[HarfBuzz] harfbuzz: Branch 'master' - 2 commits
Behdad Esfahbod
behdad at kemper.freedesktop.org
Thu Jun 19 12:39:55 PDT 2014
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 <behdad at behdad.org>
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 <behdad at behdad.org>
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)
More information about the HarfBuzz
mailing list