Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
TupleList.hpp
Go to the documentation of this file.
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 
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 
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  */
130 
131  /**Default constructor (Note: TupleList must be initialized before use!)
132  */
133  TupleList();
134 
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  */
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
283 
284  // Variables to allow for direct read access
285  const sint* vi_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 */
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) */
310  // Whether or not the object is currently allowing direct
311  // write access to the arrays
313 
314  typedef uint Index;
315 
316  template < typename Value >
317  struct SortData
318  {
319  Value v;
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>