1 /* ternary.c - Ternary Search Trees 2 Copyright (C) 2001 Free Software Foundation, Inc. 3 4 Contributed by Daniel Berlin (dan@cgsoftware.com) 5 6 This program is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 2, or (at your option) any 9 later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 19 USA. */ 20 #ifdef HAVE_CONFIG_H 21 #include "config.h" 22 #endif 23 24 #ifdef HAVE_STDLIB_H 25 #include <stdlib.h> 26 #endif 27 28 #include <stdio.h> 29 30 #include "libiberty.h" 31 #include "ternary.h" 32 33 /* Non-recursive so we don't waste stack space/time on large 34 insertions. */ 35 36 PTR 37 ternary_insert (ternary_tree *root, const char *s, PTR data, int replace) 38 { 39 int diff; 40 ternary_tree curr, *pcurr; 41 42 /* Start at the root. */ 43 pcurr = root; 44 /* Loop until we find the right position */ 45 while ((curr = *pcurr)) 46 { 47 /* Calculate the difference */ 48 diff = *s - curr->splitchar; 49 /* Handle current char equal to node splitchar */ 50 if (diff == 0) 51 { 52 /* Handle the case of a string we already have */ 53 if (*s++ == 0) 54 { 55 if (replace) 56 curr->eqkid = (ternary_tree) data; 57 return (PTR) curr->eqkid; 58 } 59 pcurr = &(curr->eqkid); 60 } 61 /* Handle current char less than node splitchar */ 62 else if (diff < 0) 63 { 64 pcurr = &(curr->lokid); 65 } 66 /* Handle current char greater than node splitchar */ 67 else 68 { 69 pcurr = &(curr->hikid); 70 } 71 } 72 /* It's not a duplicate string, and we should insert what's left of 73 the string, into the tree rooted at curr */ 74 for (;;) 75 { 76 /* Allocate the memory for the node, and fill it in */ 77 *pcurr = XNEW (ternary_node); 78 curr = *pcurr; 79 curr->splitchar = *s; 80 curr->lokid = curr->hikid = curr->eqkid = 0; 81 82 /* Place nodes until we hit the end of the string. 83 When we hit it, place the data in the right place, and 84 return. 85 */ 86 if (*s++ == 0) 87 { 88 curr->eqkid = (ternary_tree) data; 89 return data; 90 } 91 pcurr = &(curr->eqkid); 92 } 93 } 94 95 /* Free the ternary search tree rooted at p. */ 96 void 97 ternary_cleanup (ternary_tree p) 98 { 99 if (p) 100 { 101 ternary_cleanup (p->lokid); 102 if (p->splitchar) 103 ternary_cleanup (p->eqkid); 104 ternary_cleanup (p->hikid); 105 free (p); 106 } 107 } 108 109 /* Non-recursive find of a string in the ternary tree */ 110 PTR 111 ternary_search (const ternary_node *p, const char *s) 112 { 113 const ternary_node *curr; 114 int diff, spchar; 115 spchar = *s; 116 curr = p; 117 /* Loop while we haven't hit a NULL node or returned */ 118 while (curr) 119 { 120 /* Calculate the difference */ 121 diff = spchar - curr->splitchar; 122 /* Handle the equal case */ 123 if (diff == 0) 124 { 125 if (spchar == 0) 126 return (PTR) curr->eqkid; 127 spchar = *++s; 128 curr = curr->eqkid; 129 } 130 /* Handle the less than case */ 131 else if (diff < 0) 132 curr = curr->lokid; 133 /* All that's left is greater than */ 134 else 135 curr = curr->hikid; 136 } 137 return NULL; 138 } 139 140 /* For those who care, the recursive version of the search. Useful if 141 you want a starting point for pmsearch or nearsearch. */ 142 static PTR 143 ternary_recursivesearch (const ternary_node *p, const char *s) 144 { 145 if (!p) 146 return 0; 147 if (*s < p->splitchar) 148 return ternary_recursivesearch (p->lokid, s); 149 else if (*s > p->splitchar) 150 return ternary_recursivesearch (p->hikid, s); 151 else 152 { 153 if (*s == 0) 154 return (PTR) p->eqkid; 155 return ternary_recursivesearch (p->eqkid, ++s); 156 } 157 } 158