moab
|
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, sulong, 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 <limits.h> 00019 #include <stdlib.h> 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 # define floorr floorf 00049 # define ceilr ceilf 00050 # define sqrtr sqrtf 00051 # define fabsr fabsf 00052 # define cosr cosf 00053 # define sinr sinf 00054 # define EPS (128*FLT_EPSILON) 00055 # define PI 3.1415926535897932384626433832795028841971693993751058209749445923F 00056 #elif defined(USE_LONG_DOUBLE) 00057 typedef long double realType; 00058 # define floorr floorl 00059 # define ceilr ceill 00060 # define sqrtr sqrtl 00061 # define fabsr fabsl 00062 # define cosr cosl 00063 # define sinr sinl 00064 # define EPS (128*LDBL_EPSILON) 00065 # define PI 3.1415926535897932384626433832795028841971693993751058209749445923L 00066 #else 00067 typedef double realType; 00068 # define floorr floor 00069 # define ceilr ceil 00070 # define sqrtr sqrt 00071 # define fabsr fabs 00072 # define cosr cos 00073 # define sinr sin 00074 # define EPS (128*DBL_EPSILON) 00075 # define PI 3.1415926535897932384626433832795028841971693993751058209749445923 00076 #endif 00077 00078 /* apparently uint and ulong can be defined already in standard headers */ 00079 #define uint uint_ 00080 #define ulong ulong_ 00081 #define sint sint_ 00082 #define slong slong_ 00083 00084 typedef signed INTEGER sint; 00085 typedef unsigned INTEGER uint; 00086 #undef INTEGER 00087 00088 #ifdef GLOBAL_INT 00089 typedef signed GLOBAL_INT slong; 00090 typedef unsigned GLOBAL_INT ulong; 00091 #else 00092 typedef sint slong; 00093 typedef uint ulong; 00094 #endif 00095 00096 00097 00098 namespace moab 00099 { 00100 void fail(const char *fmt, ...); 00101 00102 class TupleList 00103 { 00104 public: 00105 /*--------------------------------------------------------------------------- 00106 00107 buffer: a simple class which can be used to store data 00108 00109 The ptr points to the chunk of memory allocated for the buffer's use. The 00110 size denotes the size of the allocated memory; the user must take care to 00111 note how much of the buffer they are using. 00112 00113 ---------------------------------------------------------------------------*/ 00114 class buffer 00115 { 00116 public: 00117 size_t buffSize; 00118 char *ptr; 00119 00122 buffer(size_t sz); 00123 00126 buffer(); 00127 00128 ~buffer () { this->reset(); }; 00129 00132 void buffer_init_(size_t sz, const char *file); 00133 00136 void buffer_reserve_(size_t min, const char *file); 00137 00140 void reset (); 00141 00142 //Aliases for using the buffer methods 00143 #define buffer_init(sz) buffer_init_(sz,__FILE__) 00144 #define buffer_reserve(min) buffer_reserve_(min,__FILE__) 00145 00146 }; 00147 00148 public: 00149 00152 TupleList(uint mi, uint ml, 00153 uint mul, uint mr, uint max); 00154 00157 TupleList(); 00158 00159 ~TupleList() { reset(); }; 00160 00170 void initialize(uint mi, uint ml, 00171 uint mul, uint mr, uint max); 00172 00177 ErrorCode resize(uint max); 00178 00187 /*------------------------------------------------------------------------------ 00188 00189 Hybrid Stable Sort 00190 00191 low-overhead merge sort when n is small, 00192 otherwise asymptotically superior radix sort 00193 00194 result = O(n) sort with good performance for all n 00195 00196 A, n, stride : specifices the input 00197 00198 sort: 00199 uint out[n] : the sorted values (output) 00200 uint work[n]: scratch area 00201 00202 index_sort: 00203 uint idx[n] : the sorted indices (output) 00204 sort_data work[2*n]: scratch area 00205 00206 ----------------------------------------------------------------------------*/ 00207 ErrorCode sort(uint key, TupleList::buffer *buf); 00208 00211 void reset(); 00212 00215 void reserve(); 00216 00226 int find(unsigned int key_num, sint value); 00227 int find(unsigned int key_num, slong value); 00228 int find(unsigned int key_num, ulong value); 00229 int find(unsigned int key_num, realType value); 00230 00238 sint get_sint(unsigned int index, unsigned int m); 00239 slong get_int(unsigned int index, unsigned int m); 00240 ulong get_ulong(unsigned int index, unsigned int m); 00241 realType get_double(unsigned int index, unsigned int m); 00242 00249 ErrorCode get(unsigned int index, const sint *&sp, 00250 const slong *&ip, const ulong *&lp, const realType *&dp); 00251 00260 unsigned int push_back(sint *sp, slong *ip, 00261 ulong *lp, realType *dp); 00262 00263 /*Enable or disable direct write access to arrays 00264 This is important so that we know whether or not 00265 the user of this class can directly modify data 00266 which can affect operations such as 00267 whether or not we know the tuple list is sorted 00268 (for a binary search)*/ 00269 void enableWriteAccess(); 00270 void disableWriteAccess(); 00271 00272 /*Get information on the Tuple Sizes 00273 * param &mi_out Count of uints in a tuple 00274 * param &ml_out Count of uints in a tuple 00275 * param &mul_out Count of uints in a tuple 00276 * param &mr_out Count of uints in a tuple 00277 */ 00278 void getTupleSize(uint &mi_out, uint &ml_out, 00279 uint &mul_out, uint &mr_out) const; 00280 00281 /*Set the count of Tuples in the Tuple List 00282 * Warning, automatically calls enableWriteAccess() 00283 * param n_in New count of Tuples 00284 */ 00285 void set_n(uint n_in); 00286 00287 /* Get the count of Tuples in the Tuple List */ 00288 uint get_n() const; 00289 00290 /*Get the maximum number of Tuples currently allocated for*/ 00291 uint get_max() const; 00292 00293 bool get_writeEnabled() const; 00294 00295 /*Increment n by 1 00296 * Warning, automatically calls enableWriteAccess() 00297 * returns current TupleList.n after the increment */ 00298 uint inc_n(); 00299 00300 void print(const char *) const; 00301 00302 //Variables to allow for direct write access 00303 sint *vi_wr; slong *vl_wr; ulong *vul_wr; realType *vr_wr; 00304 00305 //Variables to allow for direct read access 00306 const sint *vi_rd; slong *vl_rd; ulong *vul_rd; realType *vr_rd; 00307 00308 private: 00309 /* storage layed out as: vi[max][mi], vl[max][ml], vul[max][mul], 00310 * vr[max][mr] where "tuple" i is given by 00311 * (vi[i][0:mi-1],vl[i][0:ml-1],vul[i][0:mul-1],vr[i][0:mr-1]). 00312 * only the first n tuples are in use */ 00313 uint mi,ml,mul,mr; 00314 uint n, max; 00315 sint *vi; slong *vl; ulong *vul; realType *vr; 00316 00317 // Used by sort: see .cpp for more details 00318 //void sort_bits(uint *work, uint key); 00319 void permute(uint *perm, void *work); 00320 00321 /* last_sorted = the last sorted position in the tuple (if the 00322 * TupleList has not been sorted, or has become unsorted--i.e. 00323 * by adding a tuple--last_sorted = -1) */ 00324 int last_sorted; 00325 //Whether or not the object is currently allowing direct 00326 //write access to the arrays 00327 bool writeEnabled; 00328 00329 typedef uint Index; 00330 00331 template <typename Value> 00332 struct SortData {Value v; Index i;}; 00333 00334 #define DIGIT_BITS 8 00335 #define DIGIT_VALUES (1<<DIGIT_BITS) 00336 #define DIGIT_MASK ((Value)(DIGIT_VALUES-1)) 00337 #define CEILDIV(a,b) (((a)+(b)-1)/(b)) 00338 #define DIGITS CEILDIV(CHAR_BIT*sizeof(Value),DIGIT_BITS) 00339 #define VALUE_BITS (DIGIT_BITS*DIGITS) 00340 #define COUNT_SIZE (DIGITS*DIGIT_VALUES) 00341 00342 template<class Value> 00343 static Value radix_count(const Value *A, const Value *end, Index stride, 00344 Index count[DIGITS][DIGIT_VALUES]); 00345 00346 static void radix_offsets(Index *c); 00347 00348 template<class Value> 00349 static unsigned radix_zeros(Value bitorkey, Index count[DIGITS][DIGIT_VALUES], 00350 unsigned *shift, Index **offsets); 00351 00352 template<class Value> 00353 static void radix_index_pass_b(const Value *A, Index n, Index stride, 00354 unsigned sh, Index *off, SortData<Value> *out); 00355 00356 template<class Value> 00357 static void radix_index_pass_m(const SortData<Value> *src, const SortData<Value> *end, 00358 unsigned sh, Index *off, SortData<Value> *out); 00359 00360 template<class Value> 00361 static void radix_index_pass_e(const SortData<Value> *src, const SortData<Value> *end, 00362 unsigned sh, Index *off, Index *out); 00363 00364 template<class Value> 00365 static void radix_index_pass_be(const Value *A, Index n, Index stride, 00366 unsigned sh, Index *off, Index *out); 00367 00368 00369 /*------------------------------------------------------------------------------ 00370 00371 00372 Radix Sort 00373 00374 stable; O(n) time 00375 00376 ----------------------------------------------------------------------------*/ 00377 template<class Value> 00378 static void radix_index_sort(const Value *A, Index n, Index stride, 00379 Index *idx, SortData<Value> *work); 00380 00381 /*------------------------------------------------------------------------------ 00382 00383 00384 Merge Sort 00385 00386 stable; O(n log n) time 00387 00388 ----------------------------------------------------------------------------*/ 00389 template<class Value> 00390 static void merge_index_sort(const Value *A, const Index An, Index stride, 00391 Index *idx, SortData<Value> *work); 00392 00393 template<class Value> 00394 static void index_sort(const Value *A, Index n, Index stride, 00395 Index *idx, SortData<Value> *work); 00396 00397 00398 #undef DIGIT_BITS 00399 #undef DIGIT_VALUES 00400 #undef DIGIT_MASK 00401 #undef CEILDIV 00402 #undef DIGITS 00403 #undef VALUE_BITS 00404 #undef COUNT_SIZE 00405 }; 00406 00407 inline uint TupleList::get_max() const{ return max; } 00408 inline uint TupleList::get_n() const{ return n; } 00409 inline bool TupleList::get_writeEnabled() const{ return writeEnabled; } 00410 00411 } //namespace 00412 #endif 00413 #include <stdlib.h>