cde/programs/dthelp/parser.ccdf/htag/util/trie.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: trie.c /main/3 1995/11/08 11:43:36 rswiston $ */
  24 /*
  25                    Copyright 1986, 1987, 1988, 1989 Hewlett-Packard Co.
  26 */
  27
  28 /* Trie.c contains procedures for maintaining the tree structure
  29    used to store element names, delimiter strings, short reference strings,
  30    etc. */
  31
  32 #include <stdio.h>
  33
  34 #if defined(MSDOS)
  35 #include <stdlib.h>
  36 #endif
  37
  38 #include "basic.h"
  39 #include "common.h"
  40 #include "trie.h"
  41
  42 extern int m_line ;
  43
  44 extern FILE *m_errfile ;
  45
  46 extern M_CHARTYPE m_ctarray[M_CHARSETLEN] ;
  47
  48 void *m_malloc(
  49 #if defined(M_PROTO)
  50   int size, char *msg
  51 #endif
  52   ) ;
  53
  54 void m_entercharintrie(
  55 #if defined(M_PROTO)
  56   M_TRIE **currentnode, M_WCHAR c
  57 #endif
  58   ) ;
  59
  60 /* Enters the next character of a string into a trie */
  61 #if defined(M_PROTO)
  62 void m_entercharintrie(M_TRIE **currentnode, M_WCHAR c)
  63 #else
  64 void m_entercharintrie(currentnode, c)
  65   M_TRIE **currentnode ;
  66   M_WCHAR c ;
  67 #endif
  68   {
  69     M_TRIE *newnode ;
  70
  71     if (! (*currentnode)->data) {
  72       (*currentnode)->data = m_gettrienode() ;
  73       *currentnode = (*currentnode)->data ;
  74       (*currentnode)->next = M_NULLVAL ;
  75       (*currentnode)->symbol = c ;
  76       (*currentnode)->data = M_NULLVAL ;
  77       } /* end insert a son */
  78     else if ((*currentnode)->data->symbol > c) {
  79       newnode = m_gettrienode() ;
  80       newnode->next = (*currentnode)->data ;
  81       (*currentnode)->data = newnode ;
  82       *currentnode = (*currentnode)->data ;
  83       (*currentnode)->symbol = c ;
  84       (*currentnode)->data = M_NULLVAL ;
  85       } /* end insert before first son */
  86     else {
  87       for (*currentnode = (*currentnode)->data ;
  88            (*currentnode)->next &&(*currentnode)->next->symbol <= c;
  89            *currentnode = (*currentnode)->next ) ;
  90       if ((*currentnode)->symbol != c) {
  91         newnode = m_gettrienode() ;
  92         newnode->next = (*currentnode)->next ;
  93         (*currentnode)->next = newnode ;
  94         *currentnode = (*currentnode)->next ;
  95         (*currentnode)->symbol = c ;
  96         (*currentnode)->data = M_NULLVAL ;
  97         } /* end insert node in descendant list */
  98       } /* end check descendant list */
  99    } /* end entertree */
 100
 101 /* Gets a new node for a trie */
 102 M_TRIE *m_gettrienode(M_NOPAR)
 103   {
 104     M_TRIE *new ;
 105
 106     new = (M_TRIE *) m_malloc(sizeof(M_TRIE), "trie") ;
 107     new->symbol = 0 ;
 108     new->next = new->data = NULL ;
 109     return(new) ;
 110     } /*end m_gettrienode */
 111
 112
 113 /* M_lookfortrie(p, xtrie) looks for string p in the specified trie,
 114    returning its data value if found and otherwise FALSE */
 115 #if defined(M_PROTO)
 116 void *m_lookfortrie( const M_WCHAR *p , const M_TRIE *xtrie )
 117 #else
 118 void *m_lookfortrie(p, xtrie)
 119   M_WCHAR *p ;
 120   M_TRIE *xtrie ;
 121 #endif /* M_PROTO */
 122   {
 123     M_TRIE *currentnode ;
 124
 125     currentnode = xtrie->data ;
 126     while (TRUE) {
 127       if (! currentnode) return(NULL) ;
 128       if (currentnode->symbol == m_ctupper(*p))
 129         if (! *p) return((void *) currentnode->data) ;
 130         else {
 131           p++ ;
 132           currentnode = currentnode->data ;
 133           continue ;
 134           }
 135       else if (currentnode->symbol < *p) {
 136         currentnode = currentnode->next ;
 137         continue ;
 138         }
 139       else return(NULL) ;
 140       }
 141     }
 142
 143 /* Enters a string and associated data value into a trie */
 144 void *m_ntrtrie(p, xtrie, dataval)
 145   M_WCHAR *p ;
 146   M_TRIE *xtrie ;
 147   void *dataval ;
 148   {
 149     M_TRIE *currentnode ;
 150     void *n ;
 151
 152     if (n = m_lookfortrie(p, xtrie)) return(n) ;
 153     currentnode = xtrie ;
 154     for ( ; *p ; p++)
 155       m_entercharintrie(&currentnode, m_ctupper(*p)) ;
 156     m_entercharintrie(&currentnode, M_EOS) ;
 157     currentnode->data = (M_TRIE *) dataval ;
 158     return(NULL) ;
 159     }