Hat< T > Class Template Reference

This class implements a dynamicly growable array. More...

#include <hat.h>

Collaboration diagram for Hat< T >:

[legend]List of all members.

Public Member Functions
void	init (const size_t aExpectedSize=min_hat_size)
	Hat (const size_t aExpectedSize=min_hat_size)
	Hat default constructor (e.g., default since the class definition assigns a default value of zero to aExpectedSize).
	Hat (const Hat< T > &hat)
	~Hat ()
void	insert (const T &a, const size_t i)
	Insert an element "a" into the array at index "i".
void	remove (const size_t i)
	Remove (delete is a reserved word) the element at index "i".
void	remove_n (const size_t i, const size_t n)
	remove_n: like remove, but this function removes more than one item.
T &	operator[] (const size_t i)
T	operator[] (const size_t i) const
T &	at (const size_t i)
	the at function as an l-value
T	at (const size_t i) const
	return the address of a data element
T	first () const
	return the first data element in the array
T	last () const
	Return the last data element in the array.
void	append (const T &a)
	Add an element to the end of the array.
int	isEmpty () const
	return TRUE if there are no data elements in the array.
void	set_to_empty ()
	When the number of elements is set to zero, the array is empty of data, but contains storage.
size_t	length () const
	Return the number of data elements in the array.
void	decrement_length (const unsigned int val)
Private Member Functions
size_t	leafSize () const
size_t	topSize () const
size_t	topIndex (const unsigned i) const
size_t	leafIndex (const unsigned i) const
void	resize (const size_t newExpectedSize)
	Allocate a new HAT and copy the data from "this" HAT into the new HAT.
void	addLeaf (const T &aValue, const int doResize)
	Add a new Leaf to the HAT pointer array and insert the new data element (aValue) into it.
size_t	recommendedPower (const size_t s) const
void	setPower (const size_t p)
void	add_to_end (const T &aValue, const int doResize=1)
Private Attributes
T **	top
	top points to leaves
size_t	topUsed
	amount of top actually used (number of leaves)
size_t	power
	power of 2 used for leaves and top
size_t	leafMask
	used to compute the leaf index
size_t	numElements
	Number of elements used in the array.
size_t	numAvail
	number of elements currently allocated in the array

---

Detailed Description

template<class T>
class Hat< T >

This class implements a dynamicly growable array.

Arrays of this type are particularly useful in code generators, where algorithms like register range analysis and peephole optimization work best on arrays of instructions.

