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
36PTR
37ternary_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. */
96void
97ternary_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 */
110PTR
111ternary_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. */
142static PTR
143ternary_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