summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorobrien <obrien@FreeBSD.org>1999-11-04 10:35:02 +0000
committerobrien <obrien@FreeBSD.org>1999-11-04 10:35:02 +0000
commit077ec7b22cc6ba9c1f5d23eef88ff83789900257 (patch)
tree5dbb0dd6946cf5bf1f078e431ab087bd387439b5
parenta2002c935cbd0f080eb39fb15453135ae4221dfb (diff)
downloadFreeBSD-src-077ec7b22cc6ba9c1f5d23eef88ff83789900257.zip
FreeBSD-src-077ec7b22cc6ba9c1f5d23eef88ff83789900257.tar.gz
Virgin import from GCC 2.95.1.
As of GCC 2.95 these files from libiberty are absolutely required: ansidecl.h libiberty.h splay-tree.h splay-tree.c To keep from having to import all of libiberty, they are imported here for now. Before all is said and done, libiberty might be imported, or these files might move elsewhere.
-rw-r--r--contrib/gcc/ansidecl.h163
-rw-r--r--contrib/gcc/libiberty.h180
-rw-r--r--contrib/gcc/splay-tree.c368
-rw-r--r--contrib/gcc/splay-tree.h116
4 files changed, 827 insertions, 0 deletions
diff --git a/contrib/gcc/ansidecl.h b/contrib/gcc/ansidecl.h
new file mode 100644
index 0000000..cdb9fb7
--- /dev/null
+++ b/contrib/gcc/ansidecl.h
@@ -0,0 +1,163 @@
+/* ANSI and traditional C compatability macros
+ Copyright 1991, 1992, 1996 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+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 of the License, 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. */
+
+/* ANSI and traditional C compatibility macros
+
+ ANSI C is assumed if __STDC__ is #defined.
+
+ Macro ANSI C definition Traditional C definition
+ ----- ---- - ---------- ----------- - ----------
+ PTR `void *' `char *'
+ LONG_DOUBLE `long double' `double'
+ VOLATILE `volatile' `'
+ SIGNED `signed' `'
+ PTRCONST `void *const' `char *'
+ ANSI_PROTOTYPES 1 not defined
+
+ CONST is also defined, but is obsolete. Just use const.
+
+ obsolete -- DEFUN (name, arglist, args)
+
+ Defines function NAME.
+
+ ARGLIST lists the arguments, separated by commas and enclosed in
+ parentheses. ARGLIST becomes the argument list in traditional C.
+
+ ARGS list the arguments with their types. It becomes a prototype in
+ ANSI C, and the type declarations in traditional C. Arguments should
+ be separated with `AND'. For functions with a variable number of
+ arguments, the last thing listed should be `DOTS'.
+
+ obsolete -- DEFUN_VOID (name)
+
+ Defines a function NAME, which takes no arguments.
+
+ obsolete -- EXFUN (name, (prototype)) -- obsolete.
+
+ Replaced by PARAMS. Do not use; will disappear someday soon.
+ Was used in external function declarations.
+ In ANSI C it is `NAME PROTOTYPE' (so PROTOTYPE should be enclosed in
+ parentheses). In traditional C it is `NAME()'.
+ For a function that takes no arguments, PROTOTYPE should be `(void)'.
+
+ obsolete -- PROTO (type, name, (prototype) -- obsolete.
+
+ This one has also been replaced by PARAMS. Do not use.
+
+ PARAMS ((args))
+
+ We could use the EXFUN macro to handle prototype declarations, but
+ the name is misleading and the result is ugly. So we just define a
+ simple macro to handle the parameter lists, as in:
+
+ static int foo PARAMS ((int, char));
+
+ This produces: `static int foo();' or `static int foo (int, char);'
+
+ EXFUN would have done it like this:
+
+ static int EXFUN (foo, (int, char));
+
+ but the function is not external...and it's hard to visually parse
+ the function name out of the mess. EXFUN should be considered
+ obsolete; new code should be written to use PARAMS.
+
+ DOTS is also obsolete.
+
+ Examples:
+
+ extern int printf PARAMS ((const char *format, ...));
+*/
+
+#ifndef _ANSIDECL_H
+
+#define _ANSIDECL_H 1
+
+
+/* Every source file includes this file,
+ so they will all get the switch for lint. */
+/* LINTLIBRARY */
+
+
+#if defined (__STDC__) || defined (_AIX) || (defined (__mips) && defined (_SYSTYPE_SVR4)) || defined(_WIN32)
+/* All known AIX compilers implement these things (but don't always
+ define __STDC__). The RISC/OS MIPS compiler defines these things
+ in SVR4 mode, but does not define __STDC__. */
+
+#define PTR void *
+#define PTRCONST void *CONST
+#define LONG_DOUBLE long double
+
+#ifndef IN_GCC
+#define AND ,
+#define NOARGS void
+#define VOLATILE volatile
+#define SIGNED signed
+#endif /* ! IN_GCC */
+
+#define PARAMS(paramlist) paramlist
+#define ANSI_PROTOTYPES 1
+
+#define VPARAMS(ARGS) ARGS
+#define VA_START(va_list,var) va_start(va_list,var)
+
+/* These are obsolete. Do not use. */
+#ifndef IN_GCC
+#define CONST const
+#define DOTS , ...
+#define PROTO(type, name, arglist) type name arglist
+#define EXFUN(name, proto) name proto
+#define DEFUN(name, arglist, args) name(args)
+#define DEFUN_VOID(name) name(void)
+#endif /* ! IN_GCC */
+
+#else /* Not ANSI C. */
+
+#define PTR char *
+#define PTRCONST PTR
+#define LONG_DOUBLE double
+
+#ifndef IN_GCC
+#define AND ;
+#define NOARGS
+#define VOLATILE
+#define SIGNED
+#endif /* !IN_GCC */
+
+#ifndef const /* some systems define it in header files for non-ansi mode */
+#define const
+#endif
+
+#define PARAMS(paramlist) ()
+
+#define VPARAMS(ARGS) (va_alist) va_dcl
+#define VA_START(va_list,var) va_start(va_list)
+
+/* These are obsolete. Do not use. */
+#ifndef IN_GCC
+#define CONST
+#define DOTS
+#define PROTO(type, name, arglist) type name ()
+#define EXFUN(name, proto) name()
+#define DEFUN(name, arglist, args) name arglist args;
+#define DEFUN_VOID(name) name()
+#endif /* ! IN_GCC */
+
+#endif /* ANSI C. */
+
+#endif /* ansidecl.h */
diff --git a/contrib/gcc/libiberty.h b/contrib/gcc/libiberty.h
new file mode 100644
index 0000000..cf31366
--- /dev/null
+++ b/contrib/gcc/libiberty.h
@@ -0,0 +1,180 @@
+/* Function declarations for libiberty.
+ Written by Cygnus Support, 1994.
+
+ The libiberty library provides a number of functions which are
+ missing on some operating systems. We do not declare those here,
+ to avoid conflicts with the system header files on operating
+ systems that do support those functions. In this file we only
+ declare those functions which are specific to libiberty. */
+
+#ifndef LIBIBERTY_H
+#define LIBIBERTY_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "ansidecl.h"
+
+/* Build an argument vector from a string. Allocates memory using
+ malloc. Use freeargv to free the vector. */
+
+extern char **buildargv PARAMS ((char *));
+
+/* Free a vector returned by buildargv. */
+
+extern void freeargv PARAMS ((char **));
+
+/* Duplicate an argument vector. Allocates memory using malloc. Use
+ freeargv to free the vector. */
+
+extern char **dupargv PARAMS ((char **));
+
+
+/* Return the last component of a path name. Note that we can't use a
+ prototype here because the parameter is declared inconsistently
+ across different systems, sometimes as "char *" and sometimes as
+ "const char *" */
+
+#if defined (__GNU_LIBRARY__ ) || defined (__linux__) || defined (__FreeBSD__) || defined (__CYGWIN__) || defined (__CYGWIN32__)
+extern char *basename PARAMS ((const char *));
+#else
+extern char *basename ();
+#endif
+
+/* Concatenate an arbitrary number of strings, up to (char *) NULL.
+ Allocates memory using xmalloc. */
+
+extern char *concat PARAMS ((const char *, ...));
+
+/* Check whether two file descriptors refer to the same file. */
+
+extern int fdmatch PARAMS ((int fd1, int fd2));
+
+/* Get the amount of time the process has run, in microseconds. */
+
+extern long get_run_time PARAMS ((void));
+
+/* Choose a temporary directory to use for scratch files. */
+
+extern char *choose_temp_base PARAMS ((void));
+
+/* Allocate memory filled with spaces. Allocates using malloc. */
+
+extern const char *spaces PARAMS ((int count));
+
+/* Return the maximum error number for which strerror will return a
+ string. */
+
+extern int errno_max PARAMS ((void));
+
+/* Return the name of an errno value (e.g., strerrno (EINVAL) returns
+ "EINVAL"). */
+
+extern const char *strerrno PARAMS ((int));
+
+/* Given the name of an errno value, return the value. */
+
+extern int strtoerrno PARAMS ((const char *));
+
+/* ANSI's strerror(), but more robust. */
+
+extern char *xstrerror PARAMS ((int));
+
+/* Return the maximum signal number for which strsignal will return a
+ string. */
+
+extern int signo_max PARAMS ((void));
+
+/* Return a signal message string for a signal number
+ (e.g., strsignal (SIGHUP) returns something like "Hangup"). */
+/* This is commented out as it can conflict with one in system headers.
+ We still document its existence though. */
+
+/*extern const char *strsignal PARAMS ((int));*/
+
+/* Return the name of a signal number (e.g., strsigno (SIGHUP) returns
+ "SIGHUP"). */
+
+extern const char *strsigno PARAMS ((int));
+
+/* Given the name of a signal, return its number. */
+
+extern int strtosigno PARAMS ((const char *));
+
+/* Register a function to be run by xexit. Returns 0 on success. */
+
+extern int xatexit PARAMS ((void (*fn) (void)));
+
+/* Exit, calling all the functions registered with xatexit. */
+
+#ifndef __GNUC__
+extern void xexit PARAMS ((int status));
+#else
+void xexit PARAMS ((int status)) __attribute__ ((noreturn));
+#endif
+
+/* Set the program name used by xmalloc. */
+
+extern void xmalloc_set_program_name PARAMS ((const char *));
+
+/* Allocate memory without fail. If malloc fails, this will print a
+ message to stderr (using the name set by xmalloc_set_program_name,
+ if any) and then call xexit. */
+
+#ifdef ANSI_PROTOTYPES
+/* Get a definition for size_t. */
+#include <stddef.h>
+#endif
+extern PTR xmalloc PARAMS ((size_t));
+
+/* Reallocate memory without fail. This works like xmalloc.
+
+ FIXME: We do not declare the parameter types for the same reason as
+ xmalloc. */
+
+extern PTR xrealloc PARAMS ((PTR, size_t));
+
+/* Allocate memory without fail and set it to zero. This works like
+ xmalloc. */
+
+extern PTR xcalloc PARAMS ((size_t, size_t));
+
+/* Copy a string into a memory buffer without fail. */
+
+extern char *xstrdup PARAMS ((const char *));
+
+/* hex character manipulation routines */
+
+#define _hex_array_size 256
+#define _hex_bad 99
+extern char _hex_value[_hex_array_size];
+extern void hex_init PARAMS ((void));
+#define hex_p(c) (hex_value (c) != _hex_bad)
+/* If you change this, note well: Some code relies on side effects in
+ the argument being performed exactly once. */
+#define hex_value(c) (_hex_value[(unsigned char) (c)])
+
+/* Definitions used by the pexecute routine. */
+
+#define PEXECUTE_FIRST 1
+#define PEXECUTE_LAST 2
+#define PEXECUTE_ONE (PEXECUTE_FIRST + PEXECUTE_LAST)
+#define PEXECUTE_SEARCH 4
+#define PEXECUTE_VERBOSE 8
+
+/* Execute a program. */
+
+extern int pexecute PARAMS ((const char *, char * const *, const char *,
+ const char *, char **, char **, int));
+
+/* Wait for pexecute to finish. */
+
+extern int pwait PARAMS ((int, int *, int));
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif /* ! defined (LIBIBERTY_H) */
diff --git a/contrib/gcc/splay-tree.c b/contrib/gcc/splay-tree.c
new file mode 100644
index 0000000..b6bb5a6
--- /dev/null
+++ b/contrib/gcc/splay-tree.c
@@ -0,0 +1,368 @@
+/* A splay-tree datatype.
+ Copyright (C) 1998 Free Software Foundation, Inc.
+ Contributed by Mark Mitchell (mark@markmitchell.com).
+
+This file is part of GNU CC.
+
+GNU CC 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.
+
+GNU CC 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 GNU CC; see the file COPYING. If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
+
+/* For an easily readable description of splay-trees, see:
+
+ Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
+ Algorithms. Harper-Collins, Inc. 1991. */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifdef HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+
+#include "libiberty.h"
+#include "splay-tree.h"
+
+static void splay_tree_delete_helper PARAMS((splay_tree,
+ splay_tree_node));
+static void splay_tree_splay PARAMS((splay_tree,
+ splay_tree_key));
+static splay_tree_node splay_tree_splay_helper
+ PARAMS((splay_tree,
+ splay_tree_key,
+ splay_tree_node*,
+ splay_tree_node*,
+ splay_tree_node*));
+static int splay_tree_foreach_helper PARAMS((splay_tree,
+ splay_tree_node,
+ splay_tree_foreach_fn,
+ void*));
+
+/* Deallocate NODE (a member of SP), and all its sub-trees. */
+
+static void
+splay_tree_delete_helper (sp, node)
+ splay_tree sp;
+ splay_tree_node node;
+{
+ if (!node)
+ return;
+
+ splay_tree_delete_helper (sp, node->left);
+ splay_tree_delete_helper (sp, node->right);
+
+ if (sp->delete_key)
+ (*sp->delete_key)(node->key);
+ if (sp->delete_value)
+ (*sp->delete_value)(node->value);
+
+ free ((char*) node);
+}
+
+/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
+ and grandparent, respectively, of NODE. */
+
+static splay_tree_node
+splay_tree_splay_helper (sp, key, node, parent, grandparent)
+ splay_tree sp;
+ splay_tree_key key;
+ splay_tree_node *node;
+ splay_tree_node *parent;
+ splay_tree_node *grandparent;
+{
+ splay_tree_node *next;
+ splay_tree_node n;
+ int comparison;
+
+ n = *node;
+
+ if (!n)
+ return *parent;
+
+ comparison = (*sp->comp) (key, n->key);
+
+ if (comparison == 0)
+ /* We've found the target. */
+ next = 0;
+ else if (comparison < 0)
+ /* The target is to the left. */
+ next = &n->left;
+ else
+ /* The target is to the right. */
+ next = &n->right;
+
+ if (next)
+ {
+ /* Continue down the tree. */
+ n = splay_tree_splay_helper (sp, key, next, node, parent);
+
+ /* The recursive call will change the place to which NODE
+ points. */
+ if (*node != n)
+ return n;
+ }
+
+ if (!parent)
+ /* NODE is the root. We are done. */
+ return n;
+
+ /* First, handle the case where there is no grandparent (i.e.,
+ *PARENT is the root of the tree.) */
+ if (!grandparent)
+ {
+ if (n == (*parent)->left)
+ {
+ *node = n->right;
+ n->right = *parent;
+ }
+ else
+ {
+ *node = n->left;
+ n->left = *parent;
+ }
+ *parent = n;
+ return n;
+ }
+
+ /* Next handle the cases where both N and *PARENT are left children,
+ or where both are right children. */
+ if (n == (*parent)->left && *parent == (*grandparent)->left)
+ {
+ splay_tree_node p = *parent;
+
+ (*grandparent)->left = p->right;
+ p->right = *grandparent;
+ p->left = n->right;
+ n->right = p;
+ *grandparent = n;
+ return n;
+ }
+ else if (n == (*parent)->right && *parent == (*grandparent)->right)
+ {
+ splay_tree_node p = *parent;
+
+ (*grandparent)->right = p->left;
+ p->left = *grandparent;
+ p->right = n->left;
+ n->left = p;
+ *grandparent = n;
+ return n;
+ }
+
+ /* Finally, deal with the case where N is a left child, but *PARENT
+ is a right child, or vice versa. */
+ if (n == (*parent)->left)
+ {
+ (*parent)->left = n->right;
+ n->right = *parent;
+ (*grandparent)->right = n->left;
+ n->left = *grandparent;
+ *grandparent = n;
+ return n;
+ }
+ else
+ {
+ (*parent)->right = n->left;
+ n->left = *parent;
+ (*grandparent)->left = n->right;
+ n->right = *grandparent;
+ *grandparent = n;
+ return n;
+ }
+}
+
+/* Splay SP around KEY. */
+
+static void
+splay_tree_splay (sp, key)
+ splay_tree sp;
+ splay_tree_key key;
+{
+ if (sp->root == 0)
+ return;
+
+ splay_tree_splay_helper (sp, key, &sp->root,
+ /*grandparent=*/0, /*parent=*/0);
+}
+
+/* Call FN, passing it the DATA, for every node below NODE, all of
+ which are from SP, following an in-order traversal. If FN every
+ returns a non-zero value, the iteration ceases immediately, and the
+ value is returned. Otherwise, this function returns 0. */
+
+static int
+splay_tree_foreach_helper (sp, node, fn, data)
+ splay_tree sp;
+ splay_tree_node node;
+ splay_tree_foreach_fn fn;
+ void* data;
+{
+ int val;
+
+ if (!node)
+ return 0;
+
+ val = splay_tree_foreach_helper (sp, node->left, fn, data);
+ if (val)
+ return val;
+
+ val = (*fn)(node, data);
+ if (val)
+ return val;
+
+ return splay_tree_foreach_helper (sp, node->right, fn, data);
+}
+
+/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
+ DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
+ values. */
+
+splay_tree
+splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
+ splay_tree_compare_fn compare_fn;
+ splay_tree_delete_key_fn delete_key_fn;
+ splay_tree_delete_value_fn delete_value_fn;
+{
+ splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree));
+ sp->root = 0;
+ sp->comp = compare_fn;
+ sp->delete_key = delete_key_fn;
+ sp->delete_value = delete_value_fn;
+
+ return sp;
+}
+
+/* Deallocate SP. */
+
+void
+splay_tree_delete (sp)
+ splay_tree sp;
+{
+ splay_tree_delete_helper (sp, sp->root);
+ free ((char*) sp);
+}
+
+/* Insert a new node (associating KEY with DATA) into SP. If a
+ previous node with the indicated KEY exists, its data is replaced
+ with the new value. */
+
+void
+splay_tree_insert (sp, key, value)
+ splay_tree sp;
+ splay_tree_key key;
+ splay_tree_value value;
+{
+ int comparison;
+
+ splay_tree_splay (sp, key);
+
+ if (sp->root)
+ comparison = (*sp->comp)(sp->root->key, key);
+
+ if (sp->root && comparison == 0)
+ {
+ /* If the root of the tree already has the indicated KEY, just
+ replace the value with VALUE. */
+ if (sp->delete_value)
+ (*sp->delete_value)(sp->root->value);
+ sp->root->value = value;
+ }
+ else
+ {
+ /* Create a new node, and insert it at the root. */
+ splay_tree_node node;
+
+ node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node));
+ node->key = key;
+ node->value = value;
+
+ if (!sp->root)
+ node->left = node->right = 0;
+ else if (comparison < 0)
+ {
+ node->left = sp->root;
+ node->right = node->left->right;
+ node->left->right = 0;
+ }
+ else
+ {
+ node->right = sp->root;
+ node->left = node->right->left;
+ node->right->left = 0;
+ }
+
+ sp->root = node;
+ }
+}
+
+/* Lookup KEY in SP, returning VALUE if present, and NULL
+ otherwise. */
+
+splay_tree_node
+splay_tree_lookup (sp, key)
+ splay_tree sp;
+ splay_tree_key key;
+{
+ splay_tree_splay (sp, key);
+
+ if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
+ return sp->root;
+ else
+ return 0;
+}
+
+/* Call FN, passing it the DATA, for every node in SP, following an
+ in-order traversal. If FN every returns a non-zero value, the
+ iteration ceases immediately, and the value is returned.
+ Otherwise, this function returns 0. */
+
+int
+splay_tree_foreach (sp, fn, data)
+ splay_tree sp;
+ splay_tree_foreach_fn fn;
+ void *data;
+{
+ return splay_tree_foreach_helper (sp, sp->root, fn, data);
+}
+
+/* Splay-tree comparison function, treating the keys as ints. */
+
+int
+splay_tree_compare_ints (k1, k2)
+ splay_tree_key k1;
+ splay_tree_key k2;
+{
+ if ((int) k1 < (int) k2)
+ return -1;
+ else if ((int) k1 > (int) k2)
+ return 1;
+ else
+ return 0;
+}
+
+/* Splay-tree comparison function, treating the keys as pointers. */
+
+int
+splay_tree_compare_pointers (k1, k2)
+ splay_tree_key k1;
+ splay_tree_key k2;
+{
+ if ((char*) k1 < (char*) k2)
+ return -1;
+ else if ((char*) k1 > (char*) k2)
+ return 1;
+ else
+ return 0;
+}
diff --git a/contrib/gcc/splay-tree.h b/contrib/gcc/splay-tree.h
new file mode 100644
index 0000000..e828fe7
--- /dev/null
+++ b/contrib/gcc/splay-tree.h
@@ -0,0 +1,116 @@
+/* A splay-tree datatype.
+ Copyright (C) 1998 Free Software Foundation, Inc.
+ Contributed by Mark Mitchell (mark@markmitchell.com).
+
+This file is part of GNU CC.
+
+GNU CC 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.
+
+GNU CC 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 GNU CC; see the file COPYING. If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
+
+/* For an easily readable description of splay-trees, see:
+
+ Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
+ Algorithms. Harper-Collins, Inc. 1991.
+
+ The major feature of splay trees is that all basic tree operations
+ are amortized O(log n) time for a tree with n nodes. */
+
+#ifndef _SPLAY_TREE_H
+#define _SPLAY_TREE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+#include <ansidecl.h>
+
+/* Use typedefs for the key and data types to facilitate changing
+ these types, if necessary. These types should be sufficiently wide
+ that any pointer or scalar can be cast to these types, and then
+ cast back, without loss of precision. */
+typedef unsigned long int splay_tree_key;
+typedef unsigned long int splay_tree_value;
+
+/* Forward declaration for a node in the tree. */
+typedef struct splay_tree_node *splay_tree_node;
+
+/* The type of a function which compares two splay-tree keys. The
+ function should return values as for qsort. */
+typedef int (*splay_tree_compare_fn) PARAMS((splay_tree_key, splay_tree_key));
+
+/* The type of a function used to deallocate any resources associated
+ with the key. */
+typedef void (*splay_tree_delete_key_fn) PARAMS((splay_tree_key));
+
+/* The type of a function used to deallocate any resources associated
+ with the value. */
+typedef void (*splay_tree_delete_value_fn) PARAMS((splay_tree_value));
+
+/* The type of a function used to iterate over the tree. */
+typedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*));
+
+/* The nodes in the splay tree. */
+struct splay_tree_node
+{
+ /* The key. */
+ splay_tree_key key;
+
+ /* The value. */
+ splay_tree_value value;
+
+ /* The left and right children, respectively. */
+ splay_tree_node left;
+ splay_tree_node right;
+};
+
+/* The splay tree itself. */
+typedef struct splay_tree
+{
+ /* The root of the tree. */
+ splay_tree_node root;
+
+ /* The comparision function. */
+ splay_tree_compare_fn comp;
+
+ /* The deallocate-key function. NULL if no cleanup is necessary. */
+ splay_tree_delete_key_fn delete_key;
+
+ /* The deallocate-value function. NULL if no cleanup is necessary. */
+ splay_tree_delete_value_fn delete_value;
+} *splay_tree;
+
+extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn,
+ splay_tree_delete_key_fn,
+ splay_tree_delete_value_fn));
+extern void splay_tree_delete PARAMS((splay_tree));
+extern void splay_tree_insert PARAMS((splay_tree,
+ splay_tree_key,
+ splay_tree_value));
+extern splay_tree_node splay_tree_lookup
+ PARAMS((splay_tree,
+ splay_tree_key));
+extern int splay_tree_foreach PARAMS((splay_tree,
+ splay_tree_foreach_fn,
+ void*));
+extern int splay_tree_compare_ints PARAMS((splay_tree_key,
+ splay_tree_key));
+extern int splay_tree_compare_pointers PARAMS((splay_tree_key,
+ splay_tree_key));
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* _SPLAY_TREE_H */
OpenPOWER on IntegriCloud