TupleList.hpp

Go to the documentation of this file.

/*-----------------------------------------------------------------------------

  Tuple list definition and utilities

  Conceptually, a tuple list is a list of n records or tuples,
  each with mi integers, ml longs, mul Ulongs, and mr reals
  (these types are defined in "types.h" as sint, slong, moab::EntityHandle, real;
  it may be that sint==slong)

  There are four arrays, one for each type (vi,vl,vul,vr),
  with records layed out contiguously within each array

  -----------------------------------------------------------------------------*/

#ifndef TUPLE_LIST_HPP
#define TUPLE_LIST_HPP

#include 
#include 

#include "moab/Types.hpp"
#include 

/* Integral types defined here to ensure variable type sizes are consistent */
/* integer type to use for everything */
#if defined( USE_LONG )
#define INTEGER long
#elif defined( USE_LONG_LONG )
#define INTEGER long long
#elif defined( USE_SHORT )
#define INTEGER short
#else
#define INTEGER int
#endif

/* when defined, use the given type for global indices instead of INTEGER */
#if defined( USE_GLOBAL_LONG_LONG )
#define GLOBAL_INT long long
#elif defined( USE_GLOBAL_LONG )
#define GLOBAL_INT long
#else
#define GLOBAL_INT long
#endif

/* floating point type to use for everything */
#if defined( USE_FLOAT )
typedef float realType;
#elif defined( USE_LONG_DOUBLE )
typedef long double realType;
#else
typedef double realType;
#endif

/* apparently uint and ulong can be defined already in standard headers */
#define uint uint_
//#define ulong ulong_
#define sint  sint_
#define slong slong_

typedef signed INTEGER sint;
typedef unsigned INTEGER uint;
#undef INTEGER

#ifdef GLOBAL_INT
typedef signed GLOBAL_INT slong;
// typedef unsigned GLOBAL_INT ulong;
#else
typedef sint slong;
// typedef uint ulong;
#endif

typedef moab::EntityHandle Ulong;

namespace moab
{
void fail( const char* fmt, ... );

class TupleList
{
  public:
    /*---------------------------------------------------------------------------

      buffer: a simple class which can be used to store data

      The ptr points to the chunk of memory allocated for the buffer's use.  The
      size denotes the size of the allocated memory; the user must take care to
      note how much of the buffer they are using.

      ---------------------------------------------------------------------------*/
    class buffer
    {
      public:
        size_t buffSize;
        char* ptr;

        /**Constructor which sets an initial capacity of the buffer
         */
        buffer( size_t sz );

        /**Default constructor (Note:  buffer must be initialized before use!)
         */
        buffer();

        ~buffer()
        {
            this->reset();
        };

        /**Initializes the buffer to have a capacity of size
         */
        void buffer_init_( size_t sz, const char* file );

        /**Ensures that the buffer has at least a capacity of min
         */
        void buffer_reserve_( size_t min, const char* file );

        /**Frees any allocated memory used by the buffer
         */
        void reset();

        // Aliases for using the buffer methods
#define buffer_init( sz )     buffer_init_( sz, __FILE__ )
#define buffer_reserve( min ) buffer_reserve_( min, __FILE__ )
    };

  public:
    /**Constructor that takes all parameters and initializes the TupleList
     */
    TupleList( uint mi, uint ml, uint mul, uint mr, uint max );

    /**Default constructor (Note:  TupleList must be initialized before use!)
     */
    TupleList();

    ~TupleList()
    {
        reset();
    };

    /**Initializes the starting memory to be used by the TupleList
     * Note:  TupleLists must be initialized before they can be used
     *
     * param mi   number of signed ints in each tuple
     * param ml   number of long ints in each tuple
     * param mul  number of unsigned long ints in each tuple
     * param mr   number of reals in each tuple
     * param max  starting capacity of max tuples in the TupleList
     */
    void initialize( uint mi, uint ml, uint mul, uint mr, uint max );

    /**Resizes the TupleList to a new max
     *
     * param max   the new max capacity of the TupleList
     */
    ErrorCode resize( uint max );

    /**Sorts the TupleList by 'key'
     * if key
    struct SortData
    {
        Value v;
        Index i;
    };

#define DIGIT_BITS      8
#define DIGIT_VALUES    ( 1 << DIGIT_BITS )
#define DIGIT_MASK      ( (Value)( DIGIT_VALUES - 1 ) )
#define CEILDIV( a, b ) ( ( ( a ) + (b)-1 ) / ( b ) )
#define DIGITS          CEILDIV( CHAR_BIT * sizeof( Value ), DIGIT_BITS )
#define VALUE_BITS      ( DIGIT_BITS * DIGITS )
#define COUNT_SIZE      ( DIGITS * DIGIT_VALUES )

    template < class Value >
    static Value radix_count( const Value* A, const Value* end, Index stride, Index count[DIGITS][DIGIT_VALUES] );

    static void radix_offsets( Index* c );

    template < class Value >
    static unsigned radix_zeros( Value bitorkey, Index count[DIGITS][DIGIT_VALUES], unsigned* shift, Index** offsets );

    template < class Value >
    static void radix_index_pass_b( const Value* A,
                                    Index n,
                                    Index stride,
                                    unsigned sh,
                                    Index* off,
                                    SortData< Value >* out );

    template < class Value >
    static void radix_index_pass_m( const SortData< Value >* src,
                                    const SortData< Value >* end,
                                    unsigned sh,
                                    Index* off,
                                    SortData< Value >* out );

    template < class Value >
    static void radix_index_pass_e( const SortData< Value >* src,
                                    const SortData< Value >* end,
                                    unsigned sh,
                                    Index* off,
                                    Index* out );

    template < class Value >
    static void radix_index_pass_be( const Value* A, Index n, Index stride, unsigned sh, Index* off, Index* out );

    /*------------------------------------------------------------------------------


      Radix Sort

      stable; O(n) time

      ----------------------------------------------------------------------------*/
    template < class Value >
    static void radix_index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );

    /*------------------------------------------------------------------------------


      Merge Sort

      stable; O(n log n) time

      ----------------------------------------------------------------------------*/
    template < class Value >
    static void merge_index_sort( const Value* A, const Index An, Index stride, Index* idx, SortData< Value >* work );

    template < class Value >
    static void index_sort( const Value* A, Index n, Index stride, Index* idx, SortData< Value >* work );

#undef DIGIT_BITS
#undef DIGIT_VALUES
#undef DIGIT_MASK
#undef CEILDIV
#undef DIGITS
#undef VALUE_BITS
#undef COUNT_SIZE
};

inline uint TupleList::get_max() const
{
    return max;
}
inline uint TupleList::get_n() const
{
    return n;
}
inline bool TupleList::get_writeEnabled() const
{
    return writeEnabled;
}

}  // namespace moab
#endif
#include