xt_idxstripes.c File Reference

#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "xt/xt_core.h"
#include "xt_arithmetic_util.h"
#include "xt/xt_idxlist.h"
#include "xt_idxlist_internal.h"
#include "xt/xt_idxempty.h"
#include "xt/xt_idxvec.h"
#include "xt/xt_idxstripes.h"
#include "xt_idxstripes_internal.h"
#include "xt_stripe_util.h"
#include "xt/xt_mpi.h"
#include "xt/xt_sort.h"
#include "xt_idxlist_unpack.h"
#include "xt_cover.h"
#include "core/core.h"
#include "core/ppm_xfuncs.h"
#include "ensure_array_size.h"
#include "instr.h"

Include dependency graph for xt_idxstripes.c:

Go to the source code of this file.

Data Structures
struct	Xt_stripes_sort
struct	Xt_idxstripes_
struct	extended_gcd
struct	Xt_stripes_lookup
struct	int_vec
struct	unmatched_tail

Macros
#define	MIN(a, b)   (((a)<(b))?(a):(b))
#define	MAX(a, b)   (((a)>(b))?(a):(b))

Typedefs
typedef struct Xt_idxstripes_ *	Xt_idxstripes

Enumerations
enum	{ stripes_do_overlap_bit = 0, stripes_some_have_zero_stride_bit, stripes_do_overlap_mask = 1 << stripes_do_overlap_bit, stripes_some_have_zero_stride_mask = 1 << stripes_some_have_zero_stride_bit }

Functions
static void	idxstripes_delete (Xt_idxlist data)
static size_t	idxstripes_get_pack_size (Xt_idxlist data, MPI_Comm comm)
static void	idxstripes_pack (Xt_idxlist data, void *buffer, int buffer_size, int *position, MPI_Comm comm)
static Xt_idxlist	idxstripes_copy (Xt_idxlist idxlist)
static void	idxstripes_get_indices (Xt_idxlist idxlist, Xt_int *indices)
static const Xt_int *	idxstripes_get_indices_const (Xt_idxlist idxlist)
static void	idxstripes_get_index_stripes (Xt_idxlist idxlist, struct Xt_stripe **stripes, int *num_stripes)
static int	idxstripes_get_index_at_position (Xt_idxlist idxlist, int position, Xt_int *index)
static int	idxstripes_get_indices_at_positions (Xt_idxlist idxlist, const int *positions, int num, Xt_int *index, Xt_int undef_idx)
static int	idxstripes_get_pos_exts_of_index_stripes (Xt_idxlist idxlist, int num_stripes, const struct Xt_stripe *stripes, int *num_ext, struct Xt_pos_ext **pos_ext, int single_match_only)
static int	idxstripes_get_position_of_index (Xt_idxlist idxlist, Xt_int index, int *position)
static int	idxstripes_get_position_of_index_off (Xt_idxlist idxlist, Xt_int index, int *position, int offset)
static Xt_int	idxstripes_get_min_index (Xt_idxlist idxlist)
static Xt_int	idxstripes_get_max_index (Xt_idxlist idxlist)
void	xt_idxstripes_initialize (void)
void	xt_idxstripes_finalize (void)
static int	compare_xtstripes (const void *a_, const void *b_)
static void	idxstripes_aggregate (Xt_idxstripes idxstripes, const char *caller)
Xt_idxlist	xt_idxstripes_new (struct Xt_stripe const *stripes, int num_stripes)
Xt_idxlist	xt_idxstripes_from_idxlist_new (Xt_idxlist idxlist_src)
Xt_idxlist	xt_idxstripes_prealloc_new (const struct Xt_stripe *stripes, int num_stripes)
Xt_idxlist	xt_idxstripes_unpack (void *buffer, int buffer_size, int *position, MPI_Comm comm)
static Xt_idxlist	compute_intersection_fallback (Xt_idxstripes idxstripes_src, Xt_idxstripes idxstripes_dst)
static struct extended_gcd	extended_gcd (Xt_int a, Xt_int b)
static struct Xt_stripe	get_stripe_intersection (struct Xt_stripe stripe_a, struct Xt_stripe stripe_b)
static Xt_idxlist	idxstripes_compute_intersection (Xt_idxstripes idxstripes_src, Xt_idxstripes idxstripes_dst)
Xt_idxlist	xt_idxstripes_get_intersection (Xt_idxlist idxlist_src, Xt_idxlist idxlist_dst)
static void	append_ext (struct Xt_pos_ext pos_ext, struct Xt_pos_ext_vec *restrict result)
static void	create_stripes_lookup (struct Xt_stripes_lookup *restrict db, Xt_idxstripes idxstripes)
static void	destroy_stripes_lookup (struct Xt_stripes_lookup *restrict db)
static size_t	bsearch_stripes_sort (size_t n, const struct Xt_stripes_sort a[n], Xt_int min_key)
static void	find_candidates (struct Xt_stripe query, const struct Xt_stripes_lookup *restrict db, struct int_vec *candidates)
static struct Xt_idxstripes_ *	expand_zero_stripes (size_t num_stripes, const struct Xt_stripe *restrict stripes)
static size_t	idxstripes_get_pos_exts_of_index_stripe (struct Xt_stripe query, const struct Xt_stripes_lookup *restrict db, struct Xt_pos_ext_vec *restrict result, struct Xt_pos_ext_vec *restrict cover, bool single_match_only, size_t num_candidates, int *restrict candidates)
int	idxstripes_get_pos_exts_of_index_stripes (Xt_idxlist idxlist, int num_stripes, const struct Xt_stripe stripes[num_stripes], int *num_ext, struct Xt_pos_ext **pos_exts, int single_match_only)
static size_t	conditional_pos_ext_insert (struct Xt_stripe query, struct Xt_pos_ext pos_ext2add, const struct Xt_stripes_lookup *restrict db, struct Xt_pos_ext_vec *restrict result, struct Xt_pos_ext_vec *restrict cover, size_t num_candidates, int *restrict candidates)
static struct unmatched_tail	idxstripes_complex_get_pos_exts_of_index_stripe (struct Xt_stripe query, const struct Xt_stripes_lookup *restrict stripes_lookup, struct Xt_pos_ext_vec *restrict result, struct Xt_pos_ext_vec *restrict cover, bool single_match_only, size_t num_candidates, int *restrict candidates)
static size_t	pos_ext_insert (struct Xt_stripe query, struct Xt_pos_ext pos_ext2add, const struct Xt_stripes_lookup *stripes_lookup, struct Xt_pos_ext_vec *restrict result, struct Xt_pos_ext_vec *restrict cover, bool single_match_only, size_t num_candidates, int *restrict candidates)

