1*d2201f2fSdrahn /* ternary.h - Ternary Search Trees 2*d2201f2fSdrahn Copyright 2001 Free Software Foundation, Inc. 3*d2201f2fSdrahn 4*d2201f2fSdrahn Contributed by Daniel Berlin (dan@cgsoftware.com) 5*d2201f2fSdrahn 6*d2201f2fSdrahn 7*d2201f2fSdrahn This program is free software; you can redistribute it and/or modify it 8*d2201f2fSdrahn under the terms of the GNU General Public License as published by the 9*d2201f2fSdrahn Free Software Foundation; either version 2, or (at your option) any 10*d2201f2fSdrahn later version. 11*d2201f2fSdrahn 12*d2201f2fSdrahn This program is distributed in the hope that it will be useful, 13*d2201f2fSdrahn but WITHOUT ANY WARRANTY; without even the implied warranty of 14*d2201f2fSdrahn MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15*d2201f2fSdrahn GNU General Public License for more details. 16*d2201f2fSdrahn 17*d2201f2fSdrahn You should have received a copy of the GNU General Public License 18*d2201f2fSdrahn along with this program; if not, write to the Free Software 19*d2201f2fSdrahn Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 20*d2201f2fSdrahn USA. */ 21*d2201f2fSdrahn #ifndef TERNARY_H_ 22*d2201f2fSdrahn #define TERNARY_H_ 23*d2201f2fSdrahn /* Ternary search trees */ 24*d2201f2fSdrahn 25*d2201f2fSdrahn typedef struct ternary_node_def *ternary_tree; 26*d2201f2fSdrahn 27*d2201f2fSdrahn typedef struct ternary_node_def 28*d2201f2fSdrahn { 29*d2201f2fSdrahn char splitchar; 30*d2201f2fSdrahn ternary_tree lokid; 31*d2201f2fSdrahn ternary_tree eqkid; 32*d2201f2fSdrahn ternary_tree hikid; 33*d2201f2fSdrahn } 34*d2201f2fSdrahn ternary_node; 35*d2201f2fSdrahn 36*d2201f2fSdrahn /* Insert string S into tree P, associating it with DATA. 37*d2201f2fSdrahn Return the data in the tree associated with the string if it's 38*d2201f2fSdrahn already there, and replace is 0. 39*d2201f2fSdrahn Otherwise, replaces if it it exists, inserts if it doesn't, and 40*d2201f2fSdrahn returns the data you passed in. */ 41*d2201f2fSdrahn PTR ternary_insert PARAMS ((ternary_tree *p, const char *s, 42*d2201f2fSdrahn PTR data, int replace)); 43*d2201f2fSdrahn 44*d2201f2fSdrahn /* Delete the ternary search tree rooted at P. 45*d2201f2fSdrahn Does NOT delete the data you associated with the strings. */ 46*d2201f2fSdrahn void ternary_cleanup PARAMS ((ternary_tree p)); 47*d2201f2fSdrahn 48*d2201f2fSdrahn /* Search the ternary tree for string S, returning the data associated 49*d2201f2fSdrahn with it if found. */ 50*d2201f2fSdrahn PTR ternary_search PARAMS ((const ternary_node *p, const char *s)); 51*d2201f2fSdrahn #endif 52