isl_list_templ.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2011      INRIA Saclay
   4  * Copyright 2012      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 #define xCAT(A,B) A ## B
  16 #define CAT(A,B) xCAT(A,B)
  17 #undef EL
  18 #define EL CAT(isl_,BASE)
  19 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  20 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  21 #define xLIST(EL) EL ## _list
  22 #define LIST(EL) xLIST(EL)
  23
  24 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
  25 {
  26         return list ? list->ctx : NULL;
  27 }
  28
  29 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
  30 {
  31         LIST(EL) *list;
  32
  33         if (n < 0)
  34                 isl_die(ctx, isl_error_invalid,
  35                         "cannot create list of negative length",
  36                         return NULL);
  37         list = isl_alloc(ctx, LIST(EL),
  38                          sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
  39         if (!list)
  40                 return NULL;
  41
  42         list->ctx = ctx;
  43         isl_ctx_ref(ctx);
  44         list->ref = 1;
  45         list->size = n;
  46         list->n = 0;
  47         return list;
  48 }
  49
  50 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
  51 {
  52         if (!list)
  53                 return NULL;
  54
  55         list->ref++;
  56         return list;
  57 }
  58
  59 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
  60 {
  61         int i;
  62         LIST(EL) *dup;
  63
  64         if (!list)
  65                 return NULL;
  66
  67         dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
  68         if (!dup)
  69                 return NULL;
  70         for (i = 0; i < list->n; ++i)
  71                 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
  72         return dup;
  73 }
  74
  75 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
  76 {
  77         if (!list)
  78                 return NULL;
  79
  80         if (list->ref == 1)
  81                 return list;
  82         list->ref--;
  83         return FN(LIST(EL),dup)(list);
  84 }
  85
  86 /* Make sure "list" has room for at least "n" more pieces.
  87  *
  88  * If there is only one reference to list, we extend it in place.
  89  * Otherwise, we create a new LIST(EL) and copy the elements.
  90  */
  91 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
  92 {
  93         isl_ctx *ctx;
  94         int i, new_size;
  95         LIST(EL) *res;
  96
  97         if (!list)
  98                 return NULL;
  99         if (list->n + n <= list->size)
 100                 return list;
 101
 102         ctx = FN(LIST(EL),get_ctx)(list);
 103         new_size = ((list->n + n + 1) * 3) / 2;
 104         if (list->ref == 1) {
 105                 res = isl_realloc(ctx, list, LIST(EL),
 106                             sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
 107                 if (!res)
 108                         return FN(LIST(EL),free)(list);
 109                 res->size = new_size;
 110                 return res;
 111         }
 112
 113         res = FN(LIST(EL),alloc)(ctx, new_size);
 114         if (!res)
 115                 return FN(LIST(EL),free)(list);
 116
 117         for (i = 0; i < list->n; ++i)
 118                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 119
 120         FN(LIST(EL),free)(list);
 121         return res;
 122 }
 123
 124 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
 125         __isl_take struct EL *el)
 126 {
 127         list = FN(LIST(EL),grow)(list, 1);
 128         if (!list || !el)
 129                 goto error;
 130         list->p[list->n] = el;
 131         list->n++;
 132         return list;
 133 error:
 134         FN(EL,free)(el);
 135         FN(LIST(EL),free)(list);
 136         return NULL;
 137 }
 138
 139 /* Remove the "n" elements starting at "first" from "list".
 140  */
 141 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
 142         unsigned first, unsigned n)
 143 {
 144         int i;
 145
 146         if (!list)
 147                 return NULL;
 148         if (first + n > list->n || first + n < first)
 149                 isl_die(list->ctx, isl_error_invalid,
 150                         "index out of bounds", return FN(LIST(EL),free)(list));
 151         if (n == 0)
 152                 return list;
 153         list = FN(LIST(EL),cow)(list);
 154         if (!list)
 155                 return NULL;
 156         for (i = 0; i < n; ++i)
 157                 FN(EL,free)(list->p[first + i]);
 158         for (i = first; i + n < list->n; ++i)
 159                 list->p[i] = list->p[i + n];
 160         list->n -= n;
 161         return list;
 162 }
 163
 164 /* Insert "el" at position "pos" in "list".
 165  *
 166  * If there is only one reference to "list" and if it already has space
 167  * for one extra element, we insert it directly into "list".
 168  * Otherwise, we create a new list consisting of "el" and copied
 169  * elements from "list".
 170  */
 171 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
 172         unsigned pos, __isl_take struct EL *el)
 173 {
 174         int i;
 175         isl_ctx *ctx;
 176         LIST(EL) *res;
 177
 178         if (!list || !el)
 179                 goto error;
 180         ctx = FN(LIST(EL),get_ctx)(list);
 181         if (pos > list->n)
 182                 isl_die(ctx, isl_error_invalid,
 183                         "index out of bounds", goto error);
 184
 185         if (list->ref == 1 && list->size > list->n) {
 186                 for (i = list->n - 1; i >= pos; --i)
 187                         list->p[i + 1] = list->p[i];
 188                 list->n++;
 189                 list->p[pos] = el;
 190                 return list;
 191         }
 192
 193         res = FN(LIST(EL),alloc)(ctx, list->n + 1);
 194         for (i = 0; i < pos; ++i)
 195                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 196         res = FN(LIST(EL),add)(res, el);
 197         for (i = pos; i < list->n; ++i)
 198                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 199         FN(LIST(EL),free)(list);
 200
 201         return res;
 202 error:
 203         FN(EL,free)(el);
 204         FN(LIST(EL),free)(list);
 205         return NULL;
 206 }
 207
 208 void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
 209 {
 210         int i;
 211
 212         if (!list)
 213                 return NULL;
 214
 215         if (--list->ref > 0)
 216                 return NULL;
 217
 218         isl_ctx_deref(list->ctx);
 219         for (i = 0; i < list->n; ++i)
 220                 FN(EL,free)(list->p[i]);
 221         free(list);
 222
 223         return NULL;
 224 }
 225
 226 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
 227 {
 228         return list ? list->n : 0;
 229 }
 230
 231 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
 232 {
 233         if (!list)
 234                 return NULL;
 235         if (index < 0 || index >= list->n)
 236                 isl_die(list->ctx, isl_error_invalid,
 237                         "index out of bounds", return NULL);
 238         return FN(EL,copy)(list->p[index]);
 239 }
 240
 241 /* Replace the element at position "index" in "list" by "el".
 242  */
 243 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
 244         int index, __isl_take EL *el)
 245 {
 246         if (!list || !el)
 247                 goto error;
 248         if (index < 0 || index >= list->n)
 249                 isl_die(list->ctx, isl_error_invalid,
 250                         "index out of bounds", goto error);
 251         if (list->p[index] == el) {
 252                 FN(EL,free)(el);
 253                 return list;
 254         }
 255         list = FN(LIST(EL),cow)(list);
 256         if (!list)
 257                 goto error;
 258         FN(EL,free)(list->p[index]);
 259         list->p[index] = el;
 260         return list;
 261 error:
 262         FN(EL,free)(el);
 263         FN(LIST(EL),free)(list);
 264         return NULL;
 265 }
 266
 267 int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
 268         int (*fn)(__isl_take EL *el, void *user), void *user)
 269 {
 270         int i;
 271
 272         if (!list)
 273                 return -1;
 274
 275         for (i = 0; i < list->n; ++i) {
 276                 EL *el = FN(EL,copy(list->p[i]));
 277                 if (!el)
 278                         return -1;
 279                 if (fn(el, user) < 0)
 280                         return -1;
 281         }
 282
 283         return 0;
 284 }
 285
 286 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
 287 {
 288         isl_ctx *ctx;
 289         LIST(EL) *list;
 290
 291         if (!el)
 292                 return NULL;
 293         ctx = FN(EL,get_ctx)(el);
 294         list = FN(LIST(EL),alloc)(ctx, 1);
 295         if (!list)
 296                 goto error;
 297         list = FN(LIST(EL),add)(list, el);
 298         return list;
 299 error:
 300         FN(EL,free)(el);
 301         return NULL;
 302 }
 303
 304 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
 305         __isl_take LIST(EL) *list2)
 306 {
 307         int i;
 308         isl_ctx *ctx;
 309         LIST(EL) *res;
 310
 311         if (!list1 || !list2)
 312                 goto error;
 313
 314         ctx = FN(LIST(EL),get_ctx)(list1);
 315         res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
 316         for (i = 0; i < list1->n; ++i)
 317                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
 318         for (i = 0; i < list2->n; ++i)
 319                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
 320
 321         FN(LIST(EL),free)(list1);
 322         FN(LIST(EL),free)(list2);
 323         return res;
 324 error:
 325         FN(LIST(EL),free)(list1);
 326         FN(LIST(EL),free)(list2);
 327         return NULL;
 328 }
 329
 330 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
 331         __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
 332 {
 333         int i;
 334
 335         if (!p || !list)
 336                 goto error;
 337         p = isl_printer_print_str(p, "(");
 338         for (i = 0; i < list->n; ++i) {
 339                 if (i)
 340                         p = isl_printer_print_str(p, ",");
 341                 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
 342         }
 343         p = isl_printer_print_str(p, ")");
 344         return p;
 345 error:
 346         isl_printer_free(p);
 347         return NULL;
 348 }
 349
 350 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
 351 {
 352         isl_printer *printer;
 353
 354         if (!list)
 355                 return;
 356
 357         printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
 358         printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
 359         printer = isl_printer_end_line(printer);
 360
 361         isl_printer_free(printer);
 362 }