1 /* ternary.c - Ternary Search Trees
2 Copyright (C) 2001 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin (dan@cgsoftware.com)
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
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.
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,
30 #include "libiberty.h"
33 /* Non-recursive so we don't waste stack space/time on large
37 ternary_insert (ternary_tree
*root
, const char *s
, PTR data
, int replace
)
40 ternary_tree curr
, *pcurr
;
42 /* Start at the root. */
44 /* Loop until we find the right position */
45 while ((curr
= *pcurr
))
47 /* Calculate the difference */
48 diff
= *s
- curr
->splitchar
;
49 /* Handle current char equal to node splitchar */
52 /* Handle the case of a string we already have */
56 curr
->eqkid
= (ternary_tree
) data
;
57 return (PTR
) curr
->eqkid
;
59 pcurr
= &(curr
->eqkid
);
61 /* Handle current char less than node splitchar */
64 pcurr
= &(curr
->lokid
);
66 /* Handle current char greater than node splitchar */
69 pcurr
= &(curr
->hikid
);
72 /* It's not a duplicate string, and we should insert what's left of
73 the string, into the tree rooted at curr */
76 /* Allocate the memory for the node, and fill it in */
77 *pcurr
= XNEW (ternary_node
);
80 curr
->lokid
= curr
->hikid
= curr
->eqkid
= 0;
82 /* Place nodes until we hit the end of the string.
83 When we hit it, place the data in the right place, and
88 curr
->eqkid
= (ternary_tree
) data
;
91 pcurr
= &(curr
->eqkid
);
95 /* Free the ternary search tree rooted at p. */
97 ternary_cleanup (ternary_tree p
)
101 ternary_cleanup (p
->lokid
);
103 ternary_cleanup (p
->eqkid
);
104 ternary_cleanup (p
->hikid
);
109 /* Non-recursive find of a string in the ternary tree */
111 ternary_search (const ternary_node
*p
, const char *s
)
113 const ternary_node
*curr
;
117 /* Loop while we haven't hit a NULL node or returned */
120 /* Calculate the difference */
121 diff
= spchar
- curr
->splitchar
;
122 /* Handle the equal case */
126 return (PTR
) curr
->eqkid
;
130 /* Handle the less than case */
133 /* All that's left is greater than */
140 /* For those who care, the recursive version of the search. Useful if
141 you want a starting point for pmsearch or nearsearch. */
143 ternary_recursivesearch (const ternary_node
*p
, const char *s
)
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
);
154 return (PTR
) p
->eqkid
;
155 return ternary_recursivesearch (p
->eqkid
, ++s
);
This page took 0.031399 seconds and 4 git commands to generate.