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;

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;
	}

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

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,
194
			 ssize_t *order, excit_t *levels)
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
195
{
196 197 198
	ssize_t i;
	int err;
	excit_t index, range, comp;
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
199

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

204 205
	for (i = 0; i < tleaf->depth; i++) {
		ssize_t l = order[i];
206

207
		index = indexes == NULL ? NULL : indexes[l];
Nicolas Denoyelle's avatar
Nicolas Denoyelle committed
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 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;
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;
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 */
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

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
{
369 370
	return tleaf_init_with_it(it, depth, arities, indexes, policy,
				  user_policy, NULL, NULL);
Nicolas Denoyelle's avatar
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,
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
};