Nek5000
SEM for Incompressible NS
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
Classes | Macros | Functions
sort_imp.h File Reference
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  sort_data
 

Macros

#define sort_data   TOKEN_PASTE(sort_data ,SORT_SUFFIX)
 
#define radix_count   TOKEN_PASTE(radix_count ,SORT_SUFFIX)
 
#define radix_offsets   TOKEN_PASTE(radix_offsets ,SORT_SUFFIX)
 
#define radix_zeros   TOKEN_PASTE(radix_zeros ,SORT_SUFFIX)
 
#define radix_passv   TOKEN_PASTE(radix_passv ,SORT_SUFFIX)
 
#define radix_sortv   TOKEN_PASTE(radix_sortv ,SORT_SUFFIX)
 
#define radix_passp0_b   TOKEN_PASTE(radix_passp0_b ,SORT_SUFFIX)
 
#define radix_passp_b   TOKEN_PASTE(radix_passp_b ,SORT_SUFFIX)
 
#define radix_passp_m   TOKEN_PASTE(radix_passp_m ,SORT_SUFFIX)
 
#define radix_passp_e   TOKEN_PASTE(radix_passp_e ,SORT_SUFFIX)
 
#define radix_passp0_be   TOKEN_PASTE(radix_passp0_be,SORT_SUFFIX)
 
#define radix_passp_be   TOKEN_PASTE(radix_passp_be, SORT_SUFFIX)
 
#define radix_sortp   TOKEN_PASTE(radix_sortp ,SORT_SUFFIX)
 
#define merge_sortv   TOKEN_PASTE(merge_sortv ,SORT_SUFFIX)
 
#define merge_copy_perm   TOKEN_PASTE(merge_copy_perm,SORT_SUFFIX)
 
#define merge_sortp0   TOKEN_PASTE(merge_sortp0 ,SORT_SUFFIX)
 
#define merge_sortp   TOKEN_PASTE(merge_sortp ,SORT_SUFFIX)
 
#define heap_sortv   TOKEN_PASTE(heap_sortv ,SORT_SUFFIX)
 
#define sortv   PREFIXED_NAME(TOKEN_PASTE(sortv,SORT_SUFFIX))
 
#define sortp   PREFIXED_NAME(TOKEN_PASTE(sortp,SORT_SUFFIX))
 
#define INC_PTR(A, stride)   ((A)=(T*)((char*)(A)+(stride)))
 
#define INDEX_PTR(A, stride, i)   (*(T*)((char*)(A)+(i)*(stride)))
 
#define STATIC_DIGIT_BUCKETS   1
 
#define DIGIT_BITS   8
 
#define DIGIT_VALUES   (1<<DIGIT_BITS)
 
#define DIGIT_MASK   ((T)(DIGIT_VALUES-1))
 
#define CEILDIV(a, b)   (((a)+(b)-1)/(b))
 
#define DIGITS   CEILDIV(CHAR_BIT*sizeof(T),DIGIT_BITS)
 
#define VALUE_BITS   (DIGIT_BITS*DIGITS)
 
#define COUNT_SIZE   (DIGITS*DIGIT_VALUES)
 
#define COUNT_DIGIT_01(n, i)   if(n>i) count[i][val&DIGIT_MASK]++, val>>=DIGIT_BITS
 
#define COUNT_DIGIT_02(n, i)   COUNT_DIGIT_01(n,i); COUNT_DIGIT_01(n,i+ 1)
 
#define COUNT_DIGIT_04(n, i)   COUNT_DIGIT_02(n,i); COUNT_DIGIT_02(n,i+ 2)
 
#define COUNT_DIGIT_08(n, i)   COUNT_DIGIT_04(n,i); COUNT_DIGIT_04(n,i+ 4)
 
#define COUNT_DIGIT_16(n, i)   COUNT_DIGIT_08(n,i); COUNT_DIGIT_08(n,i+ 8)
 
#define COUNT_DIGIT_32(n, i)   COUNT_DIGIT_16(n,i); COUNT_DIGIT_16(n,i+16)
 
#define COUNT_DIGIT_64(n, i)   COUNT_DIGIT_32(n,i); COUNT_DIGIT_32(n,i+32)
 
#define MERGE_2(p, v)
 
#define MERGE_3(p, v)
 
#define MERGE_SORT()
 
#define DATA   T
 
#define VAL(x)   x
 
#define SETVAL(x, ai)   x=*A,INC_PTR(A,stride)
 
#define DATA   sort_data
 
#define VAL(x)   x.v
 
