kc3-lang/harfbuzz/src/hb-map.hh

---

src/hb-map.hh

Branch - branch -main

---

Log

Author	Commit	Date	CI	Message
	4a26e289	2025-09-30T15:31:04		Add `hb_ot_layout_lookup_collect_glyph_alternates()` (#5367) * [map] Massage operator << overloads * [ot-layout] Add +hb_ot_layout_lookup_collect_glyph_alternates To collect all glyph mapping from SingleSubst or AlternateSubst lookups in one call. Needed by FreeType autohinter for performance. New API: +hb_ot_layout_lookup_collect_glyph_alternates() * [layout] Change hb_ot_layout_lookup_collect_glyph_alternates() API https://github.com/harfbuzz/harfbuzz/pull/5367#discussion_r2149019638
	2be836c1	2025-09-17T00:31:50		Revert "[instancer] Preallocate coordinate maps from alloc pool as well" This reverts commit 3f71afe7605cdc7260990f8925e6ed49521fe728. Slowed things down.
	3f71afe7	2025-09-17T00:22:39		[instancer] Preallocate coordinate maps from alloc pool as well
	e42714cf	2025-09-15T19:05:38		[iup] Reuse bit-set allocs
	e310f811	2025-09-15T00:58:07		[instancer/gvar] Speed up hash lookup-set
	20457df5	2025-09-14T16:05:29		[map] Tune for small maps
	90ea408e	2025-09-13T18:18:08		[map] Speed up copying of trivially-assignable types
	fd282dcf	2025-09-13T17:56:34		[map] Speed up operator= for trivial item types
	e5139c51	2024-10-21T12:54:56		bug fix in hashmap get_with_hash()
	3cfdbd67	2024-02-16T23:41:55		Use `noexcept` on swap, move constructors, etc.
	6a3ca373	2023-11-13T16:36:32		[map] Optimize storage Such that population isn't a bitfield as we access it often.
	d46cd93b	2023-11-10T14:36:37		[map] Speed up copy-constructor
	e7879d6c	2023-11-10T14:13:20		[map] Micro-optimize destruction
	29d49ece	2023-11-01T15:55:47		[vector] Introduce realloc_moves tag Some types (even aggregate) can be moved using realloc(). Extend the fast path to hb_hashmap and tuple_delta_t.
	7cb7a799	2023-09-28T09:24:06		[map] Fix undefined integer-overflow Fixes https://oss-fuzz.com/testcase-detail/5814850435284992
	69da5aae	2023-09-22T21:27:12		Added minor fixes to build without errors with gcc 4.9.2
	06ff3bcb	2023-08-15T14:41:18		[COLR,glyf] Use map instead of set for tracking current glyphs / layers
	5690840c	2023-07-26T09:53:32		[map] Another try at fixing archaic clang Fixes (?) https://github.com/harfbuzz/harfbuzz/issues/4138
	1fc128f6	2023-06-26T18:34:27		Replace a few memset/memcpy's with hb_ equivalents
	393f0f9f	2023-06-25T18:14:56		[map] Rename resize() to alloc() Better matches the functionality, and hb_vector_t.
	be0cec28	2023-06-25T16:01:13		[map] Micro-optimize iteration Make is_real() faster (removes a shift). is_used() gets inlined so is not slowed down by this change.
	1902f6cc	2023-06-23T13:21:21		[map] Inline an accessor function
	43d2ced8	2023-06-23T13:16:51		[map] Minor remove a conditional
	817236dc	2023-06-23T13:12:40		[map] Speed up is_real
	cb5f4d0c	2023-06-22T18:46:33		[subset-plan] Avoid a copy in freeing name-table-overrides
	280edb90	2023-06-22T17:07:31		[map] Use a variable instead of function for is_trivial
	0aa939e7	2023-06-22T17:05:55		[map] Add a constexpr
	cf386e8c	2023-06-22T17:02:10		[map] Speed up resize()
	0f0b3bee	2023-06-08T11:13:33		[map] Fix use-after-move issue
	e0b60bd0	2023-06-07T17:25:47		[subset/cff1] Speed up remap_sids
	0364c69e	2023-06-07T15:52:18		[iter] Add has_fast_len Set iterators are not random_access, but have fast len().
	cc9651d5	2023-06-07T12:20:48		[map] Micro-optimize
	6a3fcc64	2023-06-03T16:38:18		[map] Don't call hash() if map is empty
	735d2496	2023-06-03T16:35:03		[map] Remove an unlikely Empty maps are common in some subsetting operations.
	ca27925d	2023-06-03T16:18:15		Use hb_codepoint_pair_t in more places
	c6368e01	2023-06-01T20:51:17		[map] Return const reference from operator() Like we do in operator[].
	4a93576b	2023-05-28T13:22:35		Revert "[map] Speedup for int types" This reverts commit c1b75f5ff0460274229801816265a0efe5731b3a. I was seeing very long chains (140) and a 17% slowdown in BM_subset/subset_codepoints/RobotoFlex-Variable.ttf/512 Bummer.
	c1b75f5f	2023-05-28T12:53:17		[map] Speedup for int types Since our int hash is now good, we don't need the modulo prime here, so forgo it. Major speedup: Comparing before to after Benchmark Time CPU Time Old Time New CPU Old CPU New ------------------------------------------------------------------------------------------------------------------- BM_MapInsert/16 -0.4136 -0.4137 6 4 6 4 BM_MapInsert/64 -0.4442 -0.4441 6 3 6 3 BM_MapInsert/512 -0.5382 -0.5383 8 4 8 4 BM_MapInsert/4096 -0.4160 -0.4162 8 5 8 5 BM_MapInsert/32768 -0.3256 -0.3258 12 8 12 8 BM_MapInsert/262144 -0.1723 -0.1727 11 10 11 9 BM_MapInsert/1048576 -0.2310 -0.2309 28 22 28 22 BM_MapLookup/16 -0.0247 -0.0247 3 3 3 3 BM_MapLookup/64 -0.1039 -0.1038 3 3 3 3 BM_MapLookup/512 -0.1076 -0.1079 4 3 4 3 BM_MapLookup/4096 -0.3729 -0.3732 9 6 9 6 BM_MapLookup/32768 +0.2467 +0.2468 9 12 9 12 BM_MapLookup/262144 -0.1862 -0.1868 14 11 14 11 BM_MapLookup/1048576 +0.1159 +0.1160 15 17 15 17 OVERALL_GEOMEAN -0.2414 -0.2416 0 0 0 0
	5abe7132	2023-05-26T15:56:30		[map] Resize map on long chain probes
	2655b760	2023-05-23T10:57:58		[map] Micro-optimize This shows a speedup.
	12b0680e	2023-05-23T10:49:41		[map] Fix set() This was broken in 2133aa2407657d0b3b4b73a4951c05ed26d055f2. We have to keep probing over tombstones.
	0270e3e9	2023-05-09T23:46:18		[map] Reinstate quadratic probing
	19b628bd	2023-05-09T23:40:07		Revert "[map] Implement Robinhood hashing" This reverts commit 705617856818056a44a627f340c91e335c57f310.
	18c3ba50	2023-05-09T22:44:22		[map] Implement Robinhood hashing Numbers are not improved though. :(
	2133aa24	2023-05-09T21:06:17		[map] Inline code for set()
	5bf5188e	2023-05-09T20:47:46		[map] Simplify del()
	2ffec3a6	2023-05-09T20:44:23		[map] Shuffle fetch_item
	1dc99128	2023-05-09T20:37:12		[map] Separate has() code from set() code
	2dd0803c	2023-05-09T20:35:09		[map] Downgrade from quadratic to linear probing
	49819767	2023-05-09T20:24:12		[map] Write get() in terms of has()
	abb92388	2023-05-09T10:54:54		Revert "[map] Adjust resizing criteria" This reverts commit 1fa4b415315257bdbae08e6539f2ca63423572e8.
	1fa4b415	2023-05-09T10:52:58		[map] Adjust resizing criteria
	b7a8d23b	2023-05-08T14:32:24		[map] Micro-optimize for hb_map_t
	a2efa5b4	2023-03-03T09:15:46		[map] Another try at fixing old Mac build https://github.com/harfbuzz/harfbuzz/issues/4138
	be64cae1	2023-03-02T09:50:38		[map] Another try at fixing old Mac builds Maybe fixes https://github.com/harfbuzz/harfbuzz/issues/4138
	67e01c12	2023-03-01T20:07:38		[map] Try to work around old Mac compiler bug Maybe fixes https://github.com/harfbuzz/harfbuzz/issues/4138
	8206569d	2023-01-11T13:24:50		[map] Remove hashmap create/destroy/vtable Unused now.
	9420966f	2023-01-05T10:17:24		[map] Fix next()
	35f46e74	2023-01-04T17:12:08		[map] Add hb_map_keys() and hb_map_values()
	4f607913	2023-01-04T13:58:46		[map] Add hb_map_update()
	ffafcf96	2023-01-04T12:55:59		[map] Add hb_map_next()
	5e713e99	2022-12-05T23:57:57		Revert "[map] Speed up is_real()" This reverts commit f5307c3ba8401fbaf9008705d7f8dfa7d28e944c. Found to slow down the benchmarks in some cases.
	f5307c3b	2022-12-04T11:54:16		[map] Speed up is_real()
	dbbb8e80	2022-12-04T11:13:39		Revert "[map] Add hb_map_filter_invalid" This reverts commit 8d7e92111786b21906157127c24b72b1e444e6e7. Surprisingly this slowed NotoNastaliqUrdu benchmark down by a couple percent instead of speeding it up.
	8d7e9211	2022-12-04T11:01:45		[map] Add hb_map_filter_invalid Use it in one place.
	d2a2670e	2022-11-28T19:42:27		[iter] Simplify has() interface implementations
	86a763c6	2022-11-21T20:53:44		[map] Make keys moveable
	cf20d2ec	2022-11-21T20:46:01		[map] Take const key
	3d1c76f7	2022-11-21T19:40:32		[serializer] Don't hash objects twice
	3ff8abf2	2022-11-18T19:35:49		Revert "[map] Allow std::move-ing keys into the map" This reverts commit f657ef7e57c889309c2d9d37934368ca255f9d5b. This breaks many compilers with messages like this: hb-subset-plan.hh:226: undefined reference to `OT::head::tableTag' I'm out of my depth re how to fix it.
	a3a218ed	2022-11-18T19:24:41		[map] Add a couple more sink interfaces
	f657ef7e	2022-11-18T19:17:03		[map] Allow std::move-ing keys into the map
	a1768ad8	2022-11-18T19:08:34		[map] Fix use of !=
	a9c6a20b	2022-11-18T18:29:12		[map] Support moving value in sink interface
	3ead9863	2022-11-18T16:43:47		[map] Add size()
	42db8be1	2022-11-18T16:41:50		[map] Minor remove if condition
	4ec70698	2022-11-18T16:39:30		[map] Rewrite hash() as dagger Somehow our daggers instead of for loop save size. I cannot pinpoint why, other than maybe not inlining.
	025a68cb	2022-11-18T16:33:04		[map] Optimize copy resizing logic
	f1d71687	2022-11-18T16:31:27		[map] Change bucket_for_hash() to item_for_hash()
	d012f9a9	2022-11-18T16:29:06		[map] Change bucket_for() to item_for()
	81a57300	2022-11-17T16:59:36		[map] Optimize storage
	ae080bf2	2022-11-17T16:34:58		[map] Initialize key and value explicitly If they are of int time they won't be initialized otherwise.
	ff0bb748	2022-11-17T16:17:37		[map] Call item_t constructor/destructor directly
	5c887159	2022-11-17T16:14:16		[map] Add item_t.destruct()
	7f830408	2022-11-17T16:10:37		[map] Simplify (de)construction of item_t
	99103bd9	2022-11-17T15:57:06		[map] Destruct objects when clearing
	e93c01c3	2022-11-17T15:50:00		[map] Rename item clear() to construct()
	89637746	2022-11-17T15:25:45		[map] Don't resize map if not necessary
	7595fa2d	2022-11-17T15:19:29		[map] Fix copy-assignment operator Ouch!
	41f4bdac	2022-11-17T15:16:00		[map] Fix resize during copy-construction/assignment
	7bd10172	2022-11-17T15:01:55		[map] Minor use hb_iter instead of hb_array
	238fc147	2022-11-17T14:58:50		[map] Simplify iterators
	410c14bf	2022-11-17T14:53:00		[map] Fix equality Ouch!
	dbb7f47b	2022-11-03T11:55:41		fix bug in hb_hashmap_t has() interface It was not working when the value type is hb_bytes_t because hb_array_t overloaded operator &
	bcd59b51	2022-07-20T15:57:09		[set/map] Remove init_shallow/fini_shallow()
	e1b5f2f8	2022-07-20T15:03:20		[object] Call destructor in hb_object_destroy()
	9ea4ab60	2022-07-20T14:57:32		[object] Call constructor
	61c04384	2022-07-20T14:43:58		[map] Allow geting non-const value pointer out with has()
	00cfc5c1	2022-07-20T14:38:28		[map] Don't set out value in has() if not found
	485f0432	2022-07-20T14:34:55		[map] Enable using hashmap with unique_ptr