diff options
Diffstat (limited to 'src/3rdparty/harfbuzz-ng/src/hb-bit-set.hh')
-rw-r--r-- | src/3rdparty/harfbuzz-ng/src/hb-bit-set.hh | 161 |
1 files changed, 109 insertions, 52 deletions
diff --git a/src/3rdparty/harfbuzz-ng/src/hb-bit-set.hh b/src/3rdparty/harfbuzz-ng/src/hb-bit-set.hh index fcaff9f3be..475b07b810 100644 --- a/src/3rdparty/harfbuzz-ng/src/hb-bit-set.hh +++ b/src/3rdparty/harfbuzz-ng/src/hb-bit-set.hh @@ -38,7 +38,7 @@ struct hb_bit_set_t hb_bit_set_t () = default; ~hb_bit_set_t () = default; - hb_bit_set_t (const hb_bit_set_t& other) : hb_bit_set_t () { set (other); } + hb_bit_set_t (const hb_bit_set_t& other) : hb_bit_set_t () { set (other, true); } hb_bit_set_t ( hb_bit_set_t&& other) : hb_bit_set_t () { hb_swap (*this, other); } hb_bit_set_t& operator= (const hb_bit_set_t& other) { set (other); return *this; } hb_bit_set_t& operator= (hb_bit_set_t&& other) { hb_swap (*this, other); return *this; } @@ -78,25 +78,36 @@ struct hb_bit_set_t bool successful = true; /* Allocations successful */ mutable unsigned int population = 0; - mutable unsigned int last_page_lookup = 0; + mutable hb_atomic_int_t last_page_lookup = 0; hb_sorted_vector_t<page_map_t> page_map; hb_vector_t<page_t> pages; void err () { if (successful) successful = false; } /* TODO Remove */ bool in_error () const { return !successful; } - bool resize (unsigned int count) + bool resize (unsigned int count, bool clear = true, bool exact_size = false) { if (unlikely (!successful)) return false; - if (unlikely (!pages.resize (count) || !page_map.resize (count))) + + if (pages.length == 0 && count == 1) + exact_size = true; // Most sets are small and local + + if (unlikely (!pages.resize (count, clear, exact_size) || !page_map.resize (count, clear, exact_size))) { - pages.resize (page_map.length); + pages.resize (page_map.length, clear, exact_size); successful = false; return false; } return true; } + void alloc (unsigned sz) + { + sz >>= (page_t::PAGE_BITS_LOG_2 - 1); + pages.alloc (sz); + page_map.alloc (sz); + } + void reset () { successful = true; @@ -119,6 +130,14 @@ struct hb_bit_set_t } explicit operator bool () const { return !is_empty (); } + uint32_t hash () const + { + uint32_t h = 0; + for (auto &map : page_map) + h = h * 31 + hb_hash (map.major) + hb_hash (pages[map.index]); + return h; + } + private: void dirty () { population = UINT_MAX; } public: @@ -315,10 +334,8 @@ struct hb_bit_set_t } /* Has interface. */ - static constexpr bool SENTINEL = false; - typedef bool value_t; - value_t operator [] (hb_codepoint_t k) const { return get (k); } - bool has (hb_codepoint_t k) const { return (*this)[k] != SENTINEL; } + bool operator [] (hb_codepoint_t k) const { return get (k); } + bool has (hb_codepoint_t k) const { return (*this)[k]; } /* Predicate. */ bool operator () (hb_codepoint_t k) const { return has (k); } @@ -333,23 +350,22 @@ struct hb_bit_set_t hb_codepoint_t c = first - 1; return next (&c) && c <= last; } - void set (const hb_bit_set_t &other) + void set (const hb_bit_set_t &other, bool exact_size = false) { if (unlikely (!successful)) return; unsigned int count = other.pages.length; - if (unlikely (!resize (count))) + if (unlikely (!resize (count, false, exact_size))) return; population = other.population; - /* TODO switch to vector operator =. */ - hb_memcpy ((void *) pages, (const void *) other.pages, count * pages.item_size); - hb_memcpy ((void *) page_map, (const void *) other.page_map, count * page_map.item_size); + page_map = other.page_map; + pages = other.pages; } bool is_equal (const hb_bit_set_t &other) const { if (has_population () && other.has_population () && - get_population () != other.get_population ()) + population != other.population) return false; unsigned int na = pages.length; @@ -377,7 +393,7 @@ struct hb_bit_set_t bool is_subset (const hb_bit_set_t &larger_set) const { if (has_population () && larger_set.has_population () && - get_population () != larger_set.get_population ()) + population > larger_set.population) return false; uint32_t spi = 0; @@ -410,7 +426,7 @@ struct hb_bit_set_t private: bool allocate_compact_workspace (hb_vector_t<unsigned>& workspace) { - if (unlikely (!workspace.resize (pages.length))) + if (unlikely (!workspace.resize_exact (pages.length))) { successful = false; return false; @@ -451,12 +467,10 @@ struct hb_bit_set_t } public: - template <typename Op> - void process (const Op& op, const hb_bit_set_t &other) + void process_ (hb_bit_page_t::vector_t (*op) (const hb_bit_page_t::vector_t &, const hb_bit_page_t::vector_t &), + bool passthru_left, bool passthru_right, + const hb_bit_set_t &other) { - const bool passthru_left = op (1, 0); - const bool passthru_right = op (0, 1); - if (unlikely (!successful)) return; dirty (); @@ -528,21 +542,21 @@ struct hb_bit_set_t b = nb; for (; a && b; ) { - if (page_map[a - 1].major == other.page_map[b - 1].major) + if (page_map.arrayZ[a - 1].major == other.page_map.arrayZ[b - 1].major) { a--; b--; count--; - page_map[count] = page_map[a]; + page_map.arrayZ[count] = page_map.arrayZ[a]; page_at (count).v = op (page_at (a).v, other.page_at (b).v); } - else if (page_map[a - 1].major > other.page_map[b - 1].major) + else if (page_map.arrayZ[a - 1].major > other.page_map.arrayZ[b - 1].major) { a--; if (passthru_left) { count--; - page_map[count] = page_map[a]; + page_map.arrayZ[count] = page_map.arrayZ[a]; } } else @@ -551,8 +565,8 @@ struct hb_bit_set_t if (passthru_right) { count--; - page_map[count].major = other.page_map[b].major; - page_map[count].index = next_page++; + page_map.arrayZ[count].major = other.page_map.arrayZ[b].major; + page_map.arrayZ[count].index = next_page++; page_at (count).v = other.page_at (b).v; } } @@ -562,20 +576,29 @@ struct hb_bit_set_t { a--; count--; - page_map[count] = page_map [a]; + page_map.arrayZ[count] = page_map.arrayZ[a]; } if (passthru_right) while (b) { b--; count--; - page_map[count].major = other.page_map[b].major; - page_map[count].index = next_page++; + page_map.arrayZ[count].major = other.page_map.arrayZ[b].major; + page_map.arrayZ[count].index = next_page++; page_at (count).v = other.page_at (b).v; } assert (!count); resize (newCount); } + template <typename Op> + static hb_bit_page_t::vector_t + op_ (const hb_bit_page_t::vector_t &a, const hb_bit_page_t::vector_t &b) + { return Op{} (a, b); } + template <typename Op> + void process (const Op& op, const hb_bit_set_t &other) + { + process_ (op_<Op>, op (1, 0), op (0, 1), other); + } void union_ (const hb_bit_set_t &other) { process (hb_bitwise_or, other); } void intersect (const hb_bit_set_t &other) { process (hb_bitwise_and, other); } @@ -584,8 +607,6 @@ struct hb_bit_set_t bool next (hb_codepoint_t *codepoint) const { - // TODO: this should be merged with prev() as both implementations - // are very similar. if (unlikely (*codepoint == INVALID)) { *codepoint = get_min (); return *codepoint != INVALID; @@ -619,7 +640,7 @@ struct hb_bit_set_t for (; i < page_map.length; i++) { - const page_map_t ¤t = page_map.arrayZ[i]; + const page_map_t ¤t = page_map_array[i]; hb_codepoint_t m = pages_array[current.index].get_min (); if (m != INVALID) { @@ -642,21 +663,21 @@ struct hb_bit_set_t page_map_t map = {get_major (*codepoint), 0}; unsigned int i; page_map.bfind (map, &i, HB_NOT_FOUND_STORE_CLOSEST); - if (i < page_map.length && page_map[i].major == map.major) + if (i < page_map.length && page_map.arrayZ[i].major == map.major) { - if (pages[page_map[i].index].previous (codepoint)) + if (pages[page_map.arrayZ[i].index].previous (codepoint)) { - *codepoint += page_map[i].major * page_t::PAGE_BITS; + *codepoint += page_map.arrayZ[i].major * page_t::PAGE_BITS; return true; } } i--; for (; (int) i >= 0; i--) { - hb_codepoint_t m = pages[page_map[i].index].get_max (); + hb_codepoint_t m = pages.arrayZ[page_map.arrayZ[i].index].get_max (); if (m != INVALID) { - *codepoint = page_map[i].major * page_t::PAGE_BITS + m; + *codepoint = page_map.arrayZ[i].major * page_t::PAGE_BITS + m; return true; } } @@ -874,8 +895,20 @@ struct hb_bit_set_t page_t *page_for (hb_codepoint_t g, bool insert = false) { - page_map_t map = {get_major (g), pages.length}; - unsigned int i; + unsigned major = get_major (g); + + /* The extra page_map length is necessary; can't just rely on vector here, + * since the next check would be tricked because a null page also has + * major==0, which we can't distinguish from an actualy major==0 page... */ + unsigned i = last_page_lookup; + if (likely (i < page_map.length)) + { + auto &cached_page = page_map.arrayZ[i]; + if (cached_page.major == major) + return &pages.arrayZ[cached_page.index]; + } + + page_map_t map = {major, pages.length}; if (!page_map.bfind (map, &i, HB_NOT_FOUND_STORE_CLOSEST)) { if (!insert) @@ -884,24 +917,48 @@ struct hb_bit_set_t if (unlikely (!resize (pages.length + 1))) return nullptr; - pages[map.index].init0 (); - memmove (page_map + i + 1, - page_map + i, + pages.arrayZ[map.index].init0 (); + memmove (page_map.arrayZ + i + 1, + page_map.arrayZ + i, (page_map.length - 1 - i) * page_map.item_size); page_map[i] = map; } - return &pages[page_map[i].index]; + + last_page_lookup = i; + return &pages.arrayZ[page_map.arrayZ[i].index]; } const page_t *page_for (hb_codepoint_t g) const { - page_map_t key = {get_major (g)}; - const page_map_t *found = page_map.bsearch (key); - if (found) - return &pages[found->index]; - return nullptr; + unsigned major = get_major (g); + + /* The extra page_map length is necessary; can't just rely on vector here, + * since the next check would be tricked because a null page also has + * major==0, which we can't distinguish from an actualy major==0 page... */ + unsigned i = last_page_lookup; + if (likely (i < page_map.length)) + { + auto &cached_page = page_map.arrayZ[i]; + if (cached_page.major == major) + return &pages.arrayZ[cached_page.index]; + } + + page_map_t key = {major}; + if (!page_map.bfind (key, &i)) + return nullptr; + + last_page_lookup = i; + return &pages.arrayZ[page_map[i].index]; + } + page_t &page_at (unsigned int i) + { + assert (i < page_map.length); + return pages.arrayZ[page_map.arrayZ[i].index]; + } + const page_t &page_at (unsigned int i) const + { + assert (i < page_map.length); + return pages.arrayZ[page_map.arrayZ[i].index]; } - page_t &page_at (unsigned int i) { return pages[page_map[i].index]; } - const page_t &page_at (unsigned int i) const { return pages[page_map[i].index]; } unsigned int get_major (hb_codepoint_t g) const { return g >> page_t::PAGE_BITS_LOG_2; } unsigned int page_remainder (hb_codepoint_t g) const { return g & page_t::PAGE_BITMASK; } hb_codepoint_t major_start (unsigned int major) const { return major << page_t::PAGE_BITS_LOG_2; } |