tleaf.c 10.3 KB
Newer Older
1
2
#include <stdlib.h>
#include <stdio.h>
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
3
#include "dev/excit.h"
4
5
#include "tleaf.h"

6
7
8
static int tleaf_init_with_it(excit_t it,
			      const ssize_t depth,
			      const ssize_t *arities,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
9
			      const excit_t *indexes,
10
11
			      const enum tleaf_it_policy_e policy,
			      const ssize_t *user_policy,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
12
			      excit_t levels, excit_t levels_inverse);
13

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
14
15
16
17
18
19
static int tleaf_it_alloc(excit_t it)
{
	if (it == NULL || it->data == NULL)
		return -EXCIT_EINVAL;
	it->dimension = 1;
	struct tleaf_it_s *data_it = it->data;
20

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
21
22
23
	data_it->depth = 0;
	data_it->arities = NULL;
	data_it->buf = NULL;
24
	data_it->order = NULL;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
25
	data_it->levels = NULL;
26
27
	data_it->order_inverse = NULL;
	data_it->levels_inverse = NULL;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
28
29
	return EXCIT_SUCCESS;
}
30

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
31
static void tleaf_it_free(excit_t it)
32
{
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
33
34
	struct tleaf_it_s *data_it = it->data;

Brice Videau's avatar
Brice Videau committed
35
36
	free(data_it->arities);
	free(data_it->buf);
37
	free(data_it->order);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
38
	excit_free(data_it->levels);
39
40
41
42
43
44
45
	free(data_it->order_inverse);
	excit_free(data_it->levels_inverse);
}

static int tleaf_it_size(const excit_t it, ssize_t *size)
{
	struct tleaf_it_s *data_it = it->data;
46
	int err = excit_size(data_it->levels, size);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
47

48
49
	if (err != EXCIT_SUCCESS)
		return err;
50
51
52
53
54
55
	return EXCIT_SUCCESS;
}

static int tleaf_it_rewind(excit_t it)
{
	struct tleaf_it_s *data_it = it->data;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
56

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
	return excit_rewind(data_it->levels);
}

static int tleaf_it_copy(excit_t dst_it, const excit_t src_it)
{
	int err = EXCIT_SUCCESS;
	struct tleaf_it_s *dst = dst_it->data;
	struct tleaf_it_s *src = src_it->data;

	/* dst is initialised, then wipe it */
	if (dst->buf != NULL) {
		free(dst->buf);
		free(dst->arities);
		free(dst->order);
		free(dst->order_inverse);
		excit_free(dst->levels);
		excit_free(dst->levels_inverse);
	}

	/* dst is not initialized (anymore) */
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
77
78
	excit_t levels = excit_dup(src->levels);

79
80
81
82
83
84
85
86
87
88
89
90
	if (levels == NULL) {
		err = -EXCIT_ENOMEM;
		goto error;
	}

	excit_t levels_inverse = excit_dup(src->levels_inverse);

	if (levels_inverse == NULL) {
		err = -EXCIT_ENOMEM;
		goto error_with_levels;
	}

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
91
	err = tleaf_init_with_it(dst_it, src->depth + 1, src->arities, NULL,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
92
93
				 TLEAF_POLICY_USER, src->order, levels,
				 levels_inverse);
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
	if (err != EXCIT_SUCCESS)
		goto error_with_levels_inverse;

	return EXCIT_SUCCESS;

error_with_levels_inverse:
	excit_free(levels_inverse);
error_with_levels:
	excit_free(levels);
error:
	return err;
}

static int tleaf_it_pos(const excit_t it, ssize_t *value)
{
	struct tleaf_it_s *data_it = it->data;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
110

111
112
113
114
115
116
	return excit_pos(data_it->levels, value);
}

static ssize_t tleaf_it_value(struct tleaf_it_s *it)
{
	ssize_t i, acc = 1, val = 0;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
117

118
	for (i = 0; i < it->depth; i++) {
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
119
120
		/* levels are stacked following order, then decode result backward order_inverse */
		val += acc * it->buf[it->order_inverse[it->depth - i - 1]];
121
		acc *= it->arities[it->depth - i - 1];
122
123
124
125
126
127
128
129
130
131
132
	}
	return val;
}

