src/compose/table.h


Log

Author Commit Date CI Message
Ran Benita a1770132 2023-09-25T11:41:48 Compose: add iterator API Allow users to iterate the entries in a compose table. This is useful for other projects which want programmable access to the sequences, without having to write their own parser. - New API: - `xkb_compose_table_entry_sequence`; - `xkb_compose_table_entry_keysym`; - `xkb_compose_table_entry_utf8`; - `xkb_compose_table_iterator_new`; - `xkb_compose_table_iterator_free`; - `xkb_compose_table_iterator_next`. - Add tests in `test/compose.c`. - Add benchmark for compose traversal. - `tools/compose.c`: - Print entries instead of just validating them. - Add `--file` option. - TODO: make this tool part of the xkbcli commands. Co-authored-by: Pierre Le Marre <dev@wismill.eu> Co-authored-by: Ran Benita <ran@unusedvar.com> Signed-off-by: Ran Benita <ran@unusedvar.com>
alois31 f3210cbf 2023-05-15T14:23:16 compose: drop the 65535 node limit (#343) In commit 1638409b22aef33d487863876ab214b949db4984, the number of compose nodes was limited to 65535 to enable "future optimizations", which apparently means slightly reduced memory usage due to fitting in a uint16_t. At this time, it was mentioned that the author was not aware of "any compose files which come close". However, I'm one of the users that actually do require a larger number of nodes for their compose file. Thus, use a uint32_t again and raise the limit significantly.
Ran Benita 02b9cabf 2021-03-29T16:05:14 compose: use a ternary tree instead of a regular trie Previously we used a simple trie with a linked list for each chain. Unfortunately most compose files have very long chains which means the constructions performs an almost quadratic number of comparisons. Switch to using a ternary search tree instead. This is very similar to a trie, only the linked list is essentially replaced with a binary tree. On the en_US/Compose file, the perf diff is the following (the modified function is `parse`): Event 'cycles:u' Baseline Delta Abs Shared Object Symbol ........ ......... ................ ................................. 39.91% -17.62% bench-compose [.] parse.constprop.0 20.54% +6.47% bench-compose [.] lex 17.28% +5.55% libc-2.33.so [.] __strcmp_avx2 12.78% +4.01% bench-compose [.] xkb_keysym_from_name 2.30% +0.83% libc-2.33.so [.] __GI_____strtoull_l_internal 3.36% +0.78% bench-compose [.] strcmp@plt Thanks to some careful packing, the memory usage is pretty much the same. Signed-off-by: Ran Benita <ran@unusedvar.com>
Ran Benita 8b09e177 2021-03-30T20:12:08 compose: use anonymous union Signed-off-by: Ran Benita <ran@unusedvar.com>
Ran Benita 1638409b 2021-03-30T17:52:36 compose: add a limit of 65535 sequences Fits in uint16_t, which enables some future optimizations. But also a good idea to have some limit. Not aware of any compose files which come close. Signed-off-by: Ran Benita <ran@unusedvar.com>
Ran Benita edc98b54 2014-09-12T18:44:30 compose: add xkbcommon-compose - implementation Signed-off-by: Ran Benita <ran234@gmail.com>