ternary.c revision 89858 
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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
36PTR
37ternary_insert (root, s, data, replace)
38     ternary_tree *root;
39     const char *s;
40     PTR data;
41     int replace;
42{
43  int diff;
44  ternary_tree curr, *pcurr;
45
46  /* Start at the root. */
47  pcurr = root;
48  /* Loop until we find the right position */
49  while ((curr = *pcurr))
50    {
51      /* Calculate the difference */
52      diff = *s - curr->splitchar;
53      /* Handle current char equal to node splitchar */
54      if (diff == 0)
55	{
56	  /* Handle the case of a string we already have */
57	  if (*s++ == 0)
58	    {
59	      if (replace)
60		curr->eqkid = (ternary_tree) data;
61	      return (PTR) curr->eqkid;
62	    }
63	  pcurr = &(curr->eqkid);
64	}
65      /* Handle current char less than node splitchar */
66      else if (diff < 0)
67	{
68	  pcurr = &(curr->lokid);
69	}
70      /* Handle current char greater than node splitchar */
71      else
72	{
73	  pcurr = &(curr->hikid);
74	}
75    }
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 (;;)
79    {
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;
85
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.
89       */
90      if (*s++ == 0)
91	{
92	  curr->eqkid = (ternary_tree) data;
93	  return data;
94	}
95      pcurr = &(curr->eqkid);
96    }
97}
98
99/* Free the ternary search tree rooted at p. */
100void
101ternary_cleanup (p)
102     ternary_tree p;
103{
104  if (p)
105    {
106      ternary_cleanup (p->lokid);
107      if (p->splitchar)
108	ternary_cleanup (p->eqkid);
109      ternary_cleanup (p->hikid);
110      free (p);
111    }
112}
113
114/* Non-recursive find of a string in the ternary tree */
115PTR
116ternary_search (p, s)
117     const ternary_node *p;
118     const char *s;
119{
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)
126    {
127      /* Calculate the difference */
128      diff = spchar - curr->splitchar;
129      /* Handle the equal case */
130      if (diff == 0)
131	{
132	  if (spchar == 0)
133	    return (PTR) curr->eqkid;
134	  spchar = *++s;
135	  curr = curr->eqkid;
136	}
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;
143    }
144  return NULL;
145}
146
147/* For those who care, the recursive version of the search. Useful if
148   you want a starting point for pmsearch or nearsearch. */
149static PTR
150ternary_recursivesearch (p, s)
151     const ternary_node *p;
152     const char *s;
153{
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
161    {
162      if (*s == 0)
163	return (PTR) p->eqkid;
164      return ternary_recursivesearch (p->eqkid, ++s);
165    }
166}
167