Branch data Line data Source code
1 : : /*-----------------------------------------------------------------------------
2 : :
3 : : Tuple list definition and utilities
4 : :
5 : : Conceptually, a tuple list is a list of n records or tuples,
6 : : each with mi integers, ml longs, mul Ulongs, and mr reals
7 : : (these types are defined in "types.h" as sint, slong, moab::EntityHandle, real;
8 : : it may be that sint==slong)
9 : :
10 : : There are four arrays, one for each type (vi,vl,vul,vr),
11 : : with records layed out contiguously within each array
12 : :
13 : : -----------------------------------------------------------------------------*/
14 : :
15 : : #ifndef TUPLE_LIST_HPP
16 : : #define TUPLE_LIST_HPP
17 : :
18 : : #include <limits.h>
19 : : #include <stdlib.h>
20 : :
21 : : #include "moab/Types.hpp"
22 : : #include <string>
23 : :
24 : : /* Integral types defined here to ensure variable type sizes are consistent */
25 : : /* integer type to use for everything */
26 : : #if defined( USE_LONG )
27 : : #define INTEGER long
28 : : #elif defined( USE_LONG_LONG )
29 : : #define INTEGER long long
30 : : #elif defined( USE_SHORT )
31 : : #define INTEGER short
32 : : #else
33 : : #define INTEGER int
34 : : #endif
35 : :
36 : : /* when defined, use the given type for global indices instead of INTEGER */
37 : : #if defined( USE_GLOBAL_LONG_LONG )
38 : : #define GLOBAL_INT long long
39 : : #elif defined( USE_GLOBAL_LONG )
40 : : #define GLOBAL_INT long
41 : : #else
42 : : #define GLOBAL_INT long
43 : : #endif
44 : :
45 : : /* floating point type to use for everything */
46 : : #if defined( USE_FLOAT )
47 : : typedef float realType;
48 : : #elif defined( USE_LONG_DOUBLE )
49 : : typedef long double realType;
50 : : #else
51 : : typedef double realType;
52 : : #endif
53 : :
54 : : /* apparently uint and ulong can be defined already in standard headers */
55 : : #define uint uint_
56 : : //#define ulong ulong_
57 : : #define sint sint_
58 : : #define slong slong_
59 : :
60 : : typedef signed INTEGER sint;
61 : : typedef unsigned INTEGER uint;
62 : : #undef INTEGER
63 : :
64 : : #ifdef GLOBAL_INT
65 : : typedef signed GLOBAL_INT slong;
66 : : // typedef unsigned GLOBAL_INT ulong;
67 : : #else
68 : : typedef sint slong;
69 : : // typedef uint ulong;
70 : : #endif
71 : :
72 : : typedef moab::EntityHandle Ulong;
73 : :
74 : : namespace moab
75 : : {
76 : : void fail( const char* fmt, ... );
77 : :
78 : : class TupleList
79 : : {
80 : : public:
81 : : /*---------------------------------------------------------------------------
82 : :
83 : : buffer: a simple class which can be used to store data
84 : :
85 : : The ptr points to the chunk of memory allocated for the buffer's use. The
86 : : size denotes the size of the allocated memory; the user must take care to
87 : : note how much of the buffer they are using.
88 : :
89 : : ---------------------------------------------------------------------------*/
90 : : class buffer
91 : : {
92 : : public:
93 : : size_t buffSize;
94 : : char* ptr;
95 : :
96 : : /**Constructor which sets an initial capacity of the buffer
97 : : */
98 : : buffer( size_t sz );
99 : :
100 : : /**Default constructor (Note: buffer must be initialized before use!)
101 : : */
102 : : buffer();
103 : :
104 : 5 : ~buffer()
105 : : {
106 : 5 : this->reset();
107 : 5 : };
108 : :
109 : : /**Initializes the buffer to have a capacity of size
110 : : */
111 : : void buffer_init_( size_t sz, const char* file );
112 : :
113 : : /**Ensures that the buffer has at least a capacity of min
114 : : */
115 : : void buffer_reserve_( size_t min, const char* file );
116 : :
117 : : /**Frees any allocated memory used by the buffer
118 : : */
119 : : void reset();
120 : :
121 : : // Aliases for using the buffer methods
122 : : #define buffer_init( sz ) buffer_init_( sz, __FILE__ )
123 : : #define buffer_reserve( min ) buffer_reserve_( min, __FILE__ )
124 : : };
125 : :
126 : : public:
127 : : /**Constructor that takes all parameters and initializes the TupleList
128 : : */
129 : : TupleList( uint mi, uint ml, uint mul, uint mr, uint max );
130 : :
131 : : /**Default constructor (Note: TupleList must be initialized before use!)
132 : : */
133 : : TupleList();
134 : :
135 : 9 : ~TupleList()
136 : : {
137 : 9 : reset();
138 : 9 : };
139 : :
140 : : /**Initializes the starting memory to be used by the TupleList
141 : : * Note: TupleLists must be initialized before they can be used
142 : : *
143 : : * param mi number of signed ints in each tuple
144 : : * param ml number of long ints in each tuple
145 : : * param mul number of unsigned long ints in each tuple
146 : : * param mr number of reals in each tuple
147 : : * param max starting capacity of max tuples in the TupleList
148 : : */
149 : : void initialize( uint mi, uint ml, uint mul, uint mr, uint max );
150 : :
151 : : /**Resizes the TupleList to a new max
152 : : *
153 : : * param max the new max capacity of the TupleList
154 : : */
155 : : ErrorCode resize( uint max );
156 : :
157 : : /**Sorts the TupleList by 'key'
158 : : * if key<mi: key represents the key'th index in vi
159 : : * if mi<key<ml: key represents the (key-mi)'th index in vl
160 : : * if ml<key<mul: key represents the (key-mi-ml)'th index in vul
161 : : *
162 : : * param key index to be sorted by
163 : : * param *buf buffer space used for sorting
164 : : */
165 : : /*------------------------------------------------------------------------------
166 : :
167 : : Hybrid Stable Sort
168 : :
169 : : low-overhead merge sort when n is small,
170 : : otherwise asymptotically superior radix sort
171 : :
172 : : result = O(n) sort with good performance for all n
173 : :
174 : : A, n, stride : specifices the input
175 : :
176 : : sort:
177 : : uint out[n] : the sorted values (output)
178 : : uint work[n]: scratch area
179 : :
180 : : index_sort:
181 : : uint idx[n] : the sorted indices (output)
182 : : sort_data work[2*n]: scratch area
183 : :
184 : : ----------------------------------------------------------------------------*/
185 : : ErrorCode sort( uint key, TupleList::buffer* buf );
186 : :
187 : : /**Frees all allocated memory in use by the TupleList
188 : : */
189 : : void reset();
190 : :
191 : : /**Adds one to the total number of in-use tuples and resizes if necessary
192 : : */
193 : : void reserve();
194 : :
195 : : /**Finds index of the tuple containing 'value' at the key_numth index of
196 : : * said tuple; return -1 if key_num is out of bounds or if 'value' not found
197 : : * Uses binary search if TupleList is sorted by the key_numth field, seqential
198 : : * otherwise (very slow for large TupleLists; please sort before you search)
199 : : *
200 : : * param key_num index of the tuple where to search for value
201 : : * param value value to search for at the given key_num
202 : : * return the index of the tuple that contains value
203 : : */
204 : : int find( unsigned int key_num, sint value );
205 : : int find( unsigned int key_num, slong value );
206 : : int find( unsigned int key_num, Ulong value );
207 : : int find( unsigned int key_num, realType value );
208 : :
209 : : /**get the mth number of return type in the index'th tuple
210 : : * returns 0 if m or index is out of bounds
211 : : *
212 : : * param index index of the tuple within the TupleList
213 : : * param m index of the value within the tuple
214 : : * return the value at the given position
215 : : */
216 : : sint get_sint( unsigned int index, unsigned int m );
217 : : slong get_int( unsigned int index, unsigned int m );
218 : : Ulong get_ulong( unsigned int index, unsigned int m );
219 : : realType get_double( unsigned int index, unsigned int m );
220 : :
221 : : /**get pointers to the data for the index'th tuple; ptr is
222 : : * NULL if that type is not part of this tuple
223 : : *
224 : : * param index index of the tuple needed
225 : : * param *&sp, *&ip, *&lp, *&dp pointers to each piece of the tuple
226 : : */
227 : : ErrorCode get( unsigned int index, const sint*& sp, const slong*& ip, const Ulong*& lp, const realType*& dp );
228 : :
229 : : /**push back a new tuple on the TupleList;
230 : : *
231 : : * param *sp pointer to a list of signed ints
232 : : * param *ip pointer to a list of signed longs
233 : : * param *lp pointer to a list of unsigned longs
234 : : * param *dp pointer to a list of reals
235 : : * return index of that tuple
236 : : */
237 : : unsigned int push_back( sint* sp, slong* ip, Ulong* lp, realType* dp );
238 : :
239 : : /*Enable or disable direct write access to arrays
240 : : This is important so that we know whether or not
241 : : the user of this class can directly modify data
242 : : which can affect operations such as
243 : : whether or not we know the tuple list is sorted
244 : : (for a binary search)*/
245 : : void enableWriteAccess();
246 : : void disableWriteAccess();
247 : :
248 : : /*Get information on the Tuple Sizes
249 : : * param &mi_out Count of uints in a tuple
250 : : * param &ml_out Count of uints in a tuple
251 : : * param &mul_out Count of uints in a tuple
252 : : * param &mr_out Count of uints in a tuple
253 : : */
254 : : void getTupleSize( uint& mi_out, uint& ml_out, uint& mul_out, uint& mr_out ) const;
255 : :
256 : : /*Set the count of Tuples in the Tuple List
257 : : * Warning, automatically calls enableWriteAccess()
258 : : * param n_in New count of Tuples
259 : : */
260 : : void set_n( uint n_in );
261 : :
262 : : /* Get the count of Tuples in the Tuple List */
263 : : uint get_n() const;
264 : :
265 : : /*Get the maximum number of Tuples currently allocated for*/
266 : : uint get_max() const;
267 : :
268 : : bool get_writeEnabled() const;
269 : :
270 : : /*Increment n by 1
271 : : * Warning, automatically calls enableWriteAccess()
272 : : * returns current TupleList.n after the increment */
273 : : uint inc_n();
274 : :
275 : : void print( const char* ) const;
276 : : void print_to_file( const char* ) const;
277 : :
278 : : // Variables to allow for direct write access
279 : : sint* vi_wr;
280 : : slong* vl_wr;
281 : : Ulong* vul_wr;
282 : : realType* vr_wr;
283 : :
284 : : // Variables to allow for direct read access
285 : : const sint* vi_rd;
286 : : slong* vl_rd;
287 : : Ulong* vul_rd;
288 : : realType* vr_rd;
289 : :
290 : : private:
291 : : /* storage layed out as: vi[max][mi], vl[max][ml], vul[max][mul],
292 : : * vr[max][mr] where "tuple" i is given by
293 : : * (vi[i][0:mi-1],vl[i][0:ml-1],vul[i][0:mul-1],vr[i][0:mr-1]).
294 : : * only the first n tuples are in use */
295 : : uint mi, ml, mul, mr;
296 : : uint n, max;
297 : : sint* vi;
298 : : slong* vl;
299 : : Ulong* vul;
300 : : realType* vr;
301 : :
302 : : // Used by sort: see .cpp for more details
303 : : // void sort_bits(uint *work, uint key);
304 : : void permute( uint* perm, void* work );
305 : :
306 : : /* last_sorted = the last sorted position in the tuple (if the
307 : : * TupleList has not been sorted, or has become unsorted--i.e.
308 : : * by adding a tuple--last_sorted = -1) */
309 : : int last_sorted;
310 : : // Whether or not the object is currently allowing direct
311 : : // write access to the arrays
312 : : bool writeEnabled;
313 : :
314 : : typedef uint Index;
315 : :
316 : : template < typename Value >
317 : : struct SortData
318 : : {
319 : : Value v;
320 : : Index i;
321 : : };
322 : :
323 : : #define DIGIT_BITS 8
324 : : #define DIGIT_VALUES ( 1 << DIGIT_BITS )
325 : : #define DIGIT_MASK ( ( Value )( DIGIT_VALUES - 1 ) )
326 : : #define CEILDIV( a, b ) ( ( ( a ) + (b)-1 ) / ( b ) )
327 : : #define DIGITS CEILDIV( CHAR_BIT * sizeof( Value ), DIGIT_BITS )
328 : : #define VALUE_BITS ( DIGIT_BITS * DIGITS )
329 : : #define COUNT_SIZE ( DIGITS * DIGIT_VALUES )
330 : :
331 : : template < class Value >
332 : : static Value radix_count( const Value* A, const Value* end, Index stride, Index count[DIGITS][DIGIT_VALUES] );
333 : :
334 : : static void radix_offsets( Index* c );
335 : :
336 : : template < class Value >
337 : : static unsigned radix_zeros( Value bitorkey, Index count[DIGITS][DIGIT_VALUES], unsigned* shift, Index** offsets );
338 : :
339 : : template < class Value >
340 : : static void radix_index_pass_b( const Value* A, Index n, Index stride, unsigned sh, Index* off,
341 : : SortData< Value >* out );
342 : :
343 : : template < class Value >
344 : : static void radix_index_pass_m( const SortData< Value >* src, const SortData< Value >* end, unsigned sh, Index* off,
345 : : SortData< Value >* out );
346 : :
347 : : template < class Value >
348 : : static void radix_index_pass_e( const SortData< Value >* src, const SortData< Value >* end, unsigned sh, Index* off,
349 : : Index* out );
350 : :
351 : : template < class Value >
352 : : static void radix_index_pass_be( const Value* A, Index n, Index stride, unsigned sh, Index* off, Index* out );
353 : :
354 : : /*------------------------------------------------------------------------------
355 : :
356 : :
357 : : Radix Sort
358 : :
359 : : stable; O(n) time
360 : :
361 : : ----------------------------------------------------------------------------*/
362 : : template < class Value >
363 : : static void radix_index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );
364 : :
365 : : /*------------------------------------------------------------------------------
366 : :
367 : :
368 : : Merge Sort
369 : :
370 : : stable; O(n log n) time
371 : :
372 : : ----------------------------------------------------------------------------*/
373 : : template < class Value >
374 : : static void merge_index_sort( const Value* A, const Index An, Index stride, Index* idx, SortData< Value >* work );
375 : :
376 : : template < class Value >
377 : : static void index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );
378 : :
379 : : #undef DIGIT_BITS
380 : : #undef DIGIT_VALUES
381 : : #undef DIGIT_MASK
382 : : #undef CEILDIV
383 : : #undef DIGITS
384 : : #undef VALUE_BITS
385 : : #undef COUNT_SIZE
386 : : };
387 : :
388 : 0 : inline uint TupleList::get_max() const
389 : : {
390 : 0 : return max;
391 : : }
392 : 0 : inline uint TupleList::get_n() const
393 : : {
394 : 0 : return n;
395 : : }
396 : 0 : inline bool TupleList::get_writeEnabled() const
397 : : {
398 : 0 : return writeEnabled;
399 : : }
400 : :
401 : : } // namespace moab
402 : : #endif
403 : : #include <stdlib.h>
|
