#include <sparse.h>
Inheritance diagram for sparse_array< T >:
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 |
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
|
Definition at line 69 of file sparse.h.
00070 { 00071 init( size ); 00072 } // sparse_array constructor |
|
Definition at line 75 of file sparse.h.
00076 { 00077 init(0); 00078 (*this) = a; 00079 } // sparse_array |
|
Definition at line 131 of file sparse.h. Referenced by sparse_array< chain_elem >::insert().
00132 { 00133 assert( top[ top_ix ] == NULL ); 00134 00135 top[ top_ix ] = new T [ dimension_size ]; 00136 memset( top[top_ix], 0, sizeof( T ) * dimension_size ); 00137 bytes_alloced += sizeof( T ) * dimension_size; 00138 } // add_leaf |
|
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:
|
|
Definition at line 193 of file sparse.h.
00193 { return bytes_alloced; }; |
|
Definition at line 203 of file sparse.h. References sparse_array< T >::dimension_size, NULL, sparse_array< T >::top, and uint.
00204 { 00205 uint i; 00206 int top_used, trunc; 00207 float percent, tsize, used; 00208 00209 trunc = 0; 00210 if (top != NULL) { 00211 top_used = 0; 00212 for (i = 0; i < dimension_size; i++) { 00213 if (top[ i ] != NULL) 00214 top_used++; 00215 } 00216 tsize = (float)dimension_size; 00217 used = (float)top_used; 00218 percent = (used / tsize) * (float)100; 00219 trunc = (int)percent; 00220 } 00221 00222 return trunc; 00223 } |
|
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().
|
|
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.
00190 { return dimension_size * dimension_size; } |
|
Definition at line 48 of file sparse.h. Referenced by sparse_array< chain_elem >::dealloc(), and sparse_array< chain_elem >::sparse_array().
00049 { 00050 if (size > 0) { 00051 // round size up to the nearest power of two 00052 power = get_power_of_two( size ); 00053 dimension_size = two_to_n( power ); 00054 leafMask = dimension_size - 1; // (2^n) - 1 00055 00056 top = new T* [ dimension_size ]; 00057 bytes_alloced = sizeof( T *) * dimension_size; 00058 memset( (char *)top, 0, bytes_alloced ); // make sure that top is NULL 00059 } 00060 else { 00061 power = 0; 00062 dimension_size = 0; 00063 leafMask = 0; 00064 bytes_alloced = 0; 00065 top = NULL; 00066 } 00067 } // init |
|
Definition at line 140 of file sparse.h.
00141 { 00142 unsigned int top_ix = GetTopIndex(ix); 00143 unsigned int leaf_ix = GetLeafIndex(ix); 00144 00145 assert( top_ix < dimension_size ); 00146 if (top[top_ix] == NULL) { 00147 add_leaf( top_ix ); 00148 } 00149 00150 top[top_ix][ leaf_ix ] = val; 00151 } // insert |
|
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.
00160 { 00161 unsigned int top_ix = GetTopIndex(i); 00162 unsigned int leaf_ix = GetLeafIndex(i); 00163 00164 assert( top_ix < dimension_size ); 00165 assert( top[ top_ix ] != NULL ); 00166 return top[ top_ix ][ leaf_ix ]; 00167 } |
|
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.
00176 { 00177 int rslt = TRUE; 00178 unsigned int top_ix = GetTopIndex(ix); 00179 00180 assert( top_ix < dimension_size ); 00181 if (top[top_ix] == NULL) { 00182 rslt = FALSE; 00183 } 00184 return rslt; 00185 } |
|
Definition at line 111 of file sparse.h. Referenced by sparse_array< chain_elem >::init().
00111 { return 1 << (n & 0x1f); }
|
|
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(). |
|
|
Definition at line 43 of file sparse.h. Referenced by sparse_array< chain_elem >::init(). |
|
Definition at line 41 of file sparse.h. Referenced by sparse_array< chain_elem >::init(). |
|