libiberty/ternary.c

   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., 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 }