1 /* 2 * Copyright © 2013,2021 Ran Benita <ran234@gmail.com> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24 #ifndef COMPOSE_COMPOSE_H 25 #define COMPOSE_COMPOSE_H 26 27 #include "xkbcommon/xkbcommon-compose.h" 28 #include "utils.h" 29 #include "context.h" 30 31 /* 32 * The compose table data structure is a ternary search tree. 33 * 34 * Reference: https://www.drdobbs.com/database/ternary-search-trees/184410528 35 * Visualization: https://www.cs.usfca.edu/~galles/visualization/TST.html 36 * 37 * Short example. Given these sequences: 38 * 39 * <B> <C> : "first" dead_a 40 * <B> <D> <E> : "second" dead_b 41 * <A> <F> : "third" dead_c 42 * 43 * the tree would look like: 44 * 45 * -------- [<B>]--------- 46 * | | # 47 * v V 48 * -- [<A>] -- [<C>] -------- 49 * # | # | | 50 * v # -- [<D>] -- 51 * -- [<F>] -- # | # 52 * # | # v 53 * # -- [<E>] -- 54 * # | # 55 * # 56 * 57 * where: 58 * - [<X>] is a node for a sequence keysym <X>. 59 * - right arrows are `hikid` pointers. 60 * - left arrows are `lokid` pointers. 61 * - down arrows are `eqkid` pointers. 62 * - # is a nil pointer. 63 * 64 * The nodes are all kept in a contiguous array. Pointers are represented 65 * as integer offsets into this array. A nil pointer is represented as 0 66 * (which, helpfully, is the offset of an empty dummy node). 67 * 68 * Nodes without an eqkid are leaf nodes. Since a sequence cannot be a 69 * prefix of another, these are exactly the nodes which terminate the 70 * sequences (in a bijective manner). 71 * 72 * A leaf contains the result data of its sequence. The result keysym is 73 * contained in the node struct itself; the result UTF-8 string is a byte 74 * offset into an array of the form "\0first\0second\0third" (the initial 75 * \0 is so offset 0 points to an empty string). 76 */ 77 78 /* Fits in uint16_t, also a good idea to have some limit. */ 79 #define MAX_COMPOSE_NODES 65535 80 81 struct compose_node { 82 xkb_keysym_t keysym; 83 84 /* Offset into xkb_compose_table::nodes or 0. */ 85 uint16_t lokid; 86 /* Offset into xkb_compose_table::nodes or 0. */ 87 uint16_t hikid; 88 89 union { 90 struct { 91 uint32_t _pad:31; 92 bool is_leaf:1; 93 }; 94 struct { 95 uint32_t _pad:31; 96 bool is_leaf:1; 97 /* Offset into xkb_compose_table::nodes or 0. */ 98 uint16_t eqkid; 99 } internal; 100 struct { 101 /* Offset into xkb_compose_table::utf8. */ 102 uint32_t utf8:31; 103 bool is_leaf:1; 104 xkb_keysym_t keysym; 105 } leaf; 106 }; 107 }; 108 109 struct xkb_compose_table { 110 int refcnt; 111 enum xkb_compose_format format; 112 enum xkb_compose_compile_flags flags; 113 struct xkb_context *ctx; 114 115 char *locale; 116 117 darray_char utf8; 118 darray(struct compose_node) nodes; 119 }; 120 121 #endif 122