Variables
static const struct xt_idxlist_vtable	idxstripes_vtable
static MPI_Datatype	stripe_dt

Detailed Description

Copyright

Copyright (C) 2016 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

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 xt_idxstripes.c.

Macro Definition Documentation

MAX

#define MAX	(		a,
			b
	)		(((a)>(b))?(a):(b))

Definition at line 76 of file xt_idxstripes.c.

MIN

#define MIN	(		a,
			b
	)		(((a)<(b))?(a):(b))

Definition at line 75 of file xt_idxstripes.c.

Typedef Documentation

Xt_idxstripes

typedef struct Xt_idxstripes_* Xt_idxstripes

Definition at line 191 of file xt_idxstripes.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
stripes_do_overlap_bit
stripes_some_have_zero_stride_bit
stripes_do_overlap_mask
stripes_some_have_zero_stride_mask

Definition at line 202 of file xt_idxstripes.c.

Function Documentation

append_ext()

static void append_ext ( struct Xt_pos_ext  pos_ext, struct Xt_pos_ext_vec *restrict  result  )

inlinestatic

Definition at line 954 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

bsearch_stripes_sort()

static size_t bsearch_stripes_sort ( size_t  n, const struct Xt_stripes_sort  a[n], Xt_int  min_key  )

inlinestatic

Definition at line 1021 of file xt_idxstripes.c.

Here is the caller graph for this function:

compare_xtstripes()

static int compare_xtstripes ( const void *  a_, const void *  b_  )

static

Definition at line 223 of file xt_idxstripes.c.

Here is the caller graph for this function:

compute_intersection_fallback()

static Xt_idxlist compute_intersection_fallback ( Xt_idxstripes  idxstripes_src, Xt_idxstripes  idxstripes_dst  )

static

Definition at line 459 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

conditional_pos_ext_insert()

static size_t conditional_pos_ext_insert ( struct Xt_stripe  query, struct Xt_pos_ext  pos_ext2add, const struct Xt_stripes_lookup *restrict  db, struct Xt_pos_ext_vec *restrict  result, struct Xt_pos_ext_vec *restrict  cover, size_t  num_candidates, int *restrict  candidates  )

static

Definition at line 1361 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

create_stripes_lookup()

static void create_stripes_lookup ( struct Xt_stripes_lookup *restrict  db, Xt_idxstripes  idxstripes  )

inlinestatic

Definition at line 989 of file xt_idxstripes.c.

Here is the caller graph for this function:

destroy_stripes_lookup()

static void destroy_stripes_lookup ( struct Xt_stripes_lookup *restrict  db )

inlinestatic

Definition at line 1010 of file xt_idxstripes.c.

Here is the caller graph for this function:

expand_zero_stripes()

