home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Usenet 1994 October
/
usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso
/
unix
/
volume14
/
splay-tree
/
sptree.h
< prev
Wrap
C/C++ Source or Header
|
1988-05-08
|
2KB
|
78 lines
/*
** 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
# ifndef NULL
# define NULL 0
# endif
# define STRCMP( a, b ) ( (Sct = *(a) - *(b)) ? Sct : strcmp( (a), (b) ) )
typedef struct _spblk SPBLK;
typedef struct _spblk
{
SPBLK * leftlink;
SPBLK * rightlink;
SPBLK * uplink;
char * key; /* formerly time/timetyp */
char * data; /* formerly aux/auxtype */
char * datb;
};
typedef struct
{
SPBLK * root; /* root node */
/* Statistics, not strictly necessary, but handy for tuning */
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;
} SPTREE;
/* sptree.c */
extern SPTREE * spinit(); /* init tree */
extern int spempty(); /* is tree empty? */
extern SPBLK * spenq(); /* insert item into the tree */
extern SPBLK * spdeq(); /* return and remove lowest item in subtree */
extern SPBLK * spenqprior(); /* insert before items with same key */
extern void splay(); /* reorganize tree */
/* spaux.c */
extern SPBLK * sphead(); /* return first node in tree */
extern void spdelete(); /* delete node from tree */
extern SPBLK * spnext(); /* return next node in tree */
extern SPBLK * spprev(); /* return previous node in tree */
extern SPBLK * spenqbefore(); /* enqueue before existing node */
extern SPBLK * spenqafter(); /* enqueue after existing node */
/* spdaveb.c */
extern SPBLK * splookup(); /* find key in a tree */
extern SPBLK * spinstall(); /* enter an item, allocating or replacing */
extern SPBLK * sptail(); /* find end of a tree */
extern void spscan(); /* scan forward through tree */
extern void sprscan(); /* reverse scan through tree */
extern SPBLK * spfnext(); /* fast non-splaying next */
extern SPBLK * spfprev(); /* fast non-splaying prev */
# endif