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
static int tleaf_it_alloc(excit_t it)
{
	it->dimension = 1;
	struct tleaf_it_s *data_it = it->data;
18

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

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

Brice Videau's avatar
Brice Videau committed
33
34
	free(data_it->arities);
	free(data_it->buf);
35
	free(data_it->order);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
36
	excit_free(data_it->levels);
37
38
39
40
41
42
43
	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;
44
	int err = excit_size(data_it->levels, size);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
45

46
47
	if (err != EXCIT_SUCCESS)
		return err;
48
49
50
51
52
53
	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
54

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
	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
75
76
	excit_t levels = excit_dup(src->levels);

77
78
79
80
81
82
83
84
85
86
87
88
	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
89
	err = tleaf_init_with_it(dst_it, src->depth + 1, src->arities, NULL,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
90
91
				 TLEAF_POLICY_USER, src->order, levels,
				 levels_inverse);
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
	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
108

109
110
111
112
113
114
	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
115

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

124
static int tleaf_it_nth(const excit_t it, ssize_t n, ssize_t *indexes)
125
126
127
128
129
130
{
	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;
131
132
	if (indexes != NULL)
		*indexes = tleaf_it_value(data_it);
133
134
135
	return EXCIT_SUCCESS;
}

136
static int tleaf_it_peek(const excit_t it, ssize_t *value)
137
138
139
140
141
142
{
	struct tleaf_it_s *data_it = it->data;
	int err = excit_peek(data_it->levels, data_it->buf);

	if (err != EXCIT_SUCCESS)
		return err;
143
144
	if (value != NULL)
		*value = tleaf_it_value(data_it);
145
146
147
	return EXCIT_SUCCESS;
}

148
static int tleaf_it_next(excit_t it, ssize_t *indexes)
149
150
151
152
153
154
{
	struct tleaf_it_s *data_it = it->data;
	int err = excit_next(data_it->levels, data_it->buf);

	if (err != EXCIT_SUCCESS)
		return err;
155
156
157

	if (indexes != NULL)
		*indexes = tleaf_it_value(data_it);
158
159
160
	return EXCIT_SUCCESS;
}

161
static int tleaf_it_rank(const excit_t it, const ssize_t *indexes, ssize_t *n)
162
{
163
164
165
166
167
168
	ssize_t size;
	int err;

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

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

	struct tleaf_it_s *data_it = it->data;
174

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

179
	ssize_t i, acc = 1, val = 0;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
180

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

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

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

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

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

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

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
207
208
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
		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;
		}
	}
240

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

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;
252
	return err;
253
254
}

255
256
257
static int tleaf_init_with_it(excit_t it,
			      const ssize_t depth,
			      const ssize_t *arities,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
258
			      const excit_t *indexes,
259
260
			      const enum tleaf_it_policy_e policy,
			      const ssize_t *user_policy,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
261
			      excit_t levels, excit_t levels_inverse)
262
{
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
263
264
	if (it == NULL || it->data == NULL)
		return -EXCIT_EINVAL;
Brice Videau's avatar
Brice Videau committed
265
	int err = EXCIT_SUCCESS;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
266
267
268
269
270
271
272
273
274
275
276
277
278
279
	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++)
280
			data_it->order[i] = i;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
281
282
283
		break;
	case TLEAF_POLICY_SCATTER:
		for (i = 0; i < data_it->depth; i++)
284
			data_it->order[i] = data_it->depth - i - 1;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
285
286
287
288
289
290
291
		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;
292
		goto error_with_order;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
293
294
295
296
	}

	/* Set order inverse */
	data_it->order_inverse =
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
297
	    malloc(sizeof(*data_it->order_inverse) * data_it->depth);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
298
299
300
301
302
303
304
	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;

305
	/* Set levels arity. */
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
	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
322
323
324
325
326
327
328
329
	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
330

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
331
332
333
334
335
336
337
	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
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357

	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;
358
359
360
}

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

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

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

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

388
int tleaf_it_split(const excit_t it, const ssize_t depth,
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
389
		   const ssize_t n, excit_t *out)
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
390
391
392
393
394
395
396
397
398
{
	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
399

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

405
406
	int err;
	excit_t *levels, *levels_inverse;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
407

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

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

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

	free(levels);
439
	free(levels_inverse);
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
440
441
	return EXCIT_SUCCESS;

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

Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
453
454
455
456
457
458
459
460
461
462
463
464
465
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
};