home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / libg++-2.6-fsf.lha / libg++-2.6 / libg++ / src / BitSet.cc < prev    next >
C/C++ Source or Header  |  1994-05-11  |  20KB  |  1,007 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitSet class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <BitSet.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #include <Obstack.h>
  29. #include <AllocRing.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <string.h>
  33. #include <strstream.h>
  34.  
  35. void BitSet::error(const char* msg) const
  36. {
  37.   (*lib_error_handler)("BitSet", msg);
  38. }
  39.  
  40. //  globals & constants
  41.  
  42. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  43.  
  44. #define ONES               ((unsigned short)(~0L))
  45. #define MAXBitSetRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  46. #define MINBitSetRep_SIZE  16
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD     4
  50. #endif
  51.  
  52. // break things up into .s indices and positions
  53.  
  54.  
  55. // mask out bits from left
  56.  
  57. static inline unsigned short lmask(int p)
  58. {
  59.   return ONES << p;
  60. }
  61.  
  62. // mask out high bits
  63.  
  64. static inline unsigned short rmask(int p)
  65. {
  66.   return ONES >> (BITSETBITS - 1 - p);
  67. }
  68.  
  69.  
  70. inline static BitSetRep* BSnew(int newlen)
  71. {
  72.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  73.     + MALLOC_MIN_OVERHEAD;
  74.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  75.   while (allocsiz < siz) allocsiz <<= 1;
  76.   allocsiz -= MALLOC_MIN_OVERHEAD;
  77.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  78.     (*lib_error_handler)("BitSet", "Requested length out of range");
  79.     
  80.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  81.   memset(rep, 0, allocsiz);
  82.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  83.   return rep;
  84. }
  85.  
  86. BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen,
  87.                 int newvirt, int newlen)
  88. {
  89.   if (old == &_nilBitSetRep) old = 0;
  90.   BitSetRep* rep;
  91.   if (old == 0 || newlen >= old->sz)
  92.     rep = BSnew(newlen);
  93.   else
  94.     rep = old;
  95.  
  96.   rep->len = newlen;
  97.   rep->virt = newvirt;
  98.  
  99.   if (srclen != 0 && src != rep->s)
  100.     memcpy(rep->s, src, srclen * sizeof(short));
  101.   // BUG fix: extend virtual bit! 20 Oct 1992 Kevin Karplus
  102.   if (rep->virt)
  103.       memset(&rep->s[srclen], ONES, (newlen - srclen) * sizeof(short));
  104.   if (old != rep && old != 0) delete old;
  105.   return rep;
  106. }
  107.  
  108. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  109. {
  110.   BitSetRep* rep;
  111.   if (old == 0 || old == &_nilBitSetRep)
  112.   {
  113.     rep = BSnew(newlen);
  114.     rep->virt = 0;
  115.   }
  116.   else if (newlen >= old->sz)
  117.   {
  118.     rep = BSnew(newlen);
  119.     memcpy(rep->s, old->s, old->len * sizeof(short));
  120.     rep->virt = old->virt;
  121.     // BUG fix: extend virtual bit!  20 Oct 1992 Kevin Karplus
  122.     if (rep->virt)
  123.     memset(&rep->s[old->len], ONES, (newlen - old->len) * sizeof(short));
  124.     delete old;
  125.   }
  126.   else
  127.     {
  128.       rep = old;
  129.       if (rep->len < newlen)
  130.     memset(&rep->s[rep->len],
  131.            rep->virt ? ONES : 0,
  132.            (newlen - rep->len) * sizeof(short));
  133.     }
  134.  
  135.   rep->len = newlen;
  136.  
  137.   return rep;
  138. }
  139.  
  140. // same, for straight copy
  141.  
  142. BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src)
  143. {
  144.   BitSetRep* rep;
  145.   if (old == &_nilBitSetRep) old = 0;
  146.   if (src == 0 || src == &_nilBitSetRep)
  147.   {
  148.     if (old == 0)
  149.       rep = BSnew(0);
  150.     else
  151.       rep = old;
  152.     rep->len = 0;
  153.     rep->virt = 0;
  154.   }
  155.   else if (old == src) 
  156.     return old; 
  157.   else 
  158.   {
  159.     int newlen = src->len;
  160.     if (old == 0 || newlen > old->sz)
  161.     {
  162.       rep = BSnew(newlen);
  163.       if (old != 0) delete old;
  164.     }
  165.     else
  166.       rep = old;
  167.  
  168.     memcpy(rep->s, src->s, newlen * sizeof(short));
  169.     rep->len = newlen;
  170.     rep->virt = src->virt;
  171.   }
  172.   return rep;
  173. }
  174.  
  175.  
  176. // remove unneeded top bits
  177.  
  178. inline static void trim(BitSetRep* rep)
  179. {
  180.   int l = rep->len;
  181.   unsigned short* s = &(rep->s[l - 1]);
  182.  
  183.   if (rep->virt == 0)
  184.     while (l > 0 && *s-- == 0) --l;
  185.   else
  186.     while (l > 0 && *s-- == ONES) --l;
  187.   rep->len = l;
  188. }
  189.  
  190. int operator == (const BitSet& x, const BitSet& y)
  191. {
  192.   if (x.rep->virt != y.rep->virt)
  193.     return 0;
  194.   int xl = x.rep->len;
  195.   int yl = y.rep->len;
  196.  
  197.   unsigned short* xs = x.rep->s;
  198.   unsigned short* ys = y.rep->s;
  199.   if (xl<=yl)
  200.     {
  201.       if (memcmp((void*)xs, (void*)ys, xl * sizeof(short)))
  202.       return 0;
  203.       for (register int i=xl; i<yl; i++)
  204.         if (ys[i])
  205.       return 0;
  206.       return 1;
  207.     }
  208.   else
  209.     {
  210.       if (memcmp((void*)xs, (void*)ys, yl * sizeof(short)))
  211.       return 0;
  212.       for (register int i=yl; i<xl; i++)
  213.         if (xs[i]) 
  214.       return 0;
  215.       return 1;
  216.     }
  217. }
  218.  
  219. int operator <= (const BitSet& x, const BitSet& y)
  220. {
  221.   if (x.rep->virt > y.rep->virt)
  222.     return 0;
  223.  
  224.   int xl = x.rep->len;
  225.   int yl = y.rep->len; 
  226.  
  227.   unsigned short* xs = x.rep->s;
  228.   unsigned short* ys = y.rep->s;
  229.   unsigned short* topx = &(xs[xl]);
  230.   unsigned short* topy = &(ys[yl]);
  231.  
  232.   while (xs < topx && ys < topy)
  233.   {
  234.     unsigned short a = *xs++;
  235.     unsigned short b = *ys++;
  236.     if ((a | b) != b)
  237.       return 0;
  238.   }
  239.   if (xl == yl)
  240.     return x.rep->virt <= y.rep->virt;
  241.   else if (xl < yl)
  242.     return !x.rep->virt;
  243.   else
  244.     return y.rep->virt;
  245. }
  246.  
  247.  
  248. int operator < (const BitSet& x, const BitSet& y)
  249. {
  250.   if (x.rep->virt > y.rep->virt)
  251.     return 0;
  252.  
  253.   int xl = x.rep->len;
  254.   int yl = y.rep->len;
  255.  
  256.   unsigned short* xs = x.rep->s;
  257.   unsigned short* ys = y.rep->s;
  258.   unsigned short* topx = &(xs[xl]);
  259.   unsigned short* topy = &(ys[yl]);
  260.   int one_diff = 0;
  261.   while (xs < topx && ys < topy)
  262.   {
  263.     unsigned short a = *xs++;
  264.     unsigned short b = *ys++;
  265.     unsigned short c = a | b;
  266.     if (c != b)
  267.       return 0;
  268.     else if (c != a)
  269.       one_diff = 1;
  270.   }
  271.   if (xl == yl)
  272.     return x.rep->virt < y.rep->virt || 
  273.       (one_diff && x.rep->virt == y.rep->virt);
  274.   else if (xl < yl)
  275.     return !x.rep->virt;
  276.   else
  277.     return y.rep->virt;
  278. }
  279.  
  280.  
  281.  
  282. int BitSet::empty() const
  283. {
  284.   if (rep->virt == 1)
  285.     return 0;
  286.  
  287.   unsigned short* bots = rep->s;
  288.   unsigned short* s = &(bots[rep->len - 1]);
  289.   while (s >= bots) if (*s-- != 0) return 0;
  290.   return 1;
  291. }
  292.  
  293.  
  294. int BitSet::count(int b) const
  295. {
  296.   if (b == rep->virt)
  297.     return -1;
  298.   int l = 0;
  299.   unsigned short* s = rep->s;
  300.   unsigned short* tops = &(s[rep->len]);
  301.   if (b == 1)
  302.   {
  303.     while (s < tops)
  304.     {
  305.       unsigned short a = *s++;
  306.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  307.       {
  308.         if (a & 1)
  309.           ++l;
  310.         a >>= 1;
  311.       }
  312.     }
  313.   }
  314.   else
  315.   {
  316.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  317.     while (s < tops)
  318.     {
  319.       unsigned short a = *s++;
  320.       for (int i = 0; i < BITSETBITS; ++i)
  321.       {
  322.         if ((a & maxbit) == 0)
  323.           ++l;
  324.         a <<= 1;
  325.       }
  326.     }
  327.   }
  328.   return l;
  329. }
  330.  
  331. BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r)
  332. {
  333.   r = BitSetcopy(r, src);
  334.   r->virt = !src->virt;
  335.   unsigned short* rs = r->s;
  336.   unsigned short* topr = &(rs[r->len]);
  337.   if (r->len == 0)
  338.     *rs = ONES;
  339.   else
  340.   {
  341.     while (rs < topr)
  342.     {
  343.       unsigned short cmp = ~(*rs);
  344.       *rs++ = cmp;
  345.     }
  346.   }
  347.   trim(r);
  348.   return r;
  349. }
  350.  
  351.  
  352. BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, 
  353.                     BitSetRep* r, char op)
  354. {
  355.   int xrsame = x == r;
  356.   int yrsame = y == r;
  357.   int xv = x->virt;
  358.   int yv = y->virt;
  359.   int xl = x->len;
  360.   int yl = y->len;
  361.   int rl = (xl >= yl)? xl : yl;
  362.  
  363.   r = BitSetresize(r, rl);
  364.   unsigned short* rs = r->s;
  365.   unsigned short* topr = &(rs[rl]);
  366.  
  367.   int av, bv;
  368.   const unsigned short* as;
  369.   const unsigned short* topa;
  370.   const unsigned short* bs;
  371.   const unsigned short* topb;
  372.   
  373.   if (xl <= yl)
  374.   {
  375.     as = (xrsame)? r->s : x->s;
  376.     av = xv;
  377.     topa = &(as[xl]);
  378.     bs = (yrsame)? r->s : y->s;
  379.     bv = yv;
  380.     topb = &(bs[yl]);
  381.   }
  382.   else
  383.   {
  384.     as = (yrsame)? r->s : y->