home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v92.tgz / v92.tar / v92 / src / runtime / oset.r < prev    next >
Text File  |  1996-03-22  |  9KB  |  298 lines
  1. /*
  2.  * File: oset.r
  3.  *  Contents: compl, diff, inter, union
  4.  */
  5.  
  6. "~x - complement cset x."
  7.  
  8. operator{1} ~ compl(x)
  9.    /*
  10.     * x must be a cset.
  11.     */
  12.    if !cnv:tmp_cset(x) then
  13.       runerr(104, x)
  14.  
  15.    abstract {
  16.       return cset
  17.       }
  18.    body {
  19.       register int i;
  20.       struct b_cset *cp, *cpx;
  21.  
  22.       /*
  23.        * Allocate a new cset and then copy each cset word from x
  24.        *  into the new cset words, complementing each bit.
  25.        */
  26.       Protect(cp = alccset(), runerr(0));
  27.       cpx = (struct b_cset *)BlkLoc(x);      /* must come after alccset() */
  28.       for (i = 0; i < CsetSize; i++) 
  29.           cp->bits[i] = ~cpx->bits[i];
  30.       return cset(cp);
  31.       }
  32. end
  33.  
  34.  
  35. "x -- y - difference of csets x and y or of sets x and y."
  36.  
  37. operator{1} -- diff(x,y)
  38.    if is:set(x) && is:set(y) then {
  39.       abstract {
  40.          return type(x)
  41.          }
  42.       body {
  43.      int res;
  44.          register int i;
  45.          register word slotnum;
  46.          tended union block *srcp, *tstp, *dstp;
  47.          tended struct b_slots *seg;
  48.          tended struct b_selem *ep;
  49.          struct b_selem *np;
  50.          union block **hook;
  51.  
  52.          /*
  53.           * Make a new set based on the size of x.
  54.           */
  55.          dstp = hmake(T_Set, (word)0, BlkLoc(x)->set.size);
  56.          if (dstp == NULL)
  57.             runerr(0);
  58.          /*
  59.           * For each element in set x if it is not in set y
  60.           *  copy it directly into the result set.
  61.       *
  62.       * np always has a new element ready for use.  We get one in advance,
  63.       *  and stay one ahead, because hook can't be tended.
  64.           */
  65.          srcp = BlkLoc(x);
  66.          tstp = BlkLoc(y);
  67.          Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  68.  
  69.          for (i = 0; i < HSegs && (seg = srcp->set.hdir[i]) != NULL; i++)
  70.             for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--) {
  71.                ep = (struct b_selem *)seg->hslots[slotnum];
  72.                while (ep != NULL) {
  73.                   memb(tstp, &ep->setmem, ep->hashnum, &res);
  74.                   if (res == 0) {
  75.                      hook = memb(dstp, &ep->setmem, ep->hashnum, &res);
  76.              np->setmem = ep->setmem;
  77.              np->hashnum = ep->hashnum;
  78.                      addmem(&dstp->set, np, hook);
  79.                      Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  80.                      }
  81.                   ep = (struct b_selem *)ep->clink;
  82.                   }
  83.                }
  84.      deallocate((union block *)np);
  85.          if (TooSparse(dstp))
  86.             hshrink(dstp);
  87.          return set(dstp);
  88.          }
  89.       }
  90.    else {
  91.       if !cnv:tmp_cset(x) then
  92.          runerr(120, x)
  93.       if !cnv:tmp_cset(y) then
  94.          runerr(120, y)
  95.       abstract {
  96.          return cset
  97.          }
  98.       /*
  99.        * Allocate a new cset and in each word of it, compute the value
  100.        *  of the bitwise difference of the corresponding words in the
  101.        *  Arg1 and Arg2 csets.
  102.        */
  103.       body {
  104.          struct b_cset *cp, *cpx, *cpy;
  105.          register int i;
  106.  
  107.          Protect(cp = alccset(), runerr(0));
  108.          cpx = (struct b_cset *)BlkLoc(x);  /* must come after alccset() */
  109.          cpy = (struct b_cset *)BlkLoc(y);  /* must come after alccset() */
  110.          for (i = 0; i < CsetSize; i++)
  111.             cp->bits[i] = cpx->bits[i] & ~cpy->bits[i];
  112.          return cset(cp);
  113.          }
  114.       }
  115. end
  116.  
  117.  
  118. "x ** y - intersection of csets x and y or of sets x and y."
  119.  
  120. operator{1} ** inter(x,y)
  121.    if is:set(x) && is:set(y) then {
  122.       abstract {
  123.          return new set(store[type(x).set_elem] ** store[type(y).set_elem])
  124.          }
  125.       body {
  126.      int res;
  127.          register int i;
  128.          register word slotnum;
  129.          tended union block *srcp, *tstp, *dstp;
  130.          tended struct b_slots *seg;
  131.          tended struct b_selem *ep;
  132.          struct b_selem *np;
  133.          union block **hook;
  134.  
  135.          /*
  136.           * Make a new set the size of the smaller argument set.
  137.           */
  138.          dstp = hmake(T_Set, (word)0,
  139.             Min(BlkLoc(x)->set.size, BlkLoc(y)->set.size));
  140.          if (dstp == NULL)
  141.             runerr(0);
  142.          /*
  143.           * Using the smaller of the two sets as the source
  144.           *  copy directly into the result each of its elements
  145.           *  that are also members of the other set.
  146.       *
  147.       * np always has a new element ready for use.  We get one in advance,
  148.       *  and stay one ahead, because hook can't be tended.
  149.           */
  150.          if (BlkLoc(x)->set.size <= BlkLoc(y)->set.size) {
  151.             srcp = BlkLoc(x);
  152.             tstp = BlkLoc(y);
  153.             }
  154.          else {
  155.             srcp = BlkLoc(y);
  156.             tstp = BlkLoc(x);
  157.             }
  158.          Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  159.          for (i = 0; i < HSegs && (seg = srcp->set.hdir[i]) != NULL; i++)
  160.             for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--) {
  161.                ep = (struct b_selem *)seg->hslots[slotnum];
  162.                while (ep != NULL) {
  163.                   memb(tstp, &ep->setmem, ep->hashnum, &res);
  164.                   if (res != 0) {
  165.                      hook = memb(dstp, &ep->setmem, ep->hashnum, &res);
  166.              np->setmem = ep->setmem;
  167.              np->hashnum = ep->hashnum;
  168.                      addmem(&dstp->set, np, hook);
  169.                      Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  170.                      }
  171.                   ep = (struct b_selem *)ep->clink;
  172.                   }
  173.                }
  174.      deallocate((union block *)np);
  175.          if (TooSparse(dstp))
  176.             hshrink(dstp);
  177.          return set(dstp);
  178.          }
  179.       }
  180.    else {
  181.  
  182.       if !cnv:tmp_cset(x) then
  183.          runerr(120, x)
  184.       if !cnv:tmp_cset(y) then
  185.          runerr(120, y)
  186.       abstract {
  187.          return cset
  188.          }
  189.  
  190.       /*
  191.        * Allocate a new cset and in each word of it, compute the value
  192.        *  of the bitwise intersection of the corresponding words in the
  193.        *  x and y csets.
  194.        */
  195.       body {
  196.          struct b_cset *cp, *cpx, *cpy;
  197.          register int i;
  198.  
  199.          Protect(cp = alccset(), runerr(0));
  200.          cpx = (struct b_cset *)BlkLoc(x);  /* must come after alccset() */
  201.          cpy = (struct b_cset *)BlkLoc(y);  /* must come after alccset() */
  202.          for (i = 0; i < CsetSize; i++) {
  203.             cp->bits[i] = cpx->bits[i] & cpy->bits[i];
  204.             }
  205.          return cset(cp);
  206.          }
  207.       }
  208. end
  209.  
  210.  
  211. "x ++ y - union of csets x and y or of sets x and y."
  212.  
  213. operator{1} ++ union(x,y)
  214.    if is:set(x) && is:set(y) then {
  215.       abstract {
  216.          return new set(store[type(x).set_elem] ++ store[type(y).set_elem])
  217.          }
  218.       body {
  219.      int res;
  220.      register int i;
  221.      register word slotnum;
  222.          struct descrip d;
  223.          tended union block *dstp;
  224.          tended struct b_slots *seg;
  225.          tended struct b_selem *ep;
  226.          struct b_selem *np;
  227.          union block **hook;
  228.  
  229.          /*
  230.           * Ensure that x is the larger set; if not, swap.
  231.           */
  232.          if (BlkLoc(y)->set.size > BlkLoc(x)->set.size) {
  233.         d = x;
  234.         x = y;
  235.         y = d;
  236.         }
  237.          /*
  238.           * Copy x and ensure there's room for *x + *y elements.
  239.           */
  240.          if (cpset(&x, &result, BlkLoc(x)->set.size + BlkLoc(y)->set.size)
  241.             == Error)
  242.             runerr(0);
  243.          /*
  244.           * Copy each element from y into the result, if not already there.
  245.       *
  246.       * np always has a new element ready for use.  We get one in advance,
  247.       *  and stay one ahead, because hook can't be tended.
  248.           */
  249.          dstp = BlkLoc(result);
  250.          Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  251.          for (i = 0; i < HSegs && (seg = BlkLoc(y)->set.hdir[i]) != NULL; i++)
  252.             for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--) {
  253.                ep = (struct b_selem *)seg->hslots[slotnum];
  254.                while (ep != NULL) {
  255.                   hook = memb(dstp, &ep->setmem, ep->hashnum, &res);
  256.                   if (res == 0) {
  257.              np->setmem = ep->setmem;
  258.              np->hashnum = ep->hashnum;
  259.                      addmem(&dstp->set, np, hook);
  260.                      Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  261.                      }
  262.                   ep = (struct b_selem *)ep->clink;
  263.                   }
  264.                }
  265.      deallocate((union block *)np);
  266.          if (TooCrowded(dstp))        /* if the union got too big, enlarge */
  267.             hgrow(dstp);
  268.          return result;
  269.      }
  270.       }
  271.    else {
  272.       if !cnv:tmp_cset(x) then
  273.          runerr(120, x)
  274.       if !cnv:tmp_cset(y) then
  275.          runerr(120, y)
  276.       abstract {
  277.          return cset
  278.          }
  279.  
  280.       /*
  281.        * Allocate a new cset and in each word of it, compute the value
  282.        *  of the bitwise union of the corresponding words in the
  283.        *  x and y csets.
  284.        */
  285.       body {
  286.          struct b_cset *cp, *cpx, *cpy;
  287.          register int i;
  288.  
  289.          Protect(cp = alccset(), runerr(0));
  290.          cpx = (struct b_cset *)BlkLoc(x);  /* must come after alccset() */
  291.          cpy = (struct b_cset *)BlkLoc(y);  /* must come after alccset() */
  292.          for (i = 0; i < CsetSize; i++)
  293.             cp->bits[i] = cpx->bits[i] | cpy->bits[i];
  294.          return cset(cp);
  295.          }
  296.       }
  297. end
  298.