sparse_array< T > Class Template Reference

Template class for a sparse array of fixed size (e.g., it does not grow). More...

#include <sparse.h>

Inheritance diagram for sparse_array< T >:

[legend]Collaboration diagram for sparse_array< T >:

[legend]List of all members.

Public Member Functions
void	init (const unsigned int size)
	sparse_array (const unsigned int size)
	sparse_array (const sparse_array< T > &a)
void	dealloc (void)
	An explicit destructor cannot be used, since the constructor is used to allocate memory.
unsigned int	two_to_n (unsigned int n)
unsigned int	get_power_of_two (const unsigned int val)
	get_power_of_two
void	add_leaf (const unsigned int top_ix)
void	insert (const T &val, const unsigned int ix)
T &	operator[] (const unsigned int i)
	both l-value and r-value forms of this operator operate by reference to avoid a copy constructor invokation.
int	probe (const unsigned int ix)
	probe is used by aliens on Nebraska farmers...
unsigned int	get_total_size ()
	This is the maximum number of elements that could be inserted into the array.
unsigned int	get_bytes_alloced (void)
unsigned int	get_percent_alloced (void)
Private Attributes
unsigned int	power
unsigned int	dimension_size
unsigned int	leafMask
unsigned int	bytes_alloced
T **	top

---

Detailed Description

template<class T>
class sparse_array< T >

Template class for a sparse array of fixed size (e.g., it does not grow).

This class is used as follows:

      sparse_array<my_type> a( 1024 );

This will create a sparse array object that can hold up to 1M items (1024 * 1024). This object is modeled after the hashed array tree object (see hat.h). Unlike the HAT, once it is allocated, the sparse array object size is fixed.

Definition at line 38 of file sparse.h.

---

Constructor & Destructor Documentation

template<class T> sparse_array< T >::sparse_array (  const unsigned int  size  )  [inline]

Definition at line 69 of file sparse.h. { init( size ); } // sparse_array constructor

template<class T> sparse_array< T >::sparse_array (  const sparse_array< T > &  a  )  [inline]

Definition at line 75 of file sparse.h. { init(0); (*this) = a; } // sparse_array

---

Member Function Documentation

template<class T> void sparse_array< T >::add_leaf (  const unsigned int  top_ix  )  [inline]

Definition at line 131 of file sparse.h. Referenced by sparse_array< chain_elem >::insert(). { assert( top[ top_ix ] == NULL ); top[ top_ix ] = new T [ dimension_size ]; memset( top[top_ix], 0, sizeof( T ) * dimension_size ); bytes_alloced += sizeof( T ) * dimension_size; } // add_leaf

template<class T> void sparse_array< T >::dealloc (  void   )  [inline]

