 |
Mesh Oriented datABase
(version 5.5.1)
An array-based unstructured mesh library
|
|
Mesh Oriented datABase
(version 5.5.1)
An array-based unstructured mesh library
|
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 <climits>
19 #include <cstdlib>
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 ~buffer()
105 {
106 this->reset();
107 };
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 ~TupleList()
136 {
137 reset();
138 };
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,
341 Index n,
342 Index stride,
343 unsigned sh,
344 Index* off,
345 SortData< Value >* out );
346
347 template < class Value >
348 static void radix_index_pass_m( const SortData< Value >* src,
349 const SortData< Value >* end,
350 unsigned sh,
351 Index* off,
352 SortData< Value >* out );
353
354 template < class Value >
355 static void radix_index_pass_e( const SortData< Value >* src,
356 const SortData< Value >* end,
357 unsigned sh,
358 Index* off,
359 Index* out );
360
361 template < class Value >
362 static void radix_index_pass_be( const Value* A, Index n, Index stride, unsigned sh, Index* off, Index* out );
363
364 /*------------------------------------------------------------------------------
365
366
367 Radix Sort
368
369 stable; O(n) time
370
371 ----------------------------------------------------------------------------*/
372 template < class Value >
373 static void radix_index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );
374
375 /*------------------------------------------------------------------------------
376
377
378 Merge Sort
379
380 stable; O(n log n) time
381
382 ----------------------------------------------------------------------------*/
383 template < class Value >
384 static void merge_index_sort( const Value* A, const Index An, Index stride, Index* idx, SortData< Value >* work );
385
386 template < class Value >
387 static void index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );
388
389 #undef DIGIT_BITS
390 #undef DIGIT_VALUES
391 #undef DIGIT_MASK
392 #undef CEILDIV
393 #undef DIGITS
394 #undef VALUE_BITS
395 #undef COUNT_SIZE
396 };
397
398 inline uint TupleList::get_max() const
399 {
400 return max;
401 }
402 inline uint TupleList::get_n() const
403 {
404 return n;
405 }
406 inline bool TupleList::get_writeEnabled() const
407 {
408 return writeEnabled;
409 }
410
411 } // namespace moab
412 #endif
413 #include <cstdlib>
1.9.1.