excit.h 21.1 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*******************************************************************************
 * Copyright 2019 UChicago Argonne, LLC.
 * (c.f. AUTHORS, LICENSE)
 *
 * This file is part of the EXCIT project.
 * For more info, see https://xgitlab.cels.anl.gov/argo/excit
 *
 * SPDX-License-Identifier: BSD-3-Clause
*******************************************************************************/
Brice Videau's avatar
Brice Videau committed
10 11 12
#ifndef EXCIT_H
#define EXCIT_H 1

13
#include <stdlib.h>
Brice Videau's avatar
Brice Videau committed
14
#include <sys/types.h>
15

Brice Videau's avatar
Brice Videau committed
16
/*
17 18
 * excit library provides an interface to build multi-dimensional iterators over 
 * indexes.
19 20 21 22 23 24
 * excit iterators walk an array of n elements indexed from 0 to n-1
 * and return the aforementioned elements.
 * excit iterators return elements whose type can be just an index of type ssize_t,
 * or an array of indexes (a multi-dimensional index) if the defined iterator
 * has several dimensions. ssize_t elements can fit pointers. Thus, it makes the
 * excit library an ideal toolbox for indexing and walking complex structures.
25 26
 *
 * excit implements its own interface with several iterators (see excit_type_e).
27 28 29
 * For instance, the excit implementation of product iterators enables the mixing of
 * iterators to create more complex ones. The library balanced tree "tleaf" iterator
 * is built on top of the product iterator.
30
 *
31 32 33 34
 * excit library uses the concept of "ownership".
 * An excit iterator has the ownership of its internal data, i.e., it will free
 * its own data upon call to excit_free(). This ownership
 * may be transferred to another iterator through a library call such as
35
 * excit_cons_init() or excit_product_add().
36
 * Thus, ownership must be carefully watched to avoid memory leaks or double-free.
37 38
 *
 * excit library provides a rank function to find the index given an element.
Brice Videau's avatar
Brice Videau committed
39
 */
40

Brice Videau's avatar
Brice Videau committed
41
enum excit_type_e {
42 43
	/*!< Tag for invalid iterators */
	EXCIT_INVALID,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
44 45
	/*!<
	 * Iterator over an array of indexes.
46
	 * If indexes are unique, the iterator is made invertible (see excit_rank()).
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
47 48
	 */
	EXCIT_INDEX,
49
	/*!<
50
	 * Iterator over a range of values.
51
	 * See function excit_range_init() for further details on this iterator's
52 53 54
	 * behaviour.
	 */
	EXCIT_RANGE,
55
	/*!<
56
	 * Sliding window iterator
57
	 * See function excit_cons_init() for further details on this iterator's
58 59 60
	 * behaviour.
	 */
	EXCIT_CONS,
61
	/*!<
62 63
	 * Iterator that repeat values a certain number of times.
	 * Builds an iterator on top of another iterator repeating the latter's elements.
64
	 * See function excit_repeat_init() for further details on this iterator's
65 66 67
	 * behaviour.
	 */
	EXCIT_REPEAT,
68
	/*!< Hilbert space-filling curve */
69
	EXCIT_HILBERT2D,
70 71 72
	/*!<
	 * Iterator over the cartesian product of iterators.
	 * The resulting iterator's dimension is the sum of input iterators' dimensions.
73 74
	 */
	EXCIT_PRODUCT,
75 76 77 78
	/*!<
	 * Iterator composing two iterators,
	 * i.e., using one iterator to index another.
	 * It is possible to chain composition iterators as long as
79
	 * input and output sets are compatible.
80
	 * (Only the dimension compatibility is not enforced by the library).
81 82 83
	 * It is straightforward to build a composition iterator by composing two range iterators.
	 */
	EXCIT_COMPOSITION,
84
	/*!<
85 86
	 * Iterator on balanced tree leaves.
	 * The iterator walks an index of leaves according to a policy.
87
	 * tleaf iterator has a special tleaf_it_split() function for splitting the
88
	 * tree at a specific level.
89
	 * See tleaf_it_policy_e and excit_tleaf_init() for further explanation.
90 91
	 */
	EXCIT_TLEAF,
92 93 94
	/*!<
	 * User-defined iterator
	 * excit library allows users to define their own iterators.
95
	 * To do so, they need to populate the function table excit_func_table_s
96 97
	 * with the routines to manipulate the aforementioned iterator.
	 * The outcome is that users will enjoy the functionality of the library
98 99 100
	 * for mixing with other iterators.
	 */
	EXCIT_USER,
Brice Videau's avatar
Brice Videau committed
101 102 103 104 105
	/*!<
	 * Interator looping a given amount of time over another iterator.
	 * See excit_loop_init() for further explanation.
         */
	EXCIT_LOOP,
106 107
	/*!< Guard */
	EXCIT_TYPE_MAX
Brice Videau's avatar
Brice Videau committed
108 109
};

