/*
** sptree.h:  The following type declarations provide the binary tree
**  representation of event-sets or priority queues needed by splay trees
**
**  assumes that data and datb will be provided by the application
**  to hold all application specific information
**
**  assumes that key will be provided by the application, comparable
**  with the compare function applied to the addresses of two keys.
*/

# ifndef SPTREE_H
# define SPTREE_H

typedef unsigned int spkey_t;

struct spblk {
	struct spblk	*leftlink;
	struct spblk	*rightlink;
	struct spblk	*uplink;
	spkey_t		key;
	unsigned char	*data;
	int		mark;
};

struct sptree {
	struct spblk	*root;		/* root node */
	int		lookups;	/* number of splookup()s */
	int		lkpcmps;	/* number of lookup comparisons */
	int		enqs;		/* number of spenq()s */
	int		enqcmps;	/* compares in spenq */
	int		splays;
	int		splayloops;
};

extern struct sptree *sp_init();/* init tree */

extern struct spblk
	*sp_lookup(),		/* find key in a tree */
	*sp_install();		/* enter an item, allocating or replacing */

extern void
	sp_scan(),		/* scan forward through tree */
	sp_delete();		/* delete node from tree */

extern char *sp_stats();	/* return tree statistics */


#endif	/* SPTREE_H */