static struct Xt_idxstripes_* expand_zero_stripes ( size_t  num_stripes, const struct Xt_stripe *restrict  stripes  )

static

Definition at line 1117 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

extended_gcd()

static struct extended_gcd extended_gcd ( Xt_int  a, Xt_int  b  )

static

Definition at line 492 of file xt_idxstripes.c.

Here is the caller graph for this function:

find_candidates()

static void find_candidates ( struct Xt_stripe  query, const struct Xt_stripes_lookup *restrict  db, struct int_vec *  candidates  )

static

Definition at line 1045 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

get_stripe_intersection()

static struct Xt_stripe get_stripe_intersection ( struct Xt_stripe  stripe_a, struct Xt_stripe  stripe_b  )

static

Definition at line 516 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

idxstripes_aggregate()

static void idxstripes_aggregate ( Xt_idxstripes  idxstripes, const char *  caller  )

static

Definition at line 231 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

idxstripes_complex_get_pos_exts_of_index_stripe()

static struct unmatched_tail idxstripes_complex_get_pos_exts_of_index_stripe ( struct Xt_stripe  query, const struct Xt_stripes_lookup *restrict  stripes_lookup, struct Xt_pos_ext_vec *restrict  result, struct Xt_pos_ext_vec *restrict  cover, bool  single_match_only, size_t  num_candidates, int *restrict  candidates  )

static

Definition at line 1463 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

idxstripes_compute_intersection()

static Xt_idxlist idxstripes_compute_intersection ( Xt_idxstripes  idxstripes_src, Xt_idxstripes  idxstripes_dst  )

static

Definition at line 608 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

idxstripes_copy()

static Xt_idxlist idxstripes_copy ( Xt_idxlist  idxlist )

static

Definition at line 722 of file xt_idxstripes.c.

Here is the call graph for this function:

idxstripes_delete()

static void idxstripes_delete ( Xt_idxlist  data )

static

Definition at line 374 of file xt_idxstripes.c.

idxstripes_get_index_at_position()

static int idxstripes_get_index_at_position ( Xt_idxlist  idxlist, int  position, Xt_int *  index  )

static

Definition at line 815 of file xt_idxstripes.c.

idxstripes_get_index_stripes()

static void idxstripes_get_index_stripes ( Xt_idxlist  idxlist, struct Xt_stripe **  stripes, int *  num_stripes  )

static

Definition at line 766 of file xt_idxstripes.c.

idxstripes_get_indices()

static void idxstripes_get_indices ( Xt_idxlist  idxlist, Xt_int *  indices  )

static

Todo:

use memcpy with index_array_cache if available

Definition at line 730 of file xt_idxstripes.c.

Here is the caller graph for this function:

idxstripes_get_indices_at_positions()

static int idxstripes_get_indices_at_positions ( Xt_idxlist  idxlist, const int *  positions, int  num, Xt_int *  index, Xt_int  undef_idx  )

static

Definition at line 844 of file xt_idxstripes.c.

idxstripes_get_indices_const()

static Xt_int const * idxstripes_get_indices_const ( Xt_idxlist  idxlist )

static

Definition at line 747 of file xt_idxstripes.c.

Here is the call graph for this function:

idxstripes_get_max_index()

static Xt_int idxstripes_get_max_index ( Xt_idxlist  idxlist )

static

Definition at line 1588 of file xt_idxstripes.c.

idxstripes_get_min_index()

static Xt_int idxstripes_get_min_index ( Xt_idxlist  idxlist )

static

Definition at line 1582 of file xt_idxstripes.c.

idxstripes_get_pack_size()

static size_t idxstripes_get_pack_size ( Xt_idxlist  data, MPI_Comm  comm  )

static

Definition at line 385 of file xt_idxstripes.c.

idxstripes_get_pos_exts_of_index_stripe()

size_t idxstripes_get_pos_exts_of_index_stripe ( struct Xt_stripe  query, const struct Xt_stripes_lookup *restrict  db, struct Xt_pos_ext_vec *restrict  result, struct Xt_pos_ext_vec *restrict  cover, bool  single_match_only, size_t  num_candidates, int *restrict  candidates  )

static

Definition at line 1265 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

idxstripes_get_pos_exts_of_index_stripes() [1/2]

static int idxstripes_get_pos_exts_of_index_stripes ( Xt_idxlist  idxlist, int  num_stripes, const struct Xt_stripe *  stripes, int *  num_ext, struct Xt_pos_ext **  pos_ext, int  single_match_only  )

static

idxstripes_get_pos_exts_of_index_stripes() [2/2]

int idxstripes_get_pos_exts_of_index_stripes	(	Xt_idxlist	idxlist,
		int	num_stripes,
		const struct Xt_stripe	stripes[num_stripes],
		int *	num_ext,
		struct Xt_pos_ext **	pos_exts,
		int	single_match_only
	)

