Yet Another eXchange Tool 0.11.4
Loading...
Searching...
No Matches
mergesort.c File Reference
#include <stdlib.h>
#include <stdio.h>
#include "xt/mergesort.h"
#include "xt/xt_sort.h"
#include "core/ppm_xfuncs.h"
#include "xt_mergesort_base.h"
Include dependency graph for mergesort.c:

Go to the source code of this file.

Macros

#define SORT_TYPE   idxpos_type
 
#define SORT_TYPE_SUFFIX   idxpos
 
#define SORT_TYPE_CMP_LT(a, b, ...)
 
#define SORT_TYPE_CMP_LE(a, b, ...)
 
#define SORT_TYPE_CMP_EQ(a, b, ...)
 
#define SORT_TYPE   int
 
#define SORT_TYPE_SUFFIX   int
 
#define SORT_TYPE_CMP_LT(a, b, ...)
 
#define SORT_TYPE_CMP_LE(a, b, ...)
 
#define SORT_TYPE_CMP_EQ(a, b, ...)
 
#define SORT_TYPE   Xt_int
 
#define SORT_TYPE_SUFFIX   xt_int
 
#define SORT_TYPE_CMP_LT(a, b, ...)
 
#define SORT_TYPE_CMP_LE(a, b, ...)
 
#define SORT_TYPE_CMP_EQ(a, b, ...)
 
#define SORT_TYPE   Xt_int
 
#define SORT_TYPE_SUFFIX   xt_int_permutation
 
#define SORT_TYPE_CMP_LT(u, v, i, j)
 
#define SORT_TYPE_CMP_LE(u, v, i, j)
 
#define SORT_TYPE_CMP_EQ(u, v, i, j)
 
#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation
 
#define XT_SORT_EXTRA_ARGS_PASS   , permutation
 
#define XT_SORT_EXTRA_ARGS_INNER_DECL   , int *restrict permutation_v, int *restrict permutation_w
 
#define XT_SORT_EXTRA_ARGS_INNER_PASS(a, b)
 
#define XT_SORT_EXTRA_ALLOC_SIZE   (sizeof(*permutation) * (n+1))
 
#define XT_SORT_EXTRA_ALLOC_DECL
 
#define XT_SORT_EXTRA_ARGS_SWAP(i, j)
 
#define XT_SORT_ASSIGN(a, p, b, q)
 
#define SORT_TYPE   int
 
#define SORT_TYPE_SUFFIX   int_permutation
 
#define SORT_TYPE_CMP_LT(u, v, i, j)
 
#define SORT_TYPE_CMP_LE(u, v, i, j)
 
#define SORT_TYPE_CMP_EQ(u, v, i, j)
 
#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation
 
#define XT_SORT_EXTRA_ARGS_PASS   , permutation
 
#define XT_SORT_EXTRA_ARGS_INNER_DECL   , int *restrict permutation_v, int *restrict permutation_w
 
#define XT_SORT_EXTRA_ARGS_INNER_PASS(a, b)
 
#define XT_SORT_EXTRA_ALLOC_SIZE   (sizeof(*permutation) * (n+1))
 
#define XT_SORT_EXTRA_ALLOC_DECL
 
#define XT_SORT_EXTRA_ARGS_SWAP(i, j)
 
#define XT_SORT_ASSIGN(a, p, b, q)
 

Functions

void xt_mergesort_xt_int_permutation (Xt_int *a, size_t n, int *restrict permutation)
 
void xt_mergesort_index (Xt_int *restrict v_idx, int n, int *restrict v_pos, int reset_pos)
 
static void * roundPtr (void *p, size_t mult)
 

Detailed Description

Author
Jörg Behrens behre.nosp@m.ns@d.nosp@m.krz.d.nosp@m.e Moritz Hanke hanke.nosp@m.@dkr.nosp@m.z.de Thomas Jahns jahns.nosp@m.@dkr.nosp@m.z.de

Definition in file mergesort.c.

Macro Definition Documentation

◆ SORT_TYPE [1/5]

#define SORT_TYPE   idxpos_type

Definition at line 57 of file mergesort.c.

◆ SORT_TYPE [2/5]

#define SORT_TYPE   int

Definition at line 57 of file mergesort.c.

◆ SORT_TYPE [3/5]

#define SORT_TYPE   Xt_int

Definition at line 57 of file mergesort.c.

◆ SORT_TYPE [4/5]

#define SORT_TYPE   Xt_int

Definition at line 57 of file mergesort.c.

◆ SORT_TYPE [5/5]

#define SORT_TYPE   int

Definition at line 57 of file mergesort.c.

