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 */ 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) 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) 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