@@ -0,0 +1,417 @@
#pragma once
#pragma warning(push)
#pragma warning(disable:4996)
#include < cassert>
#include < memory>
#include < vector>
template <typename T>
class compact_vector
{
std::vector<std::unique_ptr<T[]>> index_block; // Points to data blocks.
// When we deallocate, we keep the last block around so we can reuse it.
// This is required to get O(1) push/pop. Could leave it in index_block instead,
// and store a bit to indicate this. Tracking it separately makes things cleaner.
std::unique_ptr<T[]> spare_empty_db;
unsigned int num_elems;
unsigned int num_elems_in_last_data_block;
// Super blocks have no physical representation, but tracking which one we're in
// allows us to compute the size of data blocks easily.
unsigned int num_super_blocks;
// We could compute the number of DBs in all SBs, like in 'locate_data_block_and_elem',
// and compute this next value as needed by subtracting from that index_block.size().
// However, this is reasonably expensive, so we'll just track it as we go instead.
unsigned int num_dbs_in_last_sb;
// How many data blocks fit in a super block
__forceinline static unsigned int super_block_size (unsigned int super_block_index)
{
return 1 << (super_block_index/2 );
}
// How many elements fit in a data block for a super block
__forceinline static unsigned int data_block_size (unsigned int super_block_index)
{
return 1 << ((super_block_index+1 )/2 );
}
// Compute the block index and element index within that block for a given "virtual" index.
// __forceinline static void locate_data_block_and_elem2(unsigned int i, unsigned int& element_within_block, unsigned int& data_block_index)
// {
// const long r = i+1;
// unsigned long super_block_index;
// _BitScanReverse(&super_block_index, r);
//
// unsigned int num_data_blocks_before_super_block = 2 * ((1 << (super_block_index/2))-1);
// if ( super_block_index&1 )
// {
// num_data_blocks_before_super_block += 1 << (super_block_index/2);
// }
// const unsigned int e_bit_count = (super_block_index+1)/2;
// // the data block index within the superblock
// element_within_block = r & ((1 << e_bit_count) - 1);
// long r_msb_cleared = r;
// _bittestandreset( &r_msb_cleared, super_block_index);
// const unsigned int block_index_within_super_block = r_msb_cleared >> e_bit_count;
//
//
// data_block_index = num_data_blocks_before_super_block + block_index_within_super_block;
// }
__forceinline static void locate_data_block_and_elem (unsigned int i, unsigned int & element_within_block, unsigned int & data_block_index)
{
int r = i+1 ;
unsigned long k;
_BitScanReverse (&k, r);
// There's some intentional redundancy in these two branches
// Ends up slightly faster this way.
if (k & 1 )
{
const int floorKO2 = k / 2 ;
const int ceilKO2 = floorKO2 + 1 ;
const int powFloorKO2 = (1 << floorKO2);
const int p = 2 * (powFloorKO2 - 1 );
const int b = (r >> ceilKO2) & (powFloorKO2 - 1 );
element_within_block = r & ((1 << ceilKO2) - 1 );
data_block_index = p+powFloorKO2+b;
}
else
{
const int floorKO2 = k / 2 ;
const int powFloorKO2 = (1 << floorKO2);
const int p = 2 * (powFloorKO2 - 1 );
const int b = (r >> floorKO2) & (powFloorKO2 - 1 );
element_within_block = r & (powFloorKO2 - 1 );
data_block_index = p+b;
}
}
__forceinline void allocate_data_block ()
{
if (spare_empty_db)
{
index_block.push_back (std::move (spare_empty_db));
}
else
{
index_block.emplace_back (new T[data_block_size (num_super_blocks-1 )]);
}
}
// Reserves space for one more element
__forceinline void grow ()
{
// Treat the very first allocation specially.
// This is so we don't have to keep checking for this special case in the two
// size calculations later.
if (num_super_blocks == 0 )
{
allocate_data_block ();
num_super_blocks = 1 ;
num_dbs_in_last_sb = 1 ;
num_elems_in_last_data_block = 1 ;
num_elems = 1 ;
return ;
}
// Do we need to allocate?
if (num_elems_in_last_data_block == data_block_size (num_super_blocks-1 ))
{
if (num_dbs_in_last_sb == super_block_size (num_super_blocks-1 )) // track super block count
{
++num_super_blocks;
num_dbs_in_last_sb = 0 ;
}
allocate_data_block ();
++num_dbs_in_last_sb;
num_elems_in_last_data_block = 0 ;
}
++num_elems;
++num_elems_in_last_data_block;
}
// Relinquishes space for one element
__forceinline void shrink ()
{
--num_elems;
--num_elems_in_last_data_block;
if (num_elems_in_last_data_block==0 )
{
// Last block is empty, store it in our spare.
// This causes deallocation if we already had a spare.
spare_empty_db = std::move (index_block.back ());
index_block.pop_back ();
--num_dbs_in_last_sb;
if (num_dbs_in_last_sb == 0 ) // track super block count
{
--num_super_blocks;
num_dbs_in_last_sb = super_block_size (num_super_blocks-1 );
}
// The new last data block is completely full
num_elems_in_last_data_block = data_block_size (num_super_blocks-1 );
}
}
public:
compact_vector () :
num_elems (0 ),
num_super_blocks (0 ),
num_elems_in_last_data_block (0 ),
num_dbs_in_last_sb (0 )
{
}
compact_vector (compact_vector&& other) :
num_elems (other.num_elems),
num_super_blocks (other.num_super_blocks),
num_elems_in_last_data_block (other.num_elems_in_last_data_block),
num_dbs_in_last_sb (other.num_dbs_in_last_sb),
spare_empty_db (std::move(other.spare_empty_db)),
index_block (std::move(other.index_block))
{
}
compact_vector (const compact_vector& other) :
num_elems (other.num_elems),
num_super_blocks (0 ),
num_elems_in_last_data_block (other.num_elems_in_last_data_block),
num_dbs_in_last_sb (other.num_dbs_in_last_sb)
{
// Step through super blocks, copying data blocks
// of the appropriate size from the other array
auto block = other.index_block .begin ();
while (block != other.index_block .end ())
{
// Step through the book-keeping variable for super blocks. This lets us know how
// many data blocks to copy for this super block, and how big each one is.
++num_super_blocks;
const unsigned int last_super_block_size = super_block_size (num_super_blocks-1 );
const unsigned int last_data_block_size = data_block_size (num_super_blocks-1 );
// This inner loop will fill up a whole super block, unless we run out
for (unsigned int db=0 ; db < last_super_block_size && block != other.index_block .end (); ++db )
{
// Allocate data block of correct size
index_block.emplace_back (new T[last_data_block_size]);
// Copy data block over.
// TODO: This also copies unused elems in last db (harmless, but wasteful).
std::copy_n (block->get (), last_data_block_size, index_block.back ().get ());
++block;
}
}
assert (num_elems == other.num_elems );
assert (index_block.size () == other.index_block .size ());
assert (num_super_blocks == other.num_super_blocks );
assert (num_dbs_in_last_sb == other.num_dbs_in_last_sb );
assert (num_elems_in_last_data_block == other.num_elems_in_last_data_block );
}
compact_vector& operator =(compact_vector&& other)
{
num_elems = other.num_elems ;
num_super_blocks = other.num_super_blocks ;
num_elems_in_last_data_block = other.num_elems_in_last_data_block ;
num_dbs_in_last_sb = other.num_dbs_in_last_sb ;
spare_empty_db = std::move (other.spare_empty_db );
index_block = std::move (other.index_block );
return *this ;
}
compact_vector& operator =(const compact_vector& other)
{
if (this != &other)
{
*this = compact_vector (other); // copy constructor + move-assignment
}
return *this ;
}
void clear ()
{
num_elems=num_super_blocks=last_data_block_size=num_elems_in_last_data_block=last_super_block_size=num_dbs_in_last_sb=0 ;
index_block.clear ();
spare_empty_db.reset ();
}
unsigned int size () const
{
return num_elems;
}
T& back ()
{
return index_block.back ()[num_elems_in_last_data_block-1 ];
}
const T& back () const
{
return index_block.back ()[num_elems_in_last_data_block-1 ];
}
void push_back ( T&& x)
{
grow ();
// todo: allocate raw memory instead, and run constructor on last elem here
back () = std::move (x);
}
void push_back (const T& x)
{
grow ();
// todo: allocate raw memory instead, and run constructor on last elem here
back () = x;
}
void pop_back ()
{
// todo: once we run constructors manually, run destructor on last elem here
shrink ();
}
__forceinline T& operator [](unsigned int i)
{
unsigned int e, db;
locate_data_block_and_elem (i,e,db);
return index_block[db][e];
}
__forceinline const T& operator [](unsigned int i) const
{
unsigned int e, db;
locate_data_block_and_elem (i,e,db);
return index_block[db][e];
}
// iterator stuff
class iterator
{
T* elem;
T* current_db_end;
unsigned int current_db;
unsigned int current_sb;
unsigned int last_db_in_sb;
compact_vector* arr;
public:
iterator () : elem(nullptr ) {};
iterator ( compact_vector* the_array ) :
current_sb (0 ),
last_db_in_sb (0 ),
current_db (0 ),
arr (the_array)
{
if ( arr->index_block .size () > 0 )
{
elem = arr->index_block [0 ].get ();
current_db_end = elem+1 ; // first db is always of size 1
}
else
{
elem = current_db_end = nullptr ;
}
}
bool operator ==( const iterator& other )
{
return elem == other.elem ;
}
bool operator !=( const iterator& other )
{
return elem != other.elem ;
}
T& operator *()
{
return *elem;
}
iterator& operator ++()
{
if (++elem == current_db_end)
{
if (++current_db == arr->index_block .size () )
{
// we've reached the end of the whole array
elem = nullptr ;
}
else
{
elem = arr->index_block [current_db].get ();
// Track which super block we're in, so we can use this
// to compute the size of the data block later on
if (current_db > last_db_in_sb)
{
++current_sb;
last_db_in_sb += super_block_size (current_sb);
}
if ( elem == arr->index_block .back ().get () )
{
// we're in the last block, it may not be completely full
// so we need to treat it specially
current_db_end = elem + arr->num_elems_in_last_data_block ;
}
else
{
// Not the lats block, so it must be a full block, compute size
// using superblock index from before
current_db_end = elem + data_block_size (current_sb);
}
}
}
return *this ;
}
};
iterator begin ()
{
return iterator (this );
}
iterator end ()
{
return iterator ();
}
};
#pragma warning(pop)
Anonymous created this gist