2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
23 /* $XConsortium: trie.c /main/3 1995/11/08 09:55:10 rswiston $ */
25 Copyright 1986, 1987, 1988, 1989 Hewlett-Packard Co.
28 /* Trie.c contains procedures for maintaining the tree structure
29 used to store element names, delimiter strings, short reference strings,
44 extern FILE *m_errfile ;
46 extern M_CHARTYPE m_ctarray[M_CHARSETLEN] ;
54 void m_entercharintrie(
56 M_TRIE **currentnode, M_WCHAR c
60 /* Enters the next character of a string into a trie */
62 void m_entercharintrie(M_TRIE **currentnode, M_WCHAR c)
64 void m_entercharintrie(currentnode, c)
65 M_TRIE **currentnode ;
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 */
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 */
101 /* Gets a new node for a trie */
102 M_TRIE *m_gettrienode(M_NOPAR)
106 new = (M_TRIE *) m_malloc(sizeof(M_TRIE), "trie") ;
108 new->next = new->data = NULL ;
110 } /*end m_gettrienode */
113 /* M_lookfortrie(p, xtrie) looks for string p in the specified trie,
114 returning its data value if found and otherwise FALSE */
116 void *m_lookfortrie( const M_WCHAR *p , const M_TRIE *xtrie )
118 void *m_lookfortrie(p, xtrie)
123 M_TRIE *currentnode ;
125 currentnode = xtrie->data ;
127 if (! currentnode) return(NULL) ;
128 if (currentnode->symbol == m_ctupper(*p))
129 if (! *p) return((void *) currentnode->data) ;
132 currentnode = currentnode->data ;
135 else if (currentnode->symbol < *p) {
136 currentnode = currentnode->next ;
143 /* Enters a string and associated data value into a trie */
144 void *m_ntrtrie(p, xtrie, dataval)
149 M_TRIE *currentnode ;
152 if (n = m_lookfortrie(p, xtrie)) return(n) ;
153 currentnode = xtrie ;
155 m_entercharintrie(¤tnode, m_ctupper(*p)) ;
156 m_entercharintrie(¤tnode, M_EOS) ;
157 currentnode->data = (M_TRIE *) dataval ;