excit.h 19.1 KB
Newer Older
Brice Videau's avatar
Brice Videau committed
1
2
3
#ifndef EXCIT_H
#define EXCIT_H 1

4
5
#include <stdlib.h>

Brice Videau's avatar
Brice Videau committed
6
/*
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 * excit library provides an interface to build multi-dimensional iterators over 
 * indexes.
 * excit iterators walk an array of n elements indexed from 0 to n-1,
 * and returns the aforementionned elements.
 * excit return elements which type can only be 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
 * excit library the ideal tool box for indexing and ealking complex structures.
 *
 * excit implements its own interface with several iterators (see excit_type_e).
 * For instance, excit implementation of product iterators enable to mix iterators 
 * to create more complex ones. The library balanced tree "tleaf" iterator is built
 * on top of product iterator.
 *
 * excit library uses the concept of "ownership". 
 * An excit iterator has the ownership of its internal data, i.e it will free
 * its owned data upon call to excit_free(). This ownership
 * may be transferred to another iterator through a library function such as
 * excit_cons_init() or excit_product_add().
 * Thus ownership must be carefully watched to avoid memory leaks or double free.
 *
 * excit library provides a rank function to find the index given an element.
Brice Videau's avatar
Brice Videau committed
29
 */
30

Brice Videau's avatar
Brice Videau committed
31
enum excit_type_e {
32
33
	/*!< Tag for invalid iterators */
	EXCIT_INVALID,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
34
35
36
37
38
	/*!<
	 * Iterator over an array of indexes.
	 * If indexes are uniques, the iterator is made inversible (see excit_rank()).
	 */
	EXCIT_INDEX,
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
	/*!< 
	 * Iterator over a range of values.
	 * See function excit_range_init for further details on iterator
	 * behaviour.
	 */
	EXCIT_RANGE,
	/*!< 
	 * Sliding window iterator
	 * See function excit_cons_init for further details on iterator
	 * behaviour.
	 */
	EXCIT_CONS,
	/*!< 
	 * Iterator that stutters a certain amount of times. 
	 * Builds an iterator on top of another iterator repeating the latter elements.
	 * See function excit_repeat_init() for further details on iterator
	 * behaviour.
	 */
	EXCIT_REPEAT,
	/*!< Hilbert space filing curve */
	EXCIT_HILBERT2D,
	/*!< 
	 * Iterator over the catesian product of iterators.
	 * The result iterator dimension is the sum of of input iterator dimensions.
	 */
	EXCIT_PRODUCT,
	/*!< 
	 * Iterator composing two iterators, 
	 * i.e using an iterator to index another.
	 * It is possible to chain composition iterators as long as 
	 * input and output sets are compatible.
	 * (Only dimension compatibility is not enforced by the library).
	 * It is straightforward to build a composition iterator by composing two range iterators.
	 */
	EXCIT_COMPOSITION,
	/*!< 
	 * Iterator on balanced tree leaves.
	 * The iterator walks an index of leaves according to a policy.
	 * tleaf iterator has a special tleaf_it_split() for splitting the
	 * tree at a specific level.
	 * See tleaf_it_policy_e and excit_tleaf_init() for further explaination.
	 */
	EXCIT_TLEAF,
	/*!< 
	 * User-defined iterator 
	 * excit library allow users to define their own iterator.
	 * To do so, they need to populate the function table excit_func_table_s
	 * with the routines to manipulate the aforementionned iterator. 
	 * The outcome is that they will enjoy the functionnalities of the library
	 * for mixing with other iterators.
	 */
	EXCIT_USER,
	/*!< Guard */
	EXCIT_TYPE_MAX
Brice Videau's avatar
Brice Videau committed
93
94
};

Brice Videau's avatar
Brice Videau committed
95
96
97
/*
 * Returns the string representation of an iterator type.
 */
98
const char *excit_type_name(enum excit_type_e type);
99

Brice Videau's avatar
Brice Videau committed
100
101
102
/*
 * The different possible return codes of an excit function.
 */
