1 /* 2 * Copyright 2013 Ran Benita <ran234 (at) 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 simple trie. An example will 33 * help. Given these sequences: 34 * 35 * <A> <B> : "first" dead_a 36 * <A> <C> <D> : "second" dead_b 37 * <E> <F> : "third" dead_c 38 * 39 * the trie would look like: 40 * 41 * [root] ---> [<A>] -----------------> [<E>] -# 42 * | | | 43 * # v v 44 * [<B>] ---> [<C>] -# [<F>] -# 45 * | | - 46 * # v # 47 * [<D>] -# 48 * | 49 * # 50 * where: 51 * - [root] is a special empty root node. 52 * - [<X>] is a node for a sequence keysym <X>. 53 * - right arrows are `next` pointers. 54 * - down arrows are `successor` pointers. 55 * - # is a nil pointer. 56 * 57 * The nodes are all kept in a contiguous array. Pointers are represented 58 * as integer offsets into this array. A nil pointer is represented as 0 59 * (which, helpfully, is the offset of the empty root node). 60 * 61 * Nodes without a successor are leaf nodes. Since a sequence cannot be a 62 * prefix of another, these are exactly the nodes which terminate the 63 * sequences (in a bijective manner). 64 * 65 * A leaf contains the result data of its sequence. The result keysym is 66 * contained in the node struct itself; the result UTF-8 string is a byte 67 * offset into an array of the form "\0first\0second\0third" (the initial 68 * \0 is so offset 0 points to an empty string). 69 */ 70 71 struct compose_node { 72 xkb_keysym_t keysym; 73 /* Offset into xkb_compose_table::nodes. */ 74 unsigned int next:31; 75 bool is_leaf:1; 76 77 union { 78 /* Offset into xkb_compose_table::nodes. */ 79 uint32_t successor; 80 struct { 81 /* Offset into xkb_compose_table::utf8. */ 82 uint32_t utf8; 83 xkb_keysym_t keysym; 84 } leaf; 85 } u; 86 }; 87 88 struct xkb_compose_table { 89 int refcnt; 90 enum xkb_compose_format format; 91 enum xkb_compose_compile_flags flags; 92 struct xkb_context *ctx; 93 94 char *locale; 95 96 darray_char utf8; 97 darray(struct compose_node) nodes; 98 }; 99 100 #endif 101
