At 02:09 AM 3/11/2005, Eric Niebler wrote:
It's impossible to say, since I don't know how hashed_array_tree is
defined and I don't have a way to find out. If you could post a minimal,
complete example that reproduces the problem, I could probably tell you
what's wrong.
The trouble is that I wasn't sure how to make things any more minimal,
since I don't know what aspects of the container's definition are relevant;
I'll attach the headers for the hashed_array_tree, though.
// -*- c++ -*-
#pragma once
namespace cphstl {
template
class hashed_array_tree {
template friend class hat_iterator;
template friend class hat_const_iterator;
private:
inline void find_index (unsigned int n, int& leaf, int& index) {
leaf = n >> _power;
index = n & _mask;
}
inline int find_leafsize (unsigned int n) {
int leafsize = 1, capacity = 1;
while (capacity < (int) n) {
leafsize <<= 1;
capacity <<= 2;
}
return leafsize;
}
public:
typedef T value_type;
typedef A allocator_type;
typedef typename A::size_type size_type;
typedef typename A::difference_type difference_type;
typedef hat_iterator iterator;
typedef hat_const_iterator const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator const_reverse_iterator;
typedef typename A::pointer pointer;
typedef typename A::const_pointer const_pointer;
typedef typename A::reference reference;
typedef typename A::const_reference const_reference;
hashed_array_tree (const size_type c = 1,
const value_type& val = value_type(),
const A& a = A())
: _alloc(a), _size(0) {
// Find the initial capacity as the square of a power of two
// that corresponds best to the initial_capacity.
_leafsize = find_leafsize((unsigned int)c);
_top_array = _palloc.allocate(_leafsize);
int leafs = (int)(c / _leafsize + (c % _leafsize ? 1 : 0));
for (int i = 0; i < leafs; i++) {
_top_array[i] = _alloc.allocate(_leafsize);
for (int j = 0; j < _leafsize; j++)
_alloc.construct(&_top_array[i][j], val);
}
_capacity = _leafsize * leafs;
_power = log_2_ceil(_leafsize);
_mask = (1 << _power) - 1;
}
hashed_array_tree(const hashed_array_tree& v, const A& a = A())
: _leafsize(v._leafsize), _mask(v._mask),
_power(v._power), _alloc(a),
_capacity(v._capacity), _size(v._size) {
// Allocate the top array and the leafs.
_top_array = _palloc.allocate(_leafsize);
// Copy the elements.
int leafs = (int)(_capacity / _leafsize);
for (int i = 0; i < leafs; i++) {
_top_array[i] = _alloc.allocate(_leafsize);
for (int j = 0; j < _leafsize; j++) {
_alloc.construct(&_top_array[i][j], v._top_array[i][j]);
}
}
}
~hashed_array_tree () {
int leafs = (int)(_capacity / _leafsize);
for (int i = 0; i < leafs; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.destroy(&_top_array[i][j]);
_alloc.deallocate(_top_array[i], _leafsize);
}
_palloc.deallocate(_top_array, _leafsize);
}
iterator begin() {return iterator(0, this);}
iterator end() {return iterator(_size, this);}
const_iterator begin() const {return const_iterator(0, this);}
const_iterator end() const {return const_iterator(_size, this);}
reverse_iterator rbegin() {
return reverse_iterator(iterator(_size, this));
}
reverse_iterator rend() {
return reverse_iterator(iterator(0, this));
}
const_reverse_iterator rbegin() const {
return const_reverse_iterator(const_iterator(_size, this));
}
const_reverse_iterator rend() const {
return const_reverse_iterator(const_iterator(0, this));
}
reference operator[] (size_type n) {
return _top_array[n >> _power][n & _mask];
}
const_reference operator[] (size_type n) const {
return _top_array[n >> _power][n & _mask];
}
reference front() {
return _size == 0 ? 0 : _top_array[0][0];
}
const_reference front() const {
return _size == 0 ? 0 : _top_array[0][0];
}
reference back() {
if (_size == 0) return 0;
return _top_array[_size >> _power][_size & _mask];
}
const_reference back() const {
if (_size == 0) return 0;
return _top_array[_size >> _power][_size & _mask];
}
hashed_array_tree& operator=(const hashed_array_tree& v) {
// If the leafsize of the two trees are different we just
// deallocate everything and allocate new leafs.
if (_leafsize != v._leafsize) {
// Destroy and deallocate everything.
int leafs = _capacity / _leafsize;
for (int i = 0; i < leafs; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.destroy(&_top_array[i][j]);
_alloc.deallocate(_top_array[i], _leafsize);
}
_palloc.deallocate(_top_array, _leafsize);
// Allocate a new top_array and allocate the new
// elements. While doing this we copy the values from v into
// the new leafs.
_top_array = _palloc.allocate(v._leafsize);
int need = v._capacity / v._leafsize;
for (int i = 0; i < need; i++) {
_top_array[i] = _alloc.allocate(v._leafsize);
for (int j = 0; j < v._leafsize; j++)
_alloc.construct(&_top_array[i][j], v._top_array[i][j]);
}
_leafsize = v._leafsize;
_mask = v._mask;
_power = v._power;
} else {
// The leafsizes are the same. Now we free the space that is
// no longer needed or allocate extra leafs if they are
// needed.
int leafs = _capacity / _leafsize;
int need = v._capacity / _leafsize;
if (leafs < need) {
// We have to allocate extra leafs.
for (int i = leafs; i < need; i++)
_top_array[i] = _alloc.allocate(_leafsize);
} else {
// We might have to deallocate some leafs.
for (int i = need; i < leafs; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.destroy(&_top_array[i][j]);
_alloc.deallocate(_top_array[i], _leafsize);
}
// We set leafs to need to make sure that element copying
// works.
leafs = need;
}
// Copy the data from v into the new storage. First we copy
// into the old leafs where destruction of old elements are
// needed.
for (int i = 0; i < leafs; i++) {
for (int j = 0; j < _leafsize; j++) {
_alloc.destroy(&_top_array[i][j]);
_alloc.construct(&_top_array[i][j], v._top_array[i][j]);
}
}
// Then we copy into the new leafs that doesn't need
// destruction of elements.
for (int i = leafs; i < need; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.construct(&_top_array[i][j], v._top_array[i][j]);
}
}
_size = v._size;
_capacity = v._capacity;
return *this;
}
void reserve(size_type n) {
if (n <= _capacity) return;
// There are two cases here, one where we have to change the
// leafsize and one where we can reserve the space without
// changing the leafsize.
int new_leafsize = find_leafsize(n);
int needed_leafs = n / new_leafsize + (n % new_leafsize ? 1 : 0);
value_type val = value_type();
if (_leafsize == new_leafsize) {
for (int i = _capacity / _leafsize; i < needed_leafs; i++) {
_top_array[i] = _alloc.allocate(_leafsize);
for (int j = 0; j < _leafsize; j++)
_alloc.construct(&_top_array[i][j], val);
_capacity += _leafsize;
}
} else {
pointer* new_top_array = _palloc.allocate(new_leafsize);
// For each new leaf that is needed we allocate it and either
// copy the old value into the position or construct it with
// the default value val. First we allocate the new leafs.
for (int i = 0; i < needed_leafs; i++)
new_top_array[i] = _alloc.allocate(new_leafsize);
// Then we copy the elements from the old top_array.
// x is the number of old leafs that fit into one new leaf.
int x = new_leafsize / _leafsize;
int leafs = _capacity / _leafsize;
for (int i = 0; i < leafs; i++) {
for (int j = 0; j < _leafsize; j++) {
_alloc.construct(&new_top_array[i/x][(i%x) * _leafsize + j],
_top_array[i][j]);
_alloc.destroy(&_top_array[i][j]);
}
_alloc.deallocate(_top_array[i], _leafsize);
}
// Now we have to check wether one of the leafs have not been
// fully constructed.
int idx = (_capacity / new_leafsize +
(_capacity % new_leafsize ? 1 : 0)) - 1;
int start;
if ((start = _capacity % new_leafsize) != 0) {
for (int i = start; i < new_leafsize; i++)
_alloc.construct(&new_top_array[idx][i], val);
idx++;
}
// The rest of the needed leafs only needs to be constructed
// with the standard value val.
for (int i = idx; i < needed_leafs; i++) {
for (int j = 0; j < new_leafsize; j++)
_alloc.construct(&new_top_array[i][j], val);
}
_top_array = new_top_array;
_leafsize = new_leafsize;
_capacity = _leafsize * needed_leafs;
_power = log_2_ceil(_leafsize);
_mask = (1 << _power) - 1;
}
}
void swap (hashed_array_tree& v) {
int tmp_leafsize = _leafsize;
unsigned int tmp_power = _power;
unsigned int tmp_mask = _mask;
unsigned int tmp_capacity = _capacity;
unsigned int tmp_size = _size;
value_type **tmp_top_array = _top_array;
_leafsize = v._leafsize;
_power = v._power;
_mask = v._mask;
_capacity = v._capacity;
_size = v._size;
_top_array = v._top_array;
v._leafsize = tmp_leafsize;
v._power = tmp_power;
v._mask = tmp_mask;
v._capacity = tmp_capacity;
v._size = tmp_size;
v._top_array = tmp_top_array;
}
void push_back (const_reference x) {
// Check to see is extra storage must be allocated.
if (_size == _capacity) {
// Check to see if we need to change leafsize.
if (_size == (unsigned int)_leafsize * _leafsize) {
int new_leafsize = _leafsize << 1;
pointer* new_top_array = _palloc.allocate(new_leafsize);
// The is one special case here and that's when the old
// leafsize is 1. This is handled separately here. This is a
// special case because the moving of old elements does not
// completely fill the new leafs of the new top_array.
if (_leafsize == 1) {
new_top_array[0] = _alloc.allocate(2);
_alloc.construct(&new_top_array[0][0], _top_array[0][0]);
_alloc.construct(&new_top_array[0][1], x);
_alloc.destroy(&_top_array[0][0]);
_alloc.deallocate(_top_array[0], _leafsize);
_palloc.deallocate(_top_array, _leafsize);
_top_array = new_top_array;
_leafsize = 2;
_capacity = 2;
_power = 1;
_mask = 1;
} else {
// This loops over the new leafs needed by the objects in
// the old leafs.
_power += 1;
size_type last_leaf = _size >> _power;
for (size_type i = 0; i < last_leaf; i++) {
new_top_array[i] = _alloc.allocate(new_leafsize);
size_type pos = 0; // The starting position in this new leaf.
// This loops over the next two old leafs that need to
// be copied into new leafs.
size_type stop_index = (i + 1) * 2;
for (size_type j = i * 2; j < stop_index; j++) {
// Copy the actual elements.
for (int k = 0; k < _leafsize; k++) {
_alloc.construct(&new_top_array[i][pos++],
_top_array[j][k]);
_alloc.destroy(&_top_array[j][k]);
}
_alloc.deallocate(_top_array[j], _leafsize);
}
}
_palloc.deallocate(_top_array, _leafsize);
_top_array = new_top_array;
// Allocate the extra leaf that we wanted to begin with.
_top_array[last_leaf] = _alloc.allocate(new_leafsize);
value_type val = value_type();
for (int i = 1; i < new_leafsize; i++)
_alloc.construct(&_top_array[last_leaf][i], val);
_leafsize = new_leafsize;
_capacity += _leafsize;
_mask = (_mask<<1)|1;
// Insert the element.
_alloc.construct(&_top_array[last_leaf][0], x);
}
} else {
// If no change in leafsize is needed we just allocate an
// extra leaf.
size_type new_leaf = _capacity >> _power;
value_type val = value_type();
_top_array[new_leaf] = _alloc.allocate(_leafsize);
for (int i = 1; i < _leafsize; i++)
_alloc.construct(&_top_array[new_leaf][i], val);
_capacity += _leafsize;
// Insert the element.
_alloc.construct(&_top_array[new_leaf][0], x);
}
} else {
// Insert the new element.
int leaf = (int)(_size >> _power);
int leaf_idx = (int)(_size & _mask);
_alloc.destroy(&_top_array[leaf][leaf_idx]);
_alloc.construct(&_top_array[leaf][leaf_idx], x);
}
_size += 1;
}
void pop_back () {
value_type val = value_type();
size_type max_capacity = _leafsize * _leafsize;
_size -= 1;
// Check if resizing is needed.
if (_capacity != 1 && _size <= max_capacity / 8) {
int new_leafsize = _leafsize >> 1;
pointer* new_top_array = _palloc.allocate(new_leafsize);
size_type last_leaf = _size >> _power;
size_type last_idx = _size & _mask;
size_type cur_new_leaf = 0;
// Start by allocating the leafs that are needed in the new
// top_array.
size_type new_leafs = _size / new_leafsize +
(_size % new_leafsize ? 1 : 0);
if (new_leafs == 0) new_leafs = 1; // If _size is 0.
for (size_type i = 0; i < new_leafs; i++)
new_top_array[i] = _alloc.allocate(new_leafsize);
// For every leaf containing data in the old top_array but
// the last one.
for (size_type i = 0; i < last_leaf; i++) {
for (int j = 0; j < new_leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j],
_top_array[i][j]);
cur_new_leaf++;
for (int j = new_leafsize; j < _leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j%new_leafsize],
_top_array[i][j]);
cur_new_leaf++;
}
// Now take care of the last leaf. First check to see if
// index == 0 in which case no more elements must be moved.
if (last_idx != 0) {
// See if two new leafs are needed.
if ((int)last_idx > new_leafsize) {
// Fill the first leaf.
for (int j = 0; j < new_leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j],
_top_array[last_leaf][j]);
cur_new_leaf++;
// And copy the elements until n into the last leaf.
for (size_type j = new_leafsize; j < last_idx; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j%new_leafsize],
_top_array[last_leaf][j]);
// Construct the empty spaces.
for (int j = last_idx%new_leafsize; j < new_leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j], val);
} else {
for (size_type j = 0; j < last_idx; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j],
_top_array[last_leaf][j]);
// Construct the empty spaces.
for (int j = last_idx; j < new_leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j], val);
}
}
// Destroy the elements in the old top_array.
last_leaf = _capacity / _leafsize;
for (size_type i = 0; i < last_leaf; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.destroy(&_top_array[i][j]);
_alloc.deallocate(_top_array[i], _leafsize);
}
_palloc.deallocate(_top_array, _leafsize);
_top_array = new_top_array;
_leafsize = new_leafsize;
_capacity = new_leafs * _leafsize;
_power -= 1;
_mask = _mask >> 1;
} else {
// No resizing is needed.
size_type last_leaf = _size >> _power;
size_type last_idx = _size & _mask;
_alloc.destroy(&_top_array[last_leaf][last_idx]);
_alloc.construct(&_top_array[last_leaf][last_idx], val);
// Check to see if there are two empty leafs. If so we
// deallocate the last one.
last_leaf = (_capacity - 1) >> _power;
if (last_leaf >= ((_size - 1) >> _power) + 2) {
for (int i = 0; i < _leafsize; i++)
_alloc.destroy(&_top_array[last_leaf][i]);
_alloc.deallocate(_top_array[last_leaf], _leafsize);
_capacity -= _leafsize;
}
}
}
// This function could be optimized when a resize is done by
// moving elements while copying them from the old top_array. It
// has not been done because of 1) time, 2) it's not necessary for
// what I'm meassuring in my report.
iterator insert(iterator pos, const value_type& x) {
// Allocate an extra leaf if this is needed.
if (_size == _capacity) {
value_type val = value_type();
// Check to see if we need to change leafsize.
if (_size == (unsigned int)_leafsize * _leafsize) {
int new_leafsize = _leafsize << 1;
pointer* new_top_array = _palloc.allocate(new_leafsize);
// The is one special case here and that's when the old
// leafsize is 1. This is handled separately here. This is a
// special case because the moving of old elements does not
// completely fill the new leafs of the new top_array.
if (_leafsize == 1) {
new_top_array[0] = _alloc.allocate(2);
_alloc.construct(&new_top_array[0][0], _top_array[0][0]);
_alloc.construct(&new_top_array[0][1], val);
_alloc.destroy(&_top_array[0][0]);
_alloc.deallocate(_top_array[0], _leafsize);
_palloc.deallocate(_top_array, _leafsize);
_top_array = new_top_array;
_leafsize = 2;
_capacity = 2;
_power = 1;
_mask = 1;
} else {
// This loops over the new leafs needed by the objects in
// the old leafs.
int last_leaf = _size / new_leafsize;
for (int i = 0; i < last_leaf; i++) {
new_top_array[i] = _alloc.allocate(new_leafsize);
int pos = 0; // The starting position in this new leaf.
// This loops over the next two old leafs that need to
// be copied into new leafs.
for (int j = i * 2; j < (i + 1) * 2; j++) {
// Copy the actual elements.
for (int k = 0; k < _leafsize; k++) {
_alloc.construct(&new_top_array[i][pos++],
_top_array[j][k]);
_alloc.destroy(&_top_array[j][k]);
}
_alloc.deallocate(_top_array[j], _leafsize);
}
}
_palloc.deallocate(_top_array, _leafsize);
_top_array = new_top_array;
// Allocate the extra leaf that we wanted to begin with.
_top_array[last_leaf] = _alloc.allocate(new_leafsize);
for (int i = 0; i < new_leafsize; i++)
_alloc.construct(&_top_array[last_leaf][i], val);
_leafsize = new_leafsize;
_capacity += _leafsize;
_power = log_2_ceil(_leafsize);
_mask = (1 << _power) - 1;
}
} else {
// If no change in leafsize is needed we just allocate an
// extra leaf.
int new_leaf = _capacity / _leafsize;
_top_array[new_leaf] = _alloc.allocate(_leafsize);
for (int i = 0; i < _leafsize; i++)
_alloc.construct(&_top_array[new_leaf][i], val);
_capacity += _leafsize;
}
}
// Insert the element into position n.
int index = pos - this->begin();
int leaf = index / _leafsize;
int n = index % _leafsize; // The index in the leaf.
// Now move all the elements in front of position n one space up
// in the tree.
int last_leaf, move_from;
find_index(_size - 1, last_leaf, move_from);
// This loops over the leaf from the last one to the one that
// contains n.
for (int i = last_leaf; i >= leaf; i--) {
// First we check to see if we need to move the last element
// in the leaf into the leaf in front of this one.
if (move_from == _leafsize - 1) {
_alloc.destroy(&_top_array[i+1][0]);
_alloc.construct(&_top_array[i+1][0],
_top_array[i][move_from--]);
}
// The we move the rest of the elements inside of the leaf. If
// this is the leaf that contains n we only move the elements
// until the n'th position.
if (i == leaf) {
for (int j = move_from; j >= n; j--) {
_alloc.destroy(&_top_array[i][j+1]);
_alloc.construct(&_top_array[i][j+1], _top_array[i][j]);
}
} else {
for (int j = move_from; j >= 0; j--) {
_alloc.destroy(&_top_array[i][j+1]);
_alloc.construct(&_top_array[i][j+1], _top_array[i][j]);
}
}
move_from = _leafsize - 1;
}
// Insert x into the hole that has appeared.
_alloc.destroy(&_top_array[leaf][n]);
_alloc.construct(&_top_array[leaf][n], x);
_size += 1;
return iterator(n, this);
}
iterator erase(iterator pos) {
int n = pos - this->begin();
value_type val = value_type();
// Check if we need to change to another leafsize after this
// erase. We change leafsize if the size is 1/8 of the max
// capacity with the current leafsize.
unsigned int max_cap = _leafsize * _leafsize;
if (_capacity != 1 && _size - 1 <= max_cap / 8) {
int new_leafsize = _leafsize >> 1;
pointer *new_top_array = _palloc.allocate(new_leafsize);
int last_leaf = (_size - 1) / _leafsize;
int last_idx = (_size - 1) % _leafsize;
int n_leaf = n / _leafsize;
int n_idx = n % _leafsize;
int cur_new_leaf = 0;
// Start by allocating the leafs that are needed in the new
// top_array.
int new_leafs = new_leafsize == 1 ? 1 : (_size - 1) /
new_leafsize + ((_size - 1) % new_leafsize ? 1 : 0);
for (int i = 0; i < new_leafs; i++)
new_top_array[i] = _alloc.allocate(new_leafsize);
// For every leaf containing data in the old top_array.
for (int i = 0; i <= last_leaf; i++) {
// If this is before the leaf that contain n we just copy
// the elements.
if (i < n_leaf) {
int split;
for (int j = 0; j < _leafsize; j++) {
split = j >= new_leafsize ? 1 : 0;
_alloc.construct(&new_top_array[cur_new_leaf+split]
[j-new_leafsize*split], _top_array[i][j]);
}
} else if (i == n_leaf) {
// If this is exactly the leaf that contain n.
int split;
for (int j = 0; j < n_idx; j++) {
split = j >= new_leafsize ? 1 : 0;
_alloc.construct(&new_top_array[cur_new_leaf+split]
[j-new_leafsize*split], _top_array[i][j]);
}
// Now we have to check if this is the last leaf in which
// case we only have to copy the elements until last_idx.
if (i == last_leaf) {
for (int j = n_idx; j < last_idx; j++) {
split = j >= new_leafsize ? 1 : 0;
_alloc.construct(&new_top_array[cur_new_leaf+split]
[j-new_leafsize*split],
_top_array[i][j+1]);
}
// Now we need to construct the last elements in
// new_top_array.
int leaf, idx;
if (last_idx >= new_leafsize) {
leaf = cur_new_leaf + 1;
idx = last_idx - new_leafsize;
if (idx != 0) {
for (int j = idx + 1; j < new_leafsize; j++)
_alloc.construct(&new_top_array[leaf][j], val);
}
} else {
if (n_idx != 0) {
for (int j = last_idx + 1; j < new_leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j], val);
}
}
} else {
// If this is not the last leaf we copy all the elements
// from this leaf (after the n'th position) into the new
// leafs. When that is done we copy the first element
// from the next leaf into the last position of the new
// leaf.
for (int j = n_idx; j < _leafsize - 1; j++) {
split = j >= new_leafsize ? 1 : 0;
_alloc.construct(&new_top_array[cur_new_leaf+split]
[j-new_leafsize*split],
_top_array[i][j+1]);
}
_alloc.construct(&new_top_array[cur_new_leaf+1]
[new_leafsize-1], _top_array[i+1][0]);
}
} else {
// If this is a leaf that comes after the leaf that contain n.
int split;
// If this is the last leaf we just copy over the elements
// from this leaf.
if (i == last_leaf) {
for (int j = 0; j < last_idx; j++) {
split = j >= new_leafsize ? 1 : 0;
_alloc.construct(&new_top_array[cur_new_leaf+split]
[j-new_leafsize*split],
_top_array[i][j+1]);
}
// Now we construct the last elements of the new leaf.
int leaf, idx;
if (last_idx >= new_leafsize) {
leaf = cur_new_leaf + 1;
idx = last_idx - new_leafsize;
if (idx != 0) {
for (int j = idx + 1; j < new_leafsize; j++)
_alloc.construct(&new_top_array[leaf][j], val);
}
} else {
if (last_idx != 0) {
for (int j = last_idx + 1; j < new_leafsize; j++)
_alloc.construct(&new_top_array[cur_new_leaf][j], val);
}
}
} else {
for (int j = 0; j < _leafsize - 1; j++) {
split = j >= new_leafsize ? 1 : 0;
_alloc.construct(&new_top_array[cur_new_leaf+split]
[j-new_leafsize*split],
_top_array[i][j+1]);
}
_alloc.construct(&new_top_array[cur_new_leaf+1]
[new_leafsize-1], _top_array[i+1][0]);
}
}
cur_new_leaf += 2;
}
// Destroy the elements in the old top_array.
last_leaf = _capacity / _leafsize;
for (int i = 0; i < last_leaf; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.destroy(&_top_array[i][j]);
_alloc.deallocate(_top_array[i], _leafsize);
}
_palloc.deallocate(_top_array, _leafsize);
_top_array = new_top_array;
_leafsize = new_leafsize;
_capacity = new_leafs * _leafsize;
_power -= 1;
_mask = _mask >> 1;
} else {
// If no resizing of leafs is necessary we just rearrange the
// elements in the existing structure. We just start from the
// n'th position and run forward through the leafs.
int last_leaf = (_size - 1) / _leafsize;
int last_idx = (_size - 1) % _leafsize;
int n_leaf = n / _leafsize;
int start_idx = n % _leafsize;
for (int i = n_leaf; i <= last_leaf; i++) {
// If this is the last leaf with data in it we only move
// elements until last_idx.
if (i == last_leaf) {
for (int j = start_idx; j < last_idx; j++) {
_alloc.destroy(&_top_array[i][j]);
_alloc.construct(&_top_array[i][j], _top_array[i][j+1]);
}
_alloc.destroy(&_top_array[i][last_idx]);
_alloc.construct(&_top_array[i][last_idx], val);
} else {
for (int j = start_idx; j < _leafsize - 1; j++) {
_alloc.destroy(&_top_array[i][j]);
_alloc.construct(&_top_array[i][j], _top_array[i][j+1]);
}
// Move the first element from the next leaf into the last
// position in this leaf. This makes the hole that is
// needed to start rearranging the next leaf.
_alloc.destroy(&_top_array[i][_leafsize-1]);
_alloc.construct(&_top_array[i][_leafsize-1],
_top_array[i+1][0]);
}
start_idx = 0;
}
// Check to see if there are two empty leafs. If so we
// deallocate the last one.
last_leaf = _capacity / _leafsize - 1;
if (last_leaf >= (int)((_size - 2) / _leafsize + 2)) {
for (int i = 0; i < _leafsize; i++)
_alloc.destroy(&_top_array[last_leaf][i]);
_alloc.deallocate(_top_array[last_leaf], _leafsize);
_capacity -= _leafsize;
}
}
_size -= 1;
return iterator(n, this);
}
void clear() {
int last = (int)(_capacity / _leafsize);
for (int i = 0; i < last; i++) {
for (int j = 0; j < _leafsize; j++)
_alloc.destroy(&_top_array[i][j]);
_alloc.deallocate(_top_array[i], _leafsize);
}
_palloc.deallocate(_top_array, _leafsize);
_size = 0;
_capacity = 1;
_leafsize = 1;
_power = 0;
_mask = 0;
_top_array = _palloc.allocate(1);
_top_array[0] = _alloc.allocate(1);
_alloc.construct(&_top_array[0][0], value_type());
}
template friend bool operator==(const hashed_array_tree& v1,
const hashed_array_tree& v2);
template friend bool operator<(const hashed_array_tree& v1,
const hashed_array_tree& v2);
const size_type size() const {
return _size;
}
private:
int _leafsize;
unsigned int _mask;
unsigned int _power;
typedef typename A::rebind<typename A::pointer>::other palloc;
palloc _palloc;
allocator_type _alloc;
protected:
size_type _capacity;
size_type _size;
pointer *_top_array;
};
template
bool operator==(const hashed_array_tree& v1,
const hashed_array_tree& v2) {
if (v1._size != v2._size)
return false;
else {
for (unsigned int i = 0; i < v1._size; i++) {
if (v1[i] != v2[i])
return false;
}
return true;
}
}
template
bool operator<(const hashed_array_tree& v1,
const hashed_array_tree& v2) {
unsigned int size = v1._size < v2._size ? v1._size : v2._size;
for (unsigned int i = 0; i < size; i++) {
if (v1[i] < v2[i])
return true;
else if (v1[i] > v2[i])
return false;
}
return (v1._size < v2._size);
}
};
#ifndef MATH_UTILS_H
#define MATH_UTILS_H
/** A logarithm function that computes \lfloor \log_2(x) \rfloor in
LaTeX codes :-)
This function computes the 2-logarithm of the parameter rounded
down to the nearest integer.
\param x The integer to calculate the 2-logarithm for.
\return The rounded down result of the 2-logarithm function. */
inline unsigned int log_2 (unsigned int x) {
unsigned int r = 0;
x >>= 1;
while (x) {
r++;
x >>= 1;
}
return r;
}
/** A logarithm function that computes \lceil \log_2(x) \rceil.
This function computes the 2-logarithm of the parameter rounded up
to the nearest integer.
\param x The integer to calculate the 2-logarithm for.
\return The rounded down result of the 2-logarithm function.
*/
inline unsigned int log_2_ceil (unsigned int x) {
if (x == 0) return 0;
unsigned int x_copy = x;
unsigned int r = 0;
x >>= 1;
while (x) {
r++;
x >>= 1;
}
if (x_copy - (1<
Eric Niebler
Michael W Daniels