Back to index

cell-binutils  2.17cvs20070401
ternary.c
Go to the documentation of this file.
00001 /* ternary.c - Ternary Search Trees
00002    Copyright (C) 2001 Free Software Foundation, Inc.
00003 
00004    Contributed by Daniel Berlin (dan@cgsoftware.com)
00005 
00006    This program is free software; you can redistribute it and/or modify it
00007    under the terms of the GNU General Public License as published by the
00008    Free Software Foundation; either version 2, or (at your option) any
00009    later version.
00010 
00011    This program is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014    GNU General Public License for more details.
00015 
00016    You should have received a copy of the GNU General Public License
00017    along with this program; if not, write to the Free Software
00018    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301,
00019    USA.  */
00020 #ifdef HAVE_CONFIG_H
00021 #include "config.h"
00022 #endif
00023 
00024 #ifdef HAVE_STDLIB_H
00025 #include <stdlib.h>
00026 #endif
00027 
00028 #include <stdio.h>
00029 
00030 #include "libiberty.h"
00031 #include "ternary.h"
00032 
00033 /* Non-recursive so we don't waste stack space/time on large
00034    insertions. */
00035 
00036 PTR
00037 ternary_insert (ternary_tree *root, const char *s, PTR data, int replace)
00038 {
00039   int diff;
00040   ternary_tree curr, *pcurr;
00041 
00042   /* Start at the root. */
00043   pcurr = root;
00044   /* Loop until we find the right position */
00045   while ((curr = *pcurr))
00046     {
00047       /* Calculate the difference */
00048       diff = *s - curr->splitchar;
00049       /* Handle current char equal to node splitchar */
00050       if (diff == 0)
00051        {
00052          /* Handle the case of a string we already have */
00053          if (*s++ == 0)
00054            {
00055              if (replace)
00056               curr->eqkid = (ternary_tree) data;
00057              return (PTR) curr->eqkid;
00058            }
00059          pcurr = &(curr->eqkid);
00060        }
00061       /* Handle current char less than node splitchar */
00062       else if (diff < 0)
00063        {
00064          pcurr = &(curr->lokid);
00065        }
00066       /* Handle current char greater than node splitchar */
00067       else
00068        {
00069          pcurr = &(curr->hikid);
00070        }
00071     }
00072   /* It's not a duplicate string, and we should insert what's left of
00073      the string, into the tree rooted at curr */
00074   for (;;)
00075     {
00076       /* Allocate the memory for the node, and fill it in */
00077       *pcurr = XNEW (ternary_node);
00078       curr = *pcurr;
00079       curr->splitchar = *s;
00080       curr->lokid = curr->hikid = curr->eqkid = 0;
00081 
00082       /* Place nodes until we hit the end of the string.
00083          When we hit it, place the data in the right place, and
00084          return.
00085        */
00086       if (*s++ == 0)
00087        {
00088          curr->eqkid = (ternary_tree) data;
00089          return data;
00090        }
00091       pcurr = &(curr->eqkid);
00092     }
00093 }
00094 
00095 /* Free the ternary search tree rooted at p. */
00096 void
00097 ternary_cleanup (ternary_tree p)
00098 {
00099   if (p)
00100     {
00101       ternary_cleanup (p->lokid);
00102       if (p->splitchar)
00103        ternary_cleanup (p->eqkid);
00104       ternary_cleanup (p->hikid);
00105       free (p);
00106     }
00107 }
00108 
00109 /* Non-recursive find of a string in the ternary tree */
00110 PTR
00111 ternary_search (const ternary_node *p, const char *s)
00112 {
00113   const ternary_node *curr;
00114   int diff, spchar;
00115   spchar = *s;
00116   curr = p;
00117   /* Loop while we haven't hit a NULL node or returned */
00118   while (curr)
00119     {
00120       /* Calculate the difference */
00121       diff = spchar - curr->splitchar;
00122       /* Handle the equal case */
00123       if (diff == 0)
00124        {
00125          if (spchar == 0)
00126            return (PTR) curr->eqkid;
00127          spchar = *++s;
00128          curr = curr->eqkid;
00129        }
00130       /* Handle the less than case */
00131       else if (diff < 0)
00132        curr = curr->lokid;
00133       /* All that's left is greater than */
00134       else
00135        curr = curr->hikid;
00136     }
00137   return NULL;
00138 }
00139 
00140 /* For those who care, the recursive version of the search. Useful if
00141    you want a starting point for pmsearch or nearsearch. */
00142 static PTR
00143 ternary_recursivesearch (const ternary_node *p, const char *s)
00144 {
00145   if (!p)
00146     return 0;
00147   if (*s < p->splitchar)
00148     return ternary_recursivesearch (p->lokid, s);
00149   else if (*s > p->splitchar)
00150     return ternary_recursivesearch (p->hikid, s);
00151   else
00152     {
00153       if (*s == 0)
00154        return (PTR) p->eqkid;
00155       return ternary_recursivesearch (p->eqkid, ++s);
00156     }
00157 }