1 /* $OpenBSD: tries.c,v 1.6 2023/10/17 09:52:09 nicm Exp $ */
2
3 /****************************************************************************
4 * Copyright 2020,2023 Thomas E. Dickey *
5 * Copyright 1998-2009,2010 Free Software Foundation, Inc. *
6 * *
7 * Permission is hereby granted, free of charge, to any person obtaining a *
8 * copy of this software and associated documentation files (the *
9 * "Software"), to deal in the Software without restriction, including *
10 * without limitation the rights to use, copy, modify, merge, publish, *
11 * distribute, distribute with modifications, sublicense, and/or sell *
12 * copies of the Software, and to permit persons to whom the Software is *
13 * furnished to do so, subject to the following conditions: *
14 * *
15 * The above copyright notice and this permission notice shall be included *
16 * in all copies or substantial portions of the Software. *
17 * *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS *
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF *
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. *
21 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, *
22 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR *
23 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR *
24 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. *
25 * *
26 * Except as contained in this notice, the name(s) of the above copyright *
27 * holders shall not be used in advertising or otherwise to promote the *
28 * sale, use or other dealings in this Software without prior written *
29 * authorization. *
30 ****************************************************************************/
31
32 /****************************************************************************
33 * Author: Thomas E. Dickey <dickey@clark.net> 1997 *
34 ****************************************************************************/
35
36 /*
37 ** tries.c
38 **
39 ** Functions to manage the tree of partial-completions for keycodes.
40 **
41 */
42
43 #include <curses.priv.h>
44 #include <tic.h>
45
46 MODULE_ID("$Id: tries.c,v 1.6 2023/10/17 09:52:09 nicm Exp $")
47
48 /*
49 * Expand a keycode into the string that it corresponds to, returning null if
50 * no match was found, otherwise allocating a string of the result.
51 */
NCURSES_EXPORT(char *)52 NCURSES_EXPORT(char *)
53 _nc_expand_try(TRIES * tree, unsigned code, int *count, size_t len)
54 {
55 TRIES *ptr = tree;
56 char *result = 0;
57
58 if (code != 0) {
59 while (ptr != 0) {
60 if ((result = _nc_expand_try(ptr->child, code, count, len + 1))
61 != 0) {
62 break;
63 }
64 if (ptr->value == code) {
65 *count -= 1;
66 if (*count == -1) {
67 result = typeCalloc(char, len + 2);
68 break;
69 }
70 }
71 ptr = ptr->sibling;
72 }
73 }
74 if (result != 0) {
75 if (ptr != 0 && (result[len] = (char) ptr->ch) == 0)
76 *((unsigned char *) (result + len)) = 128;
77 #ifdef TRACE
78 if (len == 0 && USE_TRACEF(TRACE_MAXIMUM)) {
79 _tracef("expand_key %s %s",
80 _nc_tracechar(CURRENT_SCREEN, (int) code),
81 _nc_visbuf(result));
82 _nc_unlock_global(tracef);
83 }
84 #endif
85 }
86 return result;
87 }
88
89 /*
90 * Remove a code from the specified tree, freeing the unused nodes. Returns
91 * true if the code was found/removed.
92 */
93 NCURSES_EXPORT(int)
_nc_remove_key(TRIES ** tree,unsigned code)94 _nc_remove_key(TRIES ** tree, unsigned code)
95 {
96 T((T_CALLED("_nc_remove_key(%p,%d)"), (void *) tree, code));
97
98 if (code == 0)
99 returnCode(FALSE);
100
101 while (*tree != 0) {
102 if (_nc_remove_key(&(*tree)->child, code)) {
103 returnCode(TRUE);
104 }
105 if ((*tree)->value == code) {
106 if ((*tree)->child) {
107 /* don't cut the whole sub-tree */
108 (*tree)->value = 0;
109 } else {
110 TRIES *to_free = *tree;
111 *tree = (*tree)->sibling;
112 free(to_free);
113 }
114 returnCode(TRUE);
115 }
116 tree = &(*tree)->sibling;
117 }
118 returnCode(FALSE);
119 }
120
121 /*
122 * Remove a string from the specified tree, freeing the unused nodes. Returns
123 * true if the string was found/removed.
124 */
125 NCURSES_EXPORT(int)
_nc_remove_string(TRIES ** tree,const char * string)126 _nc_remove_string(TRIES ** tree, const char *string)
127 {
128 T((T_CALLED("_nc_remove_string(%p,%s)"), (void *) tree, _nc_visbuf(string)));
129
130 if (!VALID_STRING(string) || *string == 0)
131 returnCode(FALSE);
132
133 while (*tree != 0) {
134 if (UChar((*tree)->ch) == UChar(*string)) {
135 if (string[1] != 0)
136 returnCode(_nc_remove_string(&(*tree)->child, string + 1));
137 if ((*tree)->child == 0) {
138 TRIES *to_free = *tree;
139 *tree = (*tree)->sibling;
140 free(to_free);
141 returnCode(TRUE);
142 } else {
143 returnCode(FALSE);
144 }
145 }
146 tree = &(*tree)->sibling;
147 }
148 returnCode(FALSE);
149 }
150