Created
July 6, 2010 10:37
-
-
Save raalkml/465236 to your computer and use it in GitHub Desktop.
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
| // | |
| // A template for a dynamically reallocated bitmap of unsigned values, each | |
| // the given number of bits long. An array of bit(s)-sized elements. | |
| // The remainder of division of sizeof(unsigned) by elem_size must be 0 (to | |
| // simplify code and avoid operations on split elements of bitarray::bits). | |
| // The place of bits pointer is reused to minimize initial allocations. | |
| // | |
| #ifndef _BITARRAY_HPP_ | |
| #define _BITARRAY_HPP_ | |
| #include <string.h> | |
| #include <stdlib.h> | |
| // The type T must be an integer castable to from unsigned int. | |
| // elem_size must be one of 1, 2, 4, 8, or 16 for 32bit platforms | |
| // (and only up to 32 on 64bit platforms). | |
| // The bitarray is initialized with 0. | |
| template<typename T, const int elem_size> | |
| class bitarray | |
| { | |
| public: | |
| bitarray(); | |
| bitarray(unsigned reserve); | |
| bitarray(const bitarray<T,elem_size> &); | |
| bitarray<T,elem_size> &operator=(const bitarray<T,elem_size> &); | |
| ~bitarray(); | |
| // Preallocate the amount of elements | |
| void reserve(unsigned amount); | |
| // Remove allocated area and reset all elements to 0 | |
| void reset(); | |
| T get(unsigned pos) const; | |
| void set(unsigned pos, const T); | |
| // number of elements available in this array without reallocation | |
| unsigned available() const { return size * sizeof(unsigned) * 8 / elem_size; } | |
| private: | |
| unsigned size; | |
| union | |
| { | |
| // used when the elements do not fit in reserved anymore | |
| unsigned *bits; | |
| // the initial data storage | |
| unsigned reserved[sizeof(unsigned *)/sizeof(unsigned)]; | |
| }; | |
| unsigned reserved_size() const | |
| { | |
| return sizeof(reserved) / sizeof(*reserved); | |
| } | |
| const unsigned *data() const | |
| { | |
| return size > sizeof(reserved) / sizeof(*reserved) ? bits: reserved; | |
| } | |
| unsigned *data() | |
| { | |
| return size > sizeof(reserved) / sizeof(*reserved) ? bits: reserved; | |
| } | |
| }; | |
| template<typename T, const int elem_size> inline | |
| bitarray<T, elem_size>::bitarray() | |
| { | |
| size = reserved_size(); | |
| memset(reserved, 0, sizeof(reserved)); | |
| } | |
| template<typename T, const int elem_size> inline | |
| bitarray<T, elem_size>::bitarray(unsigned amount) | |
| { | |
| size = reserved_size(); | |
| memset(reserved, 0, sizeof(reserved)); | |
| reserve(amount); | |
| } | |
| template<typename T, const int elem_size> inline | |
| bitarray<T, elem_size>::~bitarray() | |
| { | |
| if (size > reserved_size()) | |
| free(bits); | |
| } | |
| template<typename T, const int elem_size> inline | |
| bitarray<T, elem_size>::bitarray(const bitarray<T, elem_size> &o) | |
| { | |
| if (o.size > reserved_size()) | |
| bits = (unsigned *)malloc(o.size * sizeof(unsigned)); | |
| size = o.size; | |
| memcpy(data(), o.data(), o.size * sizeof(unsigned)); | |
| } | |
| template<typename T, const int elem_size> inline | |
| bitarray<T,elem_size> &bitarray<T,elem_size>::operator=(const bitarray<T,elem_size> &o) | |
| { | |
| if (&o != this) | |
| { | |
| reset(); | |
| reserve(o.available()); | |
| memcpy(data(), o.data(), o.size * sizeof(unsigned)); | |
| } | |
| return *this; | |
| } | |
| template<typename T, const int elem_size> inline | |
| void bitarray<T, elem_size>::reserve(unsigned amount) | |
| { | |
| // number of 8bit _bytes_ needed to store amount bits | |
| amount = (amount * elem_size + sizeof(*reserved) * 8u) / 8u; | |
| if (amount / sizeof(*reserved) <= size) | |
| return; | |
| if (size > reserved_size()) | |
| bits = (unsigned *)realloc(bits, amount); | |
| else | |
| { | |
| unsigned *newbits = (unsigned *)malloc(amount); | |
| memcpy(newbits, reserved, size * sizeof(*reserved)); | |
| bits = newbits; | |
| } | |
| memset(bits + size, 0, amount - size * sizeof(*reserved)); | |
| size = amount / sizeof(*reserved); | |
| } | |
| template<typename T, const int elem_size> inline | |
| T bitarray<T, elem_size>::get(unsigned pos) const | |
| { | |
| const unsigned bitsize1 = sizeof(*reserved) * 8u; | |
| const unsigned *e; | |
| unsigned i; | |
| pos *= elem_size; | |
| i = pos / bitsize1; | |
| if (i > size) | |
| return (T)0; | |
| e = data() + i; | |
| return (T)((*e >> (pos - i * bitsize1)) & ~(~0u << elem_size)); | |
| } | |
| template<typename T, const int elem_size> inline | |
| void bitarray<T, elem_size>::set(unsigned pos, T value) | |
| { | |
| const unsigned bitsize1 = sizeof(*reserved) * 8u; | |
| const unsigned mask = ~(~0u << elem_size); | |
| unsigned *e, i; | |
| reserve(pos + 1); | |
| pos *= elem_size; | |
| i = pos / bitsize1; | |
| pos -= i * bitsize1; | |
| e = data() + i; | |
| *e &= ~(mask << pos); | |
| *e |= (value & mask) << pos; | |
| } | |
| template<typename T, const int elem_size> inline | |
| void bitarray<T, elem_size>::reset() | |
| { | |
| if (size > reserved_size()) | |
| free(bits); | |
| size = reserved_size(); | |
| memset(reserved, 0, sizeof(reserved)); | |
| } | |
| #endif // _BITARRAY_HPP_ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment