home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / libg++-2.6-fsf.lha / libg++-2.6 / libg++ / src / BitString.cc < prev    next >
C/C++ Source or Header  |  1994-05-31  |  36KB  |  1,607 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.   BitString class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <BitString.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 <strstream.h>
  33.  
  34. void BitString::error(const char* msg) const
  35. {
  36.   (*lib_error_handler)("BitString", msg);
  37. }
  38.  
  39. //  globals
  40.  
  41. BitStrRep    _nilBitStrRep = {  0, 1, {0} };
  42.  
  43. BitString _nil_BitString;
  44.  
  45. #define MINBitStrRep_SIZE  8
  46. #define MAXBitStrRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD    4
  50. #endif
  51.  
  52. #define ONES  ((_BS_word)(~0L))
  53. #define MAXBIT  (((_BS_word)1) << (BITSTRBITS - 1))
  54.  
  55. /*
  56.  *  bit manipulation utilities
  57. */
  58.  
  59. // break things up into .s indices and positions
  60.  
  61. inline static int BitStr_len(int l)
  62. {
  63.   return (unsigned)(l) / BITSTRBITS + 1;
  64. }
  65.  
  66.  
  67. // mask out low bits
  68.  
  69. static inline _BS_word lmask(int p)
  70. {
  71.   return ONES _BS_RIGHT p;
  72. }
  73.  
  74. // mask out high bits
  75.  
  76. static inline _BS_word rmask(int p)
  77. {
  78.   int s = BITSTRBITS - 1 - p;
  79.   if (s <= 0)
  80.     return ONES;
  81.   else
  82.     return ONES _BS_LEFT s;
  83. }
  84.  
  85.  
  86. // mask out unused bits in last word of rep
  87.  
  88. inline static void check_last(BitStrRep* r)
  89. {
  90.   int bit_len_mod = r->len & (BITSTRBITS - 1);
  91.   if (bit_len_mod)
  92.     r->s[r->len / BITSTRBITS] &= ONES _BS_LEFT (BITSTRBITS - bit_len_mod);
  93. }
  94.  
  95. // merge bits from next word
  96.  
  97. static inline _BS_word borrow_hi(const _BS_word a[], int ind, 
  98.                                       int maxind, int p)
  99. {
  100.   if (p == 0)
  101.     return a[ind];
  102.   else if (ind < maxind)
  103.     return (a[ind] _BS_LEFT p) | (a[ind+1] _BS_RIGHT (BITSTRBITS - p));
  104.   else
  105.     return (a[ind] _BS_LEFT p);
  106. }
  107.  
  108. // merge bits from prev word
  109.  
  110. static inline _BS_word borrow_lo(const _BS_word a[], int ind, 
  111.                                       int minind, int p)
  112. {
  113.   _BS_word word = a[ind] _BS_RIGHT (BITSTRBITS - 1 - p);
  114.   if (ind > minind)
  115.     word |= (a[ind-1] _BS_LEFT (p + 1));
  116.   return word;
  117. }
  118.  
  119. // same with bounds check (for masks shorter than patterns)
  120.  
  121. static inline _BS_word safe_borrow_hi(const _BS_word a[], int ind, 
  122.                                            int maxind, int p)
  123. {
  124.   if (ind > maxind)
  125.     return 0;
  126.   else if (p == 0)
  127.     return a[ind];
  128.   else if (ind == maxind)
  129.     return a[ind] _BS_LEFT p;
  130.   else
  131.     return (a[ind] _BS_LEFT p) | (a[ind+1] _BS_RIGHT (BITSTRBITS - p));
  132. }
  133.  
  134.  
  135. // allocate a new rep; pad to near a power of two
  136.  
  137. inline static BitStrRep* BSnew(int newlen)
  138. {
  139.   unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(_BS_word) 
  140.     + MALLOC_MIN_OVERHEAD;
  141.   unsigned int allocsiz = MINBitStrRep_SIZE;;
  142.   while (allocsiz < siz) allocsiz <<= 1;
  143.   allocsiz -= MALLOC_MIN_OVERHEAD;
  144.   if (allocsiz >= MAXBitStrRep_SIZE * sizeof(_BS_word))
  145.     (*lib_error_handler)("BitString", "Requested length out of range");
  146.     
  147.   BitStrRep* rep = (BitStrRep *) new char[allocsiz];
  148.   memset(rep, 0, allocsiz);
  149.   rep->sz =
  150.     (allocsiz - sizeof(BitStrRep) + sizeof(_BS_word)) / sizeof(_BS_word);
  151.   return rep;
  152. }
  153.  
  154. inline void
  155. copy_bits (_BS_word* pdst, _BS_size_t dstbit,
  156.        const _BS_word* psrc, _BS_size_t srcbit,
  157.        _BS_size_t length)
  158. {
  159.   _BS_NORMALIZE (pdst, dstbit);
  160.   _BS_NORMALIZE (psrc, srcbit);
  161.   _BS_copy (pdst, dstbit, psrc, srcbit, length);
  162. }
  163.  
  164. BitStrRep* BStr_alloc(BitStrRep* old, const _BS_word* src,
  165.                       int startpos, int endp, int newlen)
  166. {
  167.   if (old == &_nilBitStrRep) old = 0; 
  168.   if (newlen < 0) newlen = 0;
  169.   int news = BitStr_len(newlen);
  170.   BitStrRep* rep;
  171.   if (old == 0 || news > old->sz)
  172.     rep = BSnew(newlen);
  173.   else
  174.     rep = old;
  175.   rep->len = newlen;
  176.  
  177.   if (src != 0 && endp > 0 && (src != rep->s || startpos > 0))
  178.     copy_bits (rep->s, 0, src, startpos, endp - startpos);
  179.  
  180.   check_last(rep);
  181.  
  182.   if (old != rep && old != 0) delete old;
  183.  
  184.   return rep;
  185. }
  186.  
  187. BitStrRep* BStr_resize(BitStrRep* old, int newlen)
  188. {
  189.   BitStrRep* rep;
  190.   if (newlen < 0) newlen = 0;
  191.   int news = BitStr_len(newlen);
  192.   if (old == 0 || old == &_nilBitStrRep)
  193.   {
  194.     rep = BSnew(newlen);
  195.   }
  196.   else if (news > old->sz)
  197.   {
  198.     rep = BSnew(newlen);
  199.     memcpy(rep->s, old->s, BitStr_len(old->len) * sizeof(_BS_word));
  200.     delete old;
  201.   }
  202.   else
  203.     rep = old;
  204.  
  205.   rep->len = newlen;
  206.   check_last(rep);
  207.   return rep;
  208. }
  209.  
  210. BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src)
  211. {
  212.   BitStrRep* rep;
  213.   if (old == src && old != &_nilBitStrRep) return old; 
  214.   if (old == &_nilBitStrRep) old = 0;
  215.   if (src == &_nilBitStrRep) src = 0;
  216.   if (src == 0)
  217.   {
  218.     if (old == 0)
  219.       rep = BSnew(0);
  220.     else
  221.       rep = old;
  222.     rep->len = 0;
  223.   }
  224.   else 
  225.   {
  226.     int newlen = src->len;
  227.     int news = BitStr_len(newlen);
  228.     if (old == 0 || news  > old->sz)
  229.     {
  230.       rep = BSnew(newlen);
  231.       if (old != 0) delete old;
  232.     }
  233.     else
  234.       rep = old;
  235.     
  236.     memcpy(rep->s, src->s, news * sizeof(_BS_word));
  237.     rep->len = newlen;
  238.   }
  239.   check_last(rep);
  240.   return rep;
  241. }
  242.  
  243.  
  244. int operator == (const BitString& x, const BitString& y)
  245. {
  246.   return x.rep->len == y.rep->len && 
  247.     memcmp((void*)x.rep->s, (void*)y.rep->s, 
  248.          BitStr_len(x.rep->len) * sizeof(_BS_word)) == 0;
  249. }
  250.  
  251. int operator <= (const BitString& x, const BitString& y)
  252. {
  253.   unsigned int  xl = x.rep->len;
  254.   unsigned int  yl = y.rep->len;
  255.   if (xl > yl)
  256.     return 0;
  257.  
  258.   const _BS_word* xs = x.rep->s;
  259.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  260.   const _BS_word* ys = y.rep->s;
  261.  
  262.   while (xs < topx)
  263.   {
  264.     _BS_word a = *xs++;
  265.     _BS_word b = *ys++;
  266.     if ((a | b) != b)
  267.       return 0;
  268.   }
  269.   return 1;
  270. }
  271.  
  272. int operator < (const BitString& x, const BitString& y)
  273. {
  274.   unsigned short xl = x.rep->len;
  275.   unsigned short yl = y.rep->len;
  276.   if (xl > yl)
  277.     return 0;
  278.  
  279.   const _BS_word* xs = x.rep->s;
  280.   const _BS_word* ys = y.rep->s;
  281.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  282.   const _BS_word* topy = &(ys[BitStr_len(yl)]);
  283.   int one_diff = 0;
  284.   while (xs < topx)
  285.   {
  286.     _BS_word a = *xs++;
  287.     _BS_word b = *ys++;
  288.     _BS_word c = a | b;
  289.     if (c != b)
  290.       return 0;
  291.     else if (c != a)
  292.       one_diff = 1;
  293.   }
  294.   if (one_diff)
  295.     return 1;
  296.   else
  297.   {
  298.     while (ys < topy)
  299.       if (*ys++ != 0)
  300.         return 1;
  301.     return 0;
  302.   }
  303. }
  304.  
  305. int lcompare(const BitString& x, const BitString& y)
  306. {
  307.   return _BS_lcompare_0 (x.rep->s, x.rep->len, y.rep->s, y.rep->len);
  308. }
  309.  
  310. int BitString::count(unsigned int b) const
  311. {
  312.   int count = _BS_count (rep->s, 0, rep->len);
  313.   if (!b)
  314.     count = rep->len - count;
  315.   return count;
  316. }
  317.  
  318.  
  319. BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r)
  320. {
  321.   r = BStr_copy(r, src);
  322.   _BS_word* rs = r->s;
  323.   _BS_word* topr = &(rs[BitStr_len(r->len)]);
  324.   while (rs < topr)
  325.   {
  326.     _BS_word cmp = ~(*rs);
  327.     *rs++ = cmp;
  328.   }
  329.   check_last(r);
  330.   return r;
  331. }
  332.  
  333.  
  334. BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  335. {
  336.   int xrsame = x == r;
  337.   int yrsame = y == r;
  338.  
  339.   unsigned int  xl = x->len;
  340.   unsigned int  yl = y->len;
  341.   unsigned int  rl = (xl <= yl)? xl : yl;
  342.  
  343.   r = BStr_resize(r, rl);
  344.  
  345.   _BS_word* rs = r->s;
  346.   _BS_word* topr = &(rs[BitStr_len(rl)]);
  347.   const _BS_word* xs = (xrsame)? rs : x->s;
  348.   const _BS_word* ys = (yrsame)? rs : y->s;
  349.  
  350.   while (rs < topr) *rs++ = *xs++ & *ys++;
  351.   check_last(r);
  352.   return r;
  353. }
  354.  
  355. BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  356. {
  357.   unsigned int  xl = x->len;
  358.   unsigned int  yl = y->len;
  359.   unsigned int  rl = (xl >= yl)? xl : yl;
  360.   int xrsame = x == r;
  361.   int yrsame = y == r;
  362.  
  363.   r = BStr_resize(r, rl);
  364.  
  365.   _BS_word*