int tleaf_it_nth(const excit_t it, ssize_t n, ssize_t *indexes)
{
	struct tleaf_it_s *data_it = it->data;
	int err = excit_nth(data_it->levels, n, data_it->buf);

	if (err != EXCIT_SUCCESS)
		return err;
133
134
	if (indexes != NULL)
		*indexes = tleaf_it_value(data_it);
135
136
137
138
139
140
141
142
143
144
	return EXCIT_SUCCESS;
}

int tleaf_it_peek(const excit_t it, ssize_t *value)
{
	struct tleaf_it_s *data_it = it->data;
	int err = excit_peek(data_it->levels, data_it->buf);

	if (err != EXCIT_SUCCESS)
		return err;
145
146
	if (value != NULL)
		*value = tleaf_it_value(data_it);
147
148
149
150
151
152
153
154
155
156
	return EXCIT_SUCCESS;
}

int tleaf_it_next(excit_t it, ssize_t *indexes)
{
	struct tleaf_it_s *data_it = it->data;
	int err = excit_next(data_it->levels, data_it->buf);

	if (err != EXCIT_SUCCESS)
		return err;
157
158
159

	if (indexes != NULL)
		*indexes = tleaf_it_value(data_it);
160
161
162
163
164
	return EXCIT_SUCCESS;
}

int tleaf_it_rank(const excit_t it, const ssize_t *indexes, ssize_t *n)
{
165
166
167
168
169
170
	ssize_t size;
	int err;

	err = tleaf_it_size(it, &size);
	if (err != EXCIT_SUCCESS)
		return err;
171

172
173
174
175
	if (indexes == NULL || *indexes < 0 || *indexes >= size)
		return -EXCIT_EINVAL;

	struct tleaf_it_s *data_it = it->data;
176

177
	err = excit_nth(data_it->levels_inverse, *indexes, data_it->buf);
178
179
	if (err != EXCIT_SUCCESS)
		return err;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
180

181
	ssize_t i, acc = 1, val = 0;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
182

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
183
	for (i = data_it->depth - 1; i >= 0; i--) {
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
184
		val += acc * data_it->buf[data_it->order[i]];
185
		acc *= data_it->arities[i];
186
187
	}

188
189
	if (n != NULL)
		*n = val;
190
191
192
	return EXCIT_SUCCESS;
}

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
193
int tleaf_it_make_levels(struct tleaf_it_s *tleaf, const excit_t *indexes,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
194
			 ssize_t *order, excit_t *levels)
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
195
{
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
196
197
198
	ssize_t i;
	int err;
	excit_t index, range, comp;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
199

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
200
201
	*levels = excit_alloc(EXCIT_PRODUCT);
	if (*levels == NULL)
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
202
203
		return -EXCIT_ENOMEM;

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
204
205
	for (i = 0; i < tleaf->depth; i++) {
		ssize_t l = order[i];
206

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
207
		index = indexes == NULL ? NULL : indexes[l];
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
208

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
		range = excit_alloc(EXCIT_RANGE);

		if (range == NULL) {
			err = -EXCIT_ENOMEM;
			goto error_with_levels;
		}
		err = excit_range_init(range, 0, tleaf->arities[l] - 1, 1);
		if (err != EXCIT_SUCCESS)
			goto error_with_range;

		if (index != NULL) {
			comp = excit_alloc(EXCIT_COMPOSITION);
			if (comp == NULL) {
				err = -EXCIT_ENOMEM;
				goto error_with_range;
			}
			index = excit_dup(index);
			if (index == NULL) {
				err = -EXCIT_ENOMEM;
				goto error_with_comp;
			}
			err = excit_composition_init(comp, range, index);
			if (err != EXCIT_SUCCESS)
				goto error_with_index;
			err = excit_product_add(*levels, comp);
			if (err != EXCIT_SUCCESS)
				goto error_with_index;
		} else {
			err = excit_product_add(*levels, range);
			if (err != EXCIT_SUCCESS)
				goto error_with_range;
		}
	}
242

243
	return EXCIT_SUCCESS;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
244
245
246
247
248
249
250
251
252
253

error_with_index:
	excit_free(index);
error_with_comp:
	excit_free(comp);
error_with_range:
	excit_free(range);
error_with_levels:
	excit_free(*levels);
	*levels = NULL;
254
	return err;
255
256
}

