home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / set.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  16.0 KB  |  561 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: set.c $
  7. * Version:        $Revision: 1.4 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Module to implement bit oriented set maniuplation.
  13. *
  14. * $Id: set.c 1.4 91/12/31 19:40:33 kjb Exp $
  15. *
  16. * Revision History:
  17. * -----------------
  18. *
  19. * $Log:    set.c $
  20. * Revision 1.4  91/12/31  19:40:33  kjb
  21. * Modified include file directories
  22. * 
  23. * Revision 1.3  91/09/03  18:28:26  ROOT_DOS
  24. * Ported to UNIX.
  25. * 
  26. * Revision 1.2  91/09/01  01:14:33  ROOT_DOS
  27. * Changed search for include files to look in current directory
  28. * 
  29. * Revision 1.1  91/08/16  13:28:48  ROOT_DOS
  30. * Initial revision
  31. * 
  32. ****************************************************************************/
  33.  
  34. #include <stdio.h>
  35. #include <malloc.h>
  36. #include <ctype.h>
  37. #include <signal.h>
  38. #include <string.h>
  39. #include "debug.h"
  40. #include "set.h"
  41.  
  42. PUBLIC SET *newset(void)
  43. /****************************************************************************
  44. *
  45. * Function:        newset
  46. * Returns:        Pointer to the set, NULL upon error.
  47. *
  48. * Description:    Creates a new set and returns a pointer to it. If an error
  49. *                occurs, and error message is output and SIGABRT is raised.
  50. *                NULL is returned if raise() returns.
  51. *
  52. ****************************************************************************/
  53. {
  54.     SET    *p;
  55.  
  56.     if (!(p = (SET *)malloc( sizeof(SET)))) {
  57.         fprintf(stderr,"Can't get memory to create set\n");
  58.         raise(SIGABRT);
  59.         return NULL;            /* Usually won't get here */
  60.         }
  61.  
  62.     memset(p, 0, sizeof(SET));
  63.     p->map = p->defmap;
  64.     p->nwords = _DEFWORDS;
  65.     p->nbits = _DEFBITS;
  66.     return p;
  67. }
  68.  
  69. PUBLIC void delset(SET *set)
  70. /****************************************************************************
  71. *
  72. * Function:        delset
  73. * Parameters:    set        - Set to delete
  74. *
  75. * Description:    Delete's a set previously created with a call to newset.
  76. *
  77. ****************************************************************************/
  78. {
  79.     if (set->map != set->defmap)
  80.         free(set->map);
  81.     free(set);
  82. }
  83.  
  84. PUBLIC SET *dupset(SET *set)
  85. /****************************************************************************
  86. *
  87. * Function:        dupset
  88. * Parameters:    set        - Set to duplicate
  89. * Returns:        Pointer to the duplicated set
  90. *
  91. * Description:    Create a new set that has the same members as the input set.
  92. *
  93. ****************************************************************************/
  94. {
  95.     SET        *new;
  96.  
  97.     if (!(new = (SET *)malloc(sizeof(SET)))) {
  98.         fprintf(stderr,"Can't get memory to duplicate set\n");
  99.         exit(3);
  100.         }
  101.  
  102.     memset(new,0,sizeof(SET));
  103.     new->compl = set->compl;
  104.     new->nwords = set->nwords;
  105.     new->nbits = set->nbits;
  106.  
  107.     if (set->map == set->defmap) {                /* Default bit map in use */
  108.         new->map = new->defmap;
  109.         memcpy(new->defmap,set->defmap, _DEFWORDS * sizeof(_SETTYPE));
  110.         }
  111.     else {
  112.         new->map = (_SETTYPE *)malloc(set->nwords * sizeof(_SETTYPE));
  113.         if (!new->map) {
  114.             fprintf(stderr,"Can't get memory to duplicate set bit map\n");
  115.             exit(3);
  116.             }
  117.         memcpy(new->map, set->map, set->nwords * sizeof(_SETTYPE));
  118.         }
  119.     return new;
  120. }
  121.  
  122. PRIVATE void enlarge(int need,SET *set)
  123. /****************************************************************************
  124. *
  125. * Function:        enlarge
  126. * Parameters:    need    - Number of words required (total)
  127. *                set        - The set to enlarge
  128. *
  129. * Description:    Enlarge the set to "need" words, filling in the extre words
  130. *                with zeros. Prints an error message and aborts by calling
  131. *                exit() if there's not enough memory. This routine calls
  132. *                malloc and is hence slow and should be avoided. if possible.
  133. *
  134. ****************************************************************************/
  135. {
  136.     _SETTYPE    *new;
  137.  
  138.     if (!set || need <= set->nwords)
  139.         return;
  140.  
  141.     D(printf("enlarging %d word map to %d words\n", set->nwords,need);)
  142.  
  143.     if ( !(new = (_SETTYPE *) malloc(need * sizeof(_SETTYPE))) ) {
  144.         fprintf(stderr,"Can't get memory to expand set\n");
  145.         exit(1);
  146.         }
  147.     memcpy(new, set->map, set->nwords * sizeof(_SETTYPE));
  148.     memset(new + set->nwords, 0, (need - set->nwords) * sizeof(_SETTYPE));
  149.  
  150.     if (set->map != set->defmap)
  151.         free(set->map);
  152.  
  153.     set->map = new;
  154.     set->nwords = (unsigned char)need;
  155.     set->nbits = need * _BITS_IN_WORD;
  156. }
  157.  
  158. PUBLIC int _addset(SET *set,int bit)
  159. /****************************************************************************
  160. *
  161. * Function:        addset
  162. * Parameters:    set        - Set to add element to
  163. *                bit        - Element to add to the set
  164. *
  165. * Description:    Called by the ADD() macro when the set isn't big enough to
  166. *                hold the element being added. It exands the set to the
  167. *                necessary size and sets the indicated bit.
  168. *
  169. ****************************************************************************/
  170. {
  171.     enlarge(_ROUND(bit),set);
  172.     return _GBIT(set,bit, |= );
  173. }
  174.  
  175. PUBLIC int num_ele(SET *set)
  176. /****************************************************************************
  177. *
  178. * Function:        num_ele
  179. * Parameters:    set        - Set to determine cardinality of
  180. * Returns:        Cardinality of the set (number of elements)
  181. *
  182. * Description:    Returns the number of element (nonzero bits) in the set.
  183. *                NULL sets are considered empty. nbits[] is indexed by any
  184. *                number in the range 0-255, and it evalulates to the number
  185. *                of bits in the number.
  186. *
  187. ****************************************************************************/
  188. {
  189.     static unsigned char nbits[] = {
  190.         /*   0-15  */    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  191.         /*  16-31  */    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  192.         /*  32-47  */    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  193.         /*  48-63  */    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  194.         /*  64-79  */    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  195.         /*  80-95  */    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  196.         /*  96-111 */    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  197.         /* 112-127 */    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  198.         /* 128-143 */    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  199.         /* 144-159 */    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  200.         /* 160-175 */    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  201.         /* 176-191 */    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  202.         /* 192-207 */    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  203.         /* 208-223 */    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  204.         /* 224-239 */    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  205.         /* 240-255 */    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  206.         };
  207.  
  208.     int                i;
  209.     unsigned int    count = 0;
  210.     unsigned char    *p;
  211.  
  212.     if (!set)
  213.         return 0;
  214.  
  215.     p = (unsigned char *)set->map;
  216.  
  217.     for( i = _BYTES_IN_ARRAY(set->nwords); --i >= 0 ;)
  218.         count += nbits[*p++];
  219.  
  220.     return count;
  221. }
  222.  
  223. PUBLIC int _set_test(SET *set1,SET *set2)
  224. /****************************************************************************
  225. *
  226. * Function:        _set_test
  227. * Parameters:    set1    - First set to test
  228. *                set2    - Second set to test
  229. * Returns:        Result of the test
  230. *
  231. * Description:    Compares two sets. Returns the following codes:
  232. *
  233. *                     _SET_EQUIV        Sets are equivalent
  234. *                    _SET_INTER        Sets intersect but aren't equivalent
  235. *                    _SET_DISJ        Sets are disjoint
  236. *
  237. *                The smaller set is made larger if the two sets are of
  238. *                differing sizes.
  239. *
  240. ****************************************************************************/
  241. {
  242.     int            i, rval = _SET_EQUIV;
  243.     int            intersect = 0;
  244.     _SETTYPE    *p1,*p2;
  245.  
  246.     i = max( set1->nwords, set2->nwords);
  247.  
  248.     enlarge(i,set1);            /* Make the sets the same size */
  249.     enlarge(i,set2);
  250.  
  251.     p1 = set1->map;
  252.     p2 = set2->map;
  253.  
  254.     for (; --i >= 0; p1++,p2++) {
  255.         if (*p1 != *p2) {
  256.             /* You get here if the sets aren't equivalent. You can return
  257.              * immediately if the sets intersect but have to keep going in
  258.              * the case of disjoint sets (because the sets might actually
  259.              * intersect at some byte, as yet unseen).
  260.              */
  261.  
  262.             if (intersect || (*p1 & *p2))
  263.                 return _SET_INTER;
  264.             else
  265.                 rval = _SET_DISJ;
  266.             }
  267.         else {
  268.             /* If the words that we are currently testing are equal, then
  269.              * we must test whether they actually contain members. If they
  270.              * do, then we must assume that they also intersect (equivalent
  271.              * sets that are not empty MUST intersect!). Then we can test
  272.              * this value above, to ensure that we return with a value of
  273.              * _SET_INTER even when the sets intersect at words previously
  274.              * checked, and not in the word we are currently checking!
  275.              */
  276.  
  277.             intersect = (*p1 != 0) || intersect;
  278.             }
  279.         }
  280.  
  281.     return rval;                /* They're equivalent or disjoint */
  282. }
  283.  
  284. PUBLIC int setcmp(SET *set1,SET *set2)
  285. /****************************************************************************
  286. *
  287. * Function:        setcmp
  288. * Parameters:    set1    - First set to compare
  289. *                set2    - Second set to compare
  290. * Returns:        0 if sets are equivalent, < 0 if set1 < set2 and > 0 if
  291. *                set1 > set2.
  292. *
  293. * Description:    Another comparison function. This works like strcmp().
  294. *                Useful for quickly comparing sets for tree's etc.
  295. *
  296. ****************************************************************************/
  297. {
  298.     int            i,j;
  299.     _SETTYPE    *p1,*p2;
  300.  
  301.     i = j = min(set1->nwords,set2->nwords);
  302.  
  303.     for (p1 = set1->map, p2 = set2->map; --j >= 0; p1++,p2++)
  304.         if (*p1 != *p2)
  305.             return *p1 - *p2;
  306.  
  307.     /* You get here only if all words that exist in both sets are the same.
  308.      * Check the tail end of the larger array for all zeros.
  309.      */
  310.  
  311.     if ( (j = set1->nwords - i) > 0) {        /* Set1 is the larger */
  312.         while(--j >= 0)
  313.             if (*p1++)
  314.                 return 1;
  315.         }
  316.     else if ( (j = set2->nwords - i) > 0) {    /* Set2 is the larger */
  317.         while (--j >= 0);
  318.             if (*p2++)
  319.                 return -1;
  320.         }
  321.  
  322.     return 0;                                /* They're equivalent */
  323. }
  324.  
  325. PUBLIC unsigned sethash(SET *set)
  326. /****************************************************************************
  327. *
  328. * Function:        sethash
  329. * Parameters:    set        - Set to hash
  330. * Returns:        Hash value for the set.
  331. *
  332. * Description:    Finds the hash value for the set by summing together the
  333. *                words in the bit map.
  334. *
  335. ****************************************************************************/
  336. {
  337.     _SETTYPE    *p;
  338.     unsigned    total;
  339.     int            j;
  340.  
  341.     total = 0;
  342.     j = set->nwords;
  343.     p = set->map;
  344.  
  345.     while (--j >= 0)
  346.         total += *p++;
  347.  
  348.     return total;
  349. }
  350.  
  351. PUBLIC int subset(SET *set, SET *possible_subset)
  352. /****************************************************************************
  353. *
  354. * Function:        subset
  355. * Parameters:    set                - Superset to check with
  356. *                possible_subset    - Possible subset to check
  357. * Returns:        True if "possible_subset" is a subset of "set", 0 otherwise
  358. *
  359. * Description:    Determines if a set is a subset of another set. Empty sets
  360. *                are subsets of everythings. If the "possible_subset" is
  361. *                larger that the "set", then the extra bytes must be all
  362. *                zeros.
  363. *
  364. ****************************************************************************/
  365. {
  366.     _SETTYPE    *subsetp,*setp;
  367.     int            common;            /* This many bytes in potential subset */
  368.     int            tail;            /* This many implied 0 bytes in b */
  369.  
  370.     if (possible_subset->nwords > set->nwords) {
  371.         common = set->nwords;
  372.         tail = possible_subset->nwords - common;
  373.         }
  374.     else {
  375.         common = possible_subset->nwords;
  376.         tail = 0;
  377.         }
  378.  
  379.     subsetp = possible_subset->map;
  380.     setp = set->map;
  381.  
  382.     for (; --common >= 0; subsetp++, setp++)
  383.         if ((*subsetp & *setp) != *subsetp)
  384.             return 0;
  385.  
  386.     while (--tail >= 0)
  387.         if (*subsetp++)
  388.             return 0;
  389.  
  390.     return 1;
  391. }
  392.  
  393. PUBLIC void _set_op(int op, SET *dest, SET *src)
  394. /****************************************************************************
  395. *
  396. * Function:        _set_op
  397. * Parameters:    op        - Operation to perform
  398. *                dest    - Destination set
  399. *                src        - Source set
  400. *
  401. * Description:    Performs binary operations on the sets depending on op:
  402. *
  403. *                _UNION:            dest = union of src and dest
  404. *                _INTERSECT:        dest = intersection of src and dest
  405. *                _DIFFERENCE:    dest = symmetric difference of src and dest
  406. *                _ASSIGN:        dest = src
  407. *
  408. *                The size of the destination set is adjusted so that it's
  409. *                the same size as the source set.
  410. *
  411. ****************************************************************************/
  412. {
  413.     _SETTYPE    *d;        /* Pointer to destination map */
  414.     _SETTYPE    *s;        /* Pointer to source mape */
  415.     int            ssize;    /* # of words in src set */
  416.     int            tail;    /* dest set is this much bigger */
  417.  
  418.     ssize = src->nwords;
  419.  
  420.     if ((unsigned)dest->nwords < ssize) /* make sure dest set is at least */
  421.         enlarge(ssize,dest);            /* as big as the src set.          */
  422.  
  423.     tail = dest->nwords - ssize;
  424.     d = dest->map;
  425.     s = src->map;
  426.  
  427.     switch (op) {
  428.         case _UNION:
  429.             while (--ssize >= 0)
  430.                 *d++ |= *s++;
  431.             break;
  432.         case _INTERSECT:
  433.             while (--ssize >= 0)
  434.                 *d++ &= *s++;
  435.             while (--tail >= 0)
  436.                 *d++ = 0;
  437.             break;
  438.         case _DIFFERENCE:
  439.             while (--ssize >= 0)
  440.                 *d++ ^= *s++;
  441.             break;
  442.         case _ASSIGN:
  443.             while (--ssize >= 0)
  444.                 *d++ = *s++;
  445.             while (--tail >= 0)
  446.                 *d++ = 0;
  447.             break;
  448.         }
  449. }
  450.  
  451. PUBLIC void invert(SET *set)
  452. /****************************************************************************
  453. *
  454. * Function:        invert
  455. * Parameters:    set        - Set to invert
  456. *
  457. * Description:    Physically inverts the bits in the set. Compare with the
  458. *                COMPLEMENT() macro, which just modifies the complement bit.
  459. *
  460. ****************************************************************************/
  461. {
  462.     _SETTYPE    *p, *end;
  463.  
  464.     for (p = set->map, end = p + set->nwords; p < end; p++)
  465.         *p = ~*p;
  466. }
  467.  
  468. PUBLIC void truncate(SET *set)
  469. /****************************************************************************
  470. *
  471. * Function:        truncate
  472. * Parameters:    set        - Set to truncate
  473. *
  474. * Description:    Clears the set but also set's it back to the original,
  475. *                default size. Compare this routine to the CLEAR() macro
  476. *                which clears all the bits in the map but doesn't modify the
  477. *                size.
  478. *
  479. ****************************************************************************/
  480. {
  481.     if (set->map != set->defmap) {
  482.         free(set->map);
  483.         set->map = set->defmap;
  484.         }
  485.  
  486.     set->nwords = _DEFWORDS;
  487.     set->nbits = _DEFBITS;
  488.     memset(set->defmap, 0 , sizeof(set->defmap));
  489. }
  490.  
  491. PUBLIC int next_member(SET *set)
  492. /****************************************************************************
  493. *
  494. * Function:        next_member
  495. * Parameters:    set        - Set to return next element from
  496. * Returns:        The next element from the set (-1 if none)
  497. *
  498. * Description:    Finds and returns the next element that exists in the set.
  499. *                If "set" equals "NULL" we reset the current element. If
  500. *                "set" has changed since the last call, we reset and return
  501. *                the first element from this set.
  502. *
  503. ****************************************************************************/
  504. {
  505.     static SET    *oset = NULL;        /* "set" arg in last call */
  506.     static int    current_member = 0;    /* last accessed member of cur.set */
  507.  
  508.     if (!set)
  509.         return ( (int)(oset = NULL) );
  510.  
  511.     if (oset != set) {
  512.         oset = set;
  513.         current_member = 0;
  514.         }
  515.  
  516.     /* The increment must be put into the test because, if the TEST()
  517.      * invocation evaluates to true, then an increment on the right of a
  518.      * for() statement would never be executed.
  519.      */
  520.  
  521.     while (current_member++ < set->nbits)
  522.         if (TEST(set,current_member-1))
  523.             return(current_member-1);
  524.     return(-1);
  525. }
  526.  
  527. PUBLIC void pset(SET *set,int (*out)(void*,char*,int),void *param)
  528. /****************************************************************************
  529. *
  530. * Function:        pset
  531. * Parameters:    set        - Set to print
  532. *                out        - Routine to call for each element
  533. *                param    - Parameters to the output routine
  534. *
  535. * Description:    Prints the contents of the set in human-readable form. The
  536. *                output routine is called for each element of the set with
  537. *                the following arguments:
  538. *
  539. *                (*out)(param, "null",-1);    NULL set ("set" arg == NULL)
  540. *                (*out)(param, "empty",-2);    Empty set (no elements)
  541. *                (*out)(param, "%d ",N);        N is an element of the set
  542. *
  543. ****************************************************************************/
  544. {
  545.     int        i,did_something = 0;
  546.  
  547.     if (!set)
  548.         (*out)(param,"null",-1);
  549.     else {
  550.         next_member(NULL);
  551.         while( (i = next_member(set)) >= 0) {
  552.             did_something++;
  553.             (*out)(param,"%d ",i);
  554.             }
  555.         next_member(NULL);
  556.  
  557.         if (!did_something)
  558.             (*out)(param, "empty", -2);
  559.         }
  560. }
  561.