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