Brice Videau's avatar
Brice Videau committed
110 111 112
/*
 * Returns the string representation of an iterator type.
 */
113
const char *excit_type_name(enum excit_type_e type);
114

Brice Videau's avatar
Brice Videau committed
115 116 117
/*
 * The different possible return codes of an excit function.
 */
Brice Videau's avatar
Brice Videau committed
118
enum excit_error_e {
119
	EXCIT_SUCCESS,		/*!< Success */
120 121 122 123 124 125
	EXCIT_STOPIT,		/*!< Iteration space is depleted */
	EXCIT_ENOMEM,		/*!< Out of memory */
	EXCIT_EINVAL,		/*!< Parameter has an invalid value */
	EXCIT_EDOM,		/*!< Parameter is out of possible domain */
	EXCIT_ENOTSUP,		/*!< Operation is not supported */
	EXCIT_ERROR_MAX		/*!< Guard */
Brice Videau's avatar
Brice Videau committed
126
};
Brice Videau's avatar
Brice Videau committed
127

Brice Videau's avatar
Brice Videau committed
128 129 130
/*
 * Returns the string representation of a return code.
 */
131
const char *excit_error_name(enum excit_error_e err);
132

Brice Videau's avatar
Brice Videau committed
133 134 135
/*
 * Opaque structure of an iterator
 */
Brice Videau's avatar
Brice Videau committed
136
typedef struct excit_s *excit_t;
Brice Videau's avatar
Brice Videau committed
137
typedef const struct excit_s *const_excit_t;
Brice Videau's avatar
Brice Videau committed
138

Brice Videau's avatar
Brice Videau committed
139 140 141 142 143
/*******************************************************************************
 * Programming interface for user-defined iterators:
 ******************************************************************************/

/*
144 145
 * Sets the dimension of a (user-defined) iterator.
 * "it": a (user-defined) iterator.
Brice Videau's avatar
Brice Videau committed
146 147 148 149 150 151
 * "dimension": the new dimension of the iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
int excit_set_dimension(excit_t it, ssize_t dimension);

/*
152 153
 * Gets the dimension of an iterator.
 * "it": the iterator.
154
 * Returns the dimension or -1 if the iterator is NULL.
155 156
 */
ssize_t excit_get_dimension(excit_t it);
157

158 159 160
/*
 * Gets the inner data pointer of a (user-defined) iterator.
 * "it": a (user-defined) iterator.
161
 * "data": an address of a pointer variable where the result will be stored.
Brice Videau's avatar
Brice Videau committed
162 163 164 165 166
 * Returns EXCIT_SUCCESS or an error code.
 */
int excit_get_data(excit_t it, void **data);

/*
167 168 169
 * Function table used by iterators. A user-defined iterator must provide its
 * own table; if some of the function pointers are set to NULL, the corresponding
 * functionality will be considered unsupported and the broker will return
Brice Videau's avatar
Brice Videau committed
170 171
 * -EXCIT_ENOTSUP.
 */