#define SETVAL(x, ai)   x.v=*A,INC_PTR(A,stride),x.i=ai
 
#define DATA   sort_data
 
#define VAL(x)   x.v
 
#define SETVAL(x, ai)   x.i=idx[ai],x.v=INDEX_PTR(A,stride,x.i)
 

Functions

static T radix_count (uint(*restrict count)[DIGIT_VALUES], const T *restrict A, const T *const end, const unsigned stride)
 
static void radix_offsets (uint *restrict c)
 
static unsigned radix_zeros (T bitorkey, uint(*restrict count)[DIGIT_VALUES], unsigned *restrict shift, uint **restrict offsets)
 
static void radix_passv (const T *restrict A, const T *const end, const unsigned stride, const unsigned sh, uint *const restrict off, T *const restrict out)
 
static void radix_sortv (T *out, const T *A, const uint n, const unsigned stride, T *work, uint(*restrict count)[DIGIT_VALUES])
 
static void radix_passp0_b (const T *restrict A, const uint n, const unsigned stride, const unsigned sh, uint *const restrict off, sort_data *const restrict out)
 
static void radix_passp_b (const uint *restrict p, const T *const restrict A, const uint n, const unsigned stride, const unsigned sh, uint *const restrict off, sort_data *const out)
 
static void radix_passp_m (const sort_data *restrict src, const sort_data *const end, const unsigned sh, uint *const restrict off, sort_data *const restrict out)
 
static void radix_passp_e (const sort_data *restrict src, const sort_data *const end, const unsigned sh, uint *const restrict off, uint *const restrict out)
 
static void radix_passp0_be (uint *const restrict out, const T *restrict A, const uint n, const unsigned stride, const unsigned sh, uint *const restrict off)
 
static void radix_passp_be (uint *restrict p, const T *restrict A, const uint n, const unsigned stride, const unsigned sh, uint *const restrict off, sort_data *restrict work)
 
static void radix_sortp (uint *restrict idx, uint perm_start, const T *restrict A, const uint n, const unsigned stride, sort_data *restrict work, uint(*restrict count)[DIGIT_VALUES])
 
static void merge_sortv (T *restrict out, const T *restrict A, const uint An, const unsigned stride, T *restrict work)
 
static void merge_copy_perm (uint *restrict idx, const sort_data *restrict p, uint n)
 
static void merge_sortp0 (uint *restrict idx, const T *restrict A, const uint An, const unsigned stride, sort_data *restrict work)
 
static void merge_sortp (uint *restrict idx, const T *const restrict A, const uint An, const unsigned stride, sort_data *restrict work)
 
static void heap_sortv (T *const restrict A, unsigned n)
 
void sortv (T *out, const T *A, uint n, unsigned stride, buffer *restrict buf)
 
uint * sortp (buffer *restrict buf, int start_perm, const T *restrict A, uint n, unsigned stride)
 

Macro Definition Documentation

#define CEILDIV (   a,
  b 
)    (((a)+(b)-1)/(b))

Definition at line 58 of file sort_imp.h.

#define COUNT_DIGIT_01 (   n,
  i 
)    if(n>i) count[i][val&DIGIT_MASK]++, val>>=DIGIT_BITS

Definition at line 64 of file sort_imp.h.

#define COUNT_DIGIT_02 (   n,
  i 
)    COUNT_DIGIT_01(n,i); COUNT_DIGIT_01(n,i+ 1)

Definition at line 66 of file sort_imp.h.

#define COUNT_DIGIT_04 (   n,
  i 
)    COUNT_DIGIT_02(n,i); COUNT_DIGIT_02(n,i+ 2)

Definition at line 67 of file sort_imp.h.

#define COUNT_DIGIT_08 (   n,
  i 
)    COUNT_DIGIT_04(n,i); COUNT_DIGIT_04(n,i+ 4)

Definition at line 68 of file sort_imp.h.

#define COUNT_DIGIT_16 (   n,
  i 
)    COUNT_DIGIT_08(n,i); COUNT_DIGIT_08(n,i+ 8)

Definition at line 69 of file sort_imp.h.

#define COUNT_DIGIT_32 (   n,
  i 
)    COUNT_DIGIT_16(n,i); COUNT_DIGIT_16(n,i+16)

Definition at line 70 of file sort_imp.h.

#define COUNT_DIGIT_64 (   n,
  i 
)    COUNT_DIGIT_32(n,i); COUNT_DIGIT_32(n,i+32)

Definition at line 71 of file sort_imp.h.

