1 /* ternary.c - Ternary Search Trees
2 Copyright (C) 2001 Free Software Foundation, Inc.
3
4 Contributed by Daniel Berlin (dan@cgsoftware.com)
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301,
19 USA. */
20 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif
23
24 #ifdef HAVE_STDLIB_H
25 #include <stdlib.h>
26 #endif
27
28 #include <stdio.h>
29
30 #include "libiberty.h"
31 #include "ternary.h"
32
33 /* Non-recursive so we don't waste stack space/time on large
34 insertions. */
35
36 PTR
ternary_insert(ternary_tree * root,const char * s,PTR data,int replace)37 ternary_insert (ternary_tree *root, const char *s, PTR data, int replace)
38 {
39 int diff;
40 ternary_tree curr, *pcurr;
41
42 /* Start at the root. */
43 pcurr = root;
44 /* Loop until we find the right position */
45 while ((curr = *pcurr))
46 {
47 /* Calculate the difference */
48 diff = *s - curr->splitchar;
49 /* Handle current char equal to node splitchar */
50 if (diff == 0)
51 {
52 /* Handle the case of a string we already have */
53 if (*s++ == 0)
54 {
55 if (replace)
56 curr->eqkid = (ternary_tree) data;
57 return (PTR) curr->eqkid;
58 }
59 pcurr = &(curr->eqkid);
60 }
61 /* Handle current char less than node splitchar */
62 else if (diff < 0)
63 {
64 pcurr = &(curr->lokid);
65 }
66 /* Handle current char greater than node splitchar */
67 else
68 {
69 pcurr = &(curr->hikid);
70 }
71 }
72 /* It's not a duplicate string, and we should insert what's left of
73 the string, into the tree rooted at curr */
74 for (;;)
75 {
76 /* Allocate the memory for the node, and fill it in */
77 *pcurr = XNEW (ternary_node);
78 curr = *pcurr;
79 curr->splitchar = *s;
80 curr->lokid = curr->hikid = curr->eqkid = 0;
81
82 /* Place nodes until we hit the end of the string.
83 When we hit it, place the data in the right place, and
84 return.
85 */
86 if (*s++ == 0)
87 {
88 curr->eqkid = (ternary_tree) data;
89 return data;
90 }
91 pcurr = &(curr->eqkid);
92 }
93 }
94
95 /* Free the ternary search tree rooted at p. */
96 void
ternary_cleanup(ternary_tree p)97 ternary_cleanup (ternary_tree p)
98 {
99 if (p)
100 {
101 ternary_cleanup (p->lokid);
102 if (p->splitchar)
103 ternary_cleanup (p->eqkid);
104 ternary_cleanup (p->hikid);
105 free (p);
106 }
107 }
108
109 /* Non-recursive find of a string in the ternary tree */
110 PTR
ternary_search(const ternary_node * p,const char * s)111 ternary_search (const ternary_node *p, const char *s)
112 {
113 const ternary_node *curr;
114 int diff, spchar;
115 spchar = *s;
116 curr = p;
117 /* Loop while we haven't hit a NULL node or returned */
118 while (curr)
119 {
120 /* Calculate the difference */
121 diff = spchar - curr->splitchar;
122 /* Handle the equal case */
123 if (diff == 0)
124 {
125 if (spchar == 0)
126 return (PTR) curr->eqkid;
127 spchar = *++s;
128 curr = curr->eqkid;
129 }
130 /* Handle the less than case */
131 else if (diff < 0)
132 curr = curr->lokid;
133 /* All that's left is greater than */
134 else
135 curr = curr->hikid;
136 }
137 return NULL;
138 }
139
140 /* For those who care, the recursive version of the search. Useful if
141 you want a starting point for pmsearch or nearsearch. */
142 static PTR
ternary_recursivesearch(const ternary_node * p,const char * s)143 ternary_recursivesearch (const ternary_node *p, const char *s)
144 {
145 if (!p)
146 return 0;
147 if (*s < p->splitchar)
148 return ternary_recursivesearch (p->lokid, s);
149 else if (*s > p->splitchar)
150 return ternary_recursivesearch (p->hikid, s);
151 else
152 {
153 if (*s == 0)
154 return (PTR) p->eqkid;
155 return ternary_recursivesearch (p->eqkid, ++s);
156 }
157 }
158