Brice Videau's avatar
Brice Videau committed
172
struct excit_func_table_s {
Brice Videau's avatar
Brice Videau committed
173
	/*
174 175
	 * This function is called during excit_alloc(), after the memory
	 * allocation; the inner data pointer will already be set.
Brice Videau's avatar
Brice Videau committed
176 177
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
178
	int (*alloc)(excit_t it);
Brice Videau's avatar
Brice Videau committed
179
	/*
180 181
	 * This function is called during excit_free(). After this function
	 * returns, the iterator and the data will be freed.
Brice Videau's avatar
Brice Videau committed
182
	 */
Brice Videau's avatar
Brice Videau committed
183
	void (*free)(excit_t it);
Brice Videau's avatar
Brice Videau committed
184
	/*
185
	 * This function is called during excit_dup(). It is responsible for
Brice Videau's avatar
Brice Videau committed
186
	 * duplicating the content of the inner data between src_it and dst_it.
187
	 * The internal state of the iterator must also be copied, i.e., subsequent
188
	 * calls to excit_next() must return the same results for both iterators.
Brice Videau's avatar
Brice Videau committed
189 190
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
191
	int (*copy)(excit_t dst_it, const_excit_t src_it);
Brice Videau's avatar
Brice Videau committed
192
	/*
193
	 * This function is responsible for implementing the succession functionality
Brice Videau's avatar
Brice Videau committed
194 195 196
	 * of the iterator.
	 * Returns EXCIT_SUCCESS, EXCIT_STOPIT or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
197
	int (*next)(excit_t it, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
198 199 200 201 202
	/*
	 * This function is responsible for implementing the peek functionality
	 * of the iterator.
	 * Returns EXCIT_SUCCESS, EXCIT_STOPIT or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
203
	int (*peek)(const_excit_t it, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
204 205 206 207 208
	/*
	 * This function is responsible for implementing the size functionality
	 * of the iterator.
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
209
	int (*size)(const_excit_t it, ssize_t *size);
Brice Videau's avatar
Brice Videau committed
210 211 212 213 214
	/*
	 * This function is responsible for implementing the rewind
	 * functionality of the iterator.
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
215
	int (*rewind)(excit_t it);
Brice Videau's avatar
Brice Videau committed
216 217 218 219 220
	/*
	 * This function is responsible for implementing the split
	 * functionality of the iterator.
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
221
	int (*split)(const_excit_t it, ssize_t n, excit_t *results);
Brice Videau's avatar
Brice Videau committed
222 223 224 225 226
	/*
	 * This function is responsible for implementing the nth functionality
	 * of the iterator.
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
227
	int (*nth)(const_excit_t it, ssize_t n, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
228 229 230 231 232
	/*
	 * This function is responsible for implementing the rank functionality
	 * of the iterator.
	 * Returns EXCIT_SUCCESS or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
233
	int (*rank)(const_excit_t it, const ssize_t *indexes, ssize_t *n);
Brice Videau's avatar
Brice Videau committed
234 235 236 237 238
	/*
	 * This function is responsible for implementing the pos functionality
	 * of the iterator.
	 * Returns EXCIT_SUCCESS, EXCIT_STOPIT or an error code.
	 */
Brice Videau's avatar
Brice Videau committed
239
	int (*pos)(const_excit_t it, ssize_t *n);
Brice Videau's avatar
Brice Videau committed
240 241
};

Brice Videau's avatar
Brice Videau committed
242 243 244 245 246 247
/*
 * Sets the function table of an iterator.
 * "it": an iterator.
 * "func_table": a pointer to the new function table.
 * Returns EXCIT_SUCCESS or an error code.
 */
248
int excit_set_func_table(excit_t it, const struct excit_func_table_s *func_table);
Brice Videau's avatar
Brice Videau committed
249 250 251 252

/*
 * Gets a pointer to the function table of an iterator.
 * "it": an iterator.
253 254
 * "func_table": an address of a pointer variable where the result will be
 *               stored.
Brice Videau's avatar
Brice Videau committed
255 256
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
257
int excit_get_func_table(const_excit_t it, const struct excit_func_table_s **func_table);
Brice Videau's avatar
Brice Videau committed
258 259 260 261

/*
 * Allocates a new iterator of the given type.
 * "type": the type of the iterator, cannot be EXCIT_USER.
262 263
 * Returns an iterator (that will need to be freed unless ownership is
 * transferred) or NULL if an error occurred.
Brice Videau's avatar
Brice Videau committed
264
 */
Brice Videau's avatar
Brice Videau committed
265
excit_t excit_alloc(enum excit_type_e type);
Brice Videau's avatar
Brice Videau committed
266 267 268

/*
 * Allocates a user-defined iterator.
269
 * "func_table": the function table the iterator will use.
Brice Videau's avatar
Brice Videau committed
270
 * "data_size": the size of the inner data to allocate.
271 272
 * Returns an iterator (that will need to be freed unless ownership is
 * transferred) or NULL if an error occurred.
Brice Videau's avatar
Brice Videau committed
273
 */
