2
/*+-----------------------------------------------------------------**
4
**-----------------------------------------------------------------**
6
**-----------------------------------------------------------------**
7
** First version: 08/10/2010 **
8
**-----------------------------------------------------------------**
11
*****************************************************************************
12
* OpenScop: Structures and formats for polyhedral tools to talk together *
13
*****************************************************************************
14
* ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, *
15
* / / / // // // // / / / // // / / // / /|,_, *
16
* / / / // // // // / / / // // / / // / / / /\ *
17
* |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ *
18
* | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ *
19
* | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ *
20
* | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ *
21
* | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ *
22
* | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ *
23
* | I | | | | e | | | | | | | | | | | | | \ \ \ *
24
* | T | | | | | | | | | | | | | | | | | \ \ \ *
25
* | E | | | | | | | | | | | | | | | | | \ \ \ *
26
* | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ *
27
* | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / *
28
* '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' *
30
* Copyright (C) 2008 University Paris-Sud 11 and INRIA *
32
* (3-clause BSD license) *
33
* Redistribution and use in source and binary forms, with or without *
34
* modification, are permitted provided that the following conditions *
37
* 1. Redistributions of source code must retain the above copyright notice, *
38
* this list of conditions and the following disclaimer. *
39
* 2. Redistributions in binary form must reproduce the above copyright *
40
* notice, this list of conditions and the following disclaimer in the *
41
* documentation and/or other materials provided with the distribution. *
42
* 3. The name of the author may not be used to endorse or promote products *
43
* derived from this software without specific prior written permission. *
45
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR *
46
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES *
47
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. *
48
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, *
49
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT *
50
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
51
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
52
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
53
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF *
54
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
56
* OpenScop Library, a library to manipulate OpenScop formats and data *
57
* structures. Written by: *
58
* Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and *
59
* Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> *
61
*****************************************************************************/
69
#include <osl/macros.h>
71
#include <osl/relation.h>
72
#include <osl/relation_list.h>
75
/*+***************************************************************************
76
* Structure display function *
77
*****************************************************************************/
81
* osl_relation_list_idump function:
82
* Displays a osl_relation_list_t structure (a list of relations) into a
83
* file (file, possibly stdout). See osl_relation_print_structure for
85
* \param file File where informations are printed.
86
* \param l The list of relations whose information has to be printed.
87
* \param level Number of spaces before printing, for each line.
89
void osl_relation_list_idump(FILE * file, osl_relation_list_p l, int level) {
92
// Go to the right level.
93
for (j = 0; j < level; j++)
97
fprintf(file, "+-- osl_relation_list_t\n");
99
fprintf(file, "+-- NULL relation list\n");
103
// Go to the right level.
104
for (j = 0; j < level; j++)
105
fprintf(file, "|\t");
106
fprintf(file, "| osl_relation_list_t\n");
112
for (j = 0; j <= level+1; j++)
113
fprintf(file, "|\t");
117
osl_relation_idump(file, l->elt, level+1);
123
for (j = 0; j <= level; j++)
124
fprintf(file, "|\t");
125
fprintf(file, "V\n");
130
for (j = 0; j <= level; j++)
131
fprintf(file, "|\t");
137
* osl_relation_dump function:
138
* This function prints the content of a osl_relation_list_t into
139
* a file (file, possibly stdout).
140
* \param file File where informations are printed.
141
* \param list The relation whose information has to be printed.
143
void osl_relation_list_dump(FILE * file, osl_relation_list_p list) {
144
osl_relation_list_idump(file, list, 0);
149
* osl_relation_list_pprint_elts function:
150
* This function pretty-prints the elements of a osl_relation_list_t structure
151
* into a file (file, possibly stdout) in the OpenScop format. I.e., it prints
152
* only the elements and not the number of elements. It prints an element of the
153
* list only if it is not NULL.
154
* \param file File where informations are printed.
155
* \param list The relation list whose information has to be printed.
156
* \param[in] names Array of constraint columns names.
158
void osl_relation_list_pprint_elts(FILE * file, osl_relation_list_p list,
161
osl_relation_list_p head = list;
163
// Count the number of elements in the list with non-NULL content.
164
i = osl_relation_list_count(list);
166
// Print each element of the relation list.
170
if (head->elt != NULL) {
171
osl_relation_pprint(file, head->elt, names);
172
if (head->next != NULL)
180
fprintf(file, "# NULL relation list\n");
186
* osl_relation_list_pprint function:
187
* This function pretty-prints the content of a osl_relation_list_t structure
188
* into a file (file, possibly stdout) in the OpenScop format. It prints
189
* an element of the list only if it is not NULL.
190
* \param[in] file File where informations are printed.
191
* \param[in] list The relation list whose information has to be printed.
192
* \param[in] names Array of constraint columns names.
194
void osl_relation_list_pprint(FILE * file, osl_relation_list_p list,
198
// Count the number of elements in the list with non-NULL content.
199
i = osl_relation_list_count(list);
203
fprintf(file,"# List of %d elements\n%d\n", i, i);
205
fprintf(file,"# List of %d element \n%d\n", i, i);
207
// Print each element of the relation list.
208
osl_relation_list_pprint_elts(file, list, names);
213
* osl_relation_list_print function:
214
* This function prints the content of a osl_relation_list_t structure
215
* into a file (file, possibly stdout) in the OpenScop format. It prints
216
* an element of the list only if it is not NULL.
217
* \param file File where informations are printed.
218
* \param list The relation list whose information has to be printed.
220
void osl_relation_list_print(FILE * file, osl_relation_list_p list) {
222
osl_relation_list_pprint(file, list, NULL);
225
/*****************************************************************************
227
*****************************************************************************/
231
* osl_relation_list_pread function ("precision read"):
232
* this function reads a list of relations into a file (foo,
233
* posibly stdin) and returns a pointer this relation list.
234
* \param[in] file The input stream.
235
* \param[in] precision The precision of the relation elements.
236
* \return A pointer to the relation list structure that has been read.
238
osl_relation_list_p osl_relation_list_pread(FILE * file, int precision) {
240
osl_relation_list_p list;
241
osl_relation_list_p res;
244
// Read the number of relations to read.
245
nb_mat = osl_util_read_int(file, NULL);
248
OSL_error("negative number of relations");
250
// Allocate the header of the list and start reading each element.
251
res = list = osl_relation_list_malloc();
252
for (i = 0; i < nb_mat; ++i) {
253
list->elt = osl_relation_pread(file, precision);
255
list->next = osl_relation_list_malloc();
264
* osl_relation_list_read function:
265
* this function is equivalent to osl_relation_list_pread() except that
266
* the precision corresponds to the precision environment variable or
267
* to the highest available precision if it is not defined.
268
* \see{osl_relation_list_pread}
270
osl_relation_list_p osl_relation_list_read(FILE * foo) {
271
int precision = osl_util_get_precision();
272
return osl_relation_list_pread(foo, precision);
276
/*+***************************************************************************
277
* Memory allocation/deallocation function *
278
*****************************************************************************/
282
* osl_relation_list_malloc function:
283
* This function allocates the memory space for a osl_relation_list_t
284
* structure and sets its fields with default values. Then it returns
285
* a pointer to the allocated space.
286
* \return A pointer to an empty relation list with fields set to default
289
osl_relation_list_p osl_relation_list_malloc() {
290
osl_relation_list_p res;
292
OSL_malloc(res, osl_relation_list_p, sizeof(osl_relation_list_t));
302
* osl_relation_list_free function:
303
* This function frees the allocated memory for a osl_relation_list_t
304
* structure, and all the relations stored in the list.
305
* \param list The pointer to the relation list we want to free.
307
void osl_relation_list_free(osl_relation_list_p list) {
308
osl_relation_list_p tmp;
313
while (list != NULL) {
314
if (list->elt != NULL)
315
osl_relation_free(list->elt);
323
/*+***************************************************************************
324
* Processing functions *
325
*****************************************************************************/
329
* osl_relation_list_node function:
330
* This function builds an osl_relation_list_t node and sets its
331
* relation element as a copy of the one provided as parameter.
332
* If the relation provided as an argument is NULL, NULL is returned.
333
* \param r The pointer to the relation to copy/paste in a list node.
334
* \return A pointer to a relation list node containing a copy of "relation".
336
osl_relation_list_p osl_relation_list_node(osl_relation_p r) {
337
osl_relation_list_p new = NULL;
340
new = osl_relation_list_malloc();
341
new->elt = osl_relation_clone(r);
348
* osl_relation_list_clone function:
349
* This functions builds and returns a quasi-"hard copy" (not a pointer copy)
350
* of a osl_relation_list_t data structure provided as parameter.
351
* \param list The pointer to the relation list we want to copy.
352
* \return A pointer to the full copy of the relation list in parameter.
354
osl_relation_list_p osl_relation_list_clone(osl_relation_list_p list) {
356
osl_relation_list_p clone = NULL, node, previous = NULL;
359
while (list != NULL) {
360
node = osl_relation_list_malloc();
361
node->elt = osl_relation_clone(list->elt);
369
previous->next = node;
370
previous = previous->next;
381
* osl_relation_list_concat function:
382
* this function builds a new relation list as the concatenation of the
383
* two lists sent as parameters.
384
* \param l1 The first relation list.
385
* \param l2 The second relation list.
386
* \return A pointer to the relation list resulting from the concatenation of
389
osl_relation_list_p osl_relation_list_concat(osl_relation_list_p l1,
390
osl_relation_list_p l2) {
391
osl_relation_list_p new, end;
394
return osl_relation_list_clone(l2);
397
return osl_relation_list_clone(l1);
399
new = osl_relation_list_clone(l1);
401
while (end->next != NULL)
403
end->next = osl_relation_list_clone(l2);
410
* osl_relation_list_concat_inplace function:
411
* this function concatenates a relation list to another. No new list is
412
* created: this functions links the two input lists. If the first relation
413
* list is NULL, it is set to the second relation list.
414
* two lists sent as parameters.
415
* \param[in,out] l1 Pointer to the first relation list.
416
* \param[in] l2 The second relation list.
418
void osl_relation_list_concat_inplace(osl_relation_list_p *l1,
419
osl_relation_list_p l2) {
420
osl_relation_list_p temp;
428
while (temp->next != NULL)
435
* osl_relation_list_equal function:
436
* This function returns true if the two relation lists are the same, false
438
* \param l1 The first relation list.
439
* \param l2 The second relation list.
440
* \return 1 if l1 and l2 are the same (content-wise), 0 otherwise.
442
int osl_relation_list_equal(osl_relation_list_p l1, osl_relation_list_p l2) {
443
while ((l1 != NULL) && (l2 != NULL)) {
447
if (!osl_relation_equal(l1->elt, l2->elt))
454
if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL)))
462
* osl_relation_integrity_check function:
463
* This function checks that a list of relation is "well formed" according to
464
* some expected properties (setting an expected value to OSL_UNDEFINED
465
* means that we do not expect a specific value) and what the relations are
466
* supposed to represent (all relations of a list are supposed to have the
467
* same semantics). It returns 0 if the check failed or 1 if no problem has
469
* \param list The relation list we want to check.
470
* \param type Semantics about this relation (domain, access...).
471
* \param expected_nb_output_dims Expected number of output dimensions.
472
* \param expected_nb_input_dims Expected number of input dimensions.
473
* \param expected_nb_parameters Expected number of parameters.
474
* \return 0 if the integrity check fails, 1 otherwise.
476
int osl_relation_list_integrity_check(osl_relation_list_p list,
478
int expected_nb_output_dims,
479
int expected_nb_input_dims,
480
int expected_nb_parameters) {
481
while (list != NULL) {
482
// Check the access function.
483
if (!osl_relation_integrity_check(list->elt,
485
expected_nb_output_dims,
486
expected_nb_input_dims,
487
expected_nb_parameters)) {
499
* osl_relation_list_set_type function:
500
* this function sets the type of each relation in the relation list to the
501
* one provided as parameter.
502
* \param list The list of relations to set the type.
503
* \param type The type.
505
void osl_relation_list_set_type(osl_relation_list_p list, int type) {
507
while (list != NULL) {
508
if (list->elt != NULL) {
509
list->elt->type = type;
517
* osl_relation_list_filter function:
518
* this function returns a copy of the input relation list, restricted to
519
* the relations of a given type. The special type OSL_TYPE_ACCESS
520
* filters any kind of access (read, write, rdwr etc.).
521
* \param list The relation list to copy/filter.
522
* \param type The filtering type.
523
* \return A copy of the input list with only relation of the given type.
525
osl_relation_list_p osl_relation_list_filter(osl_relation_list_p list,
528
osl_relation_list_p copy = osl_relation_list_clone(list);
529
osl_relation_list_p filtered = NULL;
530
osl_relation_list_p previous = NULL;
531
osl_relation_list_p trash;
534
while (copy != NULL) {
535
if ((copy->elt != NULL) &&
536
(((type == OSL_TYPE_ACCESS) &&
537
(osl_relation_is_access(copy->elt))) ||
538
((type != OSL_TYPE_ACCESS) &&
539
(type == copy->elt->type)))) {
551
previous->next = copy->next;
554
osl_relation_list_free(trash);
563
* osl_relation_list_count function:
564
* this function returns the number of elements with non-NULL content
565
* in a relation list.
566
* \param list The relation list to count the number of elements.
567
* \return The number of nodes with non-NULL content in the relation list.
569
int osl_relation_list_count(osl_relation_list_p list) {
572
while (list != NULL) {
573
if (list->elt != NULL)
583
* osl_relation_list_get_attributes function:
584
* this function returns, through its parameters, the maximum values of the
585
* relation attributes (nb_iterators, nb_parameters etc) in the relation list,
586
* depending on its type. HOWEVER, it updates the parameter value iff the
587
* attribute is greater than the input parameter value. Hence it may be used
588
* to get the attributes as well as to find the maximum attributes for several
589
* relation lists. The array identifier 0 is used when there is no array
590
* identifier (AND this is OK), OSL_UNDEFINED is used to report it is
591
* impossible to provide the property while it should. This function is not
592
* intended for checking, the input relation list should be correct.
593
* \param[in] list The relation list to extract attribute values.
594
* \param[in,out] nb_parameters Number of parameter attribute.
595
* \param[in,out] nb_iterators Number of iterators attribute.
596
* \param[in,out] nb_scattdims Number of scattering dimensions attribute.
597
* \param[in,out] nb_localdims Number of local dimensions attribute.
598
* \param[in,out] array_id Maximum array identifier attribute.
600
void osl_relation_list_get_attributes(osl_relation_list_p list,
606
int local_nb_parameters = OSL_UNDEFINED;
607
int local_nb_iterators = OSL_UNDEFINED;
608
int local_nb_scattdims = OSL_UNDEFINED;
609
int local_nb_localdims = OSL_UNDEFINED;
610
int local_array_id = OSL_UNDEFINED;
612
while (list != NULL) {
613
osl_relation_get_attributes(list->elt,
614
&local_nb_parameters,
620
*nb_parameters = OSL_max(*nb_parameters, local_nb_parameters);
621
*nb_iterators = OSL_max(*nb_iterators, local_nb_iterators);
622
*nb_scattdims = OSL_max(*nb_scattdims, local_nb_scattdims);
623
*nb_localdims = OSL_max(*nb_localdims, local_nb_localdims);
624
*array_id = OSL_max(*array_id, local_array_id);
added
removed
osl/source/relation_list.c
