MOAB: Mesh Oriented datABase  (version 5.4.1)
TupleList.hpp
Go to the documentation of this file.
00001 /*-----------------------------------------------------------------------------
00002 
00003   Tuple list definition and utilities
00004 
00005   Conceptually, a tuple list is a list of n records or tuples,
00006   each with mi integers, ml longs, mul Ulongs, and mr reals
00007   (these types are defined in "types.h" as sint, slong, moab::EntityHandle, real;
00008   it may be that sint==slong)
00009 
00010   There are four arrays, one for each type (vi,vl,vul,vr),
00011   with records layed out contiguously within each array
00012 
00013   -----------------------------------------------------------------------------*/
00014 
00015 #ifndef TUPLE_LIST_HPP
00016 #define TUPLE_LIST_HPP
00017 
00018 #include <climits>
00019 #include <cstdlib>
00020 
00021 #include "moab/Types.hpp"
00022 #include <string>
00023 
00024 /* Integral types defined here to ensure variable type sizes are consistent */
00025 /* integer type to use for everything */
00026 #if defined( USE_LONG )
00027 #define INTEGER long
00028 #elif defined( USE_LONG_LONG )
00029 #define INTEGER long long
00030 #elif defined( USE_SHORT )
00031 #define INTEGER short
00032 #else
00033 #define INTEGER int
00034 #endif
00035 
00036 /* when defined, use the given type for global indices instead of INTEGER */
00037 #if defined( USE_GLOBAL_LONG_LONG )
00038 #define GLOBAL_INT long long
00039 #elif defined( USE_GLOBAL_LONG )
00040 #define GLOBAL_INT long
00041 #else
00042 #define GLOBAL_INT long
00043 #endif
00044 
00045 /* floating point type to use for everything */
00046 #if defined( USE_FLOAT )
00047 typedef float realType;
00048 #elif defined( USE_LONG_DOUBLE )
00049 typedef long double realType;
00050 #else
00051 typedef double realType;
00052 #endif
00053 
00054 /* apparently uint and ulong can be defined already in standard headers */
00055 #define uint uint_
00056 //#define ulong ulong_
00057 #define sint  sint_
00058 #define slong slong_
00059 
00060 typedef signed INTEGER sint;
00061 typedef unsigned INTEGER uint;
00062 #undef INTEGER
00063 
00064 #ifdef GLOBAL_INT
00065 typedef signed GLOBAL_INT slong;
00066 // typedef unsigned GLOBAL_INT ulong;
00067 #else
00068 typedef sint slong;
00069 // typedef uint ulong;
00070 #endif
00071 
00072 typedef moab::EntityHandle Ulong;
00073 
00074 namespace moab
00075 {
00076 void fail( const char* fmt, ... );
00077 
00078 class TupleList
00079 {
00080   public:
00081     /*---------------------------------------------------------------------------
00082 
00083       buffer: a simple class which can be used to store data
00084 
00085       The ptr points to the chunk of memory allocated for the buffer's use.  The
00086       size denotes the size of the allocated memory; the user must take care to
00087       note how much of the buffer they are using.
00088 
00089       ---------------------------------------------------------------------------*/
00090     class buffer
00091     {
00092       public:
00093         size_t buffSize;
00094         char* ptr;
00095 
00096         /**Constructor which sets an initial capacity of the buffer
00097          */
00098         buffer( size_t sz );
00099 
00100         /**Default constructor (Note:  buffer must be initialized before use!)
00101          */
00102         buffer();
00103 
00104         ~buffer()
00105         {
00106             this->reset();
00107         };
00108 
00109         /**Initializes the buffer to have a capacity of size
00110          */
00111         void buffer_init_( size_t sz, const char* file );
00112 
00113         /**Ensures that the buffer has at least a capacity of min
00114          */
00115         void buffer_reserve_( size_t min, const char* file );
00116 
00117         /**Frees any allocated memory used by the buffer
00118          */
00119         void reset();
00120 
00121         // Aliases for using the buffer methods
00122 #define buffer_init( sz )     buffer_init_( sz, __FILE__ )
00123 #define buffer_reserve( min ) buffer_reserve_( min, __FILE__ )
00124     };
00125 
00126   public:
00127     /**Constructor that takes all parameters and initializes the TupleList
00128      */
00129     TupleList( uint mi, uint ml, uint mul, uint mr, uint max );
00130 
00131     /**Default constructor (Note:  TupleList must be initialized before use!)
00132      */
00133     TupleList();
00134 
00135     ~TupleList()
00136     {
00137         reset();
00138     };
00139 
00140     /**Initializes the starting memory to be used by the TupleList
00141      * Note:  TupleLists must be initialized before they can be used
00142      *
00143      * param mi   number of signed ints in each tuple
00144      * param ml   number of long ints in each tuple
00145      * param mul  number of unsigned long ints in each tuple
00146      * param mr   number of reals in each tuple
00147      * param max  starting capacity of max tuples in the TupleList
00148      */
00149     void initialize( uint mi, uint ml, uint mul, uint mr, uint max );
00150 
00151     /**Resizes the TupleList to a new max
00152      *
00153      * param max   the new max capacity of the TupleList
00154      */
00155     ErrorCode resize( uint max );
00156 
00157     /**Sorts the TupleList by 'key'
00158      * if key<mi:  key represents the key'th index in vi
00159      * if mi<key<ml:  key represents the (key-mi)'th index in vl
00160      * if ml<key<mul:  key represents the (key-mi-ml)'th index in vul
00161      *
00162      * param key   index to be sorted by
00163      * param *buf  buffer space used for sorting
00164      */
00165     /*------------------------------------------------------------------------------
00166 
00167       Hybrid Stable Sort
00168 
00169       low-overhead merge sort when n is small,
00170       otherwise asymptotically superior radix sort
00171 
00172       result = O(n) sort with good performance for all n
00173 
00174       A, n, stride : specifices the input
00175 
00176       sort:
00177       uint out[n] : the sorted values (output)
00178       uint work[n]: scratch area
00179 
00180       index_sort:
00181       uint idx[n]  : the sorted indices (output)
00182       sort_data work[2*n]: scratch area
00183 
00184       ----------------------------------------------------------------------------*/
00185     ErrorCode sort( uint key, TupleList::buffer* buf );
00186 
00187     /**Frees all allocated memory in use by the TupleList
00188      */
00189     void reset();
00190 
00191     /**Adds one to the total number of in-use tuples and resizes if necessary
00192      */
00193     void reserve();
00194 
00195     /**Finds index of the tuple containing 'value' at the key_numth index of
00196      * said tuple; return -1 if key_num is out of bounds or if 'value' not found
00197      * Uses binary search if TupleList is sorted by the key_numth field, seqential
00198      * otherwise (very slow for large TupleLists; please sort before you search)
00199      *
00200      * param key_num   index of the tuple where to search for value
00201      * param value     value to search for at the given key_num
00202      * return the index of the tuple that contains value
00203      */
00204     int find( unsigned int key_num, sint value );
00205     int find( unsigned int key_num, slong value );
00206     int find( unsigned int key_num, Ulong value );
00207     int find( unsigned int key_num, realType value );
00208 
00209     /**get the mth number of return type in the index'th tuple
00210      * returns 0 if m or index is out of bounds
00211      *
00212      * param index     index of the tuple within the TupleList
00213      * param m         index of the value within the tuple
00214      * return the value at the given position
00215      */
00216     sint get_sint( unsigned int index, unsigned int m );
00217     slong get_int( unsigned int index, unsigned int m );
00218     Ulong get_ulong( unsigned int index, unsigned int m );
00219     realType get_double( unsigned int index, unsigned int m );
00220 
00221     /**get pointers to the data for the index'th tuple; ptr is
00222      * NULL if that type is not part of this tuple
00223      *
00224      * param index     index of the tuple needed
00225      * param *&sp, *&ip, *&lp, *&dp   pointers to each piece of the tuple
00226      */
00227     ErrorCode get( unsigned int index, const sint*& sp, const slong*& ip, const Ulong*& lp, const realType*& dp );
00228 
00229     /**push back a new tuple on the TupleList;
00230      *
00231      * param *sp   pointer to a list of signed ints
00232      * param *ip   pointer to a list of signed longs
00233      * param *lp   pointer to a list of unsigned longs
00234      * param *dp   pointer to a list of reals
00235      * return index of that tuple
00236      */
00237     unsigned int push_back( sint* sp, slong* ip, Ulong* lp, realType* dp );
00238 
00239     /*Enable or disable direct write access to arrays
00240       This is important so that we know whether or not
00241       the user of this class can directly modify data
00242       which can affect operations such as
00243       whether or not we know the tuple list is sorted
00244       (for a binary search)*/
00245     void enableWriteAccess();
00246     void disableWriteAccess();
00247 
00248     /*Get information on the Tuple Sizes
00249      * param &mi_out  Count of uints in a tuple
00250      * param &ml_out  Count of uints in a tuple
00251      * param &mul_out Count of uints in a tuple
00252      * param &mr_out  Count of uints in a tuple
00253      */
00254     void getTupleSize( uint& mi_out, uint& ml_out, uint& mul_out, uint& mr_out ) const;
00255 
00256     /*Set the count of Tuples in the Tuple List
00257      * Warning, automatically calls enableWriteAccess()
00258      * param n_in     New count of Tuples
00259      */
00260     void set_n( uint n_in );
00261 
00262     /* Get the count of Tuples in the Tuple List */
00263     uint get_n() const;
00264 
00265     /*Get the maximum number of Tuples currently allocated for*/
00266     uint get_max() const;
00267 
00268     bool get_writeEnabled() const;
00269 
00270     /*Increment n by 1
00271      * Warning, automatically calls enableWriteAccess()
00272      * returns current TupleList.n after the increment */
00273     uint inc_n();
00274 
00275     void print( const char* ) const;
00276     void print_to_file( const char* ) const;
00277 
00278     // Variables to allow for direct write access
00279     sint* vi_wr;
00280     slong* vl_wr;
00281     Ulong* vul_wr;
00282     realType* vr_wr;
00283 
00284     // Variables to allow for direct read access
00285     const sint* vi_rd;
00286     slong* vl_rd;
00287     Ulong* vul_rd;
00288     realType* vr_rd;
00289 
00290   private:
00291     /* storage layed out as: vi[max][mi], vl[max][ml], vul[max][mul],
00292      * vr[max][mr] where "tuple" i is given by
00293      * (vi[i][0:mi-1],vl[i][0:ml-1],vul[i][0:mul-1],vr[i][0:mr-1]).
00294      * only the first n tuples are in use */
00295     uint mi, ml, mul, mr;
00296     uint n, max;
00297     sint* vi;
00298     slong* vl;
00299     Ulong* vul;
00300     realType* vr;
00301 
00302     // Used by sort:  see .cpp for more details
00303     // void sort_bits(uint *work, uint key);
00304     void permute( uint* perm, void* work );
00305 
00306     /* last_sorted = the last sorted position in the tuple (if the
00307      * TupleList has not been sorted, or has become unsorted--i.e.
00308      * by adding a tuple--last_sorted = -1) */
00309     int last_sorted;
00310     // Whether or not the object is currently allowing direct
00311     // write access to the arrays
00312     bool writeEnabled;
00313 
00314     typedef uint Index;
00315 
00316     template < typename Value >
00317     struct SortData
00318     {
00319         Value v;
00320         Index i;
00321     };
00322 
00323 #define DIGIT_BITS      8
00324 #define DIGIT_VALUES    ( 1 << DIGIT_BITS )
00325 #define DIGIT_MASK      ( (Value)( DIGIT_VALUES - 1 ) )
00326 #define CEILDIV( a, b ) ( ( ( a ) + (b)-1 ) / ( b ) )
00327 #define DIGITS          CEILDIV( CHAR_BIT * sizeof( Value ), DIGIT_BITS )
00328 #define VALUE_BITS      ( DIGIT_BITS * DIGITS )
00329 #define COUNT_SIZE      ( DIGITS * DIGIT_VALUES )
00330 
00331     template < class Value >
00332     static Value radix_count( const Value* A, const Value* end, Index stride, Index count[DIGITS][DIGIT_VALUES] );
00333 
00334     static void radix_offsets( Index* c );
00335 
00336     template < class Value >
00337     static unsigned radix_zeros( Value bitorkey, Index count[DIGITS][DIGIT_VALUES], unsigned* shift, Index** offsets );
00338 
00339     template < class Value >
00340     static void radix_index_pass_b( const Value* A,
00341                                     Index n,
00342                                     Index stride,
00343                                     unsigned sh,
00344                                     Index* off,
00345                                     SortData< Value >* out );
00346 
00347     template < class Value >
00348     static void radix_index_pass_m( const SortData< Value >* src,
00349                                     const SortData< Value >* end,
00350                                     unsigned sh,
00351                                     Index* off,
00352                                     SortData< Value >* out );
00353 
00354     template < class Value >
00355     static void radix_index_pass_e( const SortData< Value >* src,
00356                                     const SortData< Value >* end,
00357                                     unsigned sh,
00358                                     Index* off,
00359                                     Index* out );
00360 
00361     template < class Value >
00362     static void radix_index_pass_be( const Value* A, Index n, Index stride, unsigned sh, Index* off, Index* out );
00363 
00364     /*------------------------------------------------------------------------------
00365 
00366 
00367       Radix Sort
00368 
00369       stable; O(n) time
00370 
00371       ----------------------------------------------------------------------------*/
00372     template < class Value >
00373     static void radix_index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );
00374 
00375     /*------------------------------------------------------------------------------
00376 
00377 
00378       Merge Sort
00379 
00380       stable; O(n log n) time
00381 
00382       ----------------------------------------------------------------------------*/
00383     template < class Value >
00384     static void merge_index_sort( const Value* A, const Index An, Index stride, Index* idx, SortData< Value >* work );
00385 
00386     template < class Value >
00387     static void index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );
00388 
00389 #undef DIGIT_BITS
00390 #undef DIGIT_VALUES
00391 #undef DIGIT_MASK
00392 #undef CEILDIV
00393 #undef DIGITS
00394 #undef VALUE_BITS
00395 #undef COUNT_SIZE
00396 };
00397 
00398 inline uint TupleList::get_max() const
00399 {
00400     return max;
00401 }
00402 inline uint TupleList::get_n() const
00403 {
00404     return n;
00405 }
00406 inline bool TupleList::get_writeEnabled() const
00407 {
00408     return writeEnabled;
00409 }
00410 
00411 }  // namespace moab
00412 #endif
00413 #include <cstdlib>
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines