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, sulong, 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 <limits.h>
#include <stdlib.h>

#include "moab/Types.hpp"
#include <string>

/* 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;
#  define floorr floorf
#  define ceilr  ceilf
#  define sqrtr  sqrtf
#  define fabsr  fabsf
#  define cosr   cosf
#  define sinr   sinf
#  define EPS   (128*FLT_EPSILON)
#  define PI 3.1415926535897932384626433832795028841971693993751058209749445923F
#elif defined(USE_LONG_DOUBLE)
typedef long double realType;
#  define floorr floorl
#  define ceilr  ceill
#  define sqrtr  sqrtl
#  define fabsr  fabsl
#  define cosr   cosl
#  define sinr   sinl
#  define EPS   (128*LDBL_EPSILON)
#  define PI 3.1415926535897932384626433832795028841971693993751058209749445923L
#else
typedef double realType;
#  define floorr floor
#  define ceilr  ceil
#  define sqrtr  sqrt
#  define fabsr  fabs
#  define cosr   cos
#  define sinr   sin
#  define EPS   (128*DBL_EPSILON)
#  define PI 3.1415926535897932384626433832795028841971693993751058209749445923
#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



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;
  
      buffer(size_t sz);

      buffer();
  
      ~buffer () { this->reset(); };
  
      void buffer_init_(size_t sz, const char *file);

      void buffer_reserve_(size_t min, const char *file);
    
      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:

    TupleList(uint mi, uint ml,
          uint mul, uint mr, uint max);

    TupleList();

    ~TupleList() { reset(); };

    void initialize(uint mi, uint ml,
            uint mul, uint mr, uint max);

    ErrorCode resize(uint max);

    /*------------------------------------------------------------------------------
  
      Hybrid Stable Sort
  
      low-overhead merge sort when n is small,
      otherwise asymptotically superior radix sort

      result = O(n) sort with good performance for all n
  
      A, n, stride : specifices the input
  
      sort:
      uint out[n] : the sorted values (output)
      uint work[n]: scratch area
  
      index_sort:
      uint idx[n]  : the sorted indices (output)
      sort_data work[2*n]: scratch area

      ----------------------------------------------------------------------------*/
    ErrorCode sort(uint key, TupleList::buffer *buf);

    void reset();

    void reserve();

    int find(unsigned int key_num, sint value);
    int find(unsigned int key_num, slong value);
    int find(unsigned int key_num, ulong value);
    int find(unsigned int key_num, realType value);

    sint get_sint(unsigned int index, unsigned int m);
    slong get_int(unsigned int index, unsigned int m);
    ulong get_ulong(unsigned int index, unsigned int m);
    realType get_double(unsigned int index, unsigned int m);

    ErrorCode get(unsigned int index, const sint *&sp, 
          const slong *&ip, const ulong *&lp, const realType *&dp);

    unsigned int push_back(sint *sp, slong *ip,
               ulong *lp, realType *dp);

    /*Enable or disable direct write access to arrays
      This is important so that we know whether or not
      the user of this class can directly modify data
      which can affect operations such as
      whether or not we know the tuple list is sorted
      (for a binary search)*/
    void enableWriteAccess();
    void disableWriteAccess();

    /*Get information on the Tuple Sizes
     * param &mi_out  Count of uints in a tuple
     * param &ml_out  Count of uints in a tuple
     * param &mul_out Count of uints in a tuple
     * param &mr_out  Count of uints in a tuple
     */
    void getTupleSize(uint &mi_out, uint &ml_out, 
              uint &mul_out, uint &mr_out) const;

    /*Set the count of Tuples in the Tuple List
     * Warning, automatically calls enableWriteAccess()
     * param n_in     New count of Tuples
     */
    void set_n(uint n_in);
  
    /* Get the count of Tuples in the Tuple List */
    uint get_n() const;
    
    /*Get the maximum number of Tuples currently allocated for*/
    uint get_max() const;

    bool get_writeEnabled() const;

    /*Increment n by 1
     * Warning, automatically calls enableWriteAccess()
     * returns current TupleList.n after the increment */
    uint inc_n();
    
    void print(const char *) const;

    //Variables to allow for direct write access
    sint *vi_wr; slong *vl_wr; ulong *vul_wr; realType *vr_wr;

    //Variables to allow for direct read access
    const sint *vi_rd; slong *vl_rd; ulong *vul_rd; realType *vr_rd;
    
  private:
    /* storage layed out as: vi[max][mi], vl[max][ml], vul[max][mul], 
     * vr[max][mr] where "tuple" i is given by 
     * (vi[i][0:mi-1],vl[i][0:ml-1],vul[i][0:mul-1],vr[i][0:mr-1]).
     * only the first n tuples are in use */
    uint mi,ml,mul,mr;
    uint n, max;
    sint *vi; slong *vl; ulong *vul; realType *vr;

    // Used by sort:  see .cpp for more details
    //void sort_bits(uint *work, uint key);
    void permute(uint *perm, void *work);
    
    /* last_sorted = the last sorted position in the tuple (if the
     * TupleList has not been sorted, or has become unsorted--i.e.
     * by adding a tuple--last_sorted = -1) */
    int last_sorted;
    //Whether or not the object is currently allowing direct
    //write access to the arrays
    bool writeEnabled;

    typedef uint Index;

    template <typename Value>
    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
#endif
#include <stdlib.h>