[HarfBuzz] harfbuzz: Branch 'master' - 8 commits
Behdad Esfahbod
behdad at kemper.freedesktop.org
Mon Oct 30 19:15:29 UTC 2017
src/Makefile.sources | 1
src/check-includes.sh | 2
src/hb-ot-map-private.hh | 18 ++
src/hb-ot-name-table.hh | 2
src/hb-ot-post-table.hh | 140 ++++++++++++++--------
src/hb-ot-tag.cc | 8 -
src/hb-ot-var-mvar-table.hh | 10 +
src/hb-private.hh | 36 ++++-
src/hb-sort-r.hh | 280 ++++++++++++++++++++++++++++++++++++++++++++
src/hb-string-array.hh | 11 +
10 files changed, 439 insertions(+), 69 deletions(-)
New commits:
commit e35a763c07b60da6e5fbdb6edd9d25f575cd3d8b
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Mon Oct 30 13:15:05 2017 -0600
[post] Implement glyph_from_name()
This concludes https://github.com/behdad/harfbuzz/pull/568
diff --git a/src/hb-ot-post-table.hh b/src/hb-ot-post-table.hh
index 7e164cba..580a6a92 100644
--- a/src/hb-ot-post-table.hh
+++ b/src/hb-ot-post-table.hh
@@ -108,9 +108,97 @@ struct post
inline void fini (void)
{
index_to_offset.finish ();
+ free (gids_sorted_by_name);
}
- inline hb_string_t _find_glyph_name (hb_codepoint_t glyph) const
+ inline bool get_glyph_name (hb_codepoint_t glyph,
+ char *buf, unsigned int buf_len) const
+ {
+ hb_string_t s = find_glyph_name (glyph);
+ if (!s.len)
+ return false;
+ if (!buf_len)
+ return true;
+ if (buf_len <= s.len) /* What to do with truncation? Returning false for now. */
+ return false;
+ strncpy (buf, s.bytes, s.len);
+ buf[s.len] = '\0';
+ return true;
+ }
+
+ inline bool get_glyph_from_name (const char *name, int len,
+ hb_codepoint_t *glyph) const
+ {
+ unsigned int count = get_glyph_count ();
+ if (unlikely (!count))
+ return false;
+
+ if (len < 0)
+ len = strlen (name);
+
+ if (unlikely (!len))
+ return false;
+
+ retry:
+ uint16_t *gids = (uint16_t *) hb_atomic_ptr_get (&gids_sorted_by_name);
+
+ if (unlikely (!gids))
+ {
+ gids = (uint16_t *) malloc (count * sizeof (gids[0]));
+ if (unlikely (!gids))
+ return false; /* Anything better?! */
+
+ for (unsigned int i = 0; i < count; i++)
+ gids[i] = i;
+ hb_sort_r (gids, count, sizeof (gids[0]), cmp_gids, (void *) this);
+
+ if (!hb_atomic_ptr_cmpexch (&gids_sorted_by_name, nullptr, gids)) {
+ free (gids);
+ goto retry;
+ }
+ }
+
+ hb_string_t st (name, len);
+ const uint16_t *gid = (const uint16_t *) hb_bsearch_r (&st, gids, count, sizeof (gids[0]), cmp_key, (void *) this);
+ if (gid)
+ {
+ *glyph = *gid;
+ return true;
+ }
+
+ return false;
+ }
+
+ protected:
+
+ inline unsigned int get_glyph_count (void) const
+ {
+ if (version == 0x00010000)
+ return NUM_FORMAT1_NAMES;
+
+ if (version == 0x00020000)
+ return glyphNameIndex->len;
+
+ return 0;
+ }
+
+ static inline int cmp_gids (const void *pa, const void *pb, void *arg)
+ {
+ const accelerator_t *thiz = (const accelerator_t *) arg;
+ uint16_t a = * (const uint16_t *) pa;
+ uint16_t b = * (const uint16_t *) pb;
+ return thiz->find_glyph_name (b).cmp (thiz->find_glyph_name (a));
+ }
+
+ static inline int cmp_key (const void *pk, const void *po, void *arg)
+ {
+ const accelerator_t *thiz = (const accelerator_t *) arg;
+ const hb_string_t *key = (const hb_string_t *) pk;
+ uint16_t o = * (const uint16_t *) po;
+ return thiz->find_glyph_name (o).cmp (*key);
+ }
+
+ inline hb_string_t find_glyph_name (hb_codepoint_t glyph) const
{
if (version == 0x00010000)
{
@@ -139,38 +227,11 @@ struct post
return hb_string_t ((const char *) data, name_length);
}
- inline bool get_glyph_name (hb_codepoint_t glyph,
- char *buf, unsigned int buf_len) const
- {
- hb_string_t s = _find_glyph_name (glyph);
- if (!s.len)
- return false;
- if (!buf_len)
- return true;
- if (buf_len <= s.len) /* What to do with truncation? Returning false for now. */
- return false;
- strncpy (buf, s.bytes, s.len);
- buf[s.len] = '\0';
- return true;
- }
-
- inline bool get_glyph_from_name (const char *name, int len,
- hb_codepoint_t *glyph) const
- {
- if (len < 0)
- len = strlen (name);
-
- if (unlikely (!len))
- return false;
-
- /* TODO format2 */
- return false;
- }
-
uint32_t version;
const ArrayOf<USHORT> *glyphNameIndex;
hb_prealloced_array_t<uint32_t, 1> index_to_offset;
const uint8_t *pool;
+ mutable uint16_t *gids_sorted_by_name;
};
public:
diff --git a/src/hb-private.hh b/src/hb-private.hh
index b88de08d..6f2106ee 100644
--- a/src/hb-private.hh
+++ b/src/hb-private.hh
@@ -1145,18 +1145,18 @@ struct hb_string_t
inline hb_string_t (void) : bytes (nullptr), len (0) {}
inline hb_string_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {}
- inline int cmp (const hb_string_t *a) const
+ inline int cmp (const hb_string_t &a) const
{
- if (len != a->len)
- return (int) a->len - (int) len;
+ if (len != a.len)
+ return (int) a.len - (int) len;
- return memcmp (a->bytes, bytes, len);
+ return memcmp (a.bytes, bytes, len);
}
static inline int cmp (const void *pa, const void *pb)
{
hb_string_t *a = (hb_string_t *) pa;
hb_string_t *b = (hb_string_t *) pb;
- return b->cmp (a);
+ return b->cmp (*a);
}
const char *bytes;
diff --git a/src/hb-sort-r.hh b/src/hb-sort-r.hh
index 371a12b5..7458b4bb 100644
--- a/src/hb-sort-r.hh
+++ b/src/hb-sort-r.hh
@@ -33,7 +33,7 @@
static inline void *
hb_bsearch_r(const void *key, const void *base,
size_t nmemb, size_t size,
- int (*compar)(const void *_a, const void *_b, const void *_arg),
+ int (*compar)(const void *_key, const void *_item, void *_arg),
void *arg)
{
int min = 0, max = (int) nmemb - 1;
commit 6c738f353ec4ab5974414fbb8ff1fb9383c4bde6
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Mon Oct 30 12:21:44 2017 -0600
Make string-array return hb_string_t
diff --git a/src/hb-ot-post-table.hh b/src/hb-ot-post-table.hh
index 090d3ccb..7e164cba 100644
--- a/src/hb-ot-post-table.hh
+++ b/src/hb-ot-post-table.hh
@@ -117,7 +117,7 @@ struct post
if (glyph >= NUM_FORMAT1_NAMES)
return hb_string_t ();
- return hb_string_t (format1_names (glyph), strlen (format1_names (glyph)));
+ return format1_names (glyph);
}
if (version != 0x00020000 || glyph >= glyphNameIndex->len)
@@ -125,7 +125,7 @@ struct post
unsigned int index = glyphNameIndex->array[glyph];
if (index < NUM_FORMAT1_NAMES)
- return hb_string_t (format1_names (index), strlen (format1_names (index)));
+ return format1_names (index);
index -= NUM_FORMAT1_NAMES;
if (index >= index_to_offset.len)
@@ -163,19 +163,6 @@ struct post
if (unlikely (!len))
return false;
- if (version == 0x00010000)
- {
- for (int i = 0; i < NUM_FORMAT1_NAMES; i++)
- {
- if (strncmp (name, format1_names (i), len) == 0 && format1_names (i)[len] == '\0')
- {
- *glyph = i;
- return true;
- }
- }
- return false;
- }
-
/* TODO format2 */
return false;
}
diff --git a/src/hb-string-array.hh b/src/hb-string-array.hh
index afad5d75..285b4b53 100644
--- a/src/hb-string-array.hh
+++ b/src/hb-string-array.hh
@@ -40,6 +40,10 @@
static const union HB_STRING_ARRAY_TYPE_NAME {
struct {
+/* I like to avoid storing the nul-termination byte since we don't need it,
+ * but C++ does not allow that.
+ * https://stackoverflow.com/questions/28433862/why-initializer-string-for-array-of-chars-is-too-long-compiles-fine-in-c-not
+ */
#define _S(s) char HB_PASTE (str, __LINE__)[sizeof (s)];
#include HB_STRING_ARRAY_LIST
#undef _S
@@ -59,12 +63,15 @@ static const unsigned int HB_STRING_ARRAY_OFFS_NAME[] =
#define _S(s) offsetof (union HB_STRING_ARRAY_TYPE_NAME, st.HB_PASTE(str, __LINE__)),
#include HB_STRING_ARRAY_LIST
#undef _S
+ sizeof (HB_STRING_ARRAY_TYPE_NAME)
};
-static inline const char *
+static inline hb_string_t
HB_STRING_ARRAY_NAME (unsigned int i)
{
- return HB_STRING_ARRAY_POOL_NAME.str + HB_STRING_ARRAY_OFFS_NAME[i];
+ assert (i < ARRAY_LENGTH (HB_STRING_ARRAY_OFFS_NAME) - 1);
+ return hb_string_t (HB_STRING_ARRAY_POOL_NAME.str + HB_STRING_ARRAY_OFFS_NAME[i],
+ HB_STRING_ARRAY_OFFS_NAME[i + 1] - HB_STRING_ARRAY_OFFS_NAME[i] - 1);
}
#undef HB_STRING_ARRAY_TYPE_NAME
commit e1a37f3db4f2364e98ff057209a94aa9b23e5c9d
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Mon Oct 30 11:42:28 2017 -0600
Add hb_string_t
diff --git a/src/hb-ot-post-table.hh b/src/hb-ot-post-table.hh
index 275988e3..090d3ccb 100644
--- a/src/hb-ot-post-table.hh
+++ b/src/hb-ot-post-table.hh
@@ -110,48 +110,39 @@ struct post
index_to_offset.finish ();
}
- struct str_t
- {
- inline str_t (void) : bytes (nullptr), len (0) {}
- inline str_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {}
-
- const char *bytes;
- unsigned int len;
- };
-
- inline str_t _find_glyph_name (hb_codepoint_t glyph) const
+ inline hb_string_t _find_glyph_name (hb_codepoint_t glyph) const
{
if (version == 0x00010000)
{
if (glyph >= NUM_FORMAT1_NAMES)
- return str_t ();
+ return hb_string_t ();
- return str_t (format1_names (glyph), strlen (format1_names (glyph)));
+ return hb_string_t (format1_names (glyph), strlen (format1_names (glyph)));
}
if (version != 0x00020000 || glyph >= glyphNameIndex->len)
- return str_t ();
+ return hb_string_t ();
unsigned int index = glyphNameIndex->array[glyph];
if (index < NUM_FORMAT1_NAMES)
- return str_t (format1_names (index), strlen (format1_names (index)));
+ return hb_string_t (format1_names (index), strlen (format1_names (index)));
index -= NUM_FORMAT1_NAMES;
if (index >= index_to_offset.len)
- return str_t ();
+ return hb_string_t ();
unsigned int offset = index_to_offset.array[index];
const uint8_t *data = pool + offset;
unsigned int name_length = *data;
data++;
- return str_t ((const char *) data, name_length);
+ return hb_string_t ((const char *) data, name_length);
}
inline bool get_glyph_name (hb_codepoint_t glyph,
char *buf, unsigned int buf_len) const
{
- str_t s = _find_glyph_name (glyph);
+ hb_string_t s = _find_glyph_name (glyph);
if (!s.len)
return false;
if (!buf_len)
diff --git a/src/hb-private.hh b/src/hb-private.hh
index f6dbbe21..b88de08d 100644
--- a/src/hb-private.hh
+++ b/src/hb-private.hh
@@ -1137,4 +1137,31 @@ hb_options (void)
/* Size signifying variable-sized array */
#define VAR 1
+
+/* String type. */
+
+struct hb_string_t
+{
+ inline hb_string_t (void) : bytes (nullptr), len (0) {}
+ inline hb_string_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {}
+
+ inline int cmp (const hb_string_t *a) const
+ {
+ if (len != a->len)
+ return (int) a->len - (int) len;
+
+ return memcmp (a->bytes, bytes, len);
+ }
+ static inline int cmp (const void *pa, const void *pb)
+ {
+ hb_string_t *a = (hb_string_t *) pa;
+ hb_string_t *b = (hb_string_t *) pb;
+ return b->cmp (a);
+ }
+
+ const char *bytes;
+ unsigned int len;
+};
+
+
#endif /* HB_PRIVATE_HH */
commit 21ac5678583259e673d961a26fadaad2bf33f1f8
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Mon Oct 30 09:48:09 2017 -0600
Fix tests
diff --git a/src/check-includes.sh b/src/check-includes.sh
index 37e372d5..fd565da5 100755
--- a/src/check-includes.sh
+++ b/src/check-includes.sh
@@ -34,7 +34,7 @@ grep -v 'hb-private[.]hh:' |
grep . >&2 && stat=1
-echo 'Checking that there is no #include <hb.*.h>'
+echo 'Checking that there is no #include <hb-*.h>'
for x in $HBHEADERS $HBSOURCES; do
test -f "$srcdir/$x" && x="$srcdir/$x"
grep '#.*\<include\>.*<.*hb' "$x" /dev/null >&2 && stat=1
diff --git a/src/hb-sort-r.hh b/src/hb-sort-r.hh
index 80cd3c80..371a12b5 100644
--- a/src/hb-sort-r.hh
+++ b/src/hb-sort-r.hh
@@ -1,8 +1,33 @@
-/* Isaac Turner 29 April 2014 Public Domain */
+/*
+ * Copyright © 2017 Google, Inc.
+ *
+ * This is part of HarfBuzz, a text shaping library.
+ *
+ * Permission is hereby granted, without written agreement and without
+ * license or royalty fees, to use, copy, modify, and distribute this
+ * software and its documentation for any purpose, provided that the
+ * above copyright notice and the following two paragraphs appear in
+ * all copies of this software.
+ *
+ * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
+ * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ *
+ * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
+ * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+ *
+ * Google Author(s): Behdad Esfahbod
+ */
+
#ifndef HB_SORT_R_HH
#define HB_SORT_R_HH
-#include <hb-private.hh>
+#include "hb-private.hh"
static inline void *
@@ -30,6 +55,9 @@ hb_bsearch_r(const void *key, const void *base,
/* From https://github.com/noporpoise/sort_r */
+
+/* Isaac Turner 29 April 2014 Public Domain */
+
/*
hb_sort_r function to be exported.
commit 0f8b5aa1bc2c831044a35fc8e52df58652cec86b
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Mon Oct 30 09:46:36 2017 -0600
[post] Minor; towards implementing get_glyph_from_name()
diff --git a/src/hb-ot-post-table.hh b/src/hb-ot-post-table.hh
index 94d1e429..275988e3 100644
--- a/src/hb-ot-post-table.hh
+++ b/src/hb-ot-post-table.hh
@@ -110,50 +110,56 @@ struct post
index_to_offset.finish ();
}
- inline bool get_glyph_name (hb_codepoint_t glyph,
- char *buf, unsigned int buf_len) const
+ struct str_t
+ {
+ inline str_t (void) : bytes (nullptr), len (0) {}
+ inline str_t (const char *bytes_, unsigned int len_) : bytes (bytes_), len (len_) {}
+
+ const char *bytes;
+ unsigned int len;
+ };
+
+ inline str_t _find_glyph_name (hb_codepoint_t glyph) const
{
if (version == 0x00010000)
{
if (glyph >= NUM_FORMAT1_NAMES)
- return false;
+ return str_t ();
- if (!buf_len)
- return true;
- strncpy (buf, format1_names (glyph), buf_len);
- buf[buf_len - 1] = '\0';
- return true;
+ return str_t (format1_names (glyph), strlen (format1_names (glyph)));
}
- if (version != 0x00020000)
- return false;
-
- if (glyph >= glyphNameIndex->len)
- return false;
+ if (version != 0x00020000 || glyph >= glyphNameIndex->len)
+ return str_t ();
unsigned int index = glyphNameIndex->array[glyph];
if (index < NUM_FORMAT1_NAMES)
- {
- if (!buf_len)
- return true;
- strncpy (buf, format1_names (index), buf_len);
- buf[buf_len - 1] = '\0';
- return true;
- }
+ return str_t (format1_names (index), strlen (format1_names (index)));
index -= NUM_FORMAT1_NAMES;
if (index >= index_to_offset.len)
- return false;
+ return str_t ();
unsigned int offset = index_to_offset.array[index];
const uint8_t *data = pool + offset;
unsigned int name_length = *data;
data++;
- if (unlikely (!name_length || buf_len <= name_length))
- return false;
- memcpy (buf, data, name_length);
- buf[name_length] = '\0';
+ return str_t ((const char *) data, name_length);
+ }
+
+ inline bool get_glyph_name (hb_codepoint_t glyph,
+ char *buf, unsigned int buf_len) const
+ {
+ str_t s = _find_glyph_name (glyph);
+ if (!s.len)
+ return false;
+ if (!buf_len)
+ return true;
+ if (buf_len <= s.len) /* What to do with truncation? Returning false for now. */
+ return false;
+ strncpy (buf, s.bytes, s.len);
+ buf[s.len] = '\0';
return true;
}
commit 977679f229a10868dc668294082bd82125e4fe48
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Sun Oct 29 17:33:32 2017 -0600
Add hb_bsearch_r()
diff --git a/src/hb-ot-post-table.hh b/src/hb-ot-post-table.hh
index 273a6d02..94d1e429 100644
--- a/src/hb-ot-post-table.hh
+++ b/src/hb-ot-post-table.hh
@@ -28,6 +28,7 @@
#define HB_OT_POST_TABLE_HH
#include "hb-open-type-private.hh"
+#include "hb-sort-r.hh"
#define HB_STRING_ARRAY_NAME format1_names
#define HB_STRING_ARRAY_LIST "hb-ot-post-macroman.hh"
diff --git a/src/hb-sort-r.hh b/src/hb-sort-r.hh
index 1b91b4da..80cd3c80 100644
--- a/src/hb-sort-r.hh
+++ b/src/hb-sort-r.hh
@@ -4,6 +4,31 @@
#include <hb-private.hh>
+
+static inline void *
+hb_bsearch_r(const void *key, const void *base,
+ size_t nmemb, size_t size,
+ int (*compar)(const void *_a, const void *_b, const void *_arg),
+ void *arg)
+{
+ int min = 0, max = (int) nmemb - 1;
+ while (min <= max)
+ {
+ int mid = (min + max) / 2;
+ const void *p = (const void *) (((const char *) base) + (mid * size));
+ int c = compar (key, p, arg);
+ if (c < 0)
+ max = mid - 1;
+ else if (c > 0)
+ min = mid + 1;
+ else
+ return (void *) p;
+ }
+ return NULL;
+}
+
+
+
/* From https://github.com/noporpoise/sort_r */
/*
commit 0712e915b4814e350aa1d833c1dee5010cdbd8f9
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Sun Oct 29 17:01:47 2017 -0600
Remove hb_compare_func_t
diff --git a/src/hb-ot-map-private.hh b/src/hb-ot-map-private.hh
index 105909a1..97b92cc9 100644
--- a/src/hb-ot-map-private.hh
+++ b/src/hb-ot-map-private.hh
@@ -63,8 +63,12 @@ struct hb_ot_map_t
unsigned short auto_zwj : 1;
hb_mask_t mask;
- static int cmp (const lookup_map_t *a, const lookup_map_t *b)
- { return a->index < b->index ? -1 : a->index > b->index ? 1 : 0; }
+ static int cmp (const void *pa, const void *pb)
+ {
+ const lookup_map_t *a = (const lookup_map_t *) pa;
+ const lookup_map_t *b = (const lookup_map_t *) pb;
+ return a->index < b->index ? -1 : a->index > b->index ? 1 : 0;
+ }
};
typedef void (*pause_func_t) (const struct hb_ot_shape_plan_t *plan, hb_font_t *font, hb_buffer_t *buffer);
@@ -210,9 +214,13 @@ struct hb_ot_map_builder_t
unsigned int default_value; /* for non-global features, what should the unset glyphs take */
unsigned int stage[2]; /* GSUB/GPOS */
- static int cmp (const feature_info_t *a, const feature_info_t *b)
- { return (a->tag != b->tag) ? (a->tag < b->tag ? -1 : 1) :
- (a->seq < b->seq ? -1 : a->seq > b->seq ? 1 : 0); }
+ static int cmp (const void *pa, const void *pb)
+ {
+ const feature_info_t *a = (const feature_info_t *) pa;
+ const feature_info_t *b = (const feature_info_t *) pb;
+ return (a->tag != b->tag) ? (a->tag < b->tag ? -1 : 1) :
+ (a->seq < b->seq ? -1 : a->seq > b->seq ? 1 : 0);
+ }
};
struct stage_info_t {
diff --git a/src/hb-ot-name-table.hh b/src/hb-ot-name-table.hh
index 870f1233..731a0dbb 100644
--- a/src/hb-ot-name-table.hh
+++ b/src/hb-ot-name-table.hh
@@ -89,7 +89,7 @@ struct name
key.encodingID.set (encoding_id);
key.languageID.set (language_id);
key.nameID.set (name_id);
- NameRecord *match = (NameRecord *) bsearch (&key, nameRecord, count, sizeof (nameRecord[0]), (hb_compare_func_t) NameRecord::cmp);
+ NameRecord *match = (NameRecord *) bsearch (&key, nameRecord, count, sizeof (nameRecord[0]), NameRecord::cmp);
if (!match)
return 0;
diff --git a/src/hb-ot-tag.cc b/src/hb-ot-tag.cc
index 64c6ce0a..dbec68c7 100644
--- a/src/hb-ot-tag.cc
+++ b/src/hb-ot-tag.cc
@@ -879,9 +879,11 @@ static const LangTagLong ot_languages_zh[] = {
};
static int
-lang_compare_first_component (const char *a,
- const char *b)
+lang_compare_first_component (const void *pa,
+ const void *pb)
{
+ const char *a = (const char *) pa;
+ const char *b = (const char *) pb;
unsigned int da, db;
const char *p;
@@ -972,7 +974,7 @@ hb_ot_tag_from_language (hb_language_t language)
const LangTag *lang_tag;
lang_tag = (LangTag *) bsearch (lang_str, ot_languages,
ARRAY_LENGTH (ot_languages), sizeof (LangTag),
- (hb_compare_func_t) lang_compare_first_component);
+ lang_compare_first_component);
if (lang_tag)
return lang_tag->tag;
}
diff --git a/src/hb-ot-var-mvar-table.hh b/src/hb-ot-var-mvar-table.hh
index 3cb74984..96bc77f3 100644
--- a/src/hb-ot-var-mvar-table.hh
+++ b/src/hb-ot-var-mvar-table.hh
@@ -77,7 +77,7 @@ struct MVAR
const VariationValueRecord *record;
record = (VariationValueRecord *) bsearch (&tag, values,
valueRecordCount, valueRecordSize,
- (hb_compare_func_t) tag_compare);
+ tag_compare);
if (!record)
return 0.;
@@ -85,8 +85,12 @@ struct MVAR
}
protected:
- static inline int tag_compare (const hb_tag_t *a, const Tag *b)
- { return b->cmp (*a); }
+ static inline int tag_compare (const void *pa, const void *pb)
+ {
+ const hb_tag_t *a = (const hb_tag_t *) pa;
+ const Tag *b = (const Tag *) pb;
+ return b->cmp (*a);
+ }
protected:
FixedVersion<>version; /* Version of the metrics variation table
diff --git a/src/hb-private.hh b/src/hb-private.hh
index ab6511dc..f6dbbe21 100644
--- a/src/hb-private.hh
+++ b/src/hb-private.hh
@@ -372,11 +372,6 @@ _hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size)
}
-/* Type of bsearch() / qsort() compare function */
-typedef int (*hb_compare_func_t) (const void *, const void *);
-
-
-
/* arrays and maps */
@@ -480,12 +475,12 @@ struct hb_prealloced_array_t
inline void qsort (void)
{
- ::qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
+ ::qsort (array, len, sizeof (Type), Type::cmp);
}
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), Type::cmp);
}
template <typename T>
commit 538da7496d70c86b41070ecf52592e52920d8808
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Sun Oct 29 16:38:58 2017 -0600
Add hb-sort-r, a portable qsort_r() replacement
diff --git a/src/Makefile.sources b/src/Makefile.sources
index d162ebef..57875213 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -40,6 +40,7 @@ HB_BASE_sources = \
hb-shaper-impl-private.hh \
hb-shaper-private.hh \
hb-shaper.cc \
+ hb-sort-r.hh \
hb-string-array.hh \
hb-unicode-private.hh \
hb-unicode.cc \
diff --git a/src/hb-sort-r.hh b/src/hb-sort-r.hh
new file mode 100644
index 00000000..1b91b4da
--- /dev/null
+++ b/src/hb-sort-r.hh
@@ -0,0 +1,227 @@
+/* Isaac Turner 29 April 2014 Public Domain */
+#ifndef HB_SORT_R_HH
+#define HB_SORT_R_HH
+
+#include <hb-private.hh>
+
+/* From https://github.com/noporpoise/sort_r */
+/*
+
+hb_sort_r function to be exported.
+
+Parameters:
+ base is the array to be sorted
+ nel is the number of elements in the array
+ width is the size in bytes of each element of the array
+ compar is the comparison function
+ arg is a pointer to be passed to the comparison function
+
+void hb_sort_r(void *base, size_t nel, size_t width,
+ int (*compar)(const void *_a, const void *_b, void *_arg),
+ void *arg);
+
+*/
+
+#define _SORT_R_INLINE inline
+
+#if (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || \
+ defined __FreeBSD__ || defined __DragonFly__)
+# define _SORT_R_BSD
+#elif (defined _GNU_SOURCE || defined __gnu_hurd__ || defined __GNU__ || \
+ defined __linux__ || defined __MINGW32__ || defined __GLIBC__)
+# define _SORT_R_LINUX
+#elif (defined _WIN32 || defined _WIN64 || defined __WINDOWS__)
+# define _SORT_R_WINDOWS
+# undef _SORT_R_INLINE
+# define _SORT_R_INLINE __inline
+#else
+ /* Using our own recursive quicksort sort_r_simple() */
+#endif
+
+#if (defined NESTED_QSORT && NESTED_QSORT == 0)
+# undef NESTED_QSORT
+#endif
+
+/* swap a, b iff a>b */
+/* __restrict is same as restrict but better support on old machines */
+static _SORT_R_INLINE int sort_r_cmpswap(char *__restrict a, char *__restrict b, size_t w,
+ int (*compar)(const void *_a, const void *_b,
+ void *_arg),
+ void *arg)
+{
+ char tmp, *end = a+w;
+ if(compar(a, b, arg) > 0) {
+ for(; a < end; a++, b++) { tmp = *a; *a = *b; *b = tmp; }
+ return 1;
+ }
+ return 0;
+}
+
+/* Implement recursive quicksort ourselves */
+/* Note: quicksort is not stable, equivalent values may be swapped */
+static _SORT_R_INLINE void sort_r_simple(void *base, size_t nel, size_t w,
+ int (*compar)(const void *_a, const void *_b,
+ void *_arg),
+ void *arg)
+{
+ char *b = (char *)base, *end = b + nel*w;
+ if(nel < 7) {
+ /* Insertion sort for arbitrarily small inputs */
+ char *pi, *pj;
+ for(pi = b+w; pi < end; pi += w) {
+ for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,arg); pj -= w) {}
+ }
+ }
+ else
+ {
+ /* nel > 6; Quicksort */
+
+ /* Use median of first, middle and last items as pivot */
+ char *x, *y, *xend, ch;
+ char *pl, *pr;
+ char *last = b+w*(nel-1), *tmp;
+ char *l[3];
+ l[0] = b;
+ l[1] = b+w*(nel/2);
+ l[2] = last;
+
+ if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; }
+ if(compar(l[1],l[2],arg) > 0) {
+ tmp=l[1]; l[1]=l[2]; l[2]=tmp; /* swap(l[1],l[2]) */
+ if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; }
+ }
+
+ /* swap l[id], l[2] to put pivot as last element */
+ for(x = l[1], y = last, xend = x+w; x<xend; x++, y++) {
+ ch = *x; *x = *y; *y = ch;
+ }
+
+ pl = b;
+ pr = last;
+
+ while(pl < pr) {
+ for(; pl < pr; pl += w) {
+ if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
+ pr -= w; /* pivot now at pl */
+ break;
+ }
+ }
+ for(; pl < pr; pr -= w) {
+ if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
+ pl += w; /* pivot now at pr */
+ break;
+ }
+ }
+ }
+
+ sort_r_simple(b, (pl-b)/w, w, compar, arg);
+ sort_r_simple(pl+w, (end-(pl+w))/w, w, compar, arg);
+ }
+}
+
+
+#if defined NESTED_QSORT
+
+ static _SORT_R_INLINE void hb_sort_r(void *base, size_t nel, size_t width,
+ int (*compar)(const void *_a, const void *_b,
+ void *aarg),
+ void *arg)
+ {
+ int nested_cmp(const void *a, const void *b)
+ {
+ return compar(a, b, arg);
+ }
+
+ qsort(base, nel, width, nested_cmp);
+ }
+
+#else /* !NESTED_QSORT */
+
+ /* Declare structs and functions */
+
+ #if defined _SORT_R_BSD
+
+ /* Ensure qsort_r is defined */
+ extern void qsort_r(void *base, size_t nel, size_t width, void *thunk,
+ int (*compar)(void *_thunk, const void *_a, const void *_b));
+
+ #endif
+
+ #if defined _SORT_R_BSD || defined _SORT_R_WINDOWS
+
+ /* BSD (qsort_r), Windows (qsort_s) require argument swap */
+
+ struct sort_r_data
+ {
+ void *arg;
+ int (*compar)(const void *_a, const void *_b, void *_arg);
+ };
+
+ static _SORT_R_INLINE int sort_r_arg_swap(void *s, const void *a, const void *b)
+ {
+ struct sort_r_data *ss = (struct sort_r_data*)s;
+ return (ss->compar)(a, b, ss->arg);
+ }
+
+ #endif
+
+ #if defined _SORT_R_LINUX
+
+#if 0 /* BE: To avoid redeclaration warning. */
+ typedef int(* __compar_d_fn_t)(const void *, const void *, void *);
+ extern void qsort_r(void *base, size_t nel, size_t width,
+ __compar_d_fn_t __compar, void *arg)
+ __attribute__((nonnull (1, 4)));
+#endif
+
+ #endif
+
+ /* implementation */
+
+ static _SORT_R_INLINE void hb_sort_r(void *base, size_t nel, size_t width,
+ int (*compar)(const void *_a, const void *_b, void *_arg),
+ void *arg)
+ {
+ #if defined _SORT_R_LINUX
+
+ #if defined __GLIBC__ && ((__GLIBC__ < 2) || (__GLIBC__ == 2 && __GLIBC_MINOR__ < 8))
+
+ /* no qsort_r in glibc before 2.8, need to use nested qsort */
+ sort_r_simple(base, nel, width, compar, arg);
+
+ #else
+
+ qsort_r(base, nel, width, compar, arg);
+
+ #endif
+
+ #elif defined _SORT_R_BSD
+
+ struct sort_r_data tmp;
+ tmp.arg = arg;
+ tmp.compar = compar;
+ qsort_r(base, nel, width, &tmp, sort_r_arg_swap);
+
+ #elif defined _SORT_R_WINDOWS
+
+ struct sort_r_data tmp;
+ tmp.arg = arg;
+ tmp.compar = compar;
+ qsort_s(base, nel, width, sort_r_arg_swap, &tmp);
+
+ #else
+
+ /* Fall back to our own quicksort implementation */
+ sort_r_simple(base, nel, width, compar, arg);
+
+ #endif
+ }
+
+#endif /* !NESTED_QSORT */
+
+#undef _SORT_R_INLINE
+#undef _SORT_R_WINDOWS
+#undef _SORT_R_LINUX
+#undef _SORT_R_BSD
+
+#endif /* HB_SORT_R_HH */
More information about the HarfBuzz
mailing list