src/compose/table.h

   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 /* 7 nodes for every potential Unicode character and then some should be
  79  * enough for all purposes. */
  80 #define MAX_COMPOSE_NODES (1 << 23)
  81
  82 struct compose_node {
  83     xkb_keysym_t keysym;
  84
  85     /* Offset into xkb_compose_table::nodes or 0. */
  86     uint32_t lokid;
  87     /* Offset into xkb_compose_table::nodes or 0. */
  88     uint32_t hikid;
  89
  90     union {
  91         struct {
  92             uint32_t _pad:31;
  93             bool is_leaf:1;
  94         };
  95         struct {
  96             uint32_t _pad:31;
  97             bool is_leaf:1;
  98             /* Offset into xkb_compose_table::nodes or 0. */
  99             uint32_t eqkid;
 100         } internal;
 101         struct {
 102             /* Offset into xkb_compose_table::utf8. */
 103             uint32_t utf8:31;
 104             bool is_leaf:1;
 105             xkb_keysym_t keysym;
 106         } leaf;
 107     };
 108 };
 109
 110 struct xkb_compose_table {
 111     int refcnt;
 112     enum xkb_compose_format format;
 113     enum xkb_compose_compile_flags flags;
 114     struct xkb_context *ctx;
 115
 116     char *locale;
 117
 118     darray_char utf8;
 119     darray(struct compose_node) nodes;
 120 };
 121
 122 struct xkb_compose_table_entry {
 123     xkb_keysym_t *sequence;
 124     size_t sequence_length;
 125     xkb_keysym_t keysym;
 126     const char *utf8;
 127 };
 128
 129 #endif