Brice Videau's avatar
Brice Videau committed
103
enum excit_error_e {
104
105
106
107
108
109
110
	EXCIT_SUCCESS,		/*!< Sucess */
	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
111
};
Brice Videau's avatar
Brice Videau committed
112

Brice Videau's avatar
Brice Videau committed
113
114
115
/*
 * Returns the string representation of a return code.
 */
116
const char *excit_error_name(enum excit_error_e err);
117

Brice Videau's avatar
Brice Videau committed
118
119
120
/*
 * Opaque structure of an iterator
 */
Brice Videau's avatar
Brice Videau committed
121
122
typedef struct excit_s *excit_t;

Brice Videau's avatar
Brice Videau committed
123
124
125
126
127
/*******************************************************************************
 * Programming interface for user-defined iterators:
 ******************************************************************************/

/*
128
129
 * Sets the dimension of a (user-defined) iterator.
 * "it": a (user-defined) iterator.
Brice Videau's avatar
Brice Videau committed
130
131
132
133
134
135
 * "dimension": the new dimension of the iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
int excit_set_dimension(excit_t it, ssize_t dimension);

/*
136
137
138
139
140
141
142
143
144
 * Gets the dimension of an iterator.
 * "it": the iterator.
 * Returns the dimension or -1 if it is NULL.
 */
ssize_t excit_get_dimension(excit_t it);
  
/*
 * Gets the inner data pointer of a (user-defined) iterator.
 * "it": a (user-defined) iterator.
Brice Videau's avatar
Brice Videau committed
145
146
147
148
149
150
151
152
153
154
155
 * "data": a pointer to a pointer variable where the result will be written.
 * Returns EXCIT_SUCCESS or an error code.
 */
int excit_get_data(excit_t it, void **data);

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

Brice Videau's avatar
Brice Videau committed
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
/*
 * 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.
 */
int excit_set_func_table(excit_t it, struct excit_func_table_s *func_table);

/*
 * Gets a pointer to the function table of an iterator.
 * "it": an iterator.
 * "func_table": a pointer to a pointer variable where the result will be
 *               written.
 * Returns EXCIT_SUCCESS or an error code.
 */
int excit_get_func_table(excit_t it, struct excit_func_table_s **func_table);

/*
 * Allocates a new iterator of the given type.
 * "type": the type of the iterator, cannot be EXCIT_USER.
 * Returns an iterator that will need to be freed unless ownership is
 * transfered or NULL if an error occured.
 */
Brice Videau's avatar
Brice Videau committed
249
excit_t excit_alloc(enum excit_type_e type);
Brice Videau's avatar
Brice Videau committed
250
251
252
253
254
255
256
257
258

/*
 * Allocates a user-defined iterator.
 * "func_table": the table of function excit will use.
 * "data_size": the size of the inner data to allocate.
 * Returns an iterator that will need to be freed unless ownership is
 * transfered or NULL if an error occured.
 */
excit_t excit_alloc_user(struct excit_func_table_s *func_table,
259
			 size_t data_size);
Brice Videau's avatar
Brice Videau committed
260
261

/*
262
 * Duplicates an iterator and keep its internal state.
Brice Videau's avatar
Brice Videau committed
263
264
265
266
 * "it": iterator to duplicate.
 * Returns an iterator that will need to be freed unless ownership is
 * transfered or NULL if an error occured.
 */
267
excit_t excit_dup(const excit_t it);
Brice Videau's avatar
Brice Videau committed
268
269
270
271
272

/*
 * Frees an iterator and all the iterators it aquired ownership to.
 * "it": iterator to free.
 */
273
void excit_free(excit_t it);
Brice Videau's avatar
Brice Videau committed
274

Brice Videau's avatar
Brice Videau committed
275
276
277
278
279
280
/*
 * Get the type of an iterator
 * "it": an iterator.
 * "type": a pointer where the result will be written.
 * Returns EXCIT_SUCCESS or an error code.
 */
281
int excit_type(excit_t it, enum excit_type_e *type);
Brice Videau's avatar
Brice Videau committed
282
283
284
285
286
287
288
289