257
258
259
static int tleaf_init_with_it(excit_t it,
			      const ssize_t depth,
			      const ssize_t *arities,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
260
			      const excit_t *indexes,
261
262
			      const enum tleaf_it_policy_e policy,
			      const ssize_t *user_policy,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
263
			      excit_t levels, excit_t levels_inverse)
264
{
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
265
266
	if (it == NULL || it->data == NULL)
		return -EXCIT_EINVAL;
Brice Videau's avatar
Brice Videau committed
267
	int err = EXCIT_SUCCESS;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
268
269
270
271
272
273
274
275
276
277
278
279
280
281
	struct tleaf_it_s *data_it = it->data;
	ssize_t i;

	data_it->depth = depth - 1;

	/* Set order according to policy */
	data_it->order = malloc(sizeof(*data_it->order) * data_it->depth);
	if (data_it->order == NULL) {
		err = -EXCIT_ENOMEM;
		goto error;
	}
	switch (policy) {
	case TLEAF_POLICY_ROUND_ROBIN:
		for (i = 0; i < data_it->depth; i++)
282
			data_it->order[i] = i;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
283
284
285
		break;
	case TLEAF_POLICY_SCATTER:
		for (i = 0; i < data_it->depth; i++)
286
			data_it->order[i] = data_it->depth - i - 1;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
287
288
289
290
291
292
293
		break;
	case TLEAF_POLICY_USER:
		for (i = 0; i < data_it->depth; i++)
			data_it->order[i] = user_policy[i];
		break;
	default:
		err = -EXCIT_EINVAL;
294
		goto error_with_order;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
295
296
297
298
	}

	/* Set order inverse */
	data_it->order_inverse =
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
299
	    malloc(sizeof(*data_it->order_inverse) * data_it->depth);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
300
301
302
303
304
305
306
	if (data_it->order_inverse == NULL) {
		err = -EXCIT_ENOMEM;
		goto error_with_order;
	}
	for (i = 0; i < data_it->depth; i++)
		data_it->order_inverse[data_it->order[i]] = i;

307
	/* Set levels arity. */
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
	data_it->arities = malloc(sizeof(*data_it->arities) * data_it->depth);
	if (data_it->arities == NULL) {
		err = -EXCIT_ENOMEM;
		goto error_with_order_inverse;
	}
	for (i = 0; i < data_it->depth; i++)
		data_it->arities[i] = arities[i];

	/* Set storage buffer for output of product iterator */
	data_it->buf = malloc(sizeof(*data_it->buf) * data_it->depth);
	if (data_it->buf == NULL) {
		err = -EXCIT_ENOMEM;
		goto error_with_arity;
	}

	/* Set product iterator if not provided */
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
324
325
326
327
328
329
330
331
	data_it->levels = levels;
	data_it->levels_inverse = levels_inverse;
	if (levels == NULL)
		err =
		    tleaf_it_make_levels(data_it, indexes, data_it->order,
					 &(data_it->levels));
	if (err != EXCIT_SUCCESS)
		goto error_with_buf;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
332

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
333
334
335
336
337
338
339
	if (levels_inverse == NULL)
		err =
		    tleaf_it_make_levels(data_it, indexes,
					 data_it->order_inverse,
					 &(data_it->levels_inverse));
	if (err != EXCIT_SUCCESS)
		goto error_with_levels;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359

	return EXCIT_SUCCESS;

error_with_levels:
	excit_free(data_it->levels);
	data_it->levels = NULL;
error_with_buf:
	free(data_it->buf);
	data_it->buf = NULL;
error_with_arity:
	free(data_it->arities);
	data_it->arities = NULL;
error_with_order_inverse:
	free(data_it->order_inverse);
	data_it->order_inverse = NULL;
error_with_order:
	free(data_it->order);
	data_it->order = NULL;
error:
	return err;
360
361
362
}