Referenced by radix_count().

#define COUNT_SIZE   (DIGITS*DIGIT_VALUES)

Definition at line 61 of file sort_imp.h.

Referenced by radix_count().

#define DATA   T
#define DATA   sort_data
#define DATA   sort_data
#define DIGIT_BITS   8

Definition at line 55 of file sort_imp.h.

Referenced by radix_zeros().

#define DIGIT_MASK   ((T)(DIGIT_VALUES-1))

Definition at line 57 of file sort_imp.h.

Referenced by radix_passp0_b(), radix_passp0_be(), radix_passp_b(), radix_passp_be(), radix_passp_e(), radix_passp_m(), radix_passv(), and radix_zeros().

#define DIGIT_VALUES   (1<<DIGIT_BITS)

Definition at line 56 of file sort_imp.h.

Referenced by radix_offsets(), sortp(), and sortv().

#define DIGITS   CEILDIV(CHAR_BIT*sizeof(T),DIGIT_BITS)

Definition at line 59 of file sort_imp.h.

Referenced by radix_count(), radix_sortp(), radix_sortv(), sortp(), and sortv().

#define heap_sortv   TOKEN_PASTE(heap_sortv ,SORT_SUFFIX)

Definition at line 22 of file sort_imp.h.

Referenced by sortv().

#define INC_PTR (   A,
  stride 
)    ((A)=(T*)((char*)(A)+(stride)))

Definition at line 29 of file sort_imp.h.

Referenced by radix_count(), radix_passp0_b(), radix_passp0_be(), and radix_passv().

#define INDEX_PTR (   A,
  stride,
  i 
)    (*(T*)((char*)(A)+(i)*(stride)))

Definition at line 30 of file sort_imp.h.

Referenced by radix_passp_b(), radix_passp_be(), radix_sortp(), and radix_sortv().

#define MERGE_2 (   p,
  v 
)
Value:
if(VAL(v[1])<VAL(v[0])) p[0]=v[1],p[1]=v[0]; \
else p[0]=v[0],p[1]=v[1]
p
p
Definition: xxt_test2.m:1
VAL
#define VAL(x)

Definition at line 266 of file sort_imp.h.

#define MERGE_3 (   p,
  v 
)
Value:
do \
if(VAL(v[1])<VAL(v[0])) { \
if(VAL(v[2])<VAL(v[1])) p[0]=v[2],p[1]=v[1],p[2]=v[0]; \
else { if(VAL(v[2])<VAL(v[0])) p[0]=v[1],p[1]=v[2],p[2]=v[0]; \
else p[0]=v[1],p[1]=v[0],p[2]=v[2]; } \
} else { \
if(VAL(v[2])<VAL(v[0])) p[0]=v[2],p[1]=v[0],p[2]=v[1]; \
else { if(VAL(v[2])<VAL(v[1])) p[0]=v[0],p[1]=v[2],p[2]=v[1]; \
else p[0]=v[0],p[1]=v[1],p[2]=v[2]; } \
} while(0)
p
p
Definition: xxt_test2.m:1
VAL
#define VAL(x)

Definition at line 269 of file sort_imp.h.

#define merge_copy_perm   TOKEN_PASTE(merge_copy_perm,SORT_SUFFIX)

Definition at line 19 of file sort_imp.h.

Referenced by merge_sortp(), and merge_sortp0().

#define MERGE_SORT ( )

Definition at line 279 of file sort_imp.h.

Referenced by merge_sortp(), merge_sortp0(), and merge_sortv().

#define merge_sortp   TOKEN_PASTE(merge_sortp ,SORT_SUFFIX)

Definition at line 21 of file sort_imp.h.

Referenced by sortp().

#define merge_sortp0   TOKEN_PASTE(merge_sortp0 ,SORT_SUFFIX)

Definition at line 20 of file sort_imp.h.

Referenced by sortp().

#define merge_sortv   TOKEN_PASTE(merge_sortv ,SORT_SUFFIX)

Definition at line 18 of file sort_imp.h.

Referenced by sortv().

#define radix_count   TOKEN_PASTE(radix_count ,SORT_SUFFIX)

Definition at line 6 of file sort_imp.h.

Referenced by radix_sortp(), and radix_sortv().

#define radix_offsets   TOKEN_PASTE(radix_offsets ,SORT_SUFFIX)

Definition at line 7 of file sort_imp.h.

Referenced by radix_zeros().

#define radix_passp0_b   TOKEN_PASTE(radix_passp0_b ,SORT_SUFFIX)