This class is implemented by a Hashed Array Tree (see HATs: Hashed Array Trees - very fast variable length arrays by Edward Sitarski, published in the "Algorithm Alley" section of Dr. Dobb's Journal, September 1996). The code here is derived from the public domain code published along with this article (e.g., ftp from the Dr. Dobbs ftp site).

This is a template class. Some C++ compilers (e.g., Sun) will only compile template classes with in-line class functions.

This code is fairly tricky. Memory is only allocated when it is needed and the addLeaf and resize functions end up being recursive co-routines. I like to think that my code is more transparent than this, since trickiness makes code difficult to understand and maintain. However, I've combed through this code and run some tests on it and as far as I can tell, it works correctly.

Notes

• Hashed Array Trees (hat)

  A slightly altered quote from the Hats: Hashed Array Trees article is included below:

  Although used to implement one dimensional arrays, HATs are really two dimensional. A HAT consists of a "Top" array and a number of "Leaves" which are pointed to by the Top array. The number of pointers in the Top array and the number of elements in each Leaf is the same, and is always a power of 2.

  Because the Top and Leaf arrays are powers of 2, you can efficiently find an element in a HAT using bit operations. Usually appending elements is very fast since the last leaf may have empty space. Less frequently, a new leaf must be added, which is also very fast and requires no copying.

  When the Top array is full, the size of new Top and Leaf arrays are calculated (e.g., a Top, that is twice as big, is allocated and enough leaf arrays are allocated to hold the current data set). A new Top is allocated. The existing data is "appended" to the new hat, allocating new leaves and deallocating old leaves as the copying is done. Recopying only occurs when the Top array is full and this happens when the number of elements exceeds the square of a power of two

• size_t

  You've got to love C++, it's huge and they constantly add to it. There are endless corners of the language that few people know about which allow people like Al Stevens (a Dr. Dobb's columnist) to count coup on the rest of us. One of these obscure features is size_t. From section 5.3.2 of The Annotated C++ Reference Manual:

  ... size_t, an impementation-dependent unsigned integral type defined in the standard header <stddef.h>. On most systems this is the local version of "unsigned int".

• Code bloat

  The Sun compiler has a habbit of in-lining constructors. As a result, a lot of code, especially in templates, ends up in line, exploding the size of the program.

Definition at line 122 of file hat.h.

---

Constructor & Destructor Documentation

template<class T> Hat< T >::Hat (  const size_t  aExpectedSize = min_hat_size  )  [inline]

Hat default constructor (e.g., default since the class definition assigns a default value of zero to aExpectedSize). Definition at line 287 of file hat.h. References Hat< T >::init(). { init( aExpectedSize ); }

template<class T> Hat< T >::Hat (  const Hat< T > &  hat  )  [inline]

Definition at line 293 of file hat.h. References Hat< T >::init(). { init( 0 ); (*this) = hat; }

template<class T> Hat< T >::~Hat (   )  [inline]

Definition at line 299 of file hat.h. References NULL, Hat< T >::top, and Hat< T >::topUsed. { if (top != NULL) { for( size_t i = 0; i < topUsed; i++ ) { if (top[i] != NULL) { delete [] top[i]; top[i] = NULL; } } delete [] top; top = NULL; } }

---

Member Function Documentation

template<class T> void Hat< T >::add_to_end (  const T &  aValue, const int  doResize = 1 )  [inline, private]

Definition at line 242 of file hat.h. References Hat< T >::addLeaf(), Hat< T >::numAvail, and Hat< T >::numElements. Referenced by Hat< T >::append(), and Hat< T >::resize(). { if (numElements == numAvail) { addLeaf( aValue, doResize ); } else { (*this)[numElements] = aValue; numElements++; } }

template<class T> void Hat< T >::addLeaf (  const T &  aValue, const int  doResize )  [inline, private]

Add a new Leaf to the HAT pointer array and insert the new data element (aValue) into it. Definition at line 182 of file hat.h. References FALSE, Hat< T >::leafSize(), Hat< T >::numAvail, Hat< T >::numElements, Hat< T >::resize(), Hat< T >::top, Hat< T >::topIndex(), Hat< T >::topSize(), Hat< T >::topUsed, and TRUE. Referenced by Hat< T >::add_to_end(). { /* If the top array is either empty (topUsed == 0) or is full topUsed == topSize (no new leaves can be added), reallocate the array. */ if( topUsed % topSize() == 0 ) { int growTop = TRUE; if( doResize ) { resize( numElements ); // Check if after the resize we have room. if( topIndex(numElements) < topUsed ) { (*this)[numElements++] = aValue; return; } // Check if we have room for a new leaf. if( topUsed % topSize() != 0 ) growTop = FALSE; } if( growTop ) { // Increase the top array by topSize. T **topNew = new T * [ topUsed + topSize() ]; for( size_t i = 0; i < topUsed; i++ ) topNew[i] = top[i]; delete [] top; top = topNew; } } /* add a new leaf */ top[topUsed] = new T [leafSize()]; top[topUsed][0] = aValue; numAvail += leafSize(); topUsed++; numElements++; } /* addLeaf */

template<class T> void Hat< T >::append (  const T &  a  )  [inline]

Add an element to the end of the array. Definition at line 441 of file hat.h. References Hat< T >::add_to_end(). Referenced by Hat< T >::insert(). { add_to_end(a); }

template<class T> T Hat< T >::at (  const size_t  i  )  const [inline]

return the address of a data element Definition at line 425 of file hat.h. { return (*this)[i]; }

template<class T> T& Hat< T >::at (  const size_t  i  )  [inline]

the at function as an l-value Definition at line 419 of file hat.h. { return (*this)[i]; }

template<class T> void Hat< T >::decrement_length (  const unsigned int  val  )  [inline]

Definition at line 469 of file hat.h. References Hat< T >::numElements. { if (val <= numElements) numElements = numElements - val; else numElements = 0; } // decrement_length

template<class T> T Hat< T >::first (  void   )  const [inline]

return the first data element in the array Definition at line 431 of file hat.h. { return (*this)[0]; }

template<class T> void Hat< T >::init (  const size_t  aExpectedSize = min_hat_size  )  [inline]

Definition at line 269 of file hat.h. References NULL, Hat< T >::numAvail, Hat< T >::numElements, Hat< T >::recommendedPower(), Hat< T >::setPower(), Hat< T >::top, and Hat< T >::topUsed. Referenced by Hat< T >::Hat(). { size_t p; /* get the smallest power of two greater than aExpectedSize */ p = recommendedPower(aExpectedSize); setPower( p ); numElements = 0; numAvail = 0; top = NULL; topUsed = 0; } // init

template<class T> void Hat< T >::insert (  const T &  a, const size_t  i )  [inline]

Insert an element "a" into the array at index "i". An empty array is an array with no data elements in it. This is not necessarily the same as the number of storage elements currently available in the array. A data element can be inserted into an empty array at index 0 (e.g., appended to an empty array). A data element can be inserted at the end of the array (that is array.insert( a, array.length())). A data element cannot be inserted beyond array.length() and an attempt to do so will result in an assert error. Except for insertion at element 0 of an empty array and insertion at the end of the array, insert can be an expensive operation. All elements from i+1 to the end of the array are moved up one array location. Definition at line 334 of file hat.h. References Hat< T >::append(), Hat< T >::length(), and Hat< T >::numElements. { assert( i <= numElements ); if (numElements == 0 || i == numElements) { append( a ); } else { assert( length() > 0 ); size_t last_ix = length() - 1; // Move all data elements from i+1 up by one index append( (*this)[last_ix] ); // append the last element to the end of the array assert( length() == last_ix + 2 ); int ix; for (ix = last_ix; ix > i; ix--) { (*this)[ix] = (*this)[ix-1]; } (*this)[i] = a; } } // insert

template<class T> int Hat< T >::isEmpty (   )  const [inline]

return TRUE if there are no data elements in the array. Definition at line 447 of file hat.h. References Hat< T >::numElements. { return numElements == 0; }

template<class T> T Hat< T >::last (   )  const [inline]

Return the last data element in the array. Definition at line 436 of file hat.h. References Hat< T >::numElements. { return (*this)[numElements-1]; }

template<class T> size_t Hat< T >::leafIndex (  const unsigned  i  )  const [inline, private]

Definition at line 128 of file hat.h. References GetLeafIndex. { return GetLeafIndex(i); }

template<class T> size_t Hat< T >::leafSize (   )  const [inline, private]

Definition at line 125 of file hat.h. References Hat< T >::power. Referenced by Hat< T >::addLeaf(), Hat< T >::resize(), and Hat< T >::setPower(). { return 1<<power; /* return 2^power */ }

template<class T> size_t Hat< T >::length (  void   )  const [inline]

Return the number of data elements in the array. As noted above, this is different from the number of storage elements. Definition at line 465 of file hat.h. References Hat< T >::numElements. Referenced by Hat< T >::insert(), Hat< T >::remove(), and Hat< T >::remove_n(). { return numElements; }

template<class T> T Hat< T >::operator[] (  const size_t  i  )  const [inline]

Definition at line 412 of file hat.h. References GetLeafIndex, GetTopIndex, Hat< T >::numAvail, and Hat< T >::top. { assert( i < numAvail ); return top[GetTopIndex(i)][GetLeafIndex(i)]; }

template<class T> T& Hat< T >::operator[] (  const size_t  i  )  [inline]

Definition at line 406 of file hat.h. References GetLeafIndex, GetTopIndex, Hat< T >::numAvail, and Hat< T >::top. { assert( i < numAvail ); return top[GetTopIndex(i)][GetLeafIndex(i)]; }

template<class T> size_t Hat< T >::recommendedPower (  const size_t  s  )  const [inline, private]

Definition at line 225 of file hat.h. Referenced by Hat< T >::init(). { const size_t powerMin = 1; // set a resonable minimum size_t p; for( p = powerMin; s > (1<<(p<<1)); p++ ) ; return p; } // recommendedPower

template<class T> void Hat< T >::remove (  const size_t  i  )  [inline]

Remove (delete is a reserved word) the element at index "i". Like insert, this can be an expensive operation. Unless the element is at the very end of the array, elements from i+1 to numElements are moved "down" one element. It is an error to attempt to remove an element beyond the end of the array. It is also an error to remove an element from an empty array. Definition at line 370 of file hat.h. References Hat< T >::length(), and Hat< T >::numElements. { assert( length() > 0 ); assert( i < length() ); if (i < length() - 1) { int ix; for (ix = i; ix < length()-1; ix++) { (*this)[ix] = (*this)[ix+1]; } } numElements--; } // remove

template<class T> void Hat< T >::remove_n (  const size_t  i, const size_t  n )  [inline]

remove_n: like remove, but this function removes more than one item. Definition at line 389 of file hat.h. References Hat< T >::length(), and Hat< T >::numElements. { assert( length() > 0 ); assert( i + n <= length() ); if (i + n < length()) { int ix; for (ix = i; ix < length()-n; ix++) { (*this)[ix] = (*this)[ix+n]; } } numElements -= n;; }

template<class T> void Hat< T >::resize (  const size_t  newExpectedSize  )  [inline, private]

Allocate a new HAT and copy the data from "this" HAT into the new HAT. Definition at line 134 of file hat.h. References Hat< T >::add_to_end(), Hat< T >::leafSize(), NULL, Hat< T >::numAvail, Hat< T >::numElements, Hat< T >::power, Hat< T >::setPower(), Hat< T >::top, Hat< T >::topIndex(), and Hat< T >::topUsed. Referenced by Hat< T >::addLeaf(). { size_t i, leaf_ix; Hat<T> hatNew( newExpectedSize ); /* if the new HAT is the same size (e.g., power) as "this" HAT, return */ if( hatNew.power == power ) return; /* copy the data from "this" hat into the new array */ for( i = 0, leaf_ix = 0; i < numElements; i++ ) { hatNew.add_to_end( (*this)[i], 0 ); // append, but do not resize again leaf_ix++; // delete the leaves as we go - this decreases memory overhead. if( leaf_ix == leafSize() ) { delete [] top[topIndex(i)]; leaf_ix = 0; } } // delete any unused leaves. for( i = topIndex(numElements); i < topUsed; i++ ) delete [] top[i]; // assign the new array to the old. delete top; top = hatNew.top; setPower( hatNew.power ); topUsed = hatNew.topUsed; numAvail = hatNew.numAvail; // clean up so nothing gets corrupted. hatNew.numElements = 0; hatNew.topUsed = 0; hatNew.top = NULL; } // resize

template<class T> void Hat< T >::set_to_empty (   )  [inline]

When the number of elements is set to zero, the array is empty of data, but contains storage. This is the difference between numElements (the number of data items) and numAvail, the number of storage elements available. Definition at line 457 of file hat.h. References Hat< T >::numElements. { numElements = 0; }

template<class T> void Hat< T >::setPower (  const size_t  p  )  [inline, private]

Definition at line 235 of file hat.h. References Hat< T >::leafMask, Hat< T >::leafSize(), and Hat< T >::power. Referenced by Hat< T >::init(), and Hat< T >::resize(). { power = p; leafMask = leafSize()-1; }

template<class T> size_t Hat< T >::topIndex (  const unsigned  i  )  const [inline, private]

Definition at line 127 of file hat.h. References GetTopIndex. Referenced by Hat< T >::addLeaf(), and Hat< T >::resize(). { return GetTopIndex(i); }

template<class T> size_t Hat< T >::topSize (   )  const [inline, private]

Definition at line 126 of file hat.h. References Hat< T >::power. Referenced by Hat< T >::addLeaf(). { return 1<<power; /* return 2^power */ }

---

Member Data Documentation

template<class T> size_t Hat< T >::leafMask [private]

used to compute the leaf index Definition at line 261 of file hat.h. Referenced by Hat< T >::setPower().

template<class T> size_t Hat< T >::numAvail [private]

number of elements currently allocated in the array Definition at line 266 of file hat.h. Referenced by Hat< T >::add_to_end(), Hat< T >::addLeaf(), Hat< T >::init(), Hat< T >::operator[](), and Hat< T >::resize().

template<class T> size_t Hat< T >::numElements [private]

Number of elements used in the array. numElements always points to the next free element in the array Definition at line 264 of file hat.h. Referenced by Hat< T >::add_to_end(), Hat< T >::addLeaf(), Hat< T >::decrement_length(), Hat< T >::init(), Hat< T >::insert(), Hat< T >::isEmpty(), Hat< T >::last(), Hat< T >::length(), Hat< T >::remove(), Hat< T >::remove_n(), Hat< T >::resize(), and Hat< T >::set_to_empty().

template<class T> size_t Hat< T >::power [private]

power of 2 used for leaves and top Definition at line 259 of file hat.h. Referenced by Hat< T >::leafSize(), Hat< T >::resize(), Hat< T >::setPower(), and Hat< T >::topSize().

template<class T> T** Hat< T >::top [private]

top points to leaves Definition at line 255 of file hat.h. Referenced by Hat< T >::addLeaf(), Hat< T >::init(), Hat< T >::operator[](), Hat< T >::resize(), and Hat< T >::~Hat().

template<class T> size_t Hat< T >::topUsed [private]

amount of top actually used (number of leaves) Definition at line 257 of file hat.h. Referenced by Hat< T >::addLeaf(), Hat< T >::init(), Hat< T >::resize(), and Hat< T >::~Hat().

---

The documentation for this class was generated from the following file:

• hat.h

---