* readelf.c (byte_get_little_endian): Comment typo fix.
[binutils.git] / libiberty / ternary.c
blob056d2cee11ee661d4e7bfc2e3def8ec5fe7f13ef
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
9 later version.
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19 USA. */
20 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif
24 #ifdef HAVE_STDLIB_H
25 #include <stdlib.h>
26 #endif
28 #include <stdio.h>
30 #include "libiberty.h"
31 #include "ternary.h"
33 /* Non-recursive so we don't waste stack space/time on large
34 insertions. */
36 PTR
37 ternary_insert (root, s, data, replace)
38 ternary_tree *root;
39 const char *s;
40 PTR data;
41 int replace;
43 int diff;
44 ternary_tree curr, *pcurr;
46 /* Start at the root. */
47 pcurr = root;
48 /* Loop until we find the right position */
49 while ((curr = *pcurr))
51 /* Calculate the difference */
52 diff = *s - curr->splitchar;
53 /* Handle current char equal to node splitchar */
54 if (diff == 0)
56 /* Handle the case of a string we already have */
57 if (*s++ == 0)
59 if (replace)
60 curr->eqkid = (ternary_tree) data;
61 return (PTR) curr->eqkid;
63 pcurr = &(curr->eqkid);
65 /* Handle current char less than node splitchar */
66 else if (diff < 0)
68 pcurr = &(curr->lokid);
70 /* Handle current char greater than node splitchar */
71 else
73 pcurr = &(curr->hikid);
76 /* It's not a duplicate string, and we should insert what's left of
77 the string, into the tree rooted at curr */
78 for (;;)
80 /* Allocate the memory for the node, and fill it in */
81 *pcurr = (ternary_tree) xmalloc (sizeof (ternary_node));
82 curr = *pcurr;
83 curr->splitchar = *s;
84 curr->lokid = curr->hikid = curr->eqkid = 0;
86 /* Place nodes until we hit the end of the string.
87 When we hit it, place the data in the right place, and
88 return.
90 if (*s++ == 0)
92 curr->eqkid = (ternary_tree) data;
93 return data;
95 pcurr = &(curr->eqkid);
99 /* Free the ternary search tree rooted at p. */
100 void
101 ternary_cleanup (p)
102 ternary_tree p;
104 if (p)
106 ternary_cleanup (p->lokid);
107 if (p->splitchar)
108 ternary_cleanup (p->eqkid);
109 ternary_cleanup (p->hikid);
110 free (p);
114 /* Non-recursive find of a string in the ternary tree */
116 ternary_search (p, s)
117 const ternary_node *p;
118 const char *s;
120 const ternary_node *curr;
121 int diff, spchar;
122 spchar = *s;
123 curr = p;
124 /* Loop while we haven't hit a NULL node or returned */
125 while (curr)
127 /* Calculate the difference */
128 diff = spchar - curr->splitchar;
129 /* Handle the equal case */
130 if (diff == 0)
132 if (spchar == 0)
133 return (PTR) curr->eqkid;
134 spchar = *++s;
135 curr = curr->eqkid;
137 /* Handle the less than case */
138 else if (diff < 0)
139 curr = curr->lokid;
140 /* All that's left is greater than */
141 else
142 curr = curr->hikid;
144 return NULL;
147 /* For those who care, the recursive version of the search. Useful if
148 you want a starting point for pmsearch or nearsearch. */
149 static PTR
150 ternary_recursivesearch (p, s)
151 const ternary_node *p;
152 const char *s;
154 if (!p)
155 return 0;
156 if (*s < p->splitchar)
157 return ternary_recursivesearch (p->lokid, s);
158 else if (*s > p->splitchar)
159 return ternary_recursivesearch (p->hikid, s);
160 else
162 if (*s == 0)
163 return (PTR) p->eqkid;
164 return ternary_recursivesearch (p->eqkid, ++s);