home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1868 / sptree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-28  |  2.3 KB  |  80 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.     int        cnt;
  29.  
  30.     char    * key;        /* formerly time/timetyp */
  31.     char    * data;        /* formerly aux/auxtype */
  32.     char    * datb;
  33. };
  34.  
  35. typedef struct
  36. {
  37.     SPBLK    * root;        /* root node */
  38.  
  39.     /* Statistics, not strictly necessary, but handy for tuning  */
  40.  
  41.     int        lookups;    /* number of splookup()s */
  42.     int        lkpcmps;    /* number of lookup comparisons */
  43.     
  44.     int        enqs;        /* number of spenq()s */
  45.     int        enqcmps;    /* compares in spenq */
  46.     
  47.     int        splays;
  48.     int        splayloops;
  49.  
  50. } SPTREE;
  51.  
  52.  
  53. /* sptree.c */
  54. extern SPTREE * spinit();    /* init tree */
  55. extern int spempty();        /* is tree empty? */
  56. extern SPBLK * spenq();        /* insert item into the tree */
  57. extern SPBLK * spdeq();        /* return and remove lowest item in subtree */
  58. extern SPBLK * spenqprior();    /* insert before items with same key */
  59. extern void splay();        /* reorganize tree */
  60.  
  61. /* spaux.c */
  62. extern SPBLK * sphead();    /* return first node in tree */
  63. extern void spdelete();        /* delete node from tree */
  64. extern SPBLK * spnext();    /* return next node in tree */
  65. extern SPBLK * spprev();    /* return previous node in tree */
  66. extern SPBLK * spenqbefore();    /* enqueue before existing node */
  67. extern SPBLK * spenqafter();    /* enqueue after existing node */
  68.  
  69. /* spdaveb.c */
  70. extern SPBLK * splookup();    /* find key in a tree */
  71. extern SPBLK * spinstall();    /* enter an item, allocating or replacing */
  72. extern SPBLK * sptail();    /* find end of a tree */
  73. extern void spscan();        /* scan forward through tree */
  74. extern void sprscan();        /* reverse scan through tree */
  75. extern SPBLK * spfhead();    /* fast non-splaying head */
  76. extern SPBLK * spfnext();    /* fast non-splaying next */
  77. extern SPBLK * spfprev();    /* fast non-splaying prev */
  78.  
  79. # endif
  80.