Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
dynamicbitset/ds.DynamicBitset.h
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
382 lines (346 sloc)
11 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* File: DynamicBitset.h | |
* Author: saad | |
* | |
* Created on October 13, 2014, 1:00 AM | |
*/ | |
#ifndef DYNAMICBITSET_H | |
#define DYNAMICBITSET_H | |
#include "common.h" | |
#include "test.this.module.h" | |
#include <string> | |
#include <cassert> | |
#include <sstream> | |
#include <bitset> | |
#include <cstring> | |
#include <string> | |
#include <iostream> | |
namespace yasi{ | |
namespace ds{ | |
class DynamicBitset { | |
FRIEND_TEST_CLASS(DynamicBitsetTest); | |
friend class IsDynamicBitsetZeroFunction; | |
typedef DynamicBitset self; | |
typedef unsigned char byte; | |
byte* data; | |
public: | |
int numBits; | |
int numBytes; | |
// resizes current storage to the specified number of bits | |
// initializes all bits to zero | |
void init(int nBits = 0){ | |
if(numBits != nBits){ | |
numBits = nBits; | |
numBytes = (nBits % 8 == 0) ? nBits / 8 : nBits / 8 + 1; | |
DELETE_ARR_SAFE(data); | |
if(numBytes > 0){ | |
data = new byte[numBytes]; | |
} | |
} | |
if(numBytes > 0){ | |
memset(data, 0, numBytes); | |
} | |
} | |
// resizes current storage to match the array-size of the supplied argument | |
// copies all bits from the supplied reference | |
void init(const DynamicBitset& other) { | |
init(other.numBits); | |
if(numBytes > 0){ | |
memcpy(data, other.data, numBytes); | |
} | |
} | |
DynamicBitset(int nBits = 0) | |
{ | |
numBits = 0; | |
numBytes = 0; | |
data = NULL; | |
init(nBits); | |
} | |
DynamicBitset(const DynamicBitset& other) | |
{ | |
numBits = 0; | |
numBytes = 0; | |
data = NULL; | |
init(other); | |
} | |
void setBit(const int index, bool value) const{ | |
ASSERT(numBytes > 0); | |
ASSERT(index >= 0); | |
ASSERT(index < numBits); | |
byte mask = 0x80; // 10000000b | |
const int chunkSize = 8; // number of bits in a byte | |
// move 1 do desired bit position inside the actual byte | |
mask >>= (index % chunkSize); | |
// now set value | |
if (value == 1){ | |
data[index / chunkSize] |= mask; | |
} | |
else{ | |
int notMask = ~mask; | |
data[index / chunkSize] &= ~mask; | |
} | |
} | |
bool getBit(const int index) const{ | |
ASSERT(numBytes > 0); | |
ASSERT(index >= 0 && index < numBits); | |
byte mask = 0x80; // 10000000b | |
const int chunkSize = 8; // bits in a byte | |
// move 1 do desired bit position inside the actual byte | |
mask >>= (index % chunkSize); | |
// now get value | |
int bit = ((data[index / chunkSize] & mask) == 0) ? 0 : 1; | |
return bit; | |
} | |
// sets the upper-order bytes of value as key | |
// currently works only with int | |
void setData(const int upperOrderBitsValue) const{ | |
ASSERT(numBytes > 0); | |
ASSERT(numBytes <= sizeof(int)); | |
clear(); | |
// key-bits are right aligned | |
// since lower-order bits of value is valid, | |
// shift value-bits appropriately to the left | |
int numShift = sizeof(int) * 8 - numBits; | |
// clear left-most trailing unnecessary bits | |
int tempValue = upperOrderBitsValue >> numShift; | |
// now right-align the bits for semantic consistency | |
tempValue <<= numShift; | |
// copy from the rightmost byte, and right-shift repeatedly | |
for (int i = 0; i < numBytes; i++){ | |
byte b = (tempValue & 0xFF000000) >> 24; // leftmost byte of the value | |
data[i] = b; | |
tempValue <<= 8; // next byte | |
} | |
} | |
bool operator==(const DynamicBitset& other) const{ | |
if (numBytes != other.numBytes) | |
return false; | |
else if(numBytes > 0) | |
return memcmp(data, other.data, numBytes) == 0; | |
else | |
return true; | |
} | |
DynamicBitset& operator=(const DynamicBitset& other) { | |
// 0-bit keys are allowed to be re-initialized | |
// but all other keys must match their numBits | |
if(numBits != 0){ | |
ASSERT(numBits == other.numBits); | |
memcpy(data, other.data, numBytes); | |
} | |
else if(other.numBits > 0){ | |
// reinitialize a zero-bit key | |
init(other); | |
} | |
return *this; | |
} | |
// bits are left-aligned. | |
// like elements in an array | |
// bit-index goes from left to right | |
int toInt() const{ | |
if(numBytes == 0) return 0; | |
ASSERT(numBytes <= sizeof(int)); | |
int n = 0; | |
for (int i = 0; i < numBytes; i++){ | |
int b = (int)data[i]; | |
n |= (b << ((3 - i) * 8)); | |
} | |
return n; | |
} | |
void clear() const{ | |
if (data) | |
memset(data, 0, numBytes); | |
} | |
virtual ~DynamicBitset(){ | |
DELETE_ARR_SAFE(data); | |
} | |
std::string toString() const{ | |
if(numBytes == 0) return ""; | |
std::stringstream stream; | |
for (int i = 0; i < numBytes; i++){ | |
if (numBits % 8 && | |
i == numBytes - 1){ | |
// last byte, partially filled | |
for (int j = i * 8; j < numBits; j++){ | |
stream << this->getBit(j); | |
} | |
} | |
else{ | |
std::bitset<8> bits(data[i]); | |
stream << bits; | |
} | |
} | |
return stream.str(); | |
} | |
// compare bits as if they are in an array | |
inline bool operator< (const self& other) const { | |
ASSERT(numBytes == other.numBytes); | |
if(numBytes == 0) return true; | |
if(other.numBytes == 0) return false; | |
bool bEqual = true; | |
for(int i = 0; i < numBytes; i++){ | |
byte me = data[i]; | |
byte you = other.data[i]; | |
if( me > you) | |
return false; | |
else | |
bEqual &= (me == you); | |
} | |
if( bEqual ) | |
return false; | |
else | |
return true; | |
} | |
inline bool operator<= (const self& other) const { | |
if(numBytes == 0) return true; | |
if(other.numBytes == 0) return false; | |
ASSERT(numBytes == other.numBytes); | |
for(int i = 0; i < numBytes; i++){ | |
if(data[i] > other.data[i]) return false; | |
} | |
return true; | |
} | |
inline bool operator> (const self& other) const { | |
if(numBytes == 0) return false; | |
if(other.numBytes == 0) return true; | |
ASSERT(numBytes == other.numBytes); | |
return ! (*this <= other); | |
} | |
inline bool operator>= (const self& other) const { | |
if(other.numBytes == 0) return true; | |
if(numBytes == 0) return false; | |
ASSERT(numBytes == other.numBytes); | |
return ! (*this < other); | |
} | |
inline bool operator!=(const self& other) const { | |
ASSERT(numBytes == other.numBytes); | |
if(numBytes == 0) return false; | |
return !((*this) == other); | |
} | |
unsigned char getByte(int i) const{ | |
ASSERT(i >= 0); | |
ASSERT(i < numBytes); | |
return data[i]; | |
} | |
// returns the original ptr to the data | |
const unsigned char* toCharPtr() const{ | |
return this->data; | |
} | |
// returns true if all bits are 1 | |
bool all() const{ | |
if(numBytes == 0) return false; | |
bool result = true; | |
for (int i = 0; i < numBytes; i++){ | |
byte mask = 0xFF; | |
if (i == numBytes - 1 && | |
numBits % 8 ){ | |
// last byte, partially filled | |
int numRemainingBits = numBits % 8; | |
mask <<= (8-numRemainingBits); | |
if((data[i] & mask) != mask) { | |
// not all bits are 1 | |
// and this is the last byte | |
return false; | |
} | |
} | |
else{ | |
// not an incomplete byte | |
if((data[i] & mask) != mask){ | |
// not all bits are 1 | |
return false; | |
} | |
} | |
} | |
return result; | |
} | |
// returns true if any bit is 1 | |
bool any() const{ | |
if(numBytes == 0) return false; | |
bool result = false; | |
for (int i = 0; i < numBytes; i++){ | |
byte mask = (byte) 0xFF; | |
if (i == numBytes - 1 && | |
numBits % 8 ){ | |
// last byte, partially filled | |
int numRemainingBits = numBits % 8; | |
mask <<= (8-numRemainingBits); | |
if((data[i] & mask) != 0) { | |
// not all bits are zero | |
// and this is the last byte | |
return true; | |
} | |
} | |
else{ | |
// not an incomplete byte | |
if((data[i] & mask) != 0){ | |
// not all bits are 0 | |
return true; | |
} | |
} | |
} | |
return result; | |
} | |
// | |
void flipBit(const int index) { | |
ASSERT(numBytes > 0); | |
ASSERT(index >= 0); | |
ASSERT(index < numBits); | |
byte mask = 0x80; // 10000000b | |
const int chunkSize = 8; // number of bits in a byte | |
// move 1 do desired bit position inside the actual byte | |
mask >>= (index % chunkSize); | |
// flip by xor | |
data[index / chunkSize] ^= mask; | |
} | |
void flip() { | |
if(numBytes == 0) return; | |
for (int i = 0; i < numBytes; i++){ | |
int mask = 0xFF; | |
if (i == numBytes - 1 && | |
numBits % 8 ){ | |
// last byte, partially filled | |
// fix mask | |
int numRemainingBits = numBits % 8; | |
mask <<= (8-numRemainingBits); | |
} | |
// flip this byte by xor with mask | |
data[i] ^= 0xFF; | |
} | |
} | |
// initializes all bits to zero | |
void reset(){ | |
if(numBytes > 0){ | |
memset(data, 0, numBytes); | |
} | |
} | |
private: | |
}; | |
// override for printing | |
std::ostream& operator<< (std::ostream& out, const yasi::ds::DynamicBitset& k); | |
std::ostream& operator<< (std::ostream& out, yasi::ds::DynamicBitset& k); | |
// functional object telling whether a bitset represents empty/NULL | |
class IsDynamicBitsetZeroFunction{ | |
public: | |
bool operator()(const yasi::ds::DynamicBitset& key) const{ | |
return key.numBits == 0 || key.numBytes == 0 || key.data == NULL; | |
} | |
}; | |
class DynamicBitsetHashFunction { | |
public: | |
virtual int operator()(const yasi::ds::DynamicBitset& k) const override{ | |
int hashedInt = 0; | |
for(int i = 0; i < k.numBytes; i++){ | |
// for each byte | |
int nextByte = (int) k.getByte(i); | |
hashedInt |= (nextByte << (8 * i)); | |
} | |
hashedInt ^= (~hashedInt << 11) ^ (hashedInt << 3) ^ (~hashedInt << 27); | |
// unsigned int n = (unsigned int )k.toInt(); | |
// int hashedInt = n ^ (~n << 11) ^ (n << 3) ^ (~n << 27); | |
// the key is already hashed | |
// unsigned int hashedInt = n >> (32 - k.numBits); // push the valid bits to the end | |
return hashedInt; | |
} | |
}; | |
} // namespace ds | |
} // namespace yasi | |
#endif /* DYNAMICBITSET_H */ | |