home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume14 / splay-tree / sptree.h < prev   
Encoding:
C/C++ Source or Header  |  1988-05-08  |  2.2 KB  |  78 lines
  1. /*
  2. ** sptree.h:  The following type declarations provide the binary tree
  3. **  representation of event-sets or priority queues needed by splay trees
  4. **
  5. **  assumes that data and datb will be provided by the application
  6. **  to hold all application specific information
  7. **
  8. **  assumes that key will be provided by the application, comparable
  9. **  with the compare function applied to the addresses of two keys.
  10. */
  11.  
  12. # ifndef SPTREE_H
  13. # define SPTREE_H
  14.  
  15. # ifndef NULL
  16. # define NULL    0
  17. # endif
  18.  
  19. # define STRCMP( a, b ) ( (Sct = *(a) - *(b)) ? Sct : strcmp( (a), (b) ) )
  20.  
  21. typedef struct _spblk SPBLK;
  22.  
  23. typedef struct _spblk
  24. {
  25.     SPBLK    * leftlink;
  26.     SPBLK    * rightlink;
  27.     SPBLK    * uplink;
  28.  
  29.     char    * key;        /* formerly time/timetyp */
  30.     char    * data;        /* formerly aux/auxtype */
  31.     char    * datb;
  32. };
  33.  
  34. typedef struct
  35. {
  36.     SPBLK    * root;        /* root node */
  37.  
  38.     /* Statistics, not strictly necessary, but handy for tuning  */
  39.  
  40.     int        lookups;    /* number of splookup()s */
  41.     int        lkpcmps;    /* number of lookup comparisons */
  42.     
  43.     int        enqs;        /* number of spenq()s */
  44.     int        enqcmps;    /* compares in spenq */
  45.     
  46.     int        splays;
  47.     int        splayloops;
  48.  
  49. } SPTREE;
  50.  
  51.  
  52. /* sptree.c */
  53. extern SPTREE * spinit();    /* init tree */
  54. extern int spempty();        /* is tree empty? */
  55. extern SPBLK * spenq();        /* insert item into the tree */
  56. extern SPBLK * spdeq();        /* return and remove lowest item in subtree */
  57. extern SPBLK * spenqprior();    /* insert before items with same key */
  58. extern void splay();        /* reorganize tree */
  59.  
  60. /* spaux.c */
  61. extern SPBLK * sphead();    /* return first node in tree */
  62. extern void spdelete();        /* delete node from tree */
  63. extern SPBLK * spnext();    /* return next node in tree */
  64. extern SPBLK * spprev();    /* return previous node in tree */
  65. extern SPBLK * spenqbefore();    /* enqueue before existing node */
  66. extern SPBLK * spenqafter();    /* enqueue after existing node */
  67.  
  68. /* spdaveb.c */
  69. extern SPBLK * splookup();    /* find key in a tree */
  70. extern SPBLK * spinstall();    /* enter an item, allocating or replacing */
  71. extern SPBLK * sptail();    /* find end of a tree */
  72. extern void spscan();        /* scan forward through tree */
  73. extern void sprscan();        /* reverse scan through tree */
  74. extern SPBLK * spfnext();    /* fast non-splaying next */
  75. extern SPBLK * spfprev();    /* fast non-splaying prev */
  76.  
  77. # endif
  78.