OpenCores
URL https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk

Subversion Repositories openrisc_2011-10-31

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

Go to most recent revision | 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.