← Back to branch summary

~ubuntu-branches/ubuntu/trusty/cloog/trusty

« back to all changes in this revision

Viewing changes to isl/isl_list_templ.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-10-17 15:54:24 UTC
  • mfrom: (3.1.5 sid)
  • Revision ID: package-import@ubuntu.com-20131017155424-3q1gw7yhddylfkpj
Tags: 0.18.1-1
http://bugs.debian.org/711681
http://bugs.debian.org/719957
* New upstream version.
* Add a comment to build-depend on libpod-latex-perl | perl (<< 5.17.0),
  when the documentation is built. Closes: #711681.
* Use dh_autotools-dev to update config.{sub,guess}. Closes: #719957.

Show diffs side-by-side

added added

removed removed

Lines of Context:
isl/isl_list_templ.c
1
1
/*
2
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
3
 * Copyright 2011      INRIA Saclay
4
 
 * Copyright 2012      Ecole Normale Superieure
 
4
 * Copyright 2012-2013 Ecole Normale Superieure
5
5
 *
6
6
 * Use of this software is governed by the MIT license
7
7
 *
12
12
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13
13
 */
14
14
 
 
15
#include <isl_sort.h>
 
16
#include <isl_tarjan.h>
 
17
 
15
18
#define xCAT(A,B) A ## B
16
19
#define CAT(A,B) xCAT(A,B)
17
20
#undef EL
20
23
#define FN(TYPE,NAME) xFN(TYPE,NAME)
21
24
#define xLIST(EL) EL ## _list
22
25
#define LIST(EL) xLIST(EL)
 
26
#define xS(TYPE,NAME) struct TYPE ## _ ## NAME
 
27
#define S(TYPE,NAME) xS(TYPE,NAME)
23
28
 
24
29
isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
25
30
{
283
288
        return 0;
284
289
}
285
290
 
 
291
/* Internal data structure for isl_*_list_sort.
 
292
 *
 
293
 * "cmp" is the original comparison function.
 
294
 * "user" is a user provided pointer that should be passed to "cmp".
 
295
 */
 
296
S(LIST(EL),sort_data) {
 
297
        int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 
298
        void *user;
 
299
};
 
300
 
 
301
/* Compare two entries of an isl_*_list based on the user provided
 
302
 * comparison function on pairs of isl_* objects.
 
303
 */
 
304
static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
 
305
{
 
306
        S(LIST(EL),sort_data) *data = user;
 
307
        EL * const *el1 = a;
 
308
        EL * const *el2 = b;
 
309
 
 
310
        return data->cmp(*el1, *el2, data->user);
 
311
}
 
312
 
 
313
/* Sort the elements of "list" in ascending order according to
 
314
 * comparison function "cmp".
 
315
 */
 
316
__isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
 
317
        int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
 
318
{
 
319
        S(LIST(EL),sort_data) data = { cmp, user };
 
320
 
 
321
        if (!list)
 
322
                return NULL;
 
323
        if (list->n <= 1)
 
324
                return list;
 
325
        list = FN(LIST(EL),cow)(list);
 
326
        if (!list)
 
327
                return NULL;
 
328
 
 
329
        if (isl_sort(list->p, list->n, sizeof(list->p[0]),
 
330
                        &FN(LIST(EL),cmp), &data) < 0)
 
331
                return FN(LIST(EL),free)(list);
 
332
 
 
333
        return list;
 
334
}
 
335
 
 
336
/* Internal data structure for isl_*_list_foreach_scc.
 
337
 *
 
338
 * "list" is the original list.
 
339
 * "follows" is the user provided callback that defines the edges of the graph.
 
340
 */
 
341
S(LIST(EL),foreach_scc_data) {
 
342
        LIST(EL) *list;
 
343
        int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 
344
        void *follows_user;
 
345
};
 
346
 
 
347
/* Does element i of data->list follow element j?
 
348
 *
 
349
 * Use the user provided callback to find out.
 
350
 */
 
351
static int FN(LIST(EL),follows)(int i, int j, void *user)
 
352
{
 
353
        S(LIST(EL),foreach_scc_data) *data = user;
 
354
 
 
355
        return data->follows(data->list->p[i], data->list->p[j],
 
356
                                data->follows_user);
 
357
}
 
358
 
 
359
/* Call "fn" on the sublist of "list" that consists of the elements
 
360
 * with indices specified by the "n" elements of "pos".
 
361
 */
 
362
static int FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n,
 
363
        int (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
 
364
{
 
365
        int i;
 
366
        isl_ctx *ctx;
 
367
        LIST(EL) *slice;
 
368
 
 
369
        ctx = FN(LIST(EL),get_ctx)(list);
 
370
        slice = FN(LIST(EL),alloc)(ctx, n);
 
371
        for (i = 0; i < n; ++i) {
 
372
                EL *el;
 
373
 
 
374
                el = FN(EL,copy)(list->p[pos[i]]);
 
375
                slice = FN(LIST(EL),add)(slice, el);
 
376
        }
 
377
 
 
378
        return fn(slice, user);
 
379
}
 
380
 
 
381
/* Call "fn" on each of the strongly connected components (SCCs) of
 
382
 * the graph with as vertices the elements of "list" and
 
383
 * a directed edge from node b to node a iff follows(a, b)
 
384
 * returns 1.  follows should return -1 on error.
 
385
 *
 
386
 * If SCC a contains a node i that follows a node j in another SCC b
 
387
 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
 
388
 * after being called on SCC b.
 
389
 *
 
390
 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
 
391
 * call fn on each of them.
 
392
 */
 
393
int FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
 
394
        int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
 
395
        void *follows_user,
 
396
        int (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
 
397
{
 
398
        S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
 
399
        int i, n;
 
400
        isl_ctx *ctx;
 
401
        struct isl_tarjan_graph *g;
 
402
 
 
403
        if (!list)
 
404
                return -1;
 
405
        if (list->n == 0)
 
406
                return 0;
 
407
        if (list->n == 1)
 
408
                return fn(FN(LIST(EL),copy)(list), fn_user);
 
409
 
 
410
        ctx = FN(LIST(EL),get_ctx)(list);
 
411
        n = list->n;
 
412
        g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
 
413
        if (!g)
 
414
                return -1;
 
415
 
 
416
        i = 0;
 
417
        do {
 
418
                int first;
 
419
 
 
420
                if (g->order[i] == -1)
 
421
                        isl_die(ctx, isl_error_internal, "cannot happen",
 
422
                                break);
 
423
                first = i;
 
424
                while (g->order[i] != -1) {
 
425
                        ++i; --n;
 
426
                }
 
427
                if (first == 0 && n == 0) {
 
428
                        isl_tarjan_graph_free(g);
 
429
                        return fn(FN(LIST(EL),copy)(list), fn_user);
 
430
                }
 
431
                if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
 
432
                                            fn, fn_user) < 0)
 
433
                        break;
 
434
                ++i;
 
435
        } while (n);
 
436
 
 
437
        isl_tarjan_graph_free(g);
 
438
 
 
439
        return n > 0 ? -1 : 0;
 
440
}
 
441
 
286
442
__isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
287
443
{
288
444
        isl_ctx *ctx;