isl_list_templ.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2011      INRIA Saclay
   4  * Copyright 2012-2013 Ecole Normale Superieure
   5  *
   6  * Use of this software is governed by the MIT license
   7  *
   8  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   9  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
  10  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  11  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  12  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  13  */
  14
  15 #include <isl_sort.h>
  16
  17 #define xCAT(A,B) A ## B
  18 #define CAT(A,B) xCAT(A,B)
  19 #undef EL
  20 #define EL CAT(isl_,BASE)
  21 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  22 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  23 #define xLIST(EL) EL ## _list
  24 #define LIST(EL) xLIST(EL)
  25 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  26 #define S(TYPE,NAME) xS(TYPE,NAME)
  27
  28 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
  29 {
  30         return list ? list->ctx : NULL;
  31 }
  32
  33 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
  34 {
  35         LIST(EL) *list;
  36
  37         if (n < 0)
  38                 isl_die(ctx, isl_error_invalid,
  39                         "cannot create list of negative length",
  40                         return NULL);
  41         list = isl_alloc(ctx, LIST(EL),
  42                          sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
  43         if (!list)
  44                 return NULL;
  45
  46         list->ctx = ctx;
  47         isl_ctx_ref(ctx);
  48         list->ref = 1;
  49         list->size = n;
  50         list->n = 0;
  51         return list;
  52 }
  53
  54 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
  55 {
  56         if (!list)
  57                 return NULL;
  58
  59         list->ref++;
  60         return list;
  61 }
  62
  63 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
  64 {
  65         int i;
  66         LIST(EL) *dup;
  67
  68         if (!list)
  69                 return NULL;
  70
  71         dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
  72         if (!dup)
  73                 return NULL;
  74         for (i = 0; i < list->n; ++i)
  75                 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
  76         return dup;
  77 }
  78
  79 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
  80 {
  81         if (!list)
  82                 return NULL;
  83
  84         if (list->ref == 1)
  85                 return list;
  86         list->ref--;
  87         return FN(LIST(EL),dup)(list);
  88 }
  89
  90 /* Make sure "list" has room for at least "n" more pieces.
  91  *
  92  * If there is only one reference to list, we extend it in place.
  93  * Otherwise, we create a new LIST(EL) and copy the elements.
  94  */
  95 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
  96 {
  97         isl_ctx *ctx;
  98         int i, new_size;
  99         LIST(EL) *res;
 100
 101         if (!list)
 102                 return NULL;
 103         if (list->n + n <= list->size)
 104                 return list;
 105
 106         ctx = FN(LIST(EL),get_ctx)(list);
 107         new_size = ((list->n + n + 1) * 3) / 2;
 108         if (list->ref == 1) {
 109                 res = isl_realloc(ctx, list, LIST(EL),
 110                             sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
 111                 if (!res)
 112                         return FN(LIST(EL),free)(list);
 113                 res->size = new_size;
 114                 return res;
 115         }
 116
 117         res = FN(LIST(EL),alloc)(ctx, new_size);
 118         if (!res)
 119                 return FN(LIST(EL),free)(list);
 120
 121         for (i = 0; i < list->n; ++i)
 122                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 123
 124         FN(LIST(EL),free)(list);
 125         return res;
 126 }
 127
 128 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
 129         __isl_take struct EL *el)
 130 {
 131         list = FN(LIST(EL),grow)(list, 1);
 132         if (!list || !el)
 133                 goto error;
 134         list->p[list->n] = el;
 135         list->n++;
 136         return list;
 137 error:
 138         FN(EL,free)(el);
 139         FN(LIST(EL),free)(list);
 140         return NULL;
 141 }
 142
 143 /* Remove the "n" elements starting at "first" from "list".
 144  */
 145 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
 146         unsigned first, unsigned n)
 147 {
 148         int i;
 149
 150         if (!list)
 151                 return NULL;
 152         if (first + n > list->n || first + n < first)
 153                 isl_die(list->ctx, isl_error_invalid,
 154                         "index out of bounds", return FN(LIST(EL),free)(list));
 155         if (n == 0)
 156                 return list;
 157         list = FN(LIST(EL),cow)(list);
 158         if (!list)
 159                 return NULL;
 160         for (i = 0; i < n; ++i)
 161                 FN(EL,free)(list->p[first + i]);
 162         for (i = first; i + n < list->n; ++i)
 163                 list->p[i] = list->p[i + n];
 164         list->n -= n;
 165         return list;
 166 }
 167
 168 /* Insert "el" at position "pos" in "list".
 169  *
 170  * If there is only one reference to "list" and if it already has space
 171  * for one extra element, we insert it directly into "list".
 172  * Otherwise, we create a new list consisting of "el" and copied
 173  * elements from "list".
 174  */
 175 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
 176         unsigned pos, __isl_take struct EL *el)
 177 {
 178         int i;
 179         isl_ctx *ctx;
 180         LIST(EL) *res;
 181
 182         if (!list || !el)
 183                 goto error;
 184         ctx = FN(LIST(EL),get_ctx)(list);
 185         if (pos > list->n)
 186                 isl_die(ctx, isl_error_invalid,
 187                         "index out of bounds", goto error);
 188
 189         if (list->ref == 1 && list->size > list->n) {
 190                 for (i = list->n - 1; i >= pos; --i)
 191                         list->p[i + 1] = list->p[i];
 192                 list->n++;
 193                 list->p[pos] = el;
 194                 return list;
 195         }
 196
 197         res = FN(LIST(EL),alloc)(ctx, list->n + 1);
 198         for (i = 0; i < pos; ++i)
 199                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 200         res = FN(LIST(EL),add)(res, el);
 201         for (i = pos; i < list->n; ++i)
 202                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 203         FN(LIST(EL),free)(list);
 204
 205         return res;
 206 error:
 207         FN(EL,free)(el);
 208         FN(LIST(EL),free)(list);
 209         return NULL;
 210 }
 211
 212 void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
 213 {
 214         int i;
 215
 216         if (!list)
 217                 return NULL;
 218
 219         if (--list->ref > 0)
 220                 return NULL;
 221
 222         isl_ctx_deref(list->ctx);
 223         for (i = 0; i < list->n; ++i)
 224                 FN(EL,free)(list->p[i]);
 225         free(list);
 226
 227         return NULL;
 228 }
 229
 230 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
 231 {
 232         return list ? list->n : 0;
 233 }
 234
 235 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
 236 {
 237         if (!list)
 238                 return NULL;
 239         if (index < 0 || index >= list->n)
 240                 isl_die(list->ctx, isl_error_invalid,
 241                         "index out of bounds", return NULL);
 242         return FN(EL,copy)(list->p[index]);
 243 }
 244
 245 /* Replace the element at position "index" in "list" by "el".
 246  */
 247 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
 248         int index, __isl_take EL *el)
 249 {
 250         if (!list || !el)
 251                 goto error;
 252         if (index < 0 || index >= list->n)
 253                 isl_die(list->ctx, isl_error_invalid,
 254                         "index out of bounds", goto error);
 255         if (list->p[index] == el) {
 256                 FN(EL,free)(el);
 257                 return list;
 258         }
 259         list = FN(LIST(EL),cow)(list);
 260         if (!list)
 261                 goto error;
 262         FN(EL,free)(list->p[index]);
 263         list->p[index] = el;
 264         return list;
 265 error:
 266         FN(EL,free)(el);
 267         FN(LIST(EL),free)(list);
 268         return NULL;
 269 }
 270
 271 int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
 272         int (*fn)(__isl_take EL *el, void *user), void *user)
 273 {
 274         int i;
 275
 276         if (!list)
 277                 return -1;
 278
 279         for (i = 0; i < list->n; ++i) {
 280                 EL *el = FN(EL,copy(list->p[i]));
 281                 if (!el)
 282                         return -1;
 283                 if (fn(el, user) < 0)
 284                         return -1;
 285         }
 286
 287         return 0;
 288 }
 289
 290 /* Internal data structure for isl_*_list_sort.
 291  *
 292  * "cmp" is the original comparison function.
 293  * "user" is a user provided pointer that should be passed to "cmp".
 294  */
 295 S(LIST(EL),sort_data) {
 296         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 297         void *user;
 298 };
 299
 300 /* Compare two entries of an isl_*_list based on the user provided
 301  * comparison function on pairs of isl_* objects.
 302  */
 303 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
 304 {
 305         S(LIST(EL),sort_data) *data = user;
 306         EL * const *el1 = a;
 307         EL * const *el2 = b;
 308
 309         return data->cmp(*el1, *el2, data->user);
 310 }
 311
 312 /* Sort the elements of "list" in ascending order according to
 313  * comparison function "cmp".
 314  */
 315 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
 316         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
 317 {
 318         S(LIST(EL),sort_data) data = { cmp, user };
 319
 320         if (!list)
 321                 return NULL;
 322         if (list->n <= 1)
 323                 return list;
 324         list = FN(LIST(EL),cow)(list);
 325         if (!list)
 326                 return NULL;
 327
 328         if (isl_sort(list->p, list->n, sizeof(list->p[0]),
 329                         &FN(LIST(EL),cmp), &data) < 0)
 330                 return FN(LIST(EL),free)(list);
 331
 332         return list;
 333 }
 334
 335 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
 336 {
 337         isl_ctx *ctx;
 338         LIST(EL) *list;
 339
 340         if (!el)
 341                 return NULL;
 342         ctx = FN(EL,get_ctx)(el);
 343         list = FN(LIST(EL),alloc)(ctx, 1);
 344         if (!list)
 345                 goto error;
 346         list = FN(LIST(EL),add)(list, el);
 347         return list;
 348 error:
 349         FN(EL,free)(el);
 350         return NULL;
 351 }
 352
 353 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
 354         __isl_take LIST(EL) *list2)
 355 {
 356         int i;
 357         isl_ctx *ctx;
 358         LIST(EL) *res;
 359
 360         if (!list1 || !list2)
 361                 goto error;
 362
 363         ctx = FN(LIST(EL),get_ctx)(list1);
 364         res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
 365         for (i = 0; i < list1->n; ++i)
 366                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
 367         for (i = 0; i < list2->n; ++i)
 368                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
 369
 370         FN(LIST(EL),free)(list1);
 371         FN(LIST(EL),free)(list2);
 372         return res;
 373 error:
 374         FN(LIST(EL),free)(list1);
 375         FN(LIST(EL),free)(list2);
 376         return NULL;
 377 }
 378
 379 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
 380         __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
 381 {
 382         int i;
 383
 384         if (!p || !list)
 385                 goto error;
 386         p = isl_printer_print_str(p, "(");
 387         for (i = 0; i < list->n; ++i) {
 388                 if (i)
 389                         p = isl_printer_print_str(p, ",");
 390                 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
 391         }
 392         p = isl_printer_print_str(p, ")");
 393         return p;
 394 error:
 395         isl_printer_free(p);
 396         return NULL;
 397 }
 398
 399 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
 400 {
 401         isl_printer *printer;
 402
 403         if (!list)
 404                 return;
 405
 406         printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
 407         printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
 408         printer = isl_printer_end_line(printer);
 409
 410         isl_printer_free(printer);
 411 }