Definition at line 1157 of file xt_idxstripes.c.

Here is the call graph for this function:

idxstripes_get_position_of_index()

static int idxstripes_get_position_of_index ( Xt_idxlist  idxlist, Xt_int  index, int *  position  )

static

Definition at line 898 of file xt_idxstripes.c.

Here is the call graph for this function:

idxstripes_get_position_of_index_off()

static int idxstripes_get_position_of_index_off ( Xt_idxlist  idxlist, Xt_int  index, int *  position, int  offset  )

static

Definition at line 905 of file xt_idxstripes.c.

Here is the caller graph for this function:

idxstripes_pack()

static void idxstripes_pack ( Xt_idxlist  data, void *  buffer, int  buffer_size, int *  position, MPI_Comm  comm  )

static

Definition at line 400 of file xt_idxstripes.c.

pos_ext_insert()

static size_t pos_ext_insert ( struct Xt_stripe  query, struct Xt_pos_ext  pos_ext2add, const struct Xt_stripes_lookup *  stripes_lookup, struct Xt_pos_ext_vec *restrict  result, struct Xt_pos_ext_vec *restrict  cover, bool  single_match_only, size_t  num_candidates, int *restrict  candidates  )

static

Definition at line 1243 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

xt_idxstripes_finalize()

void xt_idxstripes_finalize

(

void

)

Definition at line 186 of file xt_idxstripes.c.

Here is the caller graph for this function:

xt_idxstripes_from_idxlist_new()

Xt_idxlist xt_idxstripes_from_idxlist_new

(

Xt_idxlist

idxlist_src

)

Creates an index list that is built up of stripes of indices by converting another index list into stripes.

Parameters

[in]

idxlist_src

list to convert into stripes

Definition at line 320 of file xt_idxstripes.c.

Here is the call graph for this function:

xt_idxstripes_get_intersection()

Xt_idxlist xt_idxstripes_get_intersection	(	Xt_idxlist	idxlist_src,
		Xt_idxlist	idxlist_dst
	)

Definition at line 708 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

xt_idxstripes_initialize()

void xt_idxstripes_initialize

(

void

)

Definition at line 155 of file xt_idxstripes.c.

Here is the caller graph for this function:

xt_idxstripes_new()

Xt_idxlist xt_idxstripes_new	(	struct Xt_stripe const *	stripes,
		int	num_stripes
	)

Generates an index list that is built up of stripes of indices.

Parameters

[in]	stripes	array defining the stripes
[in]	num_stripes	number of stripes

Definition at line 287 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

xt_idxstripes_prealloc_new()

Xt_idxlist xt_idxstripes_prealloc_new	(	struct Xt_stripe const *	stripes,
		int	num_stripes
	)

Generates an index list that is built up of stripes of indices. Does not copy the stripes.

Parameters

[in]	stripes	array defining the stripes
[in]	num_stripes	number of stripes

Definition at line 351 of file xt_idxstripes.c.

Here is the call graph for this function:

Here is the caller graph for this function:

xt_idxstripes_unpack()

Xt_idxlist xt_idxstripes_unpack	(	void *	buffer,
		int	buffer_size,
		int *	position,
		MPI_Comm	comm
	)

Definition at line 420 of file xt_idxstripes.c.

Here is the call graph for this function:

Variable Documentation

idxstripes_vtable

const struct xt_idxlist_vtable idxstripes_vtable

static

Initial value:

= {
  .delete                       = idxstripes_delete,
  .get_pack_size                = idxstripes_get_pack_size,
  .pack                         = idxstripes_pack,
  .copy                         = idxstripes_copy,
  .get_indices                  = idxstripes_get_indices,
  .get_indices_const            = idxstripes_get_indices_const,
  .get_index_stripes            = idxstripes_get_index_stripes,
  .get_index_at_position        = idxstripes_get_index_at_position,
  .get_indices_at_positions     = idxstripes_get_indices_at_positions,
  .get_position_of_index        = idxstripes_get_position_of_index,
  .get_positions_of_indices     = NULL,
  .get_pos_exts_of_index_stripes = idxstripes_get_pos_exts_of_index_stripes,
  .get_position_of_index_off    = idxstripes_get_position_of_index_off,
  .get_positions_of_indices_off = NULL,
  .get_min_index                = idxstripes_get_min_index,
  .get_max_index                = idxstripes_get_max_index,
  .get_bounding_box             = NULL,
  .idxlist_pack_code            = STRIPES,
}

Definition at line 131 of file xt_idxstripes.c.

stripe_dt

MPI_Datatype stripe_dt

static

Definition at line 152 of file xt_idxstripes.c.