OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [gdb-5.3/] [libiberty/] [ternary.c] - Blame information for rev 1765

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 1181 sfurman
/* 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
 
36
PTR
37
ternary_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. */
100
void
101
ternary_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 */
115
PTR
116
ternary_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. */
149
static PTR
150
ternary_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
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.