274
excit_t excit_alloc_user(const struct excit_func_table_s *func_table,
275
			 size_t data_size);
Brice Videau's avatar
Brice Videau committed
276 277

/*
278
 * Duplicates an iterator and keeps its internal state.
Brice Videau's avatar
Brice Videau committed
279
 * "it": iterator to duplicate.
280 281
 * Returns an iterator (that will need to be freed unless ownership is
 * transferred) or NULL if an error occurred.
Brice Videau's avatar
Brice Videau committed
282
 */
Brice Videau's avatar
Brice Videau committed
283
excit_t excit_dup(const_excit_t it);
Brice Videau's avatar
Brice Videau committed
284 285

/*
286
 * Frees an iterator and all the iterators it acquired ownership to.
Brice Videau's avatar
Brice Videau committed
287 288
 * "it": iterator to free.
 */
289
void excit_free(excit_t it);
Brice Videau's avatar
Brice Videau committed
290

Brice Videau's avatar
Brice Videau committed
291 292 293
/*
 * Get the type of an iterator
 * "it": an iterator.
294
 * "type": a pointer to the variable where the result will be stored.
Brice Videau's avatar
Brice Videau committed
295 296
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
297
int excit_type(const_excit_t it, enum excit_type_e *type);
Brice Videau's avatar
Brice Videau committed
298 299 300

/*
 * Get the dimension of an iterator. This is the number of elements of the array
301
 * of ssize_t that is expected by the peek, next, nth and rank functionalities.
Brice Videau's avatar
Brice Videau committed
302
 * "it": an iterator.
303
 * "dimension": a pointer to the variable where the result will be stored.
Brice Videau's avatar
Brice Videau committed
304 305
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
306
int excit_dimension(const_excit_t it, ssize_t *dimension);
Brice Videau's avatar
Brice Videau committed
307

Brice Videau's avatar
Brice Videau committed
308 309 310
/*
 * Gets the current element of an iterator and increments it.
 * "it": an iterator.
311 312 313 314 315
 * "indexes": a pointer to an array of indexes with a dimension corresponding to
 *            that of the iterator, where the result will be stored; no result
 *            is returned if NULL.
 * Returns EXCIT_SUCCESS if a valid element was returned, EXCIT_STOPIT if the
 * iterator is depleted, or an error code.
Brice Videau's avatar
Brice Videau committed
316
 */