An explicit destructor cannot be used, since the constructor is used to allocate memory. For example, in the sparse_array template is used as the base of the hash table. The hash_array object is dynamically allocated and then initialized with a size: *hash = sparse_array<sym_list>( hash_size ); This call invokes the constructor and the destructor, after the assignment is complete. If the destructor de-allocates the sparse array, future references to the hash table will fail since they reference deallocated memory. Definition at line 94 of file sparse.h. { unsigned int i; for (i = 0; i < dimension_size; i++) { if (top[i] != NULL) { delete [] top[ i ]; // delete the array pointed to by top[ i ] top[ i ] = NULL; } } if (top != NULL) { delete [] top; init(0); } } // dealloc

template<class T> unsigned int sparse_array< T >::get_bytes_alloced (  void   )  [inline]

Definition at line 193 of file sparse.h. { return bytes_alloced; };

template<class T> unsigned int sparse_array< T >::get_percent_alloced (  void   )

Definition at line 203 of file sparse.h. References sparse_array< T >::dimension_size, NULL, sparse_array< T >::top, and uint. { uint i; int top_used, trunc; float percent, tsize, used; trunc = 0; if (top != NULL) { top_used = 0; for (i = 0; i < dimension_size; i++) { if (top[ i ] != NULL) top_used++; } tsize = (float)dimension_size; used = (float)top_used; percent = (used / tsize) * (float)100; trunc = (int)percent; } return trunc; }

template<class T> unsigned int sparse_array< T >::get_power_of_two (  const unsigned int  val  )  [inline]

get_power_of_two Return the smallest power of two that is greater than or equal to val. Definition at line 119 of file sparse.h. Referenced by sparse_array< chain_elem >::init(). { const uint powerMin = 1; // set a resonable minimum uint p; for( p = powerMin; val > (uint)(1 << p); p++ ) /* nada */ ; return p; } // get_power_of_two

template<class T> unsigned int sparse_array< T >::get_total_size (   )  [inline]

This is the maximum number of elements that could be inserted into the array. This will always be a power of two. Definition at line 190 of file sparse.h. { return dimension_size * dimension_size; }

template<class T> void sparse_array< T >::init (  const unsigned int  size  )  [inline]

Definition at line 48 of file sparse.h. Referenced by sparse_array< chain_elem >::dealloc(), and sparse_array< chain_elem >::sparse_array(). { if (size > 0) { // round size up to the nearest power of two power = get_power_of_two( size ); dimension_size = two_to_n( power ); leafMask = dimension_size - 1; // (2^n) - 1 top = new T* [ dimension_size ]; bytes_alloced = sizeof( T *) * dimension_size; memset( (char *)top, 0, bytes_alloced ); // make sure that top is NULL } else { power = 0; dimension_size = 0; leafMask = 0; bytes_alloced = 0; top = NULL; } } // init

template<class T> void sparse_array< T >::insert (  const T &  val, const unsigned int  ix )  [inline]

Definition at line 140 of file sparse.h. { unsigned int top_ix = GetTopIndex(ix); unsigned int leaf_ix = GetLeafIndex(ix); assert( top_ix < dimension_size ); if (top[top_ix] == NULL) { add_leaf( top_ix ); } top[top_ix][ leaf_ix ] = val; } // insert

template<class T> T& sparse_array< T >::operator[] (  const unsigned int  i  )  [inline]

both l-value and r-value forms of this operator operate by reference to avoid a copy constructor invokation. Definition at line 159 of file sparse.h. { unsigned int top_ix = GetTopIndex(i); unsigned int leaf_ix = GetLeafIndex(i); assert( top_ix < dimension_size ); assert( top[ top_ix ] != NULL ); return top[ top_ix ][ leaf_ix ]; }

template<class T> int sparse_array< T >::probe (  const unsigned int  ix  )  [inline]

probe is used by aliens on Nebraska farmers... No, actually probe returns TRUE if an element has been allocated in the table slot with index ix. Definition at line 175 of file sparse.h. { int rslt = TRUE; unsigned int top_ix = GetTopIndex(ix); assert( top_ix < dimension_size ); if (top[top_ix] == NULL) { rslt = FALSE; } return rslt; }

template<class T> unsigned int sparse_array< T >::two_to_n (  unsigned int  n  )  [inline]

Definition at line 111 of file sparse.h. Referenced by sparse_array< chain_elem >::init(). { return 1 << (n & 0x1f); }

---

Member Data Documentation

template<class T> unsigned int sparse_array< T >::bytes_alloced [private]

Definition at line 44 of file sparse.h. Referenced by sparse_array< chain_elem >::add_leaf(), sparse_array< chain_elem >::get_bytes_alloced(), and sparse_array< chain_elem >::init().

template<class T> unsigned int sparse_array< T >::dimension_size [private]

Definition at line 42 of file sparse.h. Referenced by sparse_array< chain_elem >::add_leaf(), sparse_array< chain_elem >::dealloc(), sparse_array< T >::get_percent_alloced(), sparse_array< chain_elem >::get_total_size(), sparse_array< chain_elem >::init(), sparse_array< chain_elem >::insert(), sparse_array< chain_elem >::operator[](), and sparse_array< chain_elem >::probe().

template<class T> unsigned int sparse_array< T >::leafMask [private]

Definition at line 43 of file sparse.h. Referenced by sparse_array< chain_elem >::init().

template<class T> unsigned int sparse_array< T >::power [private]

Definition at line 41 of file sparse.h. Referenced by sparse_array< chain_elem >::init().

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

Definition at line 45 of file sparse.h. Referenced by sparse_array< chain_elem >::add_leaf(), sparse_array< chain_elem >::dealloc(), sparse_array< T >::get_percent_alloced(), sparse_array< chain_elem >::init(), sparse_array< chain_elem >::insert(), sparse_array< chain_elem >::operator[](), and sparse_array< chain_elem >::probe().

---

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

• sparse.h

---