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.

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 */