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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [libiberty/] [ternary.c] - Blame information for rev 154

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* 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
 
36
PTR
37
ternary_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. */
96
void
97
ternary_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 */
110
PTR
111
ternary_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. */
142
static PTR
143
ternary_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
}

powered by: WebSVN 2.1.0

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