home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / bag < prev    next >
Text File  |  1992-07-21  |  13KB  |  526 lines
  1. /* C.Bag: Bag data type */
  2.  
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "bag.h"
  7.  
  8. #ifdef test
  9. #include <stdio.h>
  10. #endif
  11.  
  12. struct link
  13. {
  14.         struct link *next;
  15.         int count;
  16.         char data[1];
  17. };
  18.  
  19. typedef struct link *link;
  20.  
  21. /* Return values from functions */
  22.  
  23. #define OK      1
  24. #define ERR     0
  25.  
  26. /* Utility function - find an element in a bag */
  27.  
  28. static link find (const bag b, const void *element, link *prev)
  29. {
  30.         link this;
  31.         link p = NULL;
  32.         const int size = b->obj_size;
  33.  
  34.         for ( this = b->first; this != NULL; this = this->next )
  35.         {
  36.                 if ( memcmp(element,this->data,size) == 0 )
  37.                 {
  38.                         if ( prev != NULL )
  39.                                 *prev = p;
  40.                                 
  41.                         return this;
  42.                 }
  43.  
  44.                 p = this;
  45.         }
  46.  
  47.         return NULL;
  48. }
  49.  
  50. /* General component routines */
  51.  
  52. bag bag_new (int obj_len)
  53. {
  54.         register bag b;
  55.  
  56.         b = malloc(sizeof(struct bag));
  57.  
  58.         if ( b == NULL )
  59.                 return NULL;
  60.  
  61.         b->first    = NULL;
  62.         b->obj_size = obj_len;
  63.  
  64.         return b;
  65. }
  66.  
  67. void bag_free (bag b)
  68. {
  69.         bag_clear(b);
  70.         free(b);
  71. }
  72.  
  73. void bag_clear (bag b)
  74. {
  75.         link this_entry = b->first;
  76.         link next_entry;
  77.         
  78.         while ( this_entry != NULL )
  79.         {
  80.                 next_entry = this_entry->next;
  81.                 free(this_entry);
  82.                 this_entry = next_entry;
  83.         }
  84.  
  85.         b->first = NULL;
  86. }
  87.  
  88. int bag_copy (bag b1, const bag b2)
  89. {
  90.         link p;
  91.         link new;
  92.         link last;
  93.         int size;
  94.  
  95.         if ( b1->obj_size != b2->obj_size )
  96.                 return ERR;
  97.  
  98.         bag_clear(b1);
  99.  
  100.         last = (link)b1;
  101.         size = b2->obj_size;
  102.  
  103.         for ( p = b2->first; p != NULL; p = p->next )
  104.         {
  105.                 new = malloc(sizeof(struct link) - 1 + size);
  106.                 if ( new == NULL )
  107.                 {
  108.                         bag_clear(b1);
  109.                         return ERR;
  110.                 }
  111.                 last->next = new;
  112.                 memcpy(new->data,p->data,size);
  113.                 new->count = p->count;
  114.                 last = new;
  115.         }
  116.  
  117.         last->next = NULL;
  118.         return OK;
  119. }
  120.  
  121. int bag_equal (const bag b1, const bag b2)
  122. {
  123.         link p;
  124.         link q;
  125.         int n1 = 0;
  126.         int n2 = 0;
  127.  
  128.         if ( b1->obj_size != b2->obj_size )
  129.                 return 0;
  130.  
  131.         /* For every element of b1, look for it in b2 */
  132.  
  133.         for ( p = b1->first; p != NULL; p = p->next )
  134.         {
  135.                 q = find(b2,p->data,NULL);
  136.  
  137.                 /* If it's not in b2, or the counts are different, b1 != b2 */
  138.                 if ( q == NULL || p->count != q->count )
  139.                         return 0;
  140.  
  141.                 /* Count the unique elements of b1 */
  142.                 ++n1;
  143.         }
  144.  
  145.         /* Count the unique elements of b2 */
  146.         for ( p = b2->first; p != NULL; p = p->next )
  147.                 ++n2;
  148.  
  149.         /* The bags differ if there are elements in b1 not in b2 */
  150.         return ( n1 == n2 );
  151. }
  152.  
  153. int bag_empty (const bag b)
  154. {
  155.         return ( b->first == NULL );
  156. }
  157.  
  158. int bag_size (const bag b)
  159. {
  160.         int i = 0;
  161.         link p;
  162.  
  163.         for ( p = b->first; p != NULL; p = p->next )
  164.                 i += p->count;
  165.  
  166.         return i;
  167. }
  168.  
  169. int bag_iterate (const bag b, int (*process)(void *, int))
  170. {
  171.         int ret = 0;
  172.         link p;
  173.  
  174.         for ( p = b->first; p != NULL; p = p->next )
  175.         {
  176.                 ret = (*process)(p->data,p->count);
  177.  
  178.                 /* Non-zero => stop processing here */
  179.  
  180.                 if ( ret != 0 )
  181.                         break;
  182.         }
  183.  
  184.         /* Negative => Abnormal (error) termination */
  185.  
  186.         return ( ret >= 0 );
  187. }
  188.  
  189. /* bag-specific routines */
  190.  
  191. int bag_add (bag b, const void *object)
  192. {
  193.         link new;
  194.  
  195.         new = find(b,object,NULL);
  196.  
  197.         if ( new != NULL )
  198.         {
  199.                 ++new->count;
  200.                 return OK;
  201.         }
  202.  
  203.         new = malloc(sizeof(struct link) - 1 + b->obj_size);
  204.  
  205.         if ( new == NULL )
  206.                 return ERR;
  207.  
  208.         memcpy(new->data,object,b->obj_size);
  209.         new->count = 1;
  210.  
  211.         new->next = b->first;
  212.         b->first = new;
  213.  
  214.         return OK;
  215. }
  216.  
  217. int bag_remove (bag b, const void *object)
  218. {
  219.         link p;
  220.         link prev;
  221.  
  222.         p = find(b,object,&prev);
  223.  
  224.         if ( p == NULL )
  225.                 return ERR;
  226.  
  227.         if ( p->count > 1 )
  228.         {
  229.                 --p->count;
  230.                 return OK;
  231.         }
  232.  
  233.         if ( prev == NULL )
  234.                 b->first = p->next;
  235.         else
  236.                 prev->next = p->next;
  237.  
  238.         free(p);
  239.  
  240.         return OK;
  241. }
  242.  
  243. int bag_member (const bag b, const void *object)
  244. {
  245.         return ( find(b,object,NULL) != NULL );
  246. }
  247.  
  248. int bag_count (const bag b, const void *object)
  249. {
  250.         link p = find(b,object,NULL);
  251.  
  252.         return ( p != NULL ? p->count : 0 );
  253. }
  254.  
  255. int bag_union (bag b1, const bag b2, const bag b3)
  256. {
  257.         link p;
  258.         link new;
  259.  
  260.         /* Check with b2's length occurs in bag_copy */
  261.         if ( b1->obj_size != b3->obj_size )
  262.                 return ERR;
  263.  
  264.         if ( !bag_copy(b1,b2) )
  265.                 return ERR;
  266.  
  267.         for ( p = b3->first; p != NULL; p = p->next )
  268.         {
  269.                 new = find(b1,p->data,NULL);
  270.  
  271.                 if ( new != NULL )
  272.                 {
  273.                         new->count += p->count;
  274.                         continue;
  275.                 }
  276.  
  277.                 new = malloc(sizeof(struct link) - 1 + b1->obj_size);
  278.  
  279.                 if ( new == NULL )
  280.                         return ERR;
  281.  
  282.                 memcpy(new->data,p->data,b1->obj_size);
  283.                 new->count = 1;
  284.  
  285.                 new->next = b1->first;
  286.                 b1->first = new;
  287.         }
  288.  
  289.         return OK;
  290. }
  291.  
  292. int bag_intersection (bag b1, const bag b2, const bag b3)
  293. {
  294.         link p;
  295.         link q;
  296.         link new;
  297.  
  298.         if ( b1->obj_size != b2->obj_size || b1->obj_size != b3->obj_size )
  299.                 return ERR;
  300.  
  301.         bag_clear(b1);
  302.  
  303.         for ( p = b2->first; p != NULL; p = p->next )
  304.         {
  305.                 q = find(b3,p->data,NULL);
  306.  
  307.                 if ( q == NULL )
  308.                         continue;
  309.  
  310.                 new = malloc(sizeof(struct link) - 1 + b1->obj_size);
  311.  
  312.                 if ( new == NULL )
  313.                         return ERR;
  314.  
  315.                 memcpy(new->data,p->data,b1->obj_size);
  316.                 new->count = ( p->count < q->count ? p->count : q->count );
  317.  
  318.                 new->next = b1->first;
  319.                 b1->first = new;
  320.         }
  321.  
  322.         return OK;
  323. }
  324.  
  325. int bag_difference (bag b1, const bag b2, const bag b3)
  326. {
  327.         link p;
  328.         link q;
  329.         link new;
  330.  
  331.         if ( b1->obj_size != b2->obj_size || b1->obj_size != b3->obj_size )
  332.                 return ERR;
  333.  
  334.         bag_clear(b1);
  335.  
  336.         for ( p = b2->first; p != NULL; p = p->next )
  337.         {
  338.                 q = find(b3,p->data,NULL);
  339.  
  340.                 if ( q != NULL && p->count <= q->count )
  341.                         continue;
  342.  
  343.                 new = malloc(sizeof(struct link) - 1 + b1->obj_size);
  344.  
  345.                 if ( new == NULL )
  346.                         return ERR;
  347.  
  348.                 memcpy(new->data,p->data,b1->obj_size);
  349.                 new->count = p->count;
  350.                 if ( q != NULL )
  351.                         new->count -= q->count;
  352.  
  353.                 new->next = b1->first;
  354.                 b1->first = new;
  355.         }
  356.  
  357.         return OK;
  358. }
  359.  
  360. int bag_unique_count (const bag b)
  361. {
  362.         int i = 0;
  363.         link p;
  364.  
  365.         for ( p = b->first; p != NULL; p = p->next )
  366.                 ++i;
  367.  
  368.         return i;
  369. }
  370.  
  371. int bag_subset (const bag b1, const bag b2)
  372. {
  373.         link p;
  374.         link q;
  375.  
  376.         if ( b1->obj_size != b2->obj_size )
  377.                 return 0;
  378.  
  379.         /* For every element of b1, look for it in b2 */
  380.  
  381.         for ( p = b1->first; p != NULL; p = p->next )
  382.         {
  383.                 q = find(b2,p->data,NULL);
  384.  
  385.                 /* If it's not in b2, or in less times, b1 is not a subset */
  386.                 if ( q == NULL || p->count > q->count )
  387.                         return 0;
  388.         }
  389.  
  390.         return 1;