home *** CD-ROM | disk | FTP | other *** search
/ cs.rhul.ac.uk / www.cs.rhul.ac.uk.zip / www.cs.rhul.ac.uk / pub / rdp / rdp_cs3470.tar / rdp_supp / set.c < prev    next >
C/C++ Source or Header  |  1998-05-07  |  13KB  |  389 lines
  1. /*******************************************************************************
  2. *
  3. * RDP release 1.50 by Adrian Johnstone (A.Johnstone@rhbnc.ac.uk) 20 December 1997
  4. *
  5. * set.h - dynamically resizable set handling
  6. *
  7. * This file may be freely distributed. Please mail improvements to the author.
  8. *
  9. *******************************************************************************/
  10. #include <stdio.h>
  11. #include <stdarg.h>
  12. #include <string.h>
  13. #include "textio.h"
  14. #include "memalloc.h"
  15. #include "set.h"
  16.  
  17. /* lookup table of bit masks for bits 0 to 7 */
  18. /*                                    0  1  2  3   4   5   6    7 */
  19. static const unsigned char mask[8]= {1, 2, 4, 8, 16, 32, 64, 128}; 
  20.  
  21. /* minimum allowable set size so as to minimise reallocation traffic */
  22. static unsigned set_minimumsize = 0; 
  23.  
  24. #define SET_GROW_TO                                                         \
  25. { \
  26.   va_list ap;                 /* argument list walker */ \
  27.   unsigned c,                 /* running argument copy */ \
  28.   max = 0;                    /* largest element */ \
  29.   /* scan all the elements to find the largest one */ \
  30.   va_start(ap, dst);          /* read parameter list until end marker */ \
  31.   while ((c = va_arg(ap, unsigned))!= SET_END)\
  32.     if (c > max)              /* if this element is larger than max */ \
  33.     max = c;                  /* then remember it */ \
  34.   va_end(ap);                 /* end of parameter list processing */ \
  35.   set_grow(dst, max / 8 + 1);  /* set size to be at least as long max */ \
  36. }
  37.  
  38. #define SET_ITERATE_LIST(func)                                              \
  39. { \
  40.   va_list ap;                 /* argument list walker */ \
  41.   unsigned c;                 /* running argument copy */ \
  42.   va_start(ap, dst);          /* read parameter list until end marker */ \
  43.   while ((c = va_arg(ap, unsigned))!= SET_END)\
  44.     func; \
  45.   va_end(ap);                 /* end of parameter list processing */ \
  46. }
  47.  
  48. #define SET_ITERATE_SET(func, length)                                       \
  49. { \
  50.   unsigned count; \
  51.   for (count = 0; count < length; count++) /* scan sets */ \
  52.     func; \
  53. }
  54.  
  55. /* return an array of (cardinality + 1) unsigned integers, being the element
  56.    numbers of set src terminated by SET_END */
  57. unsigned * set_array(const set_ * src)
  58. {
  59.   unsigned * running, 
  60.   * block =(unsigned *) mem_malloc((set_cardinality(src)+ 1)* sizeof(unsigned)), 
  61.   c,                          /* current set byte counter */
  62.   element = 0;                /* running element number */
  63.   
  64.   running = block;            /* point running pointer at end of block */
  65.   
  66.   for (c = 0; c < src->length; c++) /* scan over all set bytes */
  67.   {
  68.     unsigned walker,          /* walking one */
  69.     byte = src->elements[c];  /* get the current byte */
  70.     
  71.     for (walker = 1; walker < 256; walker <<= 1) /* walk a one across eight bits */
  72.     {
  73.       if ((byte & walker)!= 0) /* if this element is present in the set */
  74.         * running++ = element; 
  75.       
  76.       element++; 
  77.     }
  78.   }
  79.   
  80.   * running = SET_END; 
  81.   
  82.   return block; 
  83. }
  84.  
  85. /* return the number of elements in this set */
  86. unsigned set_cardinality(const set_ * src)
  87. {
  88.   /* lookup table of number of bits set in a nibble */
  89.   /* 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 */
  90.   static const unsigned char bits[16]= {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; 
  91.   
  92.   unsigned cardinality = 0,   /* running cardinality counter */
  93.   count;                      /* set element counter */
  94.   
  95.   for (count = 0; count < src->length; count++) /* scan over whole set */
  96.   {
  97.     cardinality += bits[src->elements[count]& 15];  /* add in cardinality of hi nibble */
  98.     cardinality += bits[src->elements[count]>> 4];  /* add in cardinality of lo nibble */
  99.   }
  100.   return cardinality;         /* return result */
  101. }
  102.  
  103. /* clear a dst and then set only those bits specified by src */
  104. void set_assign_element(set_ * dst, const unsigned element) /* assign one element to a set */
  105. {
  106.   set_grow(dst, element / 8 + 1);  /* set size to be at least as long as needed */
  107.   memset(dst->elements, 0, dst->length);  /* clear the set to the empty set */
  108.   dst->elements[element >> 3]|= mask[element & 7];  /* OR in the corresponding bit */
  109. }
  110.  
  111. void set_assign_list(set_ * dst, ...) /* assign a list of elements to a set */
  112. {
  113.   SET_GROW_TO; 
  114.   memset(dst->elements, 0, dst->length);  /* clear the set to the empty set */
  115.   SET_ITERATE_LIST((dst->elements[c >> 3]|= mask[c & 7])); 
  116. }
  117.  
  118. void set_assign_set(set_ * dst, const set_ * src) /* assign one set to another */
  119. {
  120.   set_grow(dst, src->length);  /* set size to be at least as long as needed */
  121.   memset(dst->elements, 0, dst->length);  /* clear the set to the empty set */
  122.   memcpy(dst->elements, src->elements, src->length);  /* memory-memory copy */
  123. }
  124.  
  125. /* perform a comparison between sets, returning results like strcmp() */
  126. int set_compare(set_ * dst, set_ * src)
  127. {
  128.   set_normalise(dst); 
  129.   set_normalise(src); 
  130.   
  131.   if (dst->length != src->length)
  132.     return dst->length > src->length; 
  133.   else
  134.     return strncmp((char *) dst->elements, (char *) src->elements, dst->length); 
  135. }
  136.  
  137. /* remove from dst those elements in src */
  138. void set_difference_element(set_ * dst, const unsigned element)
  139. {
  140.   set_grow(dst, element / 8 + 1);  /* set size to be at least as long as needed */
  141.   dst->elements[element >> 3]&=(unsigned char)(~mask[element & 7]);  /* mask off corresponding bit */
  142. }
  143.  
  144. void set_difference_list(set_ * dst, ...)
  145. {
  146.   SET_GROW_TO; 
  147.   SET_ITERATE_LIST((dst->elements[c >> 3]&=(unsigned char)(~mask[c & 7]))); 
  148. }
  149.  
  150. void set_difference_set(const set_ * dst, const set_ * src)
  151. {
  152.   unsigned length = dst->length < src->length ? dst->length: src->length;  /* only iterate over shortest set */
  153.   
  154.   SET_ITERATE_SET((dst->elements[count]&=(unsigned char)(~src->elements[count])), length); 
  155. }
  156.  
  157. /* free storage associated with a set's elements and return set to SET_NULL */
  158. void set_free(set_ * dst)
  159. {
  160.   if (dst->elements != NULL)
  161.     mem_free(dst->elements); 
  162.   dst->length = 0; 
  163.   dst->elements = NULL; 
  164. }
  165.  
  166. void set_grow(set_ * dst, const unsigned length) /* test size of set and resize if necessary */
  167. {
  168.   if (dst->length < length)   /* if set is too small then resize */
  169.   {
  170.     /* belt and braces resize */
  171.     unsigned char * temp =(unsigned char *) mem_calloc(length, 1); 
  172.     
  173.     if (dst->elements != NULL)
  174.     {
  175.       memcpy(temp, dst->elements, dst->length); 
  176.       mem_free(dst->elements); 
  177.     }
  178.     dst->length = length; 
  179.     dst->elements = temp; 
  180.     
  181.     #if 0
  182.     dst->elements =(unsigned char *) mem_realloc(dst->elements, length); 
  183.     memset(dst->elements + dst->length, 0, length - dst->length);  /* clear new bytes */
  184.     dst->length = length;     /* and set new length accordingly */
  185.     #endif
  186.   }
  187. }
  188.  
  189. int set_includes_element(set_ * dst, const unsigned element)
  190. {
  191.   set_grow(dst, element / 8 + 1);  /* set size to be at least as long as needed */
  192.   return(dst->elements[element >> 3]& mask[element & 7])!= 0; 
  193. }
  194.  
  195. int set_includes_list(set_ * dst, ...)
  196. {
  197.   int isin = 1; 
  198.   
  199.   SET_GROW_TO; 
  200.   SET_ITERATE_LIST((isin = isin &&((dst->elements[c >> 3]& mask[c & 7])!= 0))); 
  201.   return(isin); 
  202. }
  203.  
  204. int set_includes_set(const set_ * dst, const set_ * src)
  205. {
  206.   int isin = 1; 
  207.   unsigned length = dst->length < src->length ? dst->length: src->length;  /* only iterate over shortest set */
  208.   
  209.   SET_ITERATE_SET((isin = isin &&((src->elements[count]| dst->elements[count])== dst->elements[count])), length); 
  210.   
  211.   if (src->length > dst->length) /* there may be more bits left! */
  212.   {
  213.     unsigned count; 
  214.     
  215.     for (count = length; count < src->length; count++)
  216.       isin = isin &&(src->elements[count]== 0); 
  217.   }
  218.   return(isin); 
  219. }
  220.  
  221. void set_intersect_element(set_ * dst, const unsigned element)
  222. {
  223.   unsigned char result; 
  224.   
  225.   set_grow(dst, element / 8 + 1);  /* set size to be at least as long as needed */
  226.   result = dst->elements[element >> 3]& mask[element & 7]; 
  227.   memset(dst->elements, 0, dst->length);  /* clear the set to the empty set */
  228.   dst->elements[element >> 3]= result; 
  229. }
  230.  
  231. void set_intersect_list(set_ * dst, ...)
  232. {
  233.   set_ src = SET_NULL; 
  234.   
  235.   /* first we must build a set to hold the element list: copy set_assign_list */
  236.   {
  237.     va_list ap;               /* argument list walker */
  238.     unsigned c,               /* running argument copy */
  239.     max = 0;                  /* largest element */
  240.     
  241.     /* scan all the elements to find the largest one */
  242.     va_start(ap, dst);        /* read parameter list until end marker */
  243.     while ((c = va_arg(ap, unsigned))!= SET_END)
  244.       if (c > max)            /* if this element is larger than max */
  245.       max = c;                /* then remember it */
  246.     va_end(ap);               /* end of parameter list processing */
  247.     set_grow(& src, max / 8 + 1);  /* set size to be at least as long max */
  248.   }
  249.   memset(src.elements, 0, src.length);  /* clear the set to the empty set */
  250.   SET_ITERATE_LIST((src.elements[c >> 3]|= mask[c & 7])); 
  251.   
  252.   set_intersect_set(dst, & src); 
  253.   
  254.   set_free(& src); 
  255. }
  256.  
  257. void set_intersect_set(set_ * dst, const set_ * src)
  258. {
  259.   unsigned length = dst->length < src->length ? dst->length: src->length;  /* only iterate over shortest set */
  260.   
  261.   SET_ITERATE_SET((dst->elements[count]&= src->elements[count]), length); 
  262.   /* Now clear rest of dst */
  263.   if (length < dst->length)
  264.     memset(dst->elements + length, 0, dst->length - length);  /* clear new bytes */
  265. }
  266.  
  267. void set_invert(set_ * dst, const unsigned universe)
  268. {
  269.   /* lookup table of fill values for bits 0 - 7 */
  270.   /* 0  1  2   3   4   5    6    7 */
  271.   static const unsigned char fills[8]= {1, 3, 7, 15, 31, 63, 127, 255}; 
  272.   
  273.   unsigned top = universe / 8 + 1; 
  274.   
  275.   set_grow(dst, top);         /* set size to be at least as long as needed */
  276.   SET_ITERATE_SET((dst->elements[count]^= 0xFF), dst->length); 
  277.   dst->elements[top - 1]&= fills[universe % 8];  /* mask off last byte */
  278.   memset(dst->elements + top, 0, dst->length - top);  /* clear extra bytes */
  279. }
  280.  
  281. unsigned set_minimum_size(const unsigned minimum_size)
  282. {
  283.   if (minimum_size != SET_END) /* minimum = SET_END => query only */
  284.     set_minimumsize = minimum_size;  /* set the minimum size */
  285.   
  286.   return set_minimumsize;     /* return current value */
  287. }
  288.  
  289. void set_normalise(set_ * dst)
  290. {
  291.   if (dst->length < set_minimumsize) /* do we need to grow dst? */
  292.     set_grow(dst, set_minimumsize);  /* grow to minimum size */
  293.   else
  294.   {
  295.     unsigned char * p = dst->elements + dst->length - 1;  /* find last byte */
  296.     
  297.     if (* p == 0)             /* is there an empty byte at end? */
  298.     {
  299.       while (*(p--)== 0 && dst->length > set_minimumsize) /* run down zero bytes */
  300.         dst->length--;        /* reducing length as we go */
  301.       
  302.       dst->elements =(unsigned char *) mem_realloc(dst->elements, dst->length);  /* and resize */
  303.     }
  304.   }
  305. }
  306.  
  307. void set_print_element(const unsigned element, const char * element_names)
  308. {
  309.   if (element_names == NULL)  /* just print decimal set element numbers */
  310.     text_printf("%u", element); 
  311.   else
  312.   {
  313.     unsigned c; 
  314.     
  315.     /* skip to correct element name */
  316.     for (c = element; c > 0; c--)
  317.     {
  318. /*      text_printf("\n%s", element_names); */  /* print the element name string */
  319.       
  320.       while (* element_names++ != 0)
  321.         ; 
  322.     }
  323.     
  324.     text_printf("%s", element_names);  /* print the element name string */
  325.   }
  326. }
  327.  
  328. void set_print_set(const set_ * src, const char * element_names, unsigned line_length)
  329. {
  330.   unsigned
  331.   column = 0, 
  332.   last_printed = 0, 
  333.   not_first = 0, 
  334.   * elements = set_array(src), 
  335.   * base; 
  336.   
  337.   base = elements; 
  338.   while (* elements != SET_END)
  339.   {
  340.     if (not_first)
  341.       column += text_printf(", "); 
  342.     else
  343.       not_first = 1; 
  344.     
  345.     if (line_length != 0 && column >= line_length) /* we are past margin */
  346.     {
  347.       text_printf("\n"); 
  348.       column = 0; 
  349.     }
  350.     
  351.     if (element_names == NULL) /* just print decimal set element numbers */
  352.       column += text_printf("%u", * elements++); 
  353.     else
  354.     {
  355.       unsigned c; 
  356.       
  357.       /* skip to correct element name */
  358.       for (c = * elements - last_printed; c > 0; c--)
  359.         while (* element_names++ != 0)
  360.         ; 
  361.       
  362.       column += text_printf("%s", element_names);  /* print the element name string */
  363.       last_printed = * elements++;  /* remember where we are for next time */
  364.     }
  365.   }
  366.   mem_free(base);             /* release memory block */
  367. }
  368.  
  369. void set_unite_element(set_ * dst, const unsigned element)
  370. {
  371.   set_grow(dst, element / 8 + 1);  /* set size to be at least as long as needed */
  372.   
  373.   dst->elements[element >> 3]|= mask[element & 7];  /* OR in the corresponding bit */
  374. }
  375.  
  376. void set_unite_list(set_ * dst, ...)
  377. {
  378.   SET_GROW_TO; 
  379.   SET_ITERATE_LIST((dst->elements[c >> 3]|= mask[c & 7])); 
  380. }
  381.  
  382. void set_unite_set(set_ * dst, const set_ * src)
  383. {
  384.   set_grow(dst, src->length);  /* set size to be at least as long as needed */
  385.   SET_ITERATE_SET((dst->elements[count]|= src->elements[count]), src->length); 
  386. }
  387.  
  388. /* End of set.c */
  389.