Brice Videau's avatar
Brice Videau committed
317
int excit_next(excit_t it, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
318 319 320 321

/*
 * Gets the current element of an iterator.
 * "it": an iterator.
322 323 324 325 326
 * "indexes": a pointer to an array of indexes with a dimension corresponding to
 *            that of the iterator, where the result will be stored; no result
 *            is returned if NULL.
 * Returns EXCIT_SUCCESS if a valid element was returned, EXCIT_STOPIT if the
 * iterator is depleted, or an error code.
Brice Videau's avatar
Brice Videau committed
327
 */
Brice Videau's avatar
Brice Videau committed
328
int excit_peek(const_excit_t it, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
329 330 331 332 333 334

/*
 * Rewinds an iterator to its initial state.
 * "it": an iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
335
int excit_rewind(excit_t it);
Brice Videau's avatar
Brice Videau committed
336 337 338 339

/*
 * Gets the number of elements of an iterator.
 * "it": an iterator.
340
 * "size": a pointer to the variable where the result will be stored.
Brice Videau's avatar
Brice Videau committed
341 342
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
343
int excit_size(const_excit_t it, ssize_t *size);
Brice Videau's avatar
Brice Videau committed
344 345

/*
346
 * Splits an iterator evenly into several subiterators.
Brice Videau's avatar
Brice Videau committed
347
 * "it": an iterator.
348 349 350
 * "n": the number of iterators desired.
 * "results": a pointer to an array of at least n excit_t, where the result
 *            will be stored, or NULL in which case no iterator is created.
Brice Videau's avatar
Brice Videau committed
351
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the source iterator is too small to be
352
 * subdivided into the desired number of subiterators, or an error code.
Brice Videau's avatar
Brice Videau committed
353
 */
Brice Videau's avatar
Brice Videau committed
354
int excit_split(const_excit_t it, ssize_t n, excit_t *results);
Brice Videau's avatar
Brice Videau committed
355

Brice Videau's avatar
Brice Videau committed
356
/*
357
 * Gets the nth element of an iterator. If an iterator has k dimensions,
358
 * then the nth element is an array of k nth elements along each dimension.
Brice Videau's avatar
Brice Videau committed
359
 * "it": an iterator.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
360 361
 * "rank": rank of the element, comprised between 0 and the size of the
 *         iterator.
362 363 364
 * "indexes": a pointer to an array of indexes with a dimension corresponding to
 *            that of the iterator, where the result will be stored; no result
 *            is returned if NULL.
Brice Videau's avatar
Brice Videau committed
365 366
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
367
int excit_nth(const_excit_t it, ssize_t rank, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
368 369

/*
370 371 372
 * Gets the rank of an element of an iterator. The rank of an element is its
 * iteration index, i.e., excit_nth(excit_rank(element)) should return the element.
 * If the iterator has k dimensions, element is an array of the k values
373
 * composing element.
Brice Videau's avatar
Brice Videau committed
374
 * "it": an iterator.
375 376
 * "element": an array of indexes corresponding to the element of the iterator.
 * "rank": a pointer to a variable where the result will be stored; no result is
Brice Videau's avatar
Brice Videau committed
377 378 379
 *         returned if NULL.
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
380
int excit_rank(const_excit_t it, const ssize_t *element, ssize_t *rank);
Brice Videau's avatar
Brice Videau committed
381 382 383 384 385

/*
 * Gets the position of the iterator.
 * "it": an iterator.
 * "rank": a pointer to a variable where the rank of the current element will be
386 387
 *         stored; no result is returned if NULL.
 * Returns EXCIT_SUCCESS, EXCIT_STOPIT if the iterator is depleted, or an error
Brice Videau's avatar
Brice Videau committed
388 389
 * code.
 */
Brice Videau's avatar
Brice Videau committed
390
int excit_pos(const_excit_t it, ssize_t *rank);
Brice Videau's avatar
Brice Videau committed
391 392 393 394

/*
 * Increments the iterator.
 * "it": an iterator.
395
 * Returns EXCIT_SUCCESS, EXCIT_STOPIT if the iterator is depleted, or an error
Brice Videau's avatar
Brice Videau committed
396 397
 * code.
 */
398
int excit_skip(excit_t it);
Brice Videau's avatar
Brice Videau committed
399 400 401 402 403

/*
 * Gets the current element of an iterator, rewinding it first if the iterator
 * was depleted. The iterator is incremented.
 * "it": an iterator.
404 405 406 407 408
 * "indexes": a pointer to an array of indexes with a dimension corresponding to
 *            that of the iterator, where the result will be stored; no result
 *            is returned if NULL.
 * "looped": a pointer to a variable where the information will be stored on
 *           whether the iterator was rewound (1) or not (0).
Brice Videau's avatar
Brice Videau committed
409 410
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
411
int excit_cyclic_next(excit_t it, ssize_t *indexes, int *looped);
Brice Videau's avatar
Brice Videau committed
412

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
413 414
/*
 * Initialize an index iterator with a set of indexes.
415 416 417 418
 * "it": an index iterator.
 * "len": length of the "index" array (dimension of the iterator).
 * "index": an array of indexes.
 * Returns EXCIT_SUCCESS or an error code.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
419
 */
Brice Videau's avatar
Brice Videau committed
420
int excit_index_init(excit_t it, ssize_t len, const ssize_t *index);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
421

Brice Videau's avatar
Brice Videau committed
422
/*
423
 * Initializes a range iterator to iterate from first to last (included) by step.
Brice Videau's avatar
Brice Videau committed
424 425 426
 * "it": a range iterator.
 * "first": first value of the range.
 * "last": last value of the range.
427
 * "step": between elements of the range. Must be nonzero, can be negative.
Brice Videau's avatar
Brice Videau committed
428 429
 * Returns EXCIT_SUCCESS or an error code.
 */
430
int excit_range_init(excit_t it, ssize_t first, ssize_t last, ssize_t step);
Brice Videau's avatar
Brice Videau committed
431

Brice Videau's avatar
Brice Videau committed
432 433
/*
 * Initializes a sliding window iterator over another iterator.
434 435 436
 * "it": a sliding window iterator.
 * "src": the original iterator. Ownership is transferred.
 * "n": size of the window, must not exceed the size of the src
Brice Videau's avatar
Brice Videau committed
437 438 439
 *      iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
440
int excit_cons_init(excit_t it, excit_t src, ssize_t n);
Brice Videau's avatar
Brice Videau committed
441

Brice Videau's avatar
Brice Videau committed
442 443 444
/*
 * Initializes a repeat iterator over another iterator.
 * "it": a repeat iterator.
445 446
 * "src": the original iterator. Ownership is transferred.
 * "n": the number of repeat of each element of the src iterator.
Brice Videau's avatar
Brice Videau committed
447 448
 * Returns EXCIT_SUCCESS or an error code.
 */
449
int excit_repeat_init(excit_t it, excit_t src, ssize_t n);
Brice Videau's avatar
Brice Videau committed
450

Brice Videau's avatar
Brice Videau committed
451 452
/*
 * Splits a repeat iterator between repetitions.
453 454 455 456
 * "it": a repeat iterator.
 * "n": the number of iterators desired.
 * "results": a pointer to an array of at least n excit_t where the result will
 *            be stored, or NULL in which case no iterator is created.
Brice Videau's avatar
Brice Videau committed
457
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the selected iterator is too small to
458
 * be subdivided in the desired number of iterators, or an error code.
Brice Videau's avatar
Brice Videau committed
459
 */
Brice Videau's avatar
Brice Videau committed
460
int excit_repeat_split(const_excit_t it, ssize_t n, excit_t *results);
Brice Videau's avatar
Brice Videau committed
461

Brice Videau's avatar
Brice Videau committed
462
/*
463 464 465
 * Creates a two-dimensional Hilbert space-filling curve iterator.
 * "it": a hilbert2d iterator.
 * "order": determines the iteration space: (2^order - 1)^2.
Brice Videau's avatar
Brice Videau committed
466 467
 * Returns EXCIT_SUCCESS or an error code.
 */
468
int excit_hilbert2d_init(excit_t it, ssize_t order);
Brice Videau's avatar
Brice Videau committed
469

Brice Videau's avatar
Brice Videau committed
470 471
/*
 * Adds another iterator to a product iterator.
472 473
 * "it": a product iterator.
 * "added_it": the added iterator. Ownership is transferred.
Brice Videau's avatar
Brice Videau committed
474 475
 * Returns EXCIT_SUCCESS or an error code.
 */
476
int excit_product_add(excit_t it, excit_t added_it);
Brice Videau's avatar
Brice Videau committed
477 478

/*
479
 * Adds another iterator to a product iterator without transferring ownership.
Brice Videau's avatar
Brice Videau committed
480
 * "it": a product iterator.
481
 * "added_it": the added iterator. Ownership is not transferred; a duplicate is
Brice Videau's avatar
Brice Videau committed
482 483 484
 *             created instead.
 * Returns EXCIT_SUCCESS or an error code.
 */
485
int excit_product_add_copy(excit_t it, excit_t added_it);
Brice Videau's avatar
Brice Videau committed
486 487

/*
488
 * Gets the number of iterators inside a product iterator.
Brice Videau's avatar
Brice Videau committed
489 490 491 492
 * "it": a product iterator.
 * "count": a pointer to a variable where the result will be stored.
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
493
int excit_product_count(const_excit_t it, ssize_t *count);
Brice Videau's avatar
Brice Videau committed
494 495 496 497 498 499

/*
 * Splits a product iterator along the nth iterator.
 * "it": a product iterator.
 * "dim": the number of the iterator to split, must be comprised between 0 and
 *        the number of iterator inside the product iterator - 1.
500 501 502
 * "n": the number of iterators desired.
 * "results": a pointer to an array of at least n excit_t, where the result
 *            will be stored, or NULL in which case no iterator is created.
Brice Videau's avatar
Brice Videau committed
503
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the selected iterator is too small to
504
 * be subdivided into the desired number of iterators, or an error code.
Brice Videau's avatar
Brice Videau committed
505
 */
Brice Videau's avatar
Brice Videau committed
506
int excit_product_split_dim(const_excit_t it, ssize_t dim, ssize_t n,
Brice Videau's avatar
Brice Videau committed
507
			    excit_t *results);
Brice Videau's avatar
Brice Videau committed
508

Brice Videau's avatar
Brice Videau committed
509
/*
510 511
 * Initializes a composition iterator by giving a src iterator and an indexer iterator.
 * "it": a composition iterator.
512
 * "src": the iterator whose elements are to be returned.
Brice Videau's avatar
Brice Videau committed
513 514 515
 * "indexer": the iterator that will provide the rank of the elements to return.
 * Returns EXCIT_SUCCESS or an error code.
 */
516
int excit_composition_init(excit_t it, excit_t src, excit_t indexer);
517

Brice Videau's avatar
Brice Videau committed
518 519 520 521 522 523 524 525 526
/*
 * Initializes a loop iterator by giving a src iterator and a number of loops to achieve.
 * "it": a loop iterator.
 * "src": the iterator to loop over.
 * "n": the number of time to loop over the src iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
int excit_loop_init(excit_t it, excit_t src, ssize_t n);

527
enum tleaf_it_policy_e {
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
528
  TLEAF_POLICY_ROUND_ROBIN, /* Iterate on tree leaves in a round-robin fashion */
529 530
  TLEAF_POLICY_SCATTER, /* Iterate on tree leaves spreading as much as possible */
  TLEAF_POLICY_USER /* Policy is user-defined */
531 532 533
};

/*
534 535 536 537
 * Initializes a tleaf iterator by giving its depth, levels of arity and iteration policy.
 * Example building a user scatter policy:
 *         excit_tleaf_init(it, 4, {3, 2, 4}, NULL, TLEAF_POLICY_USER, {2, 1, 0});
 * gives the output index:
538
 *         0,6,12,18,3,9,15,21,1,7,13,19,4,10,16,22,2,8,14,20,5,11,17,23.
539 540 541
 * "it": a tleaf iterator.
 * "depth": the total number of levels of the tree, including leaves.
 * "arity": An array  of size (depth-1). For each level, specifies the number of children attached to a node.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
542
 *          Leaves have no children. Arities are organized from root to leaves.
543
 * "index": NULL or an array of depth excit_t to re-index levels.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
544
 *          It is intended to prune node of certain levels while keeping index of the initial structure.
545
 *          Ownership of index is not taken. The iterator allocates a copy of index and manages it internally.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
546
 * "policy": A policy for iteration on leaves.
547 548 549 550 551 552
 * "user_policy": If policy is TLEAF_POLICY_USER, then this argument must be an array of size (depth-1) providing the
 *                order (from 0 to (depth-2)) in which levels are walked
 *                when resolving indexes. Underneath, a product iterator of range iterator returns indexes on last
 *                levels upon iterator queries. This set of indexes is then
 *                computed to a single leaf index. For instance TLEAF_POLICY_ROUND_ROBIN is obtained from walking
 *                from leaves to root whereas TLEAF_POLICY_SCATTER is
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
553
 *                obtained from walking from root to leaves.
554
 * Returns EXCIT_SUCCESS or an error code.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
555 556
 */
int excit_tleaf_init(excit_t it,
557
		     ssize_t depth,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
558
		     const ssize_t *arities,
Brice Videau's avatar
Brice Videau committed
559
		     excit_t *index,
560
		     enum tleaf_it_policy_e policy,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
561
		     const ssize_t *user_policy);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
562 563

/*
564 565
 * Splits a tree at a given level. The behaviour is different from the generic function excit_split for the
 * split might be sparse, depending on the tree level where the split occurs and the number of parts.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
566 567
 * "it": a tleaf iterator.
 * "level": The level to split.
568
 * "n": The number of parts. n must divide the target level arity.
569 570 571
 * "out": an array of n allocated tleaf iterators where the result will be stored.
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the arity of the selected level is too small to
 * be subdivided into the desired number of iterators, or an error code.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
572
 */
Brice Videau's avatar
Brice Videau committed
573
int tleaf_it_split(const_excit_t it, ssize_t level, ssize_t n, excit_t *out);
574

Brice Videau's avatar
Brice Videau committed
575
#endif