Re: [boost] Dynamic sized bitset

From: Chuck Allison (cda_at_[hidden])
Date: 2001-12-11 13:32:36

The original bitstring class overloaded += to append a bit to the container.
I don't have dyn_bitset with me to check it right now, but that's a
reasonable addition if it doesn't support it. += was removed (along with
many other methods) when bitstring was shoehorned into STL as vector<bool>.
All are candidates for dyn_bitset.

----- Original Message -----
From: "Cliff Green" <cliffg_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, December 11, 2001 1:38 AM
Subject: RE: [boost] Dynamic sized bitset

> It seems like there's some kind of Boost karma at work - every time I have
> something I think is worthy of consideration someone contributes something
> similar (and usually better). :)
>
> I've developed and used (extensively) a class for a variable sized buffer
of
> bits that has additional (useful, IMO) functionality above and beyond
> vector<bool>, bitset, and the proposed dyn_bitset. What I've needed (and
> what my class provides) is:
>
> 1. A dynamically sized container of bits, with the size not known in
advance
> (i.e. bits are pushed on the container depending on dynamic run-time
logic).
> 2. A simple mechanism to convert this container to a buffer of unsigned
> chars, and the converse (the buffer, char type, etc is a template policy
in
> my class).
> 3. Simple "get" and "append" methods to get or append bits to / from
> unsigned integral types (typically fundamental types, but could also be
> classes that meet the concepts / requirements).
> 4. The usual bit access / manipulation that vector<bool> provides, and a
few
> that bitset provides but vector<bool> does not (e.g. "flip" a specified
> bit).
>
> I've used this in code interacting with very bit-oriented or
> space-constrained protocols, such as wireless protocols or low-bandwidth
> device interfaces. Frequently the bits contained in the container are
> dependent on previous bits - e.g. a bit specifying whether a field is
> present or not, or dynamic sized buffers embedded within the full message.
> Even a buffer length field may be variable in size - e.g. if size < 128,
> length field is 8 bits, else 8th bit set ("overflow bit") and length field
> is 16 bits total, and so on.
>
> Requirement 2 is simply there to provide a way to send / receive or read /
> write this bit buffer to a network or disk.
>
> The main limitations (for my needs) of the existing std lib classes (and
the
> proposed dyn_bitset) are:
>
> 1. vector<bool> does not meet my needs for requirements 2 and 3, and part
of
> 4.
> 2. bitset does not meet my needs for requirements 1 through 3.
> 3. dyn_bitset does not meet my needs for requirements 1 through 3,
although
> 1 would not be an issue if the final / complete size was pre-computed
> (dynamically) before actually creating the bit container and setting the
> bits.
>
> Note that my requirement 2 is addressed in Herb Sutter's GOTW #72,
although
> I had written my original version before he published #72 (I ended up
> re-writing my implementation based on Herb's solution, after he published
it
> on the web).
>
> I'll be happy to post my complete code, but let me boil out the
fundamental
> interface, since that is what I'm most concerned with. And obviously, the
> bigger question is whether my additional functionality (requirements 2 and
> 3) are general or useful enough to be worthy of Boost submission, or (what
I
> think would be a better solution) adding to dyn_bitset.
>
> There are two template policies:
>
> 1. Storage policy - this defaults to vector<bool>, but is the underlying
> container storing the bits. The basic requirements on the storage policy
> class are default construction, size() method, push_back, and operator[]
> (both const and non-const versions).
> 2. Binary Buffer policy - this defaults to std::basic_string<unsigned
char>,
> but could be any container capable of storing unsigned chars and
supporting
> default construction, size(), push_back, operator&, operator[] (both
> versions), and a contiguous data buffer. Standards-wise, basic_string does
> not guarantee the contiguous data buffer, so it's probably better to
> disallow that class. There are numerous other available classes that would
> work, including vector<unsigned char>, or Andrei's Typed Buffer class, or
> the requirements / logic of the binary buffer interface could be changed
to
> allow basic_string.
>
> There are various construction and get / append interfaces to stream in /
> out the binary buffer. For example, assume the template class is named
> BitBuffer, and the binary buffer is of type BinBuf:
>
>    BitBuffer (BinBuf const& buf, size_t numBits) : mBits() {
> appendBinaryBuf(buf, numBits); }
>    void appendBinaryBuf( BinBuf const& buf, size_t numBits);
>    BinBuf const getBinaryBuf() const { return getBinaryBuf(0, size()); }
>    BinBuf const getBinaryBuf(size_t startBit, size_t numBits) const;
>
> For dyn_bitset, it probably doesn't make sense to have either template
> policy (as in my class design), but instead maybe provide binary buffer
> streaming in / out solely through template member functions. The storage
> policy could also be implicit in the dyn_bitset, or through the allocator
as
> it appears to be in the proposed interface.
>
> The get / append for unsigned integral types are template member
functions,
> such as:
>
>    template <typename T>
>      void appendVal (T val, size_t numBits);
>    template <typename T>
>     T getVal (size_t startBit, size_t numBits) const;
>
> The requirements for the unsigned integral type include the usual
suspects -
> bit shift, mod, divide by 2, etc. I'll be happy to share my
implementation,
> but I'm sure there are more efficient / elegant / less restrictive
solutions
> available.
>
> Everything in the bit container is considered to be Most Significant Bit
> first, so the "appendVal" and "getVal" template member functions have
> corresponding logic.
>
> Comments? I'd love to be able to use dyn_bitset and get rid of my existing
> utility class / functions ... I was considering a re-write of my class,
> including adding lots of Boost concepts checking and re-thinking the way I
> have my template policy classes defined, but would rather put this effort
> into something that might get wider usage, and / or synchronize with
> existing efforts.
>
> Cliff
>
>
> Info: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>