The Standard C++ Library
When ANSI Committee X3J16 convened in 1989, it planned to at least standardize the C++ library stream classes. At the close of the third meeting in July 1990 the Library Working Group emerged with more specific direction:
1) standardize the stream classes
2) define mechanisms to support language features such as the new and delete operators and exceptions
3) define the relationship between the standard C library and the C++ library and
4) define a standard string class.
The overall charter of any standards committee is to standardize existing practice. It is not feasible, however, for the committee to design a comprehensive object-oriented library. A large group of volunteers cannot accomplish what a small, focused department can (plus the pay is not as good). It would be more reasonable to standardize a small number of popular, low-level classes as building blocks for a wide spectrum of applications. To determine the existing industry practice in development of libraries, in June 1991 I volunteered to review the libraries which a number of vendors had submitted to the committee. All submissions offered at least one string class and a number of container classes, such as lists, vectors, queues, stacks, and sets. Many vendors' libraries also supported bit sets. Now, two years later, the following classes are part of the standard C++ library (in addition to streams and language support):
Class Description string dynamic array of characters wstring dynamic array of wide characters dynarray dynamic array of anything (vector) bits fixed-length bitset bitstring dynamic-length bit string
The string class, which started with contributions from Aron Insinga of Digital, and was completed through the efforts of Uwe Steinmueller of Siemens Nixdorf and Pete Becker at Borland, supports most of C's string.h functionality on dynamically-sized arrays of bytes. Beman Dawes adapted the string class to handle arrays of wide characters, of type wchar_t. (FYI: this is a keyword representing a distinct, overloadable type in C++). Uwe also designed the dynarray class.Chuck Ellison was interested in improving on C's awkward bitwise support, and designed the last two classes. In this article I will discuss the bitstring class.
Bit Sets
C's bitwise operators allow you to process an integer as an ordered set of bits. This ability is useful for system interface operations, which often interpret individual bits as flags. If you want more bits than can fit in an unsigned long, however, you're out of luck. An extended version of such a bit array can come in handy, though.
The first bitset class proposal submitted to X3J16 tried to meet all of these needs with a single class. After much discussion and little agreement among working members, the committee realized that existing practice called for two distinct abstractions: fixed-length bit sets (for a collection of flags, say) and bit strings (i.e., dynamic bit arrays). One year and three committee meetings later, these abstractions became class bits and bitstring, respectively.
Class bitstring
The bitstring class provides much of the same functionality as the string class (see the sidebar "A Simple String Class"). bitstring supports dynamically-sized bit strings with operations such as insert, remove, replace, and concatenate, as well as the basic bit operations — set, reset, test, and toggle Since a bitstring is in fact a string, the bit numbering begins with bit 0 on the left, and increases as you move to the right (this is the reverse of numeric bitfields, which are numbered from right to left). I can now easily implement a picklist by embedding a bitstring:
class Picklist : public Popmenu { bitstring picks; // . . . public: Picklist(.., nitems,..) : picks(0,nitems), .. {} // . . . };When the user highlights the nth entry, I set bit n in the bitstring:
picks.set(n);Member Function Descriptions
This section is a modified excerpt from the official proposal which describes the semantics of each member function. Since the library group is still deciding how to integrate exceptions into the standard library, I just mention them briefly here. The names and uses of exceptions are subject to change. I use assertions in place of exceptions in the implementation . Throughout the rest of this article, the value NPOS, which stands for "not a position," is the largest possible value of type size_t, which is equivalent to (size_t)(-1). A bitstring can hold up to NPOS - 1 bits.
1.0 Constructors
Synopsis
bitstring() bitstring(unsigned long n, size_t nbits) bitstring(const string& s) bitstring(const bitstring& b)1.1 Constructor bitstring()
Description
Creates a bit string of length zero.
1.2 Constructor bitstring(unsigned long n, size_t nbits)
Description
Creates a bit string at least nbits long, initialized with the contents of n. The constructor drops no significant bits, i.e., this->length == max(nbits, N+1), where N is the bit position of the highest-order one bit. The constructor pads the higher order bits with zeroes if necessary, to fill out nbits bits. The common usage of this constructor would be to initialize a bitstring of a certain length with zeroes, e.g.,
bitstring x(0,16);Be aware when using a non-zero value initializer that the bits will be "reversed." For example, the bit pattern for the decimal number 21025 is 0101001000100001, but the output from the following code
bitstring x(21025,16); cout << x << endl;is 1000010001001010.
1.3 Constructor bitstring(const string& s)
Description
Reads bit characters ('1's and '0's) from s and sets the corresponding bits in the new bitstring. The first bit read corresponds to bit 0.
Exceptions
Throws invalid_argument if any character in the string is not a '1' or '0'.
1.4 Constructor bitstring(const bitstring& b)
Description
The usual copy constructor.
2.0 Destructor bitstring()
Description
Frees resources and destroys the object.
3.0 Other Member Functions
3.1 Function string to_string()
Description
Creates a string of '1's and '0's representing the contents of *this. The first (left-most) character is bit 0.
Returns
The temporary string of '1's and '0's.
3.2 Function bitstring& operator=(const bitstring&)
Description
Standard assignment operator.
Returns
A reference to *this.
3.3 Function int operator==(const bitstring&b) const
Description
Compares *this to b for equality. Two bitstrings are equal if and only if they have the same number of bits and their bit patterns are identical.
Returns
Non-zero if the bitsets are equal, zero otherwise.
3.4 Function int operator!=(const bitstring&b) const
Description
Compares *this to b for inequality. Equivalent to !operator==(b);
Returns
Zero if the bitsets are equal, non-zero otherwise.
3.5 Functions set
Synopsis
bitstring& set(size_t n, int val = 1) bitstring& set()Description
These functions set one or more bits. The function set(size_t, int can also reset a bit, depending on the contents of val.
3.5.1 Function bitstring& set (size_t n, int val = 1)
Description
Sets the nth bit if val is non-zero, otherwise resets the bit. Appends a bit if n == length.
Returns
A reference to *this.
Exceptions
Throws out_of_range if n > length.
3.5.2 Function bitstring& set()
Description
Sets all bits,
Returns
A reference to *this.
3.6 Functions reset
Synopsis
bitstring& reset(size_t n) bitstring& reset()Description
These functions reset one or more bits.
3.6.1 Function bitstring& reset(size_t n)
Description
Resets the nth bit. Appends the bit if n == length.
Returns
A reference to *this.
Exceptions
Throws out_of_range if n > length.
3.6.2 Function bitstring& reset()
Description
Resets all bits.
Returns
A reference to *this.
3.7 Functions toggle
Synopsis
bitstring& toggle(size_t n) bitstring& toggle()Description
These functions toggle one or more bits.
3.7.1 Function bitstring& toggle(size_t n)
Description
Toggles the nth bit.
Returns
A reference to *this.
Exceptions
Throws out_of_range if n >= length.
3.7.2 Function bitstring& toggle()
Description
Toggles all bits.
Returns
A reference to *this.
3.8 Function int test(size_t n) const
Description
Tests if bit n is set.
Returns
Non-zero if the bit is set, zero otherwise.
Exceptions
Throws out_of_range if n >= length.
3.9 Function int any() const
Description
Tests if any bits at all are set.
Returns
Zero if all bits are 0, non-zero otherwise.
3.10 Function int none() const
Description
Tests if no bits at all are set. Equivalent to !any.
Returns
One if all bits are 0, non-zero otherwise.
3.11 Function bits operator~() const
Description
Toggles all the bits of a copy of *this.
Returns
A toggled copy of *this.
3.12 Function size_t count() const
Description
Counts the number of bits that are set.
Returns
The number of 1 bits in the string.
3.13 Function bitstring& operator&=(const bitstring&b)
Description
Replaces the current object with the bitwise-AND of b and *this. This function behaves as if the shorter bitstring is filled with zeroes on the right, so the operands of the AND operation will be of equal length. The new length of the object is the maximum of the lengths of the old object and b.
Returns
A reference to *this.
3.14 Function bitstring& operator|=(const bitstring& b)
Description
Replaces the current object with the bitwise-OR of b and *this. This function behaves as if the shorter bitstring is filled with zeroes on the right, so the operands of the XOR operation will be of equal length. The new length of the object is the maximum of the lengths of the old object and b.
Returns
A reference to *this.
3.15 Function bitstring& operator^=(const bitstring& b)
Description
Replaces the current object with the bitwise-XOR of b and *this. This function behaves as if the shorter bitstring is filled with zeroes on the right, so the operands of the XOR operation will be of equal length. The new length of the object is the maximum of the lengths of the old object and b.
Returns
A reference to *this.
3.16 Function bitstring& operator>>=(size_t n)
Description
Modifies the current object by shifting *this right, by n bit positions. If n > length, then this function resets all bits. Shifting "right" by n means that bit n gets the value of bit 0, bit (n+1) gets bit 1, etc. This function resets any vacated bits.
Returns
A reference to *this.
3.17 Function bitstring& operator<<=(size_t n)
Description
Modifies the current object by shifting *this left by n bit positions. if n > length, then this function resets all bits. Shifting "left" by n means that bit 0 receives the value of bit n, bit 1 receives bit (n+1), etc.
Returns
A reference to *this.
3.18 Function bitstring operator>>(const bitstring& b, size_t n) const
Description
Shifts b right by n bit positions. Does not modify b. (See 3.16).
Returns
The shifted result in a temporary bitstring.
3.19 Function bitstring operator<<(const bitstring& b, size_t n) const
Description
Shifts b left by n bit positions. Does not modify b, (See 3.17).
Returns
The shifted result in a temporary bitstring.
3.20 Function bitstring& operator+= (constbitstring& b)
Description
Appends b destructively to *this.
Returns
A reference to *this.
Exceptions
Throws length_error if length >= NPOS - b. length.
3.21 Function bitstring& insert (size_t pos, const bitstring& b)
Description
Inserts b into *this starting at bit position pos. The bits of *this starting at pos follow the inserted copy of b. Appends b if pos == length.
Returns
A reference to *this.
Exceptions
Throws out_of_range if pos > length. Throws length_error if length >= NPOS - b.length.
3.22 Function bitstring& remove(size_t pos, size_t n = NPOS)
Description
Removes up to n bits from *this starting at bit position pos. Truncates, starting at position pos, if length - pos < n.
Returns
A reference to *this.
Exceptions
Throws out_of_range if pos > length.
3.24 Function bitstring&replace(size_t pos, size_t n, const bitstring& b)
Description
Equivalent to a remove followed by a replace in the obvious way. Included for convenience and efficiency.
Returns
A reference to *this.
Exceptions
Throws out_of_range if pos >= length. Throws length_error if the new length would be >= NPOS.
3.25 Function size_t find(int val, size_t pos = 0) const
Description
Searches forward, starting from position pos, for the first occurrence of a 0 bit (if val is zero) or a 1 bit (if val is non-zero).
Returns
The found bit position, if the search was successful, NPOS otherwise.
Exceptions
Throws out_of_range if pos > length.
3.26 Function size_t rfind(int val, size_t pos = NPOS) const
Description
Searches backwards from position pos (or from position length-1 if pos == NPOS) for the first occurrence of a 0 bit (if val is zero) or a 1 bit (if val is nonzero).
Returns
The found bit position, if the search was successful, NPOS otherwise.
Exceptions
Throws out_of_range if pos > length.
3.27 Function bitstring substr(size_t pos, size_t n = NPOS) const
Description
Creates a new bitstring consisting of the bit pattern starting at position pos. This function copies up to n bits or all bits to the end of the string, whichever number is smaller. If pos == length, this function creates an empty bitstring.
Returns
The new bitstring.
Exceptions
Throws out_of_range if pos > length.
3.28 Functions length()
Synopsis
size_t length() size_t length(size_t n, int val = 0)Description
These functions determine and/or modify the length of a bit-string.
3.28.1 Function size_t length() const
Description
Determines the number of bits in the string.
Returns
The number of bits.
3.28.2 Function size_t length(size_t n, int val = 0)
Description
Resizes (i.e., truncates or expands) the object so that this->length == n. If the length increases, this function extends the object on the right with 0s if val == 0, or with 1s otherwise.
Returns
The old length.
3.29 Function bitstring& trim()
Description
Truncates high-order 0 bits. If N is the highest-numbered 1 bit, then this->length becomes N+1.
Returns
A reference to *this.
4.0 Global Functions
4.1 Function ostream& operator<<(ostream& os, const bitstring& b)
Description
Sends the sequence of '1's and '0's corresponding to b to the output stream os.
Returns
A reference to the stream os.
4.2 Function istream& operator>>(istream& is, bitstring& b)
Description
Reads a contiguous sequence of '1's and '0's from a stream into b. Skips whitespace according to is.skipws. The first bit read is bit 0. The first non-whitespace, nonbit character terminates the read and remains in the stream. This function sets is.failbit if the first non-whitespace character is not a '1' or '0'.
Returns
A reference to the stream is.
4.3 Function bitstring operator&(const bitstring& b1, const bitstring& b2)
Description
Computes the bitwise-AND of operands b1 and b2. The length of the result equals the length of the longer operand. This function behaves as if, prior to the operation, the shorter operand was extended with high-order 0 bits until its length equaled that of the longer operand.
Returns
The result of the bitwise-AND in a temporary bitstring.
4.4 Function bitstring operator|(const bitstring& b1, const bitstring& b2)
Description
Computes the bitwise-OR of operands b1 and b2. The length of the result equals the length of the longer operand. This function behaves as if, prior to the operation, the shorter operand was extended with high-order 0 bits until its length equaled that of the longer operand.
Returns
The result of the bitwise-OR in a temporary bitstring.
4.5 Function bitstring operator^(const bitstring& b1, const bitstring& b2)
Des cription
Computes the exclusive-OR of operands b1 and b2. The length of the result equals length of the longer operand. This function behaves as if, prior to the operation, the shorter operand was extended with high-order zero bits until its length equaled that of the longer operand.
Returns
The result of the exclusive-OR in a temporary bitstring.
4.6 Function bitstring operator+(const bitstring& b1, const bitstring& b2)
Description
Appends b non-destructively to *this.
Returns
The result of the concatenation in a temporary bitstring.
Implementation Notes
Following what seems to be the most popular coding style, the class definition specifies the public interface first, followed by the private artifacts of the implementation. Whenever possible, inline functions appear outside the class definition itself. This placement is not possible in the case of the functions word, offset, mask1, and mask0, because they return objects of the private nested type Block. These functions appeared as macros in last month's C version. As private, static member functions, they are available only to other bitstring member functions.
Bits of a bitstring are packed in left-to-right into an array of integral blocks. You can substitute any unsigned type for unsigned int in the line
typedef unsigned int Block;
bitstring b1, b2; // . . . b1 += b2;append b2 to b1. Consider the implementation of operator+= from Listing 5:
bitstring& bitstring::operator+=(const bitstring& b) { assert(nbits_ + b.nbits_ < NPOS); int oldlen = nbits_; length(nbits_ + b.nbits_); for (int i = 0; i < b.nbits_; ++i) (void) set_(oldlen+i,b.test_(i)); return *this; }All this function has to do is resize the object and copy b's bits to the end of the object. If the number of bits in b2 is less than or equal to the number of unused bits in b1's allocated memory, then no memory reallocation is necessary. Whether the array needs to be resized or not, the member function length(size_t) resizes the object; if the array must be resized, it handles that too.The implementation of the global operator+ is now trivial using operator+=:
bitstring operator+(const bitstring& b1, const bitstring& b2) { bitstring b(b1); return b.operator+=(b2); }We can do the same sort of thing for all the binary operators. Being small, the binary operators are good candidates for inlining, and therefore appear in bitstring.h.
A Simple String Class
The standard C++ string class is a low-level class that contains most of the functionality found in the standard C library's string.h. The string class's key advantages are automatic memory management and the syntactic convenience of overloaded operators. Also, under the current definition, a C++ string may also contain embedded null bytes.
I will not publish the entire string class here. I include only the subset needed to implement the bitstring class . Missing from my listing are functions such as insert, remove, replace and comparison operations. This is a straightforward "cloning" implementation, which makes a separate copy whenever one string is constructed from another (as opposed to a reference-counting scheme which copies only when a string is modified — see Chapter 3 of Jim Coplien's Advanced C++). Implementation also do not allow embedded nulls in a string.
Listing 1 String Class Definition and Inline Functions
#if !defined(STRING_HPP) #define STRING_HPP #include <stddef.h> #include <assert.h> class istream; class ostream; const size_t NPOS = (size_t) -1; // "SIZE_T_MAX" class string { public: // Constructors / Destructor string(); string(const string& s); string(const char *s, size_t n = NPOS); ~string(); // Assignment string& operator=(const string& s); // Concatenation string& operator+=(const string& s); friend string operator+(const string& s1, const string& s2); // Predicates friend int operator==(const string&, const string&); friend int operator!=(const string&, const string&); // Subscripting char get_at(size_t pos) const; void put_at(size_t pos, char c); string substr(size_t pos, size_t n = NPOS) const; // Searching size_t find(const string& s, size_t pos = 0) const; size_t find_first_of(const string& s, size_t pos = 0) const; size_t find_first_not_of(const string& s, size_t pos = 0) const; // I/O friend ostream& operator<<(ostream&, const string&); friend istream& operator>>(istream& is, string&); // Miscellaneous size_t length() const; const char *c_str() const; private: char *data; size_t count; // Doesn't include terminating 0 void clone(const char *s, size_t n); }; inline string::string() { *(data = new char[1]) = '\0'; count = 0; } inline string::string(const string& s) { clone(s.data,s.count); } inline string::~string() { delete [] data; } inline string operator+(const string& s1, const string& s2) { string s(s1); return s += s2; } inline char string::get_at(size_t pos) const { assert(pos < count); return data[pos]; } inline size_t string::length() const { return count; } inline const char * string::c_str() const { return data; } #endif // End of File
Listing 2 String Class Implementation
// string.cpp #include <iostream.h> #include <iomanip.h> #include <string.h> #include <assert.h> #include "string.hpp" string::string(const char *s, size_t n) { assert(s); clone(s,n); } string& string::operator=(const string& s) { if (this != &s) { delete [] data; clone(s.data,s.count); } return *this; } string& string::operator+=(const string& s) { assert(count + s.count < NPOS); if (s.count > 0) { int new_count = count + s.count; char *buf = new char[new_count + 1]; memcpy(buf,data,count); memcpy(buf+count,s.data,s.count); buf[new_count] = '\0'; delete [] data; data = buf; count = new_count; } return *this; } size_t string::find(const string& s, size_t pos) const { assert(pos < count); char *p = strstr(data,s.c_str()); if (p) return pos + (p - data); return NPOS; } size_t string::find_first_of(const string& s, size_t pos) const { assert(pos < count); char *p = strpbrk(data+pos,s.data); if (p) return p - data; return NPOS; } size_t string::find_first_not_of(const string& s, size_t pos) const { assert(pos < count); for (size_t i = pos; i < count; ++i) if (strchr(s.data,data[i]) == NULL) return i; return NPOS; } string string::substr(size_t pos, size_t n) const { assert(pos <= count); if (n > count - pos) n = count - pos; if (n > 0) return string(data+pos,n); else return string(); // Empty string } ostream& operator<<(ostream& os, const string& s) { os.write(s.data,s.count); return os; } istream& operator>>(istream& is, string& s) { const size_t BUFSIZ = 256; char buf[BUFSIZ]; is >> setw(BUFSIZ) >> buf; s.clone(buf,strlen(buf)); return is; } void string::put_at(size_t pos, char c) { assert(pos <= count); if (pos < count) data[pos] = c; else { // Append character the lazy way char buf[2]; baf[0] = c; buf[1] = '\0'; operator+=(buf); } } int operator==(const string& s1, const string& s2) { return s1.count == s2.count && memcmp(s1.data,s2.data,s1.count) == 0; } int operator!=(const string& s1, const string& s2) { return s1.count != s2.count || memcmp(s1.data,s2.data,s1.count); } // Private function void string::clone(const char *s, size_t n) { // Assumes "data" needs to be allocated assert(s != NULL); size_t len = strlen(s); count = (n >= len) ? len : n; data = new char[count + 1]; strncpy(data,s,count)[count] = '\0'; } // End of File
Listing 3 Illustrates the String Class
// tstr.cpp: Test the string class #include <iostream.h> #include "string.hpp" main() { size_t pos; string s1("Hello"), s2 = ", there, you fool! ", s3; // Concatenation cout << "s1 + s2 ==" << s1+s2 << endl; s1 += s2; cout << "Now s1 ==" << s1 << endl; // Searching if ((pos = s1.find("o")) != NPOS) cout << "find(\"o\"): " << pos << endl; cout << "s1.substr(4,10) == " << s1.substr(4,10) << endl; if ((pos = s1.find_first_of("abcde")) != NPOS) cout << "find_first_of(abcde): "<< pos << endl; if ((pos = s1.find_first_not_of("abcde")) != NPOS) cout << "find_first_not_of(abcde): " << pos << endl; // Subscripting s3 = "This is a char* constant"; cout << "s3[0] == " << s3.get_at(0) << endl; s3.put_at(3,'3'); s3.put_at(s3.length(),'!'); cout << "Now s3 ==" << s3 << endl; return 0; } /* OUTPUT: s1 + s2 == Hello, there, you fool! Now s1 == Hello, there, you fool! find("o"): 4 s1.substr(4,10) == o, there, find_first_of(abcde): 1 find_first_not_of(abcde): 0 s3[0] == T Now s3 == Thi3 is a char* constant! */ // End of File
Listing 4 Bitstring Class Definition and Inline Functions
// bitstr.h: The C++ bitstring class #if !defined(BITSTR_H) #define BITSTR_H #include <stddef.h> #include <limits.h> #include <assert.h> #include "string.hpp" class istream; class ostream; class bitstring { public: bitstring(); bitstring(unsigned long, size_t); bitstring(const string&); bitstring(const bitstring&); ~bitstring(); // Conversions string to_string() const; // Assignment bitstring& operator=(const bitstring&); // Equality int operator==(const bitstring&) const; int operator!=(const bitstring&) const; // Basic bit operations bitstring& set(size_t, int = 1); bitstring& set(); bitstring& reset(size_t); bitstring& reset(); bitstring& toggle(size_t); bitstring& toggle(); int test(size_t) const; int any() const; int none() const; bitstring operator~() const; size_t count() const; // Bitwise operators bitstring& operator&=(const bitstring&); bitstring& operator|(const bitstring&); bitstring& operator^=(const bitstring&); bitstring& operator>>=(size_t); bitstring& operator<<=(size_t); bitstring operator>>(size_t) const; bitstring operator<<(size_t) const; // String operations bitstring& operator+=(const bitstring&); bitstring& insert(size_t, const bitstring&); bitstring& remove(size_t, size_t); bitstring& replace(size_t, size_t, const bitstring&); size_t find(int, size_t = 0) const; size_t rfind(int, size_t = NPOS) const; bitstring substr(size_t, size_t) const; size_t length() const; size_t length(size_t, int = 0); size_t trim(); private: typedef unsigned int Block; Block *bits_; size_t nbits_; size_t nblks_; Block clean_mask_; enum {BLKSIZ = CHAR_BIT * sizeof(Block)}; static Block word(size_t b) {return b / BLKSIZ;} static Block offset(size_t b) {return BLKSIZ - b%BLKSIZ - 1;} static Block mask1(size_t b) {return Block(1) << offset(b);} static Block mask0(size_t b) {return ~(Block(1) << offset(b));} static size_t nblks(size_t nb) {return (nb+BLKSIZ-1) / BLKSIZ;} void make_clean_mask(); void cleanup(); void set_(size_t); int set_(size_t, int); void reset_(size_t); int test_(size_t) const; void from_string(const string&); void init(size_t); void equalize(bitstring&); friend istream& operator>>(istream&, bitstring&); }; // Global Functions: ostream& operator<<(ostream&, const bitstring&); istream& operator>>(istream&, bitstring&); bitstring operator& (const bitstring&, const bitstring&); bitstring operator|(const bitstring&, const bitstring&); bitstring operator^ (const bitstring&, const bitstring&); bitstring operator+ (const bitstring&, const bitstring&); // Inline publics: inline bitstring::bitstring() { init(0); } inline bitstring::~bitstring() { delete [] bits_; } inline bitstring& bitstring::toggle(size_t pos) { assert(pos < nbits_); bits_[word(pos)] ^= mask1(pos); return *this; } inline int bitstring::test(size_t pos) const { assert(pos < nbits_); return test_(pos); } inline bitstring bitstring::operator~() const { bitstring b(*this); b.toggle(); return b; } inline int bitstring::operator!=(const bitstring& b) const { return !operator==(b); } inline int bitstring::none() const { return !any(); } inline size_t bitstring::length() const { return nbits_; } inline bitstring operator&(const bitstring& x, const bitstring& y) { bitstring b(x); return b &= y; } inline bitstring operator|(const bitstring& x, const bitstring& y) { bitstring b(x); return b |= y; } inline bitstring operator^(const bitstring& x, const bitstring& y) { bitstring b(y); return b ^= x; } inline bitstring bitstring::operator<<(size_t n) const { bitstring r(*this); return r <<= n; } inline bitstring bitstring::operator>>(size_t n) const { bitstring r(*this); return r >>= n; } inline bitstring operator+(const bitstring& b1, const bitstring& b2) { bitstring b(b1); return b.operator+=(b2); } // Inline privates: inline void bitstring::make_cleanmask() { clean_mask = ~Block(0) << (nblks_ * BLKSIZ - nbits_); } inline void bitstring::cleanup() { // Make sure unused bits don't get set if (nbits_ % BLKSIZ) bits_[nblks_ - 1] &= clean_mask; } inline void bitstring::set_(size_t b) { bits_[word(b)] |= mask1(b); } inline void bitstring::reset_(size_t b) { bits_[word(b)] &= mask0(b); } inline int bitstring::test_(size_t b) const { return !!(bits_[word(b)] & maskl(b)); } #endif // End of File
Listing 5 Bitstring Class Implementation
// bitstr.cpp #include <assert.h> #include <iostream.h> #include <string.h> #include "string.hpp" #include "bitstr.h" // Public Functions: bitstring::bitstring(unsigned long val, size_t n) { assert(n < NPOS); // val == 0 is easy... if (val == 0) { init(n); return; } // Find highest significant bit unsigned long temp = val; int high_bit = 0; for (int i = 0; temp; ++i) { if (temp & 1) high_bit = i; temp >>= 1; } // Determine nbits_ and construct nbits_ = high_bit + 1; if (nbits_ < n) nbits_ = n; init(nbits_); // Store bit pattern for (i = 0; i < nbits_; ++i) { if (val & 1) set_(i); val >>= 1; } } bitstring::bitstring(const string& s) { // Validate that s has only 0's and 1's for (int i = 0; i < s.length(); ++i) { char c = s.get_at(i); if (c != '0' && c != '1') break; } assert(i == s.length()); from_string(s); } bitstring::bitstring(const bitstring& b) { init(b.nbits_); memcpy(bits_,b.bits_,nblks_ * sizeof bits_[0]); } string bitstring::to_string() const { char *s = new char[nbits_+1]; for (int i = 0; i < nbits_; ++i) s[i] = '0' +test_(i); s[nbits_] = '\0'; string s2(s); delete [] s; return s2; } bitstring& bitstring::operator=(const bitstring& b) { if (this != &b) { delete [] bits_; init(b.nbits_); memcpy(bits_,b.bits_,nblks_ * sizeof bits_[0]); } return *this; } int bitstring::operator==(const bitstring& b) const { return (nbits_ == b.nbits_) && !memcmp(bits_,b.bits_,nblks_ * sizeof bits_[0]); } bitstring& bitstring::set() { memset(bits_,~0u,nblks_* sizeof bits_[0]); cleanup(); return *this; } bitstring& bitstring::set(size_t pos, int val) { assert(pos <= nbits_); if (pos == nbits_) length(nbits_ + 1); // Append set_(pos,val); return *this; } bitstring& bitstring::reset(size_t pos) { assert(pos <= nbits_); if (pos == nbits_) length(nbits_ + 1); // Append reset_(pos); return *this; } bitstring& bitstring::reset() { memset(bits_,0,nblks_ * sizeof bits_[0]); return *this; } bitstring& bitstring::toggle() { size_t nw = nblks_; while (nw--) bits_[nw] = ~bits_[nw]; cleanup(); return *this; } int bitstring::any() const { for (int i = 0; i < nblks_; ++i) if (bits_[i]) return 1; return 0; } size_t bitstring::count() const { size_t sum = 0; for (int i = 0; i < nbits_; ++i) if (test_(i)) ++sum; return sum; } bitstring& bitstring::operator&=(const bitstring& b) { bitstring rhs(b); equalize(rhs); for (int i = 0; i < nblks_;++i) bits_[i] &= rhs.bits_[i]; return *this; } bitstring& bitstring::operator|=(const bitstring& b) { bitstring rhs(b); equalize(rhs); for (int i = 0; i < nblks_; ++i) bits_[i] |= rhs.bits_[i]; cleanup(); return *this; } bitstring& bitstring::operator^=(const bitstring& b) { bitstring rhs(b); equalize(rhs); for (int i = 0; i < nblks_; ++i) bits_[i] ^= rhs.bits_[i]; cleanup(); return *this; } bitstring& bitstring::operator>>=(size_t n) { if (n >= nbits_) reset(); else { for (int i = nbits_ - 1; i >= n; --i) (void) set_(i,test_(i-n)); for (i = 0; i < n;++i) reset_(i); } return *this; } bitstring& bitstring::operator<<=(size_t n) { if (n >= nbits_) reset(); else { for (int i = 0; i < nbits_ - n; ++i) (void) set_(i,test_(i+n)); for (i = nbits_ - n; i < nbits_; ++i) reset_(i); } return *this; } bitstring& bitstring::operator+=(const bitstring& b) { assert(nbits_ + b.nbits_ < NPOS); int oldlen = nbits_; length(nbits_ + b.nbits_); for (int i = 0; i < b.nbits_; ++i) (void) set_(oldlen+i,b.test_(i)); return *this; } bitstring& bitstring::insert(size_t pos, const bitstring& b) { assert(pos <= nbits_); size_t oldlen = nbits_; size_t newlen = nbits_ + b.nbits_; // Grow to accommodate insertion length(newlen); // Move tail to right for (int i = 0; i < oldlen - pos;++i) set_(newlen-i-1,test_(oldlen-i-1)); // Replicate b in between for (i = 0; i < b.nbits_;++i) set_(pos+i,b.test_(i)); return *this; } bitstring& bitstring::remove(size_t pos, size_t n) { assert(pos < nbits_); if (n > nbits_ - pos) n = nbits_ - pos; // Slide tail down to cover gap for (int i = 0; i < nbits_ - pos - n; ++i) set_(pos+i,test_(pos+n+i)); // Shrink length(nbits_ - n); return *this; } bitstring& bitstring::replace(size_t pos, size_t n, const bitstring& b) { assert(pos <= nbits_); if (n > nbits_ - pos) n = nbits_ - pos; size_t oldlen= nbits_; size_t newlen = oldlen - n + b.nbits_; int diff = newlen - oldlen; // Adjust length and move tail as needed if (diff > 0) { // Grow length(newlen); for (int i = oldlen - 1; i >= pos + n; --i) (void) set_(i+diff,test_(i)); } else if (diff < 0) { // Shrink for (int i = pos + n; i < oldlen; ++i) (void) set_(i+diff,test_(i)); length(newlen); } // Copy b into place for (int i = 0; i < b.nbits_;++i) (void) set_(pos+i,b.test_(i)); return *this; } size_t bitstring::find(int val, size_t pos) const { assert(pos < nbits_); for (size_t i = pos; i < nbits_; ++i) { int t = test_(i); if (val && t || !val && !t) return i; } return NPOS; } size_t bitstring::rfind(int val, size_t pos) const { assert(pos < nbits_); for (int i = pos; i >= 0; --i) { int t = test_(i); if (val && t || !val && !t) return i; } return NPOS; } bitstring bitstring::substr(size_t pos, size_t n) const { assert(pos <= nbits_); if (n > nbits_ - pos) n = nbits_ - pos; bitstring b(0,n); for (int i = 0; i < n; ++i) b.set_(i,test_(pos + i)); return b; } size_t bitstring::length(size_t n, int val) { size_t oldlen = nbits_; size_t nw1 = nblks_; size_t nw2 = nblks(n); // Alter the size of a bitstring if (nw1 != nw2) { Block *newbits = new Block[nw2]; for (int i = 0; i < nwl && i < nw2; ++i) newbits[i] = bits_[i]; delete [] bits_; bits_ = newbits; for (i = nw1; i < nw2;++i) bits_[i] = val ? ~Block(0) : Block(0); nblks_ = nw2; } nbits_ = n; make_clean_mask(); cleanup(); return oldlen; } size_t bitstring::trim() { for (int i = nbits_ - 1; i >= 0; --i) if (test_(i)) break; size_t newlen = i + 1; length(newlen); return newlen; } ostream& operator<<(ostream& os, const bitstring& b) { os << b.to_string(); return os; } istream& operator>>(istream& is, bitstring& b) { const size_t N = 256; char *buf = new char[N]; char c; // Consume bit characters is >> ws; for (int i = 0; i < N && is.get(c); ++i) { if (c == '0' || c == '1') buf[i] = c; else { is.putback(c); break; } } buf[i] = '\0'; if (i == 0) is.clear(ios::failbit); else { delete [] b.bits_; b.from_string(string(buf)); } delete buf; return is; } // Private Functions: int bitstring::set_(size_t n, int val) { if (val) set_(n); else reset_(n); return !!val; } void bitstring::from_string(const string& s) { // Assumes string contains only 0's and 1's init(s.length()); for (int i = 0; i < s.length(); ++i) if (s.get_at(i) == '1') set_(i); } void bitstring::init(size_t n) { nbits_ = n; nblks_ = nblks(n); if (n > 0) bits_ = new Block[nblks_]; else bits_ = 0; memset(bits_,0,nblks_ * sizeof bits_[0]); make_clean_mask(); } void bitstring::equalize(bitstring& b) { // Make the smaller the size of the larger if (b.nbits_ < nbits_) b.length(nbits_); else if (nbits_ < b.nbits_) length(b.nbits_); } // End of File
Listing 6 Illustrates the Bitstring Class
// tbitstr.cpp - Test the bitstring class #include <iostream.h> #(include "bitstr.h" #include "string.hpp" main() { bitstring x(21537,4), y(string("10110")); cout << "Initial x: " << x << endl; cout << "Initial y: " << y << endl; for (int i = 0; i <= 5; ++i) x.set(i); cout << "x: "<< x << " (" << x.count() <<" bits set)" << endl; cout << "x == 21567?" << (x == bitstring(21567,x.length())) << endl; cout << "x >>= 6 = " << (x >>= 6) << endl; cout << "x <<= 6 = " << (x <<= 6) << endl; cout << "x ^ 3 = " << (x ^ bitstring(3,2)) << endl; cout << "x | 3 = " << (x | bitstring(3,2)) << endl; cout << "x & 3 = " << (x & bitstring(3,2)) << endl; cout << "3 & x = " << (bitstring(3,2) & x) << endl; cout << "~x = " << (~x) << endl; cout << "y &= x = " << (y &= x) << endl; cout << "y ^= x = " << (y ^= x) << endl; cout << "y |= x = " << (y |= x) << endl; y.length(20); y.reset(); for (i = 4; i <= 12; ++i) y.set(i); cout << "y: "<< y << " (" << y.count() <<" bits set)" << endl; cout << "x & y = " << (x & y) << endl; cout << "x | y = " << (x | y) << endl; cout << "x ^ y = " << (x ^ y) << endl; cout << "x != y? " << (x != y) << endl; cout <<"x + y = " << x+y << endl; x += y; cout << "after x+= y: "<< x << endl; x.trim(); cout << "after x.trim(): "<< x << endl; return 0; } /* OUTPUT: Initial x: 100001000010101 Initial y: 10110 x: 111111000010101 (9 bits set) x == 21567? 1 x >>= 6 = 000000111111000 x <<= 6 = 111111000000000 x ^ 3 = 001111000000000 x | 3 = 111111000000000 x & 3 = 110000000000000 3 & x = 110000000000000 ~x = 000000111111111 y &= x = 101100000000000 y ^= x = 010011000000000 y |= x = 111111000000000 y: 00001111111110000000 (9 bits set) x & y = 00001100000000000000 x | y = 11111111111110000000 x ^ y = 11110011111110000000 x != y? 1 x + y = 11111100000000000001111111110000000 after x += y: 11111100000000000001111111110000000 after x.trim(): 1111110000000000000111111111 */
