From eec194201326ff6154193b96635d644f69745be5 Mon Sep 17 00:00:00 2001 From: dberlin Date: Mon, 16 Apr 2001 15:30:17 +0000 Subject: [PATCH] 2001-04-15 Daniel Berlin * ternary.h: New file - Ternary search tree header. 2001-04-15 Daniel Berlin * ternary.c: New file - Ternary search tree implementation. * Makefile.in: Add ternary.o, and ternary.c dependencies. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@41380 138bc75d-0d04-0410-961f-82ee72b054a4 --- include/ChangeLog | 4 ++ include/ternary.h | 50 ++++++++++++++++ libiberty/ChangeLog | 6 ++ libiberty/Makefile.in | 5 +- libiberty/ternary.c | 157 ++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 220 insertions(+), 2 deletions(-) create mode 100644 include/ternary.h create mode 100644 libiberty/ternary.c diff --git a/include/ChangeLog b/include/ChangeLog index a0372d4..f0a166c 100644 --- a/include/ChangeLog +++ b/include/ChangeLog @@ -1,3 +1,7 @@ +2001-04-15 Daniel Berlin + + * ternary.h: New file - Ternary search tree header. + 2001-04-03 Zack Weinberg * ansidecl.h: All logic from gcc/gansidecl.h moved here. diff --git a/include/ternary.h b/include/ternary.h new file mode 100644 index 0000000..2e0c828 --- /dev/null +++ b/include/ternary.h @@ -0,0 +1,50 @@ +/* ternary.h - Ternary Search Trees + Copyright 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. */ +#ifndef TERNARY_H_ +#define TERNARY_H_ +/* Ternary search trees */ + +typedef struct ternary_node_def *ternary_tree; + +typedef struct ternary_node_def +{ + char splitchar; + ternary_tree lokid; + ternary_tree eqkid; + ternary_tree hikid; +} +ternary_node; + +/* Insert string S into tree P, associating it with DATA. + Return the data in the tree associated with the string if it's + already there, and replace is 0. + Otherwise, replaces if it it exists, inserts if it doesn't, and + returns the data you passed in. */ +void *ternary_insert (ternary_tree *p, char *s, void *data, int replace); + +/* Delete the ternary search tree rooted at P. + Does NOT delete the data you associated with the strings. */ +void ternary_cleanup (ternary_tree p); + +/* Search the ternary tree for string S, returning the data associated + with it if found. */ +void *ternary_search (ternary_tree p, char *s); +#endif diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index 5ae4abe..53e4290 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,9 @@ +2001-04-15 Daniel Berlin + + * ternary.c: New file - Ternary search tree implementation. + + * Makefile.in: Add ternary.o, and ternary.c dependencies. + 2001-04-03 Zack Weinberg * make-temp-file.c (try): Inline. diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in index 9b5951f..92b90fa 100644 --- a/libiberty/Makefile.in +++ b/libiberty/Makefile.in @@ -132,7 +132,7 @@ CFILES = asprintf.c alloca.c argv.c atexit.c basename.c bcmp.c bcopy.c \ strncasecmp.c strchr.c strdup.c strerror.c strncmp.c strrchr.c \ strsignal.c strstr.c strtod.c strtol.c strtoul.c tmpnam.c vasprintf.c \ vfork.c vfprintf.c vprintf.c vsprintf.c waitpid.c xatexit.c xexit.c \ - xmalloc.c xmemdup.c xstrdup.c xstrerror.c + xmalloc.c xmemdup.c xstrdup.c xstrerror.c ternary.c # These are always included in the library. REQUIRED_OFILES = argv.o alloca.o choose-temp.o concat.o cplus-dem.o \ @@ -141,7 +141,7 @@ REQUIRED_OFILES = argv.o alloca.o choose-temp.o concat.o cplus-dem.o \ md5.o make-temp-file.o objalloc.o \ obstack.o partition.o pexecute.o safe-ctype.o sort.o spaces.o \ splay-tree.o strerror.o strsignal.o xatexit.o xexit.o xmalloc.o \ - xmemdup.o xstrdup.o xstrerror.o + xmemdup.o xstrdup.o xstrerror.o ternary.o $(TARGETLIB): $(REQUIRED_OFILES) $(EXTRA_OFILES) $(LIBOBJS) -rm -f $(TARGETLIB) @@ -290,6 +290,7 @@ strerror.o: config.h $(INCDIR)/libiberty.h strsignal.o: config.h $(INCDIR)/libiberty.h strtol.o: config.h strtoul.o: config.h +ternary.o: config.h $(INCDIR)/ternary.h $(INCDIR)/libiberty.h vasprintf.o: config.h xatexit.o: $(INCDIR)/libiberty.h xexit.o: config.h $(INCDIR)/libiberty.h diff --git a/libiberty/ternary.c b/libiberty/ternary.c new file mode 100644 index 0000000..c5ef3a5 --- /dev/null +++ b/libiberty/ternary.c @@ -0,0 +1,157 @@ +/* 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 +#endif + +#include + +#include "libiberty.h" +#include "ternary.h" + +/* Non-recursive so we don't waste stack space/time on large + insertions. */ + +void * +ternary_insert (ternary_tree * root, char *s, void *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 (void *) 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 (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 */ +void * +ternary_search (ternary_tree p, char *s) +{ + ternary_tree 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 (void *) 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 void * +ternary_recursivesearch (ternary_tree p, 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 (void *) p->eqkid; + return ternary_recursivesearch (p->eqkid, ++s); + } +} -- 2.7.4