◆ SORT_TYPE_CMP_EQ [1/5]

#define SORT_TYPE_CMP_EQ ( a,
b,
... )
Value:
((a).idx == (b).idx && (a).pos == (b).pos)

Definition at line 61 of file mergesort.c.

◆ SORT_TYPE_CMP_EQ [2/5]

#define SORT_TYPE_CMP_EQ ( a,
b,
... )
Value:
((a) == (b))

Definition at line 61 of file mergesort.c.

◆ SORT_TYPE_CMP_EQ [3/5]

#define SORT_TYPE_CMP_EQ ( a,
b,
... )
Value:
((a) == (b))

Definition at line 61 of file mergesort.c.

◆ SORT_TYPE_CMP_EQ [4/5]

#define SORT_TYPE_CMP_EQ ( u,
v,
i,
j )
Value:
((u) == (v) && permutation_v[(i)] == permutation_v[(j)])

Definition at line 61 of file mergesort.c.

◆ SORT_TYPE_CMP_EQ [5/5]

#define SORT_TYPE_CMP_EQ ( u,
v,
i,
j )
Value:
((u) == (v) && permutation_v[(i)] == permutation_v[(j)])

Definition at line 61 of file mergesort.c.

◆ SORT_TYPE_CMP_LE [1/5]

#define SORT_TYPE_CMP_LE ( a,
b,
... )
Value:
((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))

Definition at line 60 of file mergesort.c.

◆ SORT_TYPE_CMP_LE [2/5]

#define SORT_TYPE_CMP_LE ( a,
b,
... )
Value:
((a) <= (b))

Definition at line 60 of file mergesort.c.

◆ SORT_TYPE_CMP_LE [3/5]

#define SORT_TYPE_CMP_LE ( a,
b,
... )
Value:
((a) <= (b))

Definition at line 60 of file mergesort.c.

◆ SORT_TYPE_CMP_LE [4/5]

#define SORT_TYPE_CMP_LE ( u,
v,
i,
j )
Value:
((u) < (v) || ((u) == (v) && permutation_v[(i)] <= permutation_v[(j)]))

Definition at line 60 of file mergesort.c.

◆ SORT_TYPE_CMP_LE [5/5]

#define SORT_TYPE_CMP_LE ( u,
v,
i,
j )
Value:
((u) < (v) || (u == v && permutation_v[(i)] <= permutation_v[(j)]))

Definition at line 60 of file mergesort.c.

◆ SORT_TYPE_CMP_LT [1/5]

#define SORT_TYPE_CMP_LT ( a,
b,
... )
Value:
((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))

Definition at line 59 of file mergesort.c.

◆ SORT_TYPE_CMP_LT [2/5]

#define SORT_TYPE_CMP_LT ( a,
b,
... )
Value:
((a) < (b))

Definition at line 59 of file mergesort.c.

◆ SORT_TYPE_CMP_LT [3/5]

#define SORT_TYPE_CMP_LT ( a,
b,
... )
Value:
((a) < (b))

Definition at line 59 of file mergesort.c.

◆ SORT_TYPE_CMP_LT [4/5]

#define SORT_TYPE_CMP_LT ( u,
v,
i,
j )
Value:
((u) < (v) || ((u) == (v) && permutation_v[(i)] < permutation_v[(j)]))

Definition at line 59 of file mergesort.c.

◆ SORT_TYPE_CMP_LT [5/5]

#define SORT_TYPE_CMP_LT ( u,
v,
i,
j )
Value:
((u) < (v) || (u == v && permutation_v[(i)] < permutation_v[(j)]))

Definition at line 59 of file mergesort.c.

◆ SORT_TYPE_SUFFIX [1/5]

#define SORT_TYPE_SUFFIX   idxpos

Definition at line 58 of file mergesort.c.

◆ SORT_TYPE_SUFFIX [2/5]

#define SORT_TYPE_SUFFIX   int

Definition at line 58 of file mergesort.c.

◆ SORT_TYPE_SUFFIX [3/5]

#define SORT_TYPE_SUFFIX   xt_int

Definition at line 58 of file mergesort.c.

◆ SORT_TYPE_SUFFIX [4/5]

#define SORT_TYPE_SUFFIX   xt_int_permutation

Definition at line 58 of file mergesort.c.

◆ SORT_TYPE_SUFFIX [5/5]

#define SORT_TYPE_SUFFIX   int_permutation

Definition at line 58 of file mergesort.c.

◆ XT_SORT_ASSIGN [1/2]