Definition at line 11 of file sort_imp.h.

Referenced by radix_sortp().

#define radix_passp0_be   TOKEN_PASTE(radix_passp0_be,SORT_SUFFIX)

Definition at line 15 of file sort_imp.h.

Referenced by radix_sortp().

#define radix_passp_b   TOKEN_PASTE(radix_passp_b ,SORT_SUFFIX)

Definition at line 12 of file sort_imp.h.

Referenced by radix_sortp().

#define radix_passp_be   TOKEN_PASTE(radix_passp_be, SORT_SUFFIX)

Definition at line 16 of file sort_imp.h.

Referenced by radix_sortp().

#define radix_passp_e   TOKEN_PASTE(radix_passp_e ,SORT_SUFFIX)

Definition at line 14 of file sort_imp.h.

Referenced by radix_sortp().

#define radix_passp_m   TOKEN_PASTE(radix_passp_m ,SORT_SUFFIX)

Definition at line 13 of file sort_imp.h.

Referenced by radix_sortp().

#define radix_passv   TOKEN_PASTE(radix_passv ,SORT_SUFFIX)

Definition at line 9 of file sort_imp.h.

Referenced by radix_sortv().

#define radix_sortp   TOKEN_PASTE(radix_sortp ,SORT_SUFFIX)

Definition at line 17 of file sort_imp.h.

Referenced by sortp().

#define radix_sortv   TOKEN_PASTE(radix_sortv ,SORT_SUFFIX)

Definition at line 10 of file sort_imp.h.

Referenced by sortv().

#define radix_zeros   TOKEN_PASTE(radix_zeros ,SORT_SUFFIX)

Definition at line 8 of file sort_imp.h.

Referenced by radix_sortp(), and radix_sortv().

#define SETVAL (   x,
  ai 
)    x=*A,INC_PTR(A,stride)
#define SETVAL (   x,
  ai 
)    x.v=*A,INC_PTR(A,stride),x.i=ai
#define SETVAL (   x,
  ai 
)    x.i=idx[ai],x.v=INDEX_PTR(A,stride,x.i)
#define sort_data   TOKEN_PASTE(sort_data ,SORT_SUFFIX)

Definition at line 5 of file sort_imp.h.

#define sortp   PREFIXED_NAME(TOKEN_PASTE(sortp,SORT_SUFFIX))

Definition at line 25 of file sort_imp.h.

#define sortv   PREFIXED_NAME(TOKEN_PASTE(sortv,SORT_SUFFIX))

Definition at line 24 of file sort_imp.h.

#define STATIC_DIGIT_BUCKETS   1

Definition at line 53 of file sort_imp.h.

Referenced by sortp(), and sortv().

#define VAL (   x)    x
#define VAL (   x)    x.v
#define VAL (   x)    x.v
#define VALUE_BITS   (DIGIT_BITS*DIGITS)

Definition at line 60 of file sort_imp.h.

Referenced by radix_zeros().

Function Documentation

static void heap_sortv ( T *const restrict  A,
unsigned  n 
)
static

Definition at line 395 of file sort_imp.h.

References i, n, and p.

static void merge_copy_perm ( uint *restrict  idx,
const sort_data *restrict  p,
uint  n 
)
static

Definition at line 333 of file sort_imp.h.

References i, and uint.

static void merge_sortp ( uint *restrict  idx,
const T *const restrict  A,
const uint  An,
const unsigned  stride,
sort_data *restrict  work 
)
static

Definition at line 368 of file sort_imp.h.

References merge_copy_perm, MERGE_SORT, and work.

static void merge_sortp0 ( uint *restrict  idx,
const T *restrict  A,
const uint  An,
const unsigned  stride,
sort_data *restrict  work 
)
static

Definition at line 352 of file sort_imp.h.

References merge_copy_perm, MERGE_SORT, and work.

static void merge_sortv ( T *restrict  out,
const T *restrict  A,
const uint  An,
const unsigned  stride,
T *restrict  work 
)
static

Definition at line 318 of file sort_imp.h.

References MERGE_SORT, out, and work.

static T radix_count ( uint(*)  count[DIGIT_VALUES],
const T *restrict  A,
const T *const  end,
const unsigned  stride 
)
static

Definition at line 73 of file sort_imp.h.

References A, COUNT_DIGIT_64, COUNT_SIZE, DIGITS, INC_PTR, and uint.

static void radix_offsets ( uint *restrict  c)
static

Definition at line 101 of file sort_imp.h.

References DIGIT_VALUES, sum(), and uint.

