Back to index

tetex-bin  3.0
tries.c
Go to the documentation of this file.
00001 /****************************************************************************
00002  * Copyright (c) 1998-2001,2003 Free Software Foundation, Inc.              *
00003  *                                                                          *
00004  * Permission is hereby granted, free of charge, to any person obtaining a  *
00005  * copy of this software and associated documentation files (the            *
00006  * "Software"), to deal in the Software without restriction, including      *
00007  * without limitation the rights to use, copy, modify, merge, publish,      *
00008  * distribute, distribute with modifications, sublicense, and/or sell       *
00009  * copies of the Software, and to permit persons to whom the Software is    *
00010  * furnished to do so, subject to the following conditions:                 *
00011  *                                                                          *
00012  * The above copyright notice and this permission notice shall be included  *
00013  * in all copies or substantial portions of the Software.                   *
00014  *                                                                          *
00015  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
00016  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
00017  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
00018  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
00019  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
00020  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
00021  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
00022  *                                                                          *
00023  * Except as contained in this notice, the name(s) of the above copyright   *
00024  * holders shall not be used in advertising or otherwise to promote the     *
00025  * sale, use or other dealings in this Software without prior written       *
00026  * authorization.                                                           *
00027  ****************************************************************************/
00028 
00029 /****************************************************************************
00030  *  Author: Thomas E. Dickey <dickey@clark.net> 1997                        *
00031  ****************************************************************************/
00032 
00033 /*
00034 **     tries.c
00035 **
00036 **     Functions to manage the tree of partial-completions for keycodes.
00037 **
00038 */
00039 
00040 #include <curses.priv.h>
00041 
00042 MODULE_ID("$Id: tries.c,v 1.19 2003/05/17 23:11:24 tom Exp $")
00043 
00044 /*
00045  * Expand a keycode into the string that it corresponds to, returning null if
00046  * no match was found, otherwise allocating a string of the result.
00047  */
00048 NCURSES_EXPORT(char *)
00049 _nc_expand_try(struct tries *tree, unsigned short code, int *count, size_t len)
00050 {
00051     struct tries *ptr = tree;
00052     char *result = 0;
00053 
00054     if (code != 0) {
00055        while (ptr != 0) {
00056            if ((result = _nc_expand_try(ptr->child, code, count, len + 1))
00057               != 0) {
00058               break;
00059            }
00060            if (ptr->value == code) {
00061               *count -= 1;
00062               if (*count == -1) {
00063                   result = typeCalloc(char, len + 2);
00064                   break;
00065               }
00066            }
00067            ptr = ptr->sibling;
00068        }
00069     }
00070     if (result != 0) {
00071        if ((result[len] = ptr->ch) == 0)
00072            *((unsigned char *) (result + len)) = 128;
00073 #ifdef TRACE
00074        if (len == 0)
00075            _tracef("expand_key %s %s", _tracechar(code), _nc_visbuf(result));
00076 #endif
00077     }
00078     return result;
00079 }
00080 
00081 /*
00082  * Remove a code from the specified tree, freeing the unused nodes.  Returns
00083  * true if the code was found/removed.
00084  */
00085 NCURSES_EXPORT(int)
00086 _nc_remove_key(struct tries **tree, unsigned short code)
00087 {
00088     T((T_CALLED("_nc_remove_key(%p,%d)"), tree, code));
00089 
00090     if (code == 0)
00091        returnCode(FALSE);
00092 
00093     while (*tree != 0) {
00094        if (_nc_remove_key(&(*tree)->child, code)) {
00095            returnCode(TRUE);
00096        }
00097        if ((*tree)->value == code) {
00098            if ((*tree)->child) {
00099               /* don't cut the whole sub-tree */
00100               (*tree)->value = 0;
00101            } else {
00102               struct tries *to_free = *tree;
00103               *tree = (*tree)->sibling;
00104               free(to_free);
00105            }
00106            returnCode(TRUE);
00107        }
00108        tree = &(*tree)->sibling;
00109     }
00110     returnCode(FALSE);
00111 }
00112 
00113 /*
00114  * Remove a string from the specified tree, freeing the unused nodes.  Returns
00115  * true if the string was found/removed.
00116  */
00117 NCURSES_EXPORT(int)
00118 _nc_remove_string(struct tries **tree, const char *string)
00119 {
00120     T((T_CALLED("_nc_remove_string(%p,%s)"), tree, _nc_visbuf(string)));
00121 
00122     if (string == 0 || *string == 0)
00123        returnCode(FALSE);
00124 
00125     while (*tree != 0) {
00126        if (UChar((*tree)->ch) == UChar(*string)) {
00127            if (string[1] != 0)
00128               returnCode(_nc_remove_string(&(*tree)->child, string + 1));
00129            if ((*tree)->child == 0) {
00130               struct tries *to_free = *tree;
00131               *tree = (*tree)->sibling;
00132               free(to_free);
00133               returnCode(TRUE);
00134            } else {
00135               returnCode(FALSE);
00136            }
00137        }
00138        tree = &(*tree)->sibling;
00139     }
00140     returnCode(FALSE);
00141 }