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 (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 = (ternary_tree) xmalloc (sizeof (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 }