1*c7ef0cfcSnicm /* $OpenBSD: tries.c,v 1.6 2023/10/17 09:52:09 nicm Exp $ */
292dd1ec0Smillert
392dd1ec0Smillert /****************************************************************************
4*c7ef0cfcSnicm * Copyright 2020,2023 Thomas E. Dickey *
5*c7ef0cfcSnicm * Copyright 1998-2009,2010 Free Software Foundation, Inc. *
692dd1ec0Smillert * *
792dd1ec0Smillert * Permission is hereby granted, free of charge, to any person obtaining a *
892dd1ec0Smillert * copy of this software and associated documentation files (the *
992dd1ec0Smillert * "Software"), to deal in the Software without restriction, including *
1092dd1ec0Smillert * without limitation the rights to use, copy, modify, merge, publish, *
1192dd1ec0Smillert * distribute, distribute with modifications, sublicense, and/or sell *
1292dd1ec0Smillert * copies of the Software, and to permit persons to whom the Software is *
1392dd1ec0Smillert * furnished to do so, subject to the following conditions: *
1492dd1ec0Smillert * *
1592dd1ec0Smillert * The above copyright notice and this permission notice shall be included *
1692dd1ec0Smillert * in all copies or substantial portions of the Software. *
1792dd1ec0Smillert * *
1892dd1ec0Smillert * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS *
1992dd1ec0Smillert * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF *
2092dd1ec0Smillert * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. *
2192dd1ec0Smillert * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, *
2292dd1ec0Smillert * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR *
2392dd1ec0Smillert * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR *
2492dd1ec0Smillert * THE USE OR OTHER DEALINGS IN THE SOFTWARE. *
2592dd1ec0Smillert * *
2692dd1ec0Smillert * Except as contained in this notice, the name(s) of the above copyright *
2792dd1ec0Smillert * holders shall not be used in advertising or otherwise to promote the *
2892dd1ec0Smillert * sale, use or other dealings in this Software without prior written *
2992dd1ec0Smillert * authorization. *
3092dd1ec0Smillert ****************************************************************************/
3192dd1ec0Smillert
3292dd1ec0Smillert /****************************************************************************
3392dd1ec0Smillert * Author: Thomas E. Dickey <dickey@clark.net> 1997 *
3492dd1ec0Smillert ****************************************************************************/
3592dd1ec0Smillert
3692dd1ec0Smillert /*
3792dd1ec0Smillert ** tries.c
3892dd1ec0Smillert **
3992dd1ec0Smillert ** Functions to manage the tree of partial-completions for keycodes.
4092dd1ec0Smillert **
4192dd1ec0Smillert */
4292dd1ec0Smillert
4392dd1ec0Smillert #include <curses.priv.h>
44*c7ef0cfcSnicm #include <tic.h>
4592dd1ec0Smillert
46*c7ef0cfcSnicm MODULE_ID("$Id: tries.c,v 1.6 2023/10/17 09:52:09 nicm Exp $")
4792dd1ec0Smillert
4892dd1ec0Smillert /*
4992dd1ec0Smillert * Expand a keycode into the string that it corresponds to, returning null if
5092dd1ec0Smillert * no match was found, otherwise allocating a string of the result.
5192dd1ec0Smillert */
NCURSES_EXPORT(char *)5284af20ceSmillert NCURSES_EXPORT(char *)
5381d8c4e1Snicm _nc_expand_try(TRIES * tree, unsigned code, int *count, size_t len)
5492dd1ec0Smillert {
5581d8c4e1Snicm TRIES *ptr = tree;
5692dd1ec0Smillert char *result = 0;
5792dd1ec0Smillert
5892dd1ec0Smillert if (code != 0) {
5992dd1ec0Smillert while (ptr != 0) {
6084af20ceSmillert if ((result = _nc_expand_try(ptr->child, code, count, len + 1))
6184af20ceSmillert != 0) {
6292dd1ec0Smillert break;
6392dd1ec0Smillert }
6492dd1ec0Smillert if (ptr->value == code) {
65c21ba70dSmillert *count -= 1;
66c21ba70dSmillert if (*count == -1) {
6792dd1ec0Smillert result = typeCalloc(char, len + 2);
6892dd1ec0Smillert break;
6992dd1ec0Smillert }
70c21ba70dSmillert }
7192dd1ec0Smillert ptr = ptr->sibling;
7292dd1ec0Smillert }
7392dd1ec0Smillert }
7492dd1ec0Smillert if (result != 0) {
7581d8c4e1Snicm if (ptr != 0 && (result[len] = (char) ptr->ch) == 0)
7692dd1ec0Smillert *((unsigned char *) (result + len)) = 128;
7792dd1ec0Smillert #ifdef TRACE
7881d8c4e1Snicm if (len == 0 && USE_TRACEF(TRACE_MAXIMUM)) {
79*c7ef0cfcSnicm _tracef("expand_key %s %s",
80*c7ef0cfcSnicm _nc_tracechar(CURRENT_SCREEN, (int) code),
81*c7ef0cfcSnicm _nc_visbuf(result));
8281d8c4e1Snicm _nc_unlock_global(tracef);
8381d8c4e1Snicm }
8492dd1ec0Smillert #endif
8592dd1ec0Smillert }
8692dd1ec0Smillert return result;
8792dd1ec0Smillert }
8892dd1ec0Smillert
8992dd1ec0Smillert /*
9092dd1ec0Smillert * Remove a code from the specified tree, freeing the unused nodes. Returns
9192dd1ec0Smillert * true if the code was found/removed.
9292dd1ec0Smillert */
9384af20ceSmillert NCURSES_EXPORT(int)
_nc_remove_key(TRIES ** tree,unsigned code)9481d8c4e1Snicm _nc_remove_key(TRIES ** tree, unsigned code)
9592dd1ec0Smillert {
96*c7ef0cfcSnicm T((T_CALLED("_nc_remove_key(%p,%d)"), (void *) tree, code));
97feef4803Smillert
9892dd1ec0Smillert if (code == 0)
99feef4803Smillert returnCode(FALSE);
10092dd1ec0Smillert
10192dd1ec0Smillert while (*tree != 0) {
10292dd1ec0Smillert if (_nc_remove_key(&(*tree)->child, code)) {
103feef4803Smillert returnCode(TRUE);
10492dd1ec0Smillert }
10592dd1ec0Smillert if ((*tree)->value == code) {
10692dd1ec0Smillert if ((*tree)->child) {
10792dd1ec0Smillert /* don't cut the whole sub-tree */
10892dd1ec0Smillert (*tree)->value = 0;
10992dd1ec0Smillert } else {
11081d8c4e1Snicm TRIES *to_free = *tree;
11192dd1ec0Smillert *tree = (*tree)->sibling;
11292dd1ec0Smillert free(to_free);
11392dd1ec0Smillert }
114feef4803Smillert returnCode(TRUE);
11592dd1ec0Smillert }
11692dd1ec0Smillert tree = &(*tree)->sibling;
11792dd1ec0Smillert }
118feef4803Smillert returnCode(FALSE);
11992dd1ec0Smillert }
120c21ba70dSmillert
121c21ba70dSmillert /*
122c21ba70dSmillert * Remove a string from the specified tree, freeing the unused nodes. Returns
123c21ba70dSmillert * true if the string was found/removed.
124c21ba70dSmillert */
12584af20ceSmillert NCURSES_EXPORT(int)
_nc_remove_string(TRIES ** tree,const char * string)12681d8c4e1Snicm _nc_remove_string(TRIES ** tree, const char *string)
127c21ba70dSmillert {
128*c7ef0cfcSnicm T((T_CALLED("_nc_remove_string(%p,%s)"), (void *) tree, _nc_visbuf(string)));
129feef4803Smillert
130*c7ef0cfcSnicm if (!VALID_STRING(string) || *string == 0)
131feef4803Smillert returnCode(FALSE);
132c21ba70dSmillert
133c21ba70dSmillert while (*tree != 0) {
13481d8c4e1Snicm if (UChar((*tree)->ch) == UChar(*string)) {
135feef4803Smillert if (string[1] != 0)
136feef4803Smillert returnCode(_nc_remove_string(&(*tree)->child, string + 1));
13781d8c4e1Snicm if ((*tree)->child == 0) {
13881d8c4e1Snicm TRIES *to_free = *tree;
139c21ba70dSmillert *tree = (*tree)->sibling;
140c21ba70dSmillert free(to_free);
141feef4803Smillert returnCode(TRUE);
14281d8c4e1Snicm } else {
14381d8c4e1Snicm returnCode(FALSE);
14481d8c4e1Snicm }
145c21ba70dSmillert }
146c21ba70dSmillert tree = &(*tree)->sibling;
147c21ba70dSmillert }
148feef4803Smillert returnCode(FALSE);
149c21ba70dSmillert }
150