tries.c revision 174993
150276Speter/**************************************************************************** 2174993Srafan * Copyright (c) 1998-2006,2007 Free Software Foundation, Inc. * 350276Speter * * 450276Speter * Permission is hereby granted, free of charge, to any person obtaining a * 550276Speter * copy of this software and associated documentation files (the * 650276Speter * "Software"), to deal in the Software without restriction, including * 750276Speter * without limitation the rights to use, copy, modify, merge, publish, * 850276Speter * distribute, distribute with modifications, sublicense, and/or sell * 950276Speter * copies of the Software, and to permit persons to whom the Software is * 1050276Speter * furnished to do so, subject to the following conditions: * 1150276Speter * * 1250276Speter * The above copyright notice and this permission notice shall be included * 1350276Speter * in all copies or substantial portions of the Software. * 1450276Speter * * 1550276Speter * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 1650276Speter * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 1750276Speter * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 1850276Speter * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 1950276Speter * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 2050276Speter * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 2150276Speter * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 2250276Speter * * 2350276Speter * Except as contained in this notice, the name(s) of the above copyright * 2450276Speter * holders shall not be used in advertising or otherwise to promote the * 2550276Speter * sale, use or other dealings in this Software without prior written * 2650276Speter * authorization. * 2750276Speter ****************************************************************************/ 2850276Speter 2950276Speter/**************************************************************************** 3050276Speter * Author: Thomas E. Dickey <dickey@clark.net> 1997 * 3150276Speter ****************************************************************************/ 3250276Speter 3350276Speter/* 3450276Speter** tries.c 3550276Speter** 3650276Speter** Functions to manage the tree of partial-completions for keycodes. 3750276Speter** 3850276Speter*/ 3950276Speter 4050276Speter#include <curses.priv.h> 4150276Speter 42174993SrafanMODULE_ID("$Id: tries.c,v 1.25 2007/09/29 20:37:13 tom Exp $") 4350276Speter 4450276Speter/* 4550276Speter * Expand a keycode into the string that it corresponds to, returning null if 4650276Speter * no match was found, otherwise allocating a string of the result. 4750276Speter */ 4876726SpeterNCURSES_EXPORT(char *) 49174993Srafan_nc_expand_try(TRIES * tree, unsigned code, int *count, size_t len) 5050276Speter{ 51174993Srafan TRIES *ptr = tree; 5276726Speter char *result = 0; 5350276Speter 5476726Speter if (code != 0) { 5576726Speter while (ptr != 0) { 5676726Speter if ((result = _nc_expand_try(ptr->child, code, count, len + 1)) 5776726Speter != 0) { 5876726Speter break; 5976726Speter } 6076726Speter if (ptr->value == code) { 6176726Speter *count -= 1; 6276726Speter if (*count == -1) { 6376726Speter result = typeCalloc(char, len + 2); 6476726Speter break; 6550276Speter } 6676726Speter } 6776726Speter ptr = ptr->sibling; 6850276Speter } 6976726Speter } 7076726Speter if (result != 0) { 71174993Srafan if (ptr != 0 && (result[len] = ptr->ch) == 0) 7276726Speter *((unsigned char *) (result + len)) = 128; 7350276Speter#ifdef TRACE 74174993Srafan if (len == 0 && USE_TRACEF(TRACE_MAXIMUM)) { 7597049Speter _tracef("expand_key %s %s", _tracechar(code), _nc_visbuf(result)); 76174993Srafan _nc_unlock_global(tracef); 77174993Srafan } 7850276Speter#endif 7976726Speter } 8076726Speter return result; 8150276Speter} 8250276Speter 8350276Speter/* 8450276Speter * Remove a code from the specified tree, freeing the unused nodes. Returns 8550276Speter * true if the code was found/removed. 8650276Speter */ 8776726SpeterNCURSES_EXPORT(int) 88174993Srafan_nc_remove_key(TRIES ** tree, unsigned code) 8950276Speter{ 9076726Speter T((T_CALLED("_nc_remove_key(%p,%d)"), tree, code)); 9150276Speter 9276726Speter if (code == 0) 9376726Speter returnCode(FALSE); 9476726Speter 9576726Speter while (*tree != 0) { 9676726Speter if (_nc_remove_key(&(*tree)->child, code)) { 9776726Speter returnCode(TRUE); 9850276Speter } 9976726Speter if ((*tree)->value == code) { 10076726Speter if ((*tree)->child) { 10176726Speter /* don't cut the whole sub-tree */ 10276726Speter (*tree)->value = 0; 10376726Speter } else { 104174993Srafan TRIES *to_free = *tree; 10576726Speter *tree = (*tree)->sibling; 10676726Speter free(to_free); 10776726Speter } 10876726Speter returnCode(TRUE); 10976726Speter } 11076726Speter tree = &(*tree)->sibling; 11176726Speter } 11276726Speter returnCode(FALSE); 11350276Speter} 11450276Speter 11550276Speter/* 11650276Speter * Remove a string from the specified tree, freeing the unused nodes. Returns 11750276Speter * true if the string was found/removed. 11850276Speter */ 11976726SpeterNCURSES_EXPORT(int) 120174993Srafan_nc_remove_string(TRIES ** tree, const char *string) 12150276Speter{ 12276726Speter T((T_CALLED("_nc_remove_string(%p,%s)"), tree, _nc_visbuf(string))); 12350276Speter 12476726Speter if (string == 0 || *string == 0) 12576726Speter returnCode(FALSE); 12676726Speter 12776726Speter while (*tree != 0) { 128166124Srafan if (UChar((*tree)->ch) == UChar(*string)) { 12976726Speter if (string[1] != 0) 13076726Speter returnCode(_nc_remove_string(&(*tree)->child, string + 1)); 131166124Srafan if ((*tree)->child == 0) { 132174993Srafan TRIES *to_free = *tree; 13376726Speter *tree = (*tree)->sibling; 13476726Speter free(to_free); 135166124Srafan returnCode(TRUE); 136166124Srafan } else { 137166124Srafan returnCode(FALSE); 13876726Speter } 13950276Speter } 14076726Speter tree = &(*tree)->sibling; 14176726Speter } 14276726Speter returnCode(FALSE); 14350276Speter} 144