1169695Skan/* ternary.c - Ternary Search Trees 2169695Skan Copyright (C) 2001 Free Software Foundation, Inc. 3169695Skan 4169695Skan Contributed by Daniel Berlin (dan@cgsoftware.com) 5169695Skan 6169695Skan This program is free software; you can redistribute it and/or modify it 7169695Skan under the terms of the GNU General Public License as published by the 8169695Skan Free Software Foundation; either version 2, or (at your option) any 9169695Skan later version. 10169695Skan 11169695Skan This program is distributed in the hope that it will be useful, 12169695Skan but WITHOUT ANY WARRANTY; without even the implied warranty of 13169695Skan MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169695Skan GNU General Public License for more details. 15169695Skan 16169695Skan You should have received a copy of the GNU General Public License 17169695Skan along with this program; if not, write to the Free Software 18169695Skan Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 19169695Skan USA. */ 20169695Skan#ifdef HAVE_CONFIG_H 21169695Skan#include "config.h" 22169695Skan#endif 23169695Skan 24169695Skan#ifdef HAVE_STDLIB_H 25169695Skan#include <stdlib.h> 26169695Skan#endif 27169695Skan 28169695Skan#include <stdio.h> 29169695Skan 30169695Skan#include "libiberty.h" 31169695Skan#include "ternary.h" 32169695Skan 33169695Skan/* Non-recursive so we don't waste stack space/time on large 34169695Skan insertions. */ 35169695Skan 36169695SkanPTR 37169695Skanternary_insert (ternary_tree *root, const char *s, PTR data, int replace) 38169695Skan{ 39169695Skan int diff; 40169695Skan ternary_tree curr, *pcurr; 41169695Skan 42169695Skan /* Start at the root. */ 43169695Skan pcurr = root; 44169695Skan /* Loop until we find the right position */ 45169695Skan while ((curr = *pcurr)) 46169695Skan { 47169695Skan /* Calculate the difference */ 48169695Skan diff = *s - curr->splitchar; 49169695Skan /* Handle current char equal to node splitchar */ 50169695Skan if (diff == 0) 51169695Skan { 52169695Skan /* Handle the case of a string we already have */ 53169695Skan if (*s++ == 0) 54169695Skan { 55169695Skan if (replace) 56169695Skan curr->eqkid = (ternary_tree) data; 57169695Skan return (PTR) curr->eqkid; 58169695Skan } 59169695Skan pcurr = &(curr->eqkid); 60169695Skan } 61169695Skan /* Handle current char less than node splitchar */ 62169695Skan else if (diff < 0) 63169695Skan { 64169695Skan pcurr = &(curr->lokid); 65169695Skan } 66169695Skan /* Handle current char greater than node splitchar */ 67169695Skan else 68169695Skan { 69169695Skan pcurr = &(curr->hikid); 70169695Skan } 71169695Skan } 72169695Skan /* It's not a duplicate string, and we should insert what's left of 73169695Skan the string, into the tree rooted at curr */ 74169695Skan for (;;) 75169695Skan { 76169695Skan /* Allocate the memory for the node, and fill it in */ 77169695Skan *pcurr = XNEW (ternary_node); 78169695Skan curr = *pcurr; 79169695Skan curr->splitchar = *s; 80169695Skan curr->lokid = curr->hikid = curr->eqkid = 0; 81169695Skan 82169695Skan /* Place nodes until we hit the end of the string. 83169695Skan When we hit it, place the data in the right place, and 84169695Skan return. 85169695Skan */ 86169695Skan if (*s++ == 0) 87169695Skan { 88169695Skan curr->eqkid = (ternary_tree) data; 89169695Skan return data; 90169695Skan } 91169695Skan pcurr = &(curr->eqkid); 92169695Skan } 93169695Skan} 94169695Skan 95169695Skan/* Free the ternary search tree rooted at p. */ 96169695Skanvoid 97169695Skanternary_cleanup (ternary_tree p) 98169695Skan{ 99169695Skan if (p) 100169695Skan { 101169695Skan ternary_cleanup (p->lokid); 102169695Skan if (p->splitchar) 103169695Skan ternary_cleanup (p->eqkid); 104169695Skan ternary_cleanup (p->hikid); 105169695Skan free (p); 106169695Skan } 107169695Skan} 108169695Skan 109169695Skan/* Non-recursive find of a string in the ternary tree */ 110169695SkanPTR 111169695Skanternary_search (const ternary_node *p, const char *s) 112169695Skan{ 113169695Skan const ternary_node *curr; 114169695Skan int diff, spchar; 115169695Skan spchar = *s; 116169695Skan curr = p; 117169695Skan /* Loop while we haven't hit a NULL node or returned */ 118169695Skan while (curr) 119169695Skan { 120169695Skan /* Calculate the difference */ 121169695Skan diff = spchar - curr->splitchar; 122169695Skan /* Handle the equal case */ 123169695Skan if (diff == 0) 124169695Skan { 125169695Skan if (spchar == 0) 126169695Skan return (PTR) curr->eqkid; 127169695Skan spchar = *++s; 128169695Skan curr = curr->eqkid; 129169695Skan } 130169695Skan /* Handle the less than case */ 131169695Skan else if (diff < 0) 132169695Skan curr = curr->lokid; 133169695Skan /* All that's left is greater than */ 134169695Skan else 135169695Skan curr = curr->hikid; 136169695Skan } 137169695Skan return NULL; 138169695Skan} 139169695Skan 140169695Skan/* For those who care, the recursive version of the search. Useful if 141169695Skan you want a starting point for pmsearch or nearsearch. */ 142169695Skanstatic PTR 143169695Skanternary_recursivesearch (const ternary_node *p, const char *s) 144169695Skan{ 145169695Skan if (!p) 146169695Skan return 0; 147169695Skan if (*s < p->splitchar) 148169695Skan return ternary_recursivesearch (p->lokid, s); 149169695Skan else if (*s > p->splitchar) 150169695Skan return ternary_recursivesearch (p->hikid, s); 151169695Skan else 152169695Skan { 153169695Skan if (*s == 0) 154169695Skan return (PTR) p->eqkid; 155169695Skan return ternary_recursivesearch (p->eqkid, ++s); 156169695Skan } 157169695Skan} 158