/* ternary.c - Ternary Search Trees
|
/* ternary.c - Ternary Search Trees
|
Copyright (C) 2001 Free Software Foundation, Inc.
|
Copyright (C) 2001 Free Software Foundation, Inc.
|
|
|
Contributed by Daniel Berlin (dan@cgsoftware.com)
|
Contributed by Daniel Berlin (dan@cgsoftware.com)
|
|
|
This program is free software; you can redistribute it and/or modify it
|
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
|
under the terms of the GNU General Public License as published by the
|
Free Software Foundation; either version 2, or (at your option) any
|
Free Software Foundation; either version 2, or (at your option) any
|
later version.
|
later version.
|
|
|
This program is distributed in the hope that it will be useful,
|
This program is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with this program; if not, write to the Free Software
|
along with this program; if not, write to the Free Software
|
Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301,
|
Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301,
|
USA. */
|
USA. */
|
#ifdef HAVE_CONFIG_H
|
#ifdef HAVE_CONFIG_H
|
#include "config.h"
|
#include "config.h"
|
#endif
|
#endif
|
|
|
#ifdef HAVE_STDLIB_H
|
#ifdef HAVE_STDLIB_H
|
#include <stdlib.h>
|
#include <stdlib.h>
|
#endif
|
#endif
|
|
|
#include <stdio.h>
|
#include <stdio.h>
|
|
|
#include "libiberty.h"
|
#include "libiberty.h"
|
#include "ternary.h"
|
#include "ternary.h"
|
|
|
/* Non-recursive so we don't waste stack space/time on large
|
/* Non-recursive so we don't waste stack space/time on large
|
insertions. */
|
insertions. */
|
|
|
PTR
|
PTR
|
ternary_insert (ternary_tree *root, const char *s, PTR data, int replace)
|
ternary_insert (ternary_tree *root, const char *s, PTR data, int replace)
|
{
|
{
|
int diff;
|
int diff;
|
ternary_tree curr, *pcurr;
|
ternary_tree curr, *pcurr;
|
|
|
/* Start at the root. */
|
/* Start at the root. */
|
pcurr = root;
|
pcurr = root;
|
/* Loop until we find the right position */
|
/* Loop until we find the right position */
|
while ((curr = *pcurr))
|
while ((curr = *pcurr))
|
{
|
{
|
/* Calculate the difference */
|
/* Calculate the difference */
|
diff = *s - curr->splitchar;
|
diff = *s - curr->splitchar;
|
/* Handle current char equal to node splitchar */
|
/* Handle current char equal to node splitchar */
|
if (diff == 0)
|
if (diff == 0)
|
{
|
{
|
/* Handle the case of a string we already have */
|
/* Handle the case of a string we already have */
|
if (*s++ == 0)
|
if (*s++ == 0)
|
{
|
{
|
if (replace)
|
if (replace)
|
curr->eqkid = (ternary_tree) data;
|
curr->eqkid = (ternary_tree) data;
|
return (PTR) curr->eqkid;
|
return (PTR) curr->eqkid;
|
}
|
}
|
pcurr = &(curr->eqkid);
|
pcurr = &(curr->eqkid);
|
}
|
}
|
/* Handle current char less than node splitchar */
|
/* Handle current char less than node splitchar */
|
else if (diff < 0)
|
else if (diff < 0)
|
{
|
{
|
pcurr = &(curr->lokid);
|
pcurr = &(curr->lokid);
|
}
|
}
|
/* Handle current char greater than node splitchar */
|
/* Handle current char greater than node splitchar */
|
else
|
else
|
{
|
{
|
pcurr = &(curr->hikid);
|
pcurr = &(curr->hikid);
|
}
|
}
|
}
|
}
|
/* It's not a duplicate string, and we should insert what's left of
|
/* It's not a duplicate string, and we should insert what's left of
|
the string, into the tree rooted at curr */
|
the string, into the tree rooted at curr */
|
for (;;)
|
for (;;)
|
{
|
{
|
/* Allocate the memory for the node, and fill it in */
|
/* Allocate the memory for the node, and fill it in */
|
*pcurr = XNEW (ternary_node);
|
*pcurr = XNEW (ternary_node);
|
curr = *pcurr;
|
curr = *pcurr;
|
curr->splitchar = *s;
|
curr->splitchar = *s;
|
curr->lokid = curr->hikid = curr->eqkid = 0;
|
curr->lokid = curr->hikid = curr->eqkid = 0;
|
|
|
/* Place nodes until we hit the end of the string.
|
/* Place nodes until we hit the end of the string.
|
When we hit it, place the data in the right place, and
|
When we hit it, place the data in the right place, and
|
return.
|
return.
|
*/
|
*/
|
if (*s++ == 0)
|
if (*s++ == 0)
|
{
|
{
|
curr->eqkid = (ternary_tree) data;
|
curr->eqkid = (ternary_tree) data;
|
return data;
|
return data;
|
}
|
}
|
pcurr = &(curr->eqkid);
|
pcurr = &(curr->eqkid);
|
}
|
}
|
}
|
}
|
|
|
/* Free the ternary search tree rooted at p. */
|
/* Free the ternary search tree rooted at p. */
|
void
|
void
|
ternary_cleanup (ternary_tree p)
|
ternary_cleanup (ternary_tree p)
|
{
|
{
|
if (p)
|
if (p)
|
{
|
{
|
ternary_cleanup (p->lokid);
|
ternary_cleanup (p->lokid);
|
if (p->splitchar)
|
if (p->splitchar)
|
ternary_cleanup (p->eqkid);
|
ternary_cleanup (p->eqkid);
|
ternary_cleanup (p->hikid);
|
ternary_cleanup (p->hikid);
|
free (p);
|
free (p);
|
}
|
}
|
}
|
}
|
|
|
/* Non-recursive find of a string in the ternary tree */
|
/* Non-recursive find of a string in the ternary tree */
|
PTR
|
PTR
|
ternary_search (const ternary_node *p, const char *s)
|
ternary_search (const ternary_node *p, const char *s)
|
{
|
{
|
const ternary_node *curr;
|
const ternary_node *curr;
|
int diff, spchar;
|
int diff, spchar;
|
spchar = *s;
|
spchar = *s;
|
curr = p;
|
curr = p;
|
/* Loop while we haven't hit a NULL node or returned */
|
/* Loop while we haven't hit a NULL node or returned */
|
while (curr)
|
while (curr)
|
{
|
{
|
/* Calculate the difference */
|
/* Calculate the difference */
|
diff = spchar - curr->splitchar;
|
diff = spchar - curr->splitchar;
|
/* Handle the equal case */
|
/* Handle the equal case */
|
if (diff == 0)
|
if (diff == 0)
|
{
|
{
|
if (spchar == 0)
|
if (spchar == 0)
|
return (PTR) curr->eqkid;
|
return (PTR) curr->eqkid;
|
spchar = *++s;
|
spchar = *++s;
|
curr = curr->eqkid;
|
curr = curr->eqkid;
|
}
|
}
|
/* Handle the less than case */
|
/* Handle the less than case */
|
else if (diff < 0)
|
else if (diff < 0)
|
curr = curr->lokid;
|
curr = curr->lokid;
|
/* All that's left is greater than */
|
/* All that's left is greater than */
|
else
|
else
|
curr = curr->hikid;
|
curr = curr->hikid;
|
}
|
}
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* For those who care, the recursive version of the search. Useful if
|
/* For those who care, the recursive version of the search. Useful if
|
you want a starting point for pmsearch or nearsearch. */
|
you want a starting point for pmsearch or nearsearch. */
|
static PTR
|
static PTR
|
ternary_recursivesearch (const ternary_node *p, const char *s)
|
ternary_recursivesearch (const ternary_node *p, const char *s)
|
{
|
{
|
if (!p)
|
if (!p)
|
return 0;
|
return 0;
|
if (*s < p->splitchar)
|
if (*s < p->splitchar)
|
return ternary_recursivesearch (p->lokid, s);
|
return ternary_recursivesearch (p->lokid, s);
|
else if (*s > p->splitchar)
|
else if (*s > p->splitchar)
|
return ternary_recursivesearch (p->hikid, s);
|
return ternary_recursivesearch (p->hikid, s);
|
else
|
else
|
{
|
{
|
if (*s == 0)
|
if (*s == 0)
|
return (PTR) p->eqkid;
|
return (PTR) p->eqkid;
|
return ternary_recursivesearch (p->eqkid, ++s);
|
return ternary_recursivesearch (p->eqkid, ++s);
|
}
|
}
|
}
|
}
|
|
|