int excit_tleaf_init(excit_t it,
363
		     const ssize_t depth,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
364
		     const ssize_t *arities,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
365
		     const excit_t *indexes,
366
		     const enum tleaf_it_policy_e policy,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
367
		     const ssize_t *user_policy)
368
{
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
369
370
	return tleaf_init_with_it(it, depth, arities, indexes, policy,
				  user_policy, NULL, NULL);
Nicolas Denoyelle's avatar
wip    
Nicolas Denoyelle committed
371
}
372

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
373
374
375
376
int tleaf_split_levels(excit_t levels, const ssize_t depth, const ssize_t n,
		       excit_t **out)
{
	*out = malloc(sizeof(**out) * n);
377
378
	if (*out == NULL)
		return -EXCIT_ENOMEM;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
379

380
	int err = excit_product_split_dim(levels, depth, n, *out);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
381
382

	if (err != EXCIT_SUCCESS) {
383
384
		free(*out);
		*out = NULL;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
385
		return err;
386
	}
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
387
	return EXCIT_SUCCESS;
388
}
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
389

390
int tleaf_it_split(const excit_t it, const ssize_t depth,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
391
		   const ssize_t n, excit_t *out)
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
392
393
394
395
396
397
398
399
400
{
	ssize_t i;

	if (out == NULL)
		return EXCIT_SUCCESS;
	if (it == NULL || it->data == NULL)
		return -EXCIT_EINVAL;

	struct tleaf_it_s *data_it = it->data;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
401

402
	if (data_it->arities[depth] % n != 0)
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
403
		return -EXCIT_EINVAL;
404
405
	if (out == NULL)
		return EXCIT_SUCCESS;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
406

407
408
	int err;
	excit_t *levels, *levels_inverse;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
409

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
410
411
412
413
	err =
	    tleaf_split_levels(data_it->levels, data_it->order[depth], n,
			       &levels);
	if (err != EXCIT_SUCCESS)
414
		return err;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
415
416
417
418
	err =
	    tleaf_split_levels(data_it->levels_inverse,
			       data_it->order_inverse[depth], n,
			       &levels_inverse);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
419
420
421
422
	if (err != EXCIT_SUCCESS)
		goto error_with_levels;

	for (i = 0; i < n; i++) {
423
424
425
426
427
428
		out[i] = excit_alloc(EXCIT_TLEAF);
		if (out == NULL) {
			err = -EXCIT_ENOMEM;
			goto error_with_levels_inverse;
		}

429
430
431
		err = tleaf_init_with_it(out[i],
					 data_it->depth + 1,
					 data_it->arities,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
432
					 NULL,
433
					 TLEAF_POLICY_USER,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
434
435
					 data_it->order, levels[i],
					 levels_inverse[i]);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
436
		if (err != EXCIT_SUCCESS)
437
			goto error_with_levels_inverse;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
438
439
440
	}

	free(levels);
441
	free(levels_inverse);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
442
443
	return EXCIT_SUCCESS;

444
error_with_levels_inverse:
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
445
	for (i = 0; i < n; i++)
446
447
		excit_free(levels_inverse[i]);
	free(levels_inverse);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
448
error_with_levels:
449
450
	for (i = 0; i < n; i++)
		excit_free(levels[i]);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
451
452
	free(levels);
	return err;
453
454
}

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
455
456
457
458
459
460
461
462
463
464
465
466
467
struct excit_func_table_s excit_tleaf_func_table = {
	tleaf_it_alloc,
	tleaf_it_free,
	tleaf_it_copy,
	tleaf_it_next,
	tleaf_it_peek,
	tleaf_it_size,
	tleaf_it_rewind,
	NULL,
	tleaf_it_nth,
	tleaf_it_rank,
	tleaf_it_pos
};