home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / set.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  4.0 KB  |  135 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: set.h $
  7. * Version:        $Revision: 1.5 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Macros and function prototypes for the set manipulation
  13. *                module.
  14. *
  15. * $Id: set.h 1.5 91/12/31 19:41:22 kjb Exp $
  16. *
  17. * Revision History:
  18. * -----------------
  19. *
  20. * $Log:    set.h $
  21. * Revision 1.5  91/12/31  19:41:22  kjb
  22. * 
  23. * Modified include files directories.
  24. * 
  25. * Revision 1.4  91/09/27  03:11:10  kjb
  26. * Added compatibility with C++.
  27. * 
  28. * Revision 1.3  91/09/26  10:07:51  kjb
  29. * Took out extern references
  30. * 
  31. * Revision 1.2  91/09/01  01:16:00  ROOT_DOS
  32. * Changed search for include files to look in current directory
  33. * 
  34. * Revision 1.1  91/08/16  13:30:52  ROOT_DOS
  35. * Initial revision
  36. * 
  37. ****************************************************************************/
  38.  
  39. #ifndef    __SET_H
  40. #define    __SET_H
  41.  
  42. #ifndef    __DEBUG_H
  43. #include "debug.h"
  44. #endif
  45.  
  46. #ifndef    __STRING_H
  47. #include <string.h>
  48. #endif
  49.  
  50. /*---------------------- Macros and type definitions ----------------------*/
  51.  
  52. /* The following macros will need to be changed when porting from one
  53.  * platform to another.
  54.  */
  55.  
  56. typedef unsigned short        _SETTYPE;        /* one cell in bit map        */
  57. #define    _BITS_IN_WORD        16
  58. #define    _BYTES_IN_ARRAY(x)    (x << 1)        /* # of bytes in bit map    */
  59. #define    _DIV_WSIZE(x)        ((unsigned)(x) >> 4)
  60. #define    _MOD_WSIZE(x)        ((x) & 0x0F)
  61. #define    _DEFWORDS            8                /* elements in default set    */
  62. #define    _DEFBITS    (_DEFWORDS * _BITS_IN_WORD)    /* Bits in default set    */
  63. #define    _ROUND(bit)    (((_DIV_WSIZE(bit) + 8) >> 3) << 3)
  64.  
  65. typedef struct _set_ {
  66.     unsigned char    nwords;            /* Number of words in map            */
  67.     unsigned char    compl;            /* is a negative true set if true    */
  68.     unsigned        nbits;            /* Number of bits in map            */
  69.     _SETTYPE        *map;            /* Pointer to the map                */
  70.     _SETTYPE        defmap[_DEFWORDS];    /* The map itself                */
  71.     } SET;
  72.  
  73.                                 /* Op argument passed to _set_op    */
  74. #define    _UNION            0        /* x is in s1 or s2                    */
  75. #define    _INTERSECT        1        /* x is in s1 and s2                */
  76. #define    _DIFFERENCE        2        /* (x in s1) && (s not in s2)        */
  77. #define    _ASSIGN            4        /* s1 = s2                            */
  78.  
  79. #define    UNION(d,s)        _set_op(_UNION,d,s)
  80. #define    INTERSECT(d,s)    _set_op(_INTERSECT,d,s)
  81. #define    DIFFERENCE(d,s)    _set_op(_DIFFERENCE,d,s)
  82. #define    ASSIGN(d,s)        _set_op(_ASSIGN,d,s)
  83.  
  84. #define    CLEAR(s)        memset( (s)->map, 0, (s)->nwords * sizeof(_SETTYPE))
  85. #define    FILL(s)            memset( (s)->map, ~0, (s)->nwords * sizeof(_SETTYPE))
  86. #define    COMPLEMENT(s)    ( (s)->compl = !(s)->compl)
  87. #define    INVERT(s)        invert(s)
  88.  
  89. #define    _SET_EQUIV        0    /* Value returned by _set_test, equivalent     */
  90. #define    _SET_DISJ        1    /*                                 disjoint     */
  91. #define    _SET_INTER        2    /*                                intersecting */
  92.  
  93. #define    IS_DISJOINT(s1,s2)        (_set_test(s1,s2) == _SET_DISJ)
  94. #define    IS_INTERSECTING(s1,s2)    (_set_test(s1,s2) == _SET_INTER)
  95. #define    IS_EQUIVALENT(s1,s2)    (_set_test(s1,s2) == _SET_EQUIV)
  96.  
  97. #define    IS_EMPTY(s)                (num_ele(s) == 0)
  98.  
  99. /* All of the following have heavy-duty side-effects. Be careful. */
  100.  
  101. #define    _GBIT(s,x,op)    ( ((s)->map)[_DIV_WSIZE(x)] op (1 << _MOD_WSIZE(x)) )
  102.  
  103. #define    REMOVE(s,x)        (((x) >= (s)->nbits) ? 0 : _GBIT(s,x,&= ~))
  104. #define    ADD(s,x)        (((x) >= (s)->nbits) ? _addset(s,x) : _GBIT(s,x,|=))
  105. #define    MEMBER(s,x)        (((x) >= (s)->nbits) ? 0 : _GBIT(s,x,&))
  106. #define    TEST(s,x)        (( MEMBER(s,x) ) ? !(s)->compl : (s)->compl )
  107.  
  108. /*-------------------------- Function Prototypes --------------------------*/
  109.  
  110. #ifdef __cplusplus
  111. extern "C" {
  112. #endif
  113.  
  114. SET *newset(void);
  115. void delset(SET *set);
  116. SET *dupset(SET *set);
  117. int _addset(SET *set,int bit);
  118. int num_ele(SET *set);
  119. int _set_test(SET *set1,SET *set2);
  120. int setcmp(SET *set1,SET *set2);
  121. unsigned sethash(SET *set);
  122. int subset(SET *set, SET *possible_subset);
  123. void _set_op(int op, SET *dest, SET *src);
  124. void invert(SET *set);
  125. void truncate(SET *set);
  126. int next_member(SET *set);
  127. void pset(SET *set,int (*output_routine)(void*,char*,int),
  128.           void *param);
  129.  
  130. #ifdef __cplusplus
  131. }
  132. #endif
  133.  
  134. #endif
  135.