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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 */
_______________________________________________ HarfBuzz mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/harfbuzz
