libiberty/ternary.c

/* ternary.c - Ternary Search Trees
   Copyright (C) 2001 Free Software Foundation, Inc.

   Contributed by Daniel Berlin (dan@cgsoftware.com)

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
   USA.  */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#include <stdio.h>

#include "libiberty.h"
#include "ternary.h"

/* Non-recursive so we don't waste stack space/time on large
   insertions. */

PTR
ternary_insert (root, s, data, replace)
     ternary_tree *root;
     const char *s;
     PTR data;
     int replace;
{
  int diff;
  ternary_tree curr, *pcurr;

  /* Start at the root. */
  pcurr = root;
  /* Loop until we find the right position */
  while ((curr = *pcurr))
    {
      /* Calculate the difference */
      diff = *s - curr->splitchar;
      /* Handle current char equal to node splitchar */
      if (diff == 0)
	{
	  /* Handle the case of a string we already have */
	  if (*s++ == 0)
	    {
	      if (replace)
		curr->eqkid = (ternary_tree) data;
	      return (PTR) curr->eqkid;
	    }
	  pcurr = &(curr->eqkid);
	}
      /* Handle current char less than node splitchar */
      else if (diff < 0)
	{
	  pcurr = &(curr->lokid);
	}
      /* Handle current char greater than node splitchar */
      else
	{
	  pcurr = &(curr->hikid);
	}
    }
  /* It's not a duplicate string, and we should insert what's left of
     the string, into the tree rooted at curr */
  for (;;)
    {
      /* Allocate the memory for the node, and fill it in */
      *pcurr = (ternary_tree) xmalloc (sizeof (ternary_node));
      curr = *pcurr;
      curr->splitchar = *s;
      curr->lokid = curr->hikid = curr->eqkid = 0;

      /* Place nodes until we hit the end of the string.
         When we hit it, place the data in the right place, and
         return.
       */
      if (*s++ == 0)
	{
	  curr->eqkid = (ternary_tree) data;
	  return data;
	}
      pcurr = &(curr->eqkid);
    }
}

/* Free the ternary search tree rooted at p. */
void
ternary_cleanup (p)
     ternary_tree p;
{
  if (p)
    {
      ternary_cleanup (p->lokid);
      if (p->splitchar)
	ternary_cleanup (p->eqkid);
      ternary_cleanup (p->hikid);
      free (p);
    }
}

/* Non-recursive find of a string in the ternary tree */
PTR
ternary_search (p, s)
     const ternary_node *p;
     const char *s;
{
  const ternary_node *curr;
  int diff, spchar;
  spchar = *s;
  curr = p;
  /* Loop while we haven't hit a NULL node or returned */
  while (curr)
    {
      /* Calculate the difference */
      diff = spchar - curr->splitchar;
      /* Handle the equal case */
      if (diff == 0)
	{
	  if (spchar == 0)
	    return (PTR) curr->eqkid;
	  spchar = *++s;
	  curr = curr->eqkid;
	}
      /* Handle the less than case */
      else if (diff < 0)
	curr = curr->lokid;
      /* All that's left is greater than */
      else
	curr = curr->hikid;
    }
  return NULL;
}

/* For those who care, the recursive version of the search. Useful if
   you want a starting point for pmsearch or nearsearch. */
static PTR
ternary_recursivesearch (p, s)
     const ternary_node *p;
     const char *s;
{
  if (!p)
    return 0;
  if (*s < p->splitchar)
    return ternary_recursivesearch (p->lokid, s);
  else if (*s > p->splitchar)
    return ternary_recursivesearch (p->hikid, s);
  else
    {
      if (*s == 0)
	return (PTR) p->eqkid;
      return ternary_recursivesearch (p->eqkid, ++s);
    }
}