+ Here is the call graph for this function:

static void radix_passp0_b ( const T *restrict  A,
const uint  n,
const unsigned  stride,
const unsigned  sh,
uint *const restrict  off,
sort_data *const restrict  out 
)
static

Definition at line 157 of file sort_imp.h.

References A, DIGIT_MASK, sort_data::i, i, INC_PTR, n, uint, and sort_data::v.

static void radix_passp0_be ( uint *const restrict  out,
const T *restrict  A,
const uint  n,
const unsigned  stride,
const unsigned  sh,
uint *const restrict  off 
)
static

Definition at line 204 of file sort_imp.h.

References DIGIT_MASK, i, INC_PTR, n, and uint.

static void radix_passp_b ( const uint *restrict  p,
const T *const restrict  A,
const uint  n,
const unsigned  stride,
const unsigned  sh,
uint *const restrict  off,
sort_data *const  out 
)
static

Definition at line 170 of file sort_imp.h.

References DIGIT_MASK, sort_data::i, INDEX_PTR, n, uint, and sort_data::v.

static void radix_passp_be ( uint *restrict  p,
const T *restrict  A,
const uint  n,
const unsigned  stride,
const unsigned  sh,
uint *const restrict  off,
sort_data *restrict  work 
)
static

Definition at line 213 of file sort_imp.h.

References DIGIT_MASK, INDEX_PTR, n, p, and uint.

static void radix_passp_e ( const sort_data *restrict  src,
const sort_data *const  end,
const unsigned  sh,
uint *const restrict  off,
uint *const restrict  out 
)
static

Definition at line 196 of file sort_imp.h.

References DIGIT_MASK.

static void radix_passp_m ( const sort_data *restrict  src,
const sort_data *const  end,
const unsigned  sh,
uint *const restrict  off,
sort_data *const restrict  out 
)
static

Definition at line 185 of file sort_imp.h.

References DIGIT_MASK, sort_data::i, and sort_data::v.

static void radix_passv ( const T *restrict  A,
const T *const  end,
const unsigned  stride,
const unsigned  sh,
uint *const restrict  off,
T *const restrict  out 
)
static

Definition at line 126 of file sort_imp.h.

References DIGIT_MASK, and INC_PTR.

static void radix_sortp ( uint *restrict  idx,
uint  perm_start,
const T *restrict  A,
const uint  n,
const unsigned  stride,
sort_data *restrict  work,
uint(*)  count[DIGIT_VALUES] 
)
static

Definition at line 229 of file sort_imp.h.

References DIGITS, i, INDEX_PTR, n, radix_count, radix_passp0_b, radix_passp0_be, radix_passp_b, radix_passp_be, radix_passp_e, radix_passp_m, radix_zeros, uint, and work.

static void radix_sortv ( T *  out,
const T *  A,
const uint  n,
const unsigned  stride,
T *  work,
uint(*)  count[DIGIT_VALUES] 
)
static

Definition at line 133 of file sort_imp.h.

References DIGITS, INDEX_PTR, out, radix_count, radix_passv, radix_zeros, uint, and work.

static unsigned radix_zeros ( T  bitorkey,
uint(*)  count[DIGIT_VALUES],
unsigned *restrict  shift,
uint **restrict  offsets 
)
static

Definition at line 114 of file sort_imp.h.

References DIGIT_BITS, DIGIT_MASK, radix_offsets, uint, and VALUE_BITS.

uint* sortp ( buffer *restrict  buf,
int  start_perm,
const T *restrict  A,
uint  n,
unsigned  stride 
)

Definition at line 477 of file sort_imp.h.

References align_as, buffer_reserve, DIGIT_VALUES, DIGITS, merge_sortp, merge_sortp0, radix_sortp, restrict, STATIC_DIGIT_BUCKETS, uint, and work.

Referenced by discover_dofs(), fcrystal_ituple_sort(), fcrystal_tuple_sort(), main(), and sarray_transfer_many().

+ Here is the caller graph for this function:

void sortv ( T *  out,
const T *  A,
uint  n,
unsigned  stride,
buffer *restrict  buf 
)

Definition at line 446 of file sort_imp.h.

References A, align_as, buffer_reserve, DIGIT_VALUES, DIGITS, fail(), heap_sortv, merge_sortv, radix_sortv, restrict, STATIC_DIGIT_BUCKETS, uint, and work.

Referenced by factor_symbolic(), and main().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Generated on Tue Jul 14 2015 10:52:59 for Nek5000 by   doxygen 1.8.8