#define XT_SORT_ASSIGN ( a,
p,
b,
q )
Value:
do { \
(a)[(p)] = (b)[(q)]; \
TOKEN_PASTE(permutation,a)[(p)] = TOKEN_PASTE(permutation,b)[(q)]; \
} while (0)
#define TOKEN_PASTE(a, b)

Definition at line 143 of file mergesort.c.

◆ XT_SORT_ASSIGN [2/2]

#define XT_SORT_ASSIGN ( a,
p,
b,
q )
Value:
do { \
(a)[(p)] = (b)[(q)]; \
TOKEN_PASTE(permutation,a)[(p)] = TOKEN_PASTE(permutation,b)[(q)]; \
} while (0)

Definition at line 143 of file mergesort.c.

◆ XT_SORT_EXTRA_ALLOC_DECL [1/2]

#define XT_SORT_EXTRA_ALLOC_DECL
Value:
int *permutation_v = permutation, \
*permutation_w = roundPtr(XT_SORT_EXTRA_ALLOC, sizeof (int))
static void * roundPtr(void *p, size_t mult)
Definition mergesort.c:128
#define XT_SORT_EXTRA_ALLOC

Definition at line 134 of file mergesort.c.

◆ XT_SORT_EXTRA_ALLOC_DECL [2/2]

#define XT_SORT_EXTRA_ALLOC_DECL
Value:
int *permutation_v = permutation, \
*permutation_w = XT_SORT_EXTRA_ALLOC

Definition at line 134 of file mergesort.c.

◆ XT_SORT_EXTRA_ALLOC_SIZE [1/2]

#define XT_SORT_EXTRA_ALLOC_SIZE   (sizeof(*permutation) * (n+1))

Definition at line 126 of file mergesort.c.

◆ XT_SORT_EXTRA_ALLOC_SIZE [2/2]

#define XT_SORT_EXTRA_ALLOC_SIZE   (sizeof(*permutation) * (n+1))

Definition at line 126 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_DECL [1/2]

#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation

Definition at line 121 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_DECL [2/2]

#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation

Definition at line 121 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_INNER_DECL [1/2]

#define XT_SORT_EXTRA_ARGS_INNER_DECL   , int *restrict permutation_v, int *restrict permutation_w

Definition at line 123 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_INNER_DECL [2/2]

#define XT_SORT_EXTRA_ARGS_INNER_DECL   , int *restrict permutation_v, int *restrict permutation_w

Definition at line 123 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_INNER_PASS [1/2]

#define XT_SORT_EXTRA_ARGS_INNER_PASS ( a,
b )
Value:
, TOKEN_PASTE(permutation,a), \
TOKEN_PASTE(permutation,b)

Definition at line 124 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_INNER_PASS [2/2]

#define XT_SORT_EXTRA_ARGS_INNER_PASS ( a,
b )
Value:
, TOKEN_PASTE(permutation,a), \
TOKEN_PASTE(permutation,b)

Definition at line 124 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_PASS [1/2]

#define XT_SORT_EXTRA_ARGS_PASS   , permutation

Definition at line 122 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_PASS [2/2]

#define XT_SORT_EXTRA_ARGS_PASS   , permutation

Definition at line 122 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_SWAP [1/2]

#define XT_SORT_EXTRA_ARGS_SWAP ( i,
j )
Value:
do { \
size_t i_ = (size_t)(i), j_ = (size_t)(j); \
int tp = permutation_v[i_]; \
permutation_v[i_] = permutation_v[j_]; \
permutation_v[j_] = tp; \
(void)permutation_w; \
} while (0)

Definition at line 136 of file mergesort.c.

◆ XT_SORT_EXTRA_ARGS_SWAP [2/2]

#define XT_SORT_EXTRA_ARGS_SWAP ( i,
j )
Value:
do { \
size_t i_ = (size_t)(i), j_ = (size_t)(j); \
int tp = permutation_v[i_]; \
permutation_v[i_] = permutation_v[j_]; \
permutation_v[j_] = tp; \
(void)permutation_w; \
} while (0)

Definition at line 136 of file mergesort.c.

Function Documentation

◆ roundPtr()

static void * roundPtr ( void * p,
size_t mult )
inlinestatic

Definition at line 128 of file mergesort.c.

◆ xt_mergesort_index()

void xt_mergesort_index ( Xt_int *restrict v_idx,
int n,
int *restrict v_pos,
int reset_pos )
Examples
test_sort.c.

Definition at line 69 of file mergesort.c.

Here is the call graph for this function:

◆ xt_mergesort_xt_int_permutation()

void xt_mergesort_xt_int_permutation ( Xt_int * a,
size_t n,
int *restrict permutation )
Here is the caller graph for this function: