diff options
Diffstat (limited to 'libiberty/ternary.c')
| -rw-r--r-- | libiberty/ternary.c | 166 |
1 files changed, 0 insertions, 166 deletions
diff --git a/libiberty/ternary.c b/libiberty/ternary.c deleted file mode 100644 index 056d2cee11e..00000000000 --- a/libiberty/ternary.c +++ /dev/null @@ -1,166 +0,0 @@ -/* 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); - } -} |