/*
 * Get the dimension of an iterator. This is the number of elements of the array
 * of ssize_t that is expected by the peek, next, nth and n functionalities.
 * "it": an iterator.
 * "dimension": a pointer where the result will be written.
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
290
int excit_dimension(excit_t it, ssize_t *dimension);
Brice Videau's avatar
Brice Videau committed
291

Brice Videau's avatar
Brice Videau committed
292
293
294
295
296
297
298
299
/*
 * Gets the current element of an iterator and increments it.
 * "it": an iterator.
 * "indexes": an array of indexes with a dimension corresponding to that of the
 *            iterator, no results is returned if NULL.
 * Returns EXCIT_SUCCESS if a valid element was retured or EXCIT_STOPIT if the
 * iterator is depleted or an error code.
 */
Brice Videau's avatar
Brice Videau committed
300
int excit_next(excit_t it, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
301
302
303
304
305
306
307
308
309

/*
 * Gets the current element of an iterator.
 * "it": an iterator.
 * "indexes": an array of indexes with a dimension corresponding to that of the
 *            iterator, no results is returned if NULL.
 * Returns EXCIT_SUCCESS if a valid element was retured or EXCIT_STOPIT if the
 * iterator is depleted or an error code.
 */
Brice Videau's avatar
Brice Videau committed
310
int excit_peek(const excit_t it, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
311
312
313
314
315
316

/*
 * Rewinds an iterator to its initial state.
 * "it": an iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
317
int excit_rewind(excit_t it);
Brice Videau's avatar
Brice Videau committed
318
319
320
321
322
323
324

/*
 * Gets the number of elements of an iterator.
 * "it": an iterator.
 * "size": an pointer to the variable where the result will be stored.
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
325
int excit_size(const excit_t it, ssize_t *size);
Brice Videau's avatar
Brice Videau committed
326
327
328
329
330
331

/*
 * Splits an iterator envenly into several suub iterators.
 * "it": an iterator.
 * "n": number of iterators desired.
 * "results": an array of at least n excit_t, or NULL in which case no iterator
Brice Videau's avatar
Brice Videau committed
332
 *            is created.
Brice Videau's avatar
Brice Videau committed
333
334
335
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the source iterator is too small to be
 * subdivised in the wanted number or an error code.
 */
Brice Videau's avatar
Brice Videau committed
336
int excit_split(const excit_t it, ssize_t n, excit_t *results);
Brice Videau's avatar
Brice Videau committed
337

Brice Videau's avatar
Brice Videau committed
338
/*
339
340
 * Gets the nth element of an iterator. If an iterator has k dimensions, 
 * then the nth element is an array of k nth elements along each dimension.
Brice Videau's avatar
Brice Videau committed
341
 * "it": an iterator.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
342
343
 * "rank": rank of the element, comprised between 0 and the size of the
 *         iterator.
Brice Videau's avatar
Brice Videau committed
344
345
346
347
 * "indexes": an array of indexes with a dimension corresponding to that of the
 *            iterator, no results is returned if NULL.
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
348
int excit_nth(const excit_t it, ssize_t rank, ssize_t *indexes);
Brice Videau's avatar
Brice Videau committed
349
350

/*
351
352
353
354
 * 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 element.
 * If the iterator has k dimensions, element is an array of the k values 
 * composing element.
Brice Videau's avatar
Brice Videau committed
355
356
357
358
359
360
 * "it": an iterator.
 * "indexes": 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
 *         returned if NULL.
 * Returns EXCIT_SUCCESS or an error code.
 */
361
int excit_rank(const excit_t it, const ssize_t *element, ssize_t *rank);
Brice Videau's avatar
Brice Videau committed
362
363
364
365
366
367
368
369
370

/*
 * Gets the position of the iterator.
 * "it": an iterator.
 * "rank": a pointer to a variable where the rank of the current element will be
 *         stored, no result is returned if NULL.
 * Returns EXCIT_SUCCESS or EXCIT_STOPIT if the iterator is depleted or an error
 * code.
 */
Brice Videau's avatar
Brice Videau committed
371
int excit_pos(const excit_t it, ssize_t *rank);
Brice Videau's avatar
Brice Videau committed
372
373
374
375
376
377
378

/*
 * Increments the iterator.
 * "it": an iterator.
 * Returns EXCIT_SUCCESS or EXCIT_STOPIT if the iterator is depleted or an error
 * code.
 */
379
int excit_skip(excit_t it);
Brice Videau's avatar
Brice Videau committed
380
381
382
383
384
385
386
387
388

/*
 * Gets the current element of an iterator, rewinding it first if the iterator
 * was depleted. The iterator is incremented.
 * "it": an iterator.
 * "indexes": an array of indexes with a dimension corresponding to that of the
 *            iterator, no results is returned if NULL.
 * Returns EXCIT_SUCCESS or an error code.
 */
Brice Videau's avatar
Brice Videau committed
389
int excit_cyclic_next(excit_t it, ssize_t *indexes, int *looped);
Brice Videau's avatar
Brice Videau committed
390

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
391
392
393
394
395
/*
 * Initialize an index iterator with a set of indexes.
 */
int excit_index_init(excit_t it, const ssize_t  len, const ssize_t  *index);

Brice Videau's avatar
Brice Videau committed
396
/*
397
 * Initializes a range iterator to iterate from first to last (included) by step.
Brice Videau's avatar
Brice Videau committed
398
399
400
401
402
403
 * "it": a range iterator.
 * "first": first value of the range.
 * "last": last value of the range.
 * "step": between elements of the range. Must be non null, can be negative.
 * Returns EXCIT_SUCCESS or an error code.
 */
404
int excit_range_init(excit_t it, ssize_t first, ssize_t last, ssize_t step);
Brice Videau's avatar
Brice Videau committed
405

Brice Videau's avatar
Brice Videau committed
406
407
408
409
410
411
412
413
/*
 * Initializes a sliding window iterator over another iterator.
 * "it": a cons iterator.
 * "src": the original iterator. Ownership is transfered.
 * "n": size of the window, must not be superior to the size of the src
 *      iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
414
int excit_cons_init(excit_t it, excit_t src, ssize_t n);
Brice Videau's avatar
Brice Videau committed
415

Brice Videau's avatar
Brice Videau committed
416
417
418
419
420
421
422
/*
 * Initializes a repeat iterator over another iterator.
 * "it": a repeat iterator.
 * "src": the original iterator. Ownership is transfered.
 * "n": number of repeat of each element of the src iterator.
 * Returns EXCIT_SUCCESS or an error code.
 */
423
int excit_repeat_init(excit_t it, excit_t src, ssize_t n);
Brice Videau's avatar
Brice Videau committed
424

Brice Videau's avatar
Brice Videau committed
425
426
427
428
429
430
431
432
433
434
435
/*
 * Splits a repeat iterator between repetitions.
 * "it": a product iterator.
 * "n": number of iterators desired.
 * "results": an array of at least n excit_t, or NULL in which case no iterator
 *            is created.
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the selected iterator is too small to
 * be subdivised in the wanted number or an error code.
 */
int excit_repeat_split(const excit_t it, ssize_t n, excit_t *results);

Brice Videau's avatar
Brice Videau committed
436
437
438
439
440
441
/*
 * Creates a two dimensional Hilbert space-filling curve iterator.
 * "it": an hilbert2d iterator.
 * "order": the iteration space is (2^order - 1)^2.
 * Returns EXCIT_SUCCESS or an error code.
 */
442
int excit_hilbert2d_init(excit_t it, ssize_t order);
Brice Videau's avatar
Brice Videau committed
443

Brice Videau's avatar
Brice Videau committed
444
445
446
447
448
449
/*
 * Adds another iterator to a product iterator.
 * "it": a repeat iterator.
 * "added_it": the added iterator. Ownership is transfered.
 * Returns EXCIT_SUCCESS or an error code.
 */
450
int excit_product_add(excit_t it, excit_t added_it);
Brice Videau's avatar
Brice Videau committed
451
452
453
454
455
456
457
458

/*
 * Adds another iterator to a product iterator without transfering ownership.
 * "it": a product iterator.
 * "added_it": the added iterator. Ownership is not transfered, a duplicate is
 *             created instead.
 * Returns EXCIT_SUCCESS or an error code.
 */
459
int excit_product_add_copy(excit_t it, excit_t added_it);
Brice Videau's avatar
Brice Videau committed
460
461
462
463
464
465
466

/*
 * Gets the number of iterator inside a product iterator.
 * "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
467
int excit_product_count(const excit_t it, ssize_t *count);
Brice Videau's avatar
Brice Videau committed
468
469
470
471
472
473
474
475
476
477
478
479

/*
 * 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.
 * "n": number of iterators desired.
 * "results": an array of at least n excit_t, or NULL in which case no iterator
 *            is created.
 * Returns EXCIT_SUCCESS, -EXCIT_EDOM if the selected iterator is too small to
 * be subdivised in the wanted number or an error code.
 */
480
int excit_product_split_dim(const excit_t it, ssize_t dim, ssize_t n,
Brice Videau's avatar
Brice Videau committed
481
			    excit_t *results);
Brice Videau's avatar
Brice Videau committed
482

Brice Videau's avatar
Brice Videau committed
483
/*
484
485
 * Initializes a composition iterator by giving a src iterator and an indexer iterator.
 * "it": a composition iterator.
Brice Videau's avatar
Brice Videau committed
486
487
488
489
 * "src": the iterator whom elements are to be returned.
 * "indexer": the iterator that will provide the rank of the elements to return.
 * Returns EXCIT_SUCCESS or an error code.
 */
490
int excit_composition_init(excit_t it, excit_t src, excit_t indexer);
491
492

enum tleaf_it_policy_e {
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
493
494
495
  TLEAF_POLICY_ROUND_ROBIN, /* Iterate on tree leaves in a round-robin fashion */
  TLEAF_POLICY_SCATTER, /* Iterate on tree leaves such spreading as much as possible */
  TLEAF_POLICY_USER /* Policy is a user defined policy */
496
497
498
499
};

/*
 * Initialize a tleaf iterator by giving its depth, levels arity and iteration policy.
500
501
502
503
 * example building a user scatter policy: 
 *         excit_tleaf_init(it, 4, {3, 2, 4}, TLEAF_POLICY_USER, {2, 1, 0});
 * gives the output index: 
 *         0,6,12,18,3,9,15,21,1,7,13,19,4,10,16,22,2,8,14,20,5,11,17,23.
504
505
 * "it": a tleaf iterator
 * "depth": the total number of levels of the tree, including leaves
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
506
507
508
509
510
 * "arity": An array  of size (depth-1). For each level, the number of children attached to a node. 
 *          Leaves have no children. Arities are organized from root to leaves.
 * "index": NULL or an array of depth excit_t to re-index levels. 
 *          It is intended to prune node of certain levels while keeping index of the initial structure.
 *          Ownership of index is not taken. The iterator allocates a copy of index and manage it internally.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
511
 * "policy": A policy for iteration on leaves.
512
513
514
515
516
517
 * "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
518
519
520
521
522
 *                obtained from walking from root to leaves.
 */
int excit_tleaf_init(excit_t it,
		     const ssize_t depth,
		     const ssize_t *arities,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
523
		     const excit_t *index,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
524
525
		     const enum tleaf_it_policy_e policy,
		     const ssize_t *user_policy);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
526
527

/*
528
529
 * Split 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 occures and the number of parts.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
530
531
 * "it": a tleaf iterator.
 * "level": The level to split.
532
 * "n": The number of parts. n must divide the target level arity.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
533
 * "out": an array of n allocated tleaf iterators.
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
534
535
 */
int tleaf_it_split(const excit_t it, const ssize_t level, const ssize_t n, excit_t *out);
536

Brice Videau's avatar
Brice Videau committed
537
#endif