ternary.c revision 302408
141502Swpaul/* ternary.c - Ternary Search Trees 241502Swpaul Copyright (C) 2001 Free Software Foundation, Inc. 341502Swpaul 441502Swpaul Contributed by Daniel Berlin (dan@cgsoftware.com) 541502Swpaul 641502Swpaul This program is free software; you can redistribute it and/or modify it 741502Swpaul under the terms of the GNU General Public License as published by the 841502Swpaul Free Software Foundation; either version 2, or (at your option) any 941502Swpaul later version. 1041502Swpaul 1141502Swpaul This program is distributed in the hope that it will be useful, 1241502Swpaul but WITHOUT ANY WARRANTY; without even the implied warranty of 1341502Swpaul MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1441502Swpaul GNU General Public License for more details. 1541502Swpaul 1641502Swpaul You should have received a copy of the GNU General Public License 1741502Swpaul along with this program; if not, write to the Free Software 1841502Swpaul Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 1941502Swpaul USA. */ 2041502Swpaul#ifdef HAVE_CONFIG_H 2141502Swpaul#include "config.h" 2241502Swpaul#endif 2341502Swpaul 2441502Swpaul#ifdef HAVE_STDLIB_H 2541502Swpaul#include <stdlib.h> 2641502Swpaul#endif 2741502Swpaul 2841502Swpaul#include <stdio.h> 2941502Swpaul 3041502Swpaul#include "libiberty.h" 3141502Swpaul#include "ternary.h" 3250477Speter 3341502Swpaul/* Non-recursive so we don't waste stack space/time on large 3441502Swpaul insertions. */ 3541502Swpaul 3641502SwpaulPTR 3741502Swpaulternary_insert (ternary_tree *root, const char *s, PTR data, int replace) 3841502Swpaul{ 3941502Swpaul int diff; 4041502Swpaul ternary_tree curr, *pcurr; 4141502Swpaul 4241502Swpaul /* Start at the root. */ 4341502Swpaul pcurr = root; 4441502Swpaul /* Loop until we find the right position */ 4541502Swpaul while ((curr = *pcurr)) 4641502Swpaul { 4741502Swpaul /* Calculate the difference */ 4841502Swpaul diff = *s - curr->splitchar; 4941502Swpaul /* Handle current char equal to node splitchar */ 5041502Swpaul if (diff == 0) 5141502Swpaul { 5241502Swpaul /* Handle the case of a string we already have */ 5341502Swpaul if (*s++ == 0) 5441502Swpaul { 5541502Swpaul if (replace) 5641502Swpaul curr->eqkid = (ternary_tree) data; 5741502Swpaul return (PTR) curr->eqkid; 5841502Swpaul } 5941502Swpaul pcurr = &(curr->eqkid); 6041502Swpaul } 6141502Swpaul /* Handle current char less than node splitchar */ 6248645Sdes else if (diff < 0) 6341502Swpaul { 6441502Swpaul pcurr = &(curr->lokid); 6541502Swpaul } 6641502Swpaul /* Handle current char greater than node splitchar */ 6741502Swpaul else 6841502Swpaul { 6941502Swpaul pcurr = &(curr->hikid); 7041502Swpaul } 7141502Swpaul } 7241502Swpaul /* It's not a duplicate string, and we should insert what's left of 7341502Swpaul the string, into the tree rooted at curr */ 7441502Swpaul for (;;) 7541502Swpaul { 7641502Swpaul /* Allocate the memory for the node, and fill it in */ 7741502Swpaul *pcurr = XNEW (ternary_node); 7848645Sdes curr = *pcurr; 7941502Swpaul curr->splitchar = *s; 8041502Swpaul curr->lokid = curr->hikid = curr->eqkid = 0; 8141502Swpaul 8251354Swpaul /* Place nodes until we hit the end of the string. 8351354Swpaul When we hit it, place the data in the right place, and 8451354Swpaul return. 8551354Swpaul */ 8651354Swpaul if (*s++ == 0) 8741502Swpaul { 8841502Swpaul curr->eqkid = (ternary_tree) data; 8941502Swpaul return data; 9041502Swpaul } 9141502Swpaul pcurr = &(curr->eqkid); 9241502Swpaul } 9349610Swpaul} 9449610Swpaul 9549610Swpaul/* Free the ternary search tree rooted at p. */ 9641502Swpaulvoid 9751432Swpaulternary_cleanup (ternary_tree p) 9851432Swpaul{ 9951432Swpaul if (p) 10041502Swpaul { 10141502Swpaul ternary_cleanup (p->lokid); 10241502Swpaul if (p->splitchar) 10341502Swpaul ternary_cleanup (p->eqkid); 10441502Swpaul ternary_cleanup (p->hikid); 10541502Swpaul free (p); 10641502Swpaul } 10751432Swpaul} 10851432Swpaul 10951432Swpaul/* Non-recursive find of a string in the ternary tree */ 11041502SwpaulPTR 11141591Sarchieternary_search (const ternary_node *p, const char *s) 11250477Speter{ 11341502Swpaul const ternary_node *curr; 11441502Swpaul int diff, spchar; 11541502Swpaul spchar = *s; 11641502Swpaul curr = p; 11741502Swpaul /* Loop while we haven't hit a NULL node or returned */ 11841502Swpaul while (curr) 11941502Swpaul { 12041502Swpaul /* Calculate the difference */ 12141502Swpaul diff = spchar - curr->splitchar; 12241502Swpaul /* Handle the equal case */ 12344238Swpaul if (diff == 0) 12444238Swpaul { 12544238Swpaul if (spchar == 0) 12644238Swpaul return (PTR) curr->eqkid; 12741502Swpaul spchar = *++s; 12841502Swpaul curr = curr->eqkid; 12941502Swpaul } 13049610Swpaul /* Handle the less than case */ 13149610Swpaul else if (diff < 0) 13249610Swpaul curr = curr->lokid; 13341502Swpaul /* All that's left is greater than */ 13441502Swpaul else 13549610Swpaul curr = curr->hikid; 13649610Swpaul } 13741502Swpaul return NULL; 13841502Swpaul} 13941502Swpaul 14041502Swpaul/* For those who care, the recursive version of the search. Useful if 14141502Swpaul you want a starting point for pmsearch or nearsearch. */ 14241502Swpaulstatic PTR 14341502Swpaulternary_recursivesearch (const ternary_node *p, const char *s) 14451432Swpaul{ 14541502Swpaul if (!p) 14641502Swpaul return 0; 14741502Swpaul if (*s < p->splitchar) 14841502Swpaul return ternary_recursivesearch (p->lokid, s); 14941502Swpaul else if (*s > p->splitchar) 15041502Swpaul return ternary_recursivesearch (p->hikid, s); 15149610Swpaul else 15241502Swpaul { 15341502Swpaul if (*s == 0) 15441502Swpaul return (PTR) p->eqkid; 15541502Swpaul return ternary_recursivesearch (p->eqkid, ++s); 15641502Swpaul } 15741502Swpaul} 15841502Swpaul