Objects/listobject.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI not be used in advertising or publicity pertaining to
  13 distribution of the software without specific, written prior permission.
  14
  15 STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
  16 THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17 FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
  18 FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  20 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  21 OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22
  23 ******************************************************************/
  24
  25 /* List object implementation */
  26
  27 #include "allobjects.h"
  28 #include "modsupport.h"
  29 #include "ceval.h"
  30 #ifdef STDC_HEADERS
  31 #include <stddef.h>
  32 #else
  33 #include <sys/types.h>          /* For size_t */
  34 #endif
  35
  36 #define ROUNDUP(n, block) ((((n)+(block)-1)/(block))*(block))
  37
  38 static int
  39 roundup(n)
  40         int n;
  41 {
  42         if (n < 500)
  43                 return ROUNDUP(n, 10);
  44         else
  45                 return ROUNDUP(n, 100);
  46 }
  47
  48 #define NRESIZE(var, type, nitems) RESIZE(var, type, roundup(nitems))
  49
  50 object *
  51 newlistobject(size)
  52         int size;
  53 {
  54         int i;
  55         listobject *op;
  56         size_t nbytes;
  57         if (size < 0) {
  58                 err_badcall();
  59                 return NULL;
  60         }
  61         nbytes = size * sizeof(object *);
  62         /* Check for overflow */
  63         if (nbytes / sizeof(object *) != size) {
  64                 return err_nomem();
  65         }
  66         op = (listobject *) malloc(sizeof(listobject));
  67         if (op == NULL) {
  68                 return err_nomem();
  69         }
  70         if (size <= 0) {
  71                 op->ob_item = NULL;
  72         }
  73         else {
  74                 op->ob_item = (object **) malloc(nbytes);
  75                 if (op->ob_item == NULL) {
  76                         free((ANY *)op);
  77                         return err_nomem();
  78                 }
  79         }
  80         op->ob_type = &Listtype;
  81         op->ob_size = size;
  82         for (i = 0; i < size; i++)
  83                 op->ob_item[i] = NULL;
  84         NEWREF(op);
  85         return (object *) op;
  86 }
  87
  88 int
  89 getlistsize(op)
  90         object *op;
  91 {
  92         if (!is_listobject(op)) {
  93                 err_badcall();
  94                 return -1;
  95         }
  96         else
  97                 return ((listobject *)op) -> ob_size;
  98 }
  99
 100 object *
 101 getlistitem(op, i)
 102         object *op;
 103         int i;
 104 {
 105         if (!is_listobject(op)) {
 106                 err_badcall();
 107                 return NULL;
 108         }
 109         if (i < 0 || i >= ((listobject *)op) -> ob_size) {
 110                 err_setstr(IndexError, "list index out of range");
 111                 return NULL;
 112         }
 113         return ((listobject *)op) -> ob_item[i];
 114 }
 115
 116 int
 117 setlistitem(op, i, newitem)
 118         register object *op;
 119         register int i;
 120         register object *newitem;
 121 {
 122         register object *olditem;
 123         register object **p;
 124         if (!is_listobject(op)) {
 125                 XDECREF(newitem);
 126                 err_badcall();
 127                 return -1;
 128         }
 129         if (i < 0 || i >= ((listobject *)op) -> ob_size) {
 130                 XDECREF(newitem);
 131                 err_setstr(IndexError, "list assignment index out of range");
 132                 return -1;
 133         }
 134         p = ((listobject *)op) -> ob_item + i;
 135         olditem = *p;
 136         *p = newitem;
 137         XDECREF(olditem);
 138         return 0;
 139 }
 140
 141 static int
 142 ins1(self, where, v)
 143         listobject *self;
 144         int where;
 145         object *v;
 146 {
 147         int i;
 148         object **items;
 149         if (v == NULL) {
 150                 err_badcall();
 151                 return -1;
 152         }
 153         items = self->ob_item;
 154         NRESIZE(items, object *, self->ob_size+1);
 155         if (items == NULL) {
 156                 err_nomem();
 157                 return -1;
 158         }
 159         if (where < 0)
 160                 where = 0;
 161         if (where > self->ob_size)
 162                 where = self->ob_size;
 163         for (i = self->ob_size; --i >= where; )
 164                 items[i+1] = items[i];
 165         INCREF(v);
 166         items[where] = v;
 167         self->ob_item = items;
 168         self->ob_size++;
 169         return 0;
 170 }
 171
 172 int
 173 inslistitem(op, where, newitem)
 174         object *op;
 175         int where;
 176         object *newitem;
 177 {
 178         if (!is_listobject(op)) {
 179                 err_badcall();
 180                 return -1;
 181         }
 182         return ins1((listobject *)op, where, newitem);
 183 }
 184
 185 int
 186 addlistitem(op, newitem)
 187         object *op;
 188         object *newitem;
 189 {
 190         if (!is_listobject(op)) {
 191                 err_badcall();
 192                 return -1;
 193         }
 194         return ins1((listobject *)op,
 195                 (int) ((listobject *)op)->ob_size, newitem);
 196 }
 197
 198 /* Methods */
 199
 200 static void
 201 list_dealloc(op)
 202         listobject *op;
 203 {
 204         int i;
 205         if (op->ob_item != NULL) {
 206                 for (i = 0; i < op->ob_size; i++) {
 207                         XDECREF(op->ob_item[i]);
 208                 }
 209                 free((ANY *)op->ob_item);
 210         }
 211         free((ANY *)op);
 212 }
 213
 214 static int
 215 list_print(op, fp, flags)
 216         listobject *op;
 217         FILE *fp;
 218         int flags;
 219 {
 220         int i;
 221         fprintf(fp, "[");
 222         for (i = 0; i < op->ob_size; i++) {
 223                 if (i > 0)
 224                         fprintf(fp, ", ");
 225                 if (printobject(op->ob_item[i], fp, 0) != 0)
 226                         return -1;
 227         }
 228         fprintf(fp, "]");
 229         return 0;
 230 }
 231
 232 static object *
 233 list_repr(v)
 234         listobject *v;
 235 {
 236         object *s, *comma;
 237         int i;
 238         s = newstringobject("[");
 239         comma = newstringobject(", ");
 240         for (i = 0; i < v->ob_size && s != NULL; i++) {
 241                 if (i > 0)
 242                         joinstring(&s, comma);
 243                 joinstring_decref(&s, reprobject(v->ob_item[i]));
 244         }
 245         XDECREF(comma);
 246         joinstring_decref(&s, newstringobject("]"));
 247         return s;
 248 }
 249
 250 static int
 251 list_compare(v, w)
 252         listobject *v, *w;
 253 {
 254         int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
 255         int i;
 256         for (i = 0; i < len; i++) {
 257                 int cmp = cmpobject(v->ob_item[i], w->ob_item[i]);
 258                 if (cmp != 0)
 259                         return cmp;
 260         }
 261         return v->ob_size - w->ob_size;
 262 }
 263
 264 static int
 265 list_length(a)
 266         listobject *a;
 267 {
 268         return a->ob_size;
 269 }
 270
 271 static object *
 272 list_item(a, i)
 273         listobject *a;
 274         int i;
 275 {
 276         if (i < 0 || i >= a->ob_size) {
 277                 err_setstr(IndexError, "list index out of range");
 278                 return NULL;
 279         }
 280         INCREF(a->ob_item[i]);
 281         return a->ob_item[i];
 282 }
 283
 284 static object *
 285 list_slice(a, ilow, ihigh)
 286         listobject *a;
 287         int ilow, ihigh;
 288 {
 289         listobject *np;
 290         int i;
 291         if (ilow < 0)
 292                 ilow = 0;
 293         else if (ilow > a->ob_size)
 294                 ilow = a->ob_size;
 295         if (ihigh < 0)
 296                 ihigh = 0;
 297         if (ihigh < ilow)
 298                 ihigh = ilow;
 299         else if (ihigh > a->ob_size)
 300                 ihigh = a->ob_size;
 301         np = (listobject *) newlistobject(ihigh - ilow);
 302         if (np == NULL)
 303                 return NULL;
 304         for (i = ilow; i < ihigh; i++) {
 305                 object *v = a->ob_item[i];
 306                 INCREF(v);
 307                 np->ob_item[i - ilow] = v;
 308         }
 309         return (object *)np;
 310 }
 311
 312 object *
 313 getlistslice(a, ilow, ihigh)
 314         object *a;
 315         int ilow, ihigh;
 316 {
 317         if (!is_listobject(a)) {
 318                 err_badcall();
 319                 return NULL;
 320         }
 321         return list_slice((listobject *)a, ilow, ihigh);
 322 }
 323
 324 static object *
 325 list_concat(a, bb)
 326         listobject *a;
 327         object *bb;
 328 {
 329         int size;
 330         int i;
 331         listobject *np;
 332         if (!is_listobject(bb)) {
 333                 err_badarg();
 334                 return NULL;
 335         }
 336 #define b ((listobject *)bb)
 337         size = a->ob_size + b->ob_size;
 338         np = (listobject *) newlistobject(size);
 339         if (np == NULL) {
 340                 return NULL;
 341         }
 342         for (i = 0; i < a->ob_size; i++) {
 343                 object *v = a->ob_item[i];
 344                 INCREF(v);
 345                 np->ob_item[i] = v;
 346         }
 347         for (i = 0; i < b->ob_size; i++) {
 348                 object *v = b->ob_item[i];
 349                 INCREF(v);
 350                 np->ob_item[i + a->ob_size] = v;
 351         }
 352         return (object *)np;
 353 #undef b
 354 }
 355
 356 static object *
 357 list_repeat(a, n)
 358         listobject *a;
 359         int n;
 360 {
 361         int i, j;
 362         int size;
 363         listobject *np;
 364         object **p;
 365         if (n < 0)
 366                 n = 0;
 367         size = a->ob_size * n;
 368         np = (listobject *) newlistobject(size);
 369         if (np == NULL)
 370                 return NULL;
 371         p = np->ob_item;
 372         for (i = 0; i < n; i++) {
 373                 for (j = 0; j < a->ob_size; j++) {
 374                         *p = a->ob_item[j];
 375                         INCREF(*p);
 376                         p++;
 377                 }
 378         }
 379         return (object *) np;
 380 }
 381
 382 static int
 383 list_ass_slice(a, ilow, ihigh, v)
 384         listobject *a;
 385         int ilow, ihigh;
 386         object *v;
 387 {
 388         /* Because [X]DECREF can recursively invoke list operations on
 389            this list, we must postpone all [X]DECREF activity until
 390            after the list is back in its canonical shape.  Therefore
 391            we must allocate an additional array, 'recycle', into which
 392            we temporarily copy the items that are deleted from the
 393            list. :-( */
 394         object **recycle, **p;
 395         object **item;
 396         int n; /* Size of replacement list */
 397         int d; /* Change in size */
 398         int k; /* Loop index */
 399 #define b ((listobject *)v)
 400         if (v == NULL)
 401                 n = 0;
 402         else if (is_listobject(v)) {
 403                 n = b->ob_size;
 404                 if (a == b) {
 405                         /* Special case "a[i:j] = a" -- copy b first */
 406                         int ret;
 407                         v = list_slice(b, 0, n);
 408                         ret = list_ass_slice(a, ilow, ihigh, v);
 409                         DECREF(v);
 410                         return ret;
 411                 }
 412         }
 413         else {
 414                 err_badarg();
 415                 return -1;
 416         }
 417         if (ilow < 0)
 418                 ilow = 0;
 419         else if (ilow > a->ob_size)
 420                 ilow = a->ob_size;
 421         if (ihigh < 0)
 422                 ihigh = 0;
 423         if (ihigh < ilow)
 424                 ihigh = ilow;
 425         else if (ihigh > a->ob_size)
 426                 ihigh = a->ob_size;
 427         item = a->ob_item;
 428         d = n - (ihigh-ilow);
 429         if (ihigh > ilow)
 430                 p = recycle = NEW(object *, (ihigh-ilow));
 431         else
 432                 p = recycle = NULL;
 433         if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
 434                 for (k = ilow; k < ihigh; k++)
 435                         *p++ = item[k];
 436                 if (d < 0) {
 437                         for (/*k = ihigh*/; k < a->ob_size; k++)
 438                                 item[k+d] = item[k];
 439                         a->ob_size += d;
 440                         NRESIZE(item, object *, a->ob_size); /* Can't fail */
 441                         a->ob_item = item;
 442                 }
 443         }
 444         else { /* Insert d items; recycle ihigh-ilow items */
 445                 NRESIZE(item, object *, a->ob_size + d);
 446                 if (item == NULL) {
 447                         XDEL(recycle);
 448                         err_nomem();
 449                         return -1;
 450                 }
 451                 for (k = a->ob_size; --k >= ihigh; )
 452                         item[k+d] = item[k];
 453                 for (/*k = ihigh-1*/; k >= ilow; --k)
 454                         *p++ = item[k];
 455                 a->ob_item = item;
 456                 a->ob_size += d;
 457         }
 458         for (k = 0; k < n; k++, ilow++) {
 459                 object *w = b->ob_item[k];
 460                 XINCREF(w);
 461                 item[ilow] = w;
 462         }
 463         if (recycle) {
 464                 while (--p >= recycle)
 465                         XDECREF(*p);
 466                 DEL(recycle);
 467         }
 468         return 0;
 469 #undef b
 470 }
 471
 472 int
 473 setlistslice(a, ilow, ihigh, v)
 474         object *a;
 475         int ilow, ihigh;
 476         object *v;
 477 {
 478         if (!is_listobject(a)) {
 479                 err_badcall();
 480                 return -1;
 481         }
 482         return list_ass_slice((listobject *)a, ilow, ihigh, v);
 483 }
 484
 485 static int
 486 list_ass_item(a, i, v)
 487         listobject *a;
 488         int i;
 489         object *v;
 490 {
 491         object *old_value;
 492         if (i < 0 || i >= a->ob_size) {
 493                 err_setstr(IndexError, "list assignment index out of range");
 494                 return -1;
 495         }
 496         if (v == NULL)
 497                 return list_ass_slice(a, i, i+1, v);
 498         INCREF(v);
 499         old_value = a->ob_item[i];
 500         a->ob_item[i] = v;
 501         DECREF(old_value);
 502         return 0;
 503 }
 504
 505 static object *
 506 ins(self, where, v)
 507         listobject *self;
 508         int where;
 509         object *v;
 510 {
 511         if (ins1(self, where, v) != 0)
 512                 return NULL;
 513         INCREF(None);
 514         return None;
 515 }
 516
 517 static object *
 518 listinsert(self, args)
 519         listobject *self;
 520         object *args;
 521 {
 522         int i;
 523         object *v;
 524         if (!getargs(args, "(iO)", &i, &v))
 525                 return NULL;
 526         return ins(self, i, v);
 527 }
 528
 529 static object *
 530 listappend(self, args)
 531         listobject *self;
 532         object *args;
 533 {
 534         object *v;
 535         if (!getargs(args, "O", &v))
 536                 return NULL;
 537         return ins(self, (int) self->ob_size, v);
 538 }
 539
 540 static object *comparefunc;
 541
 542 static int
 543 cmp(v, w)
 544         const ANY *v, *w;
 545 {
 546         object *t, *res;
 547         long i;
 548
 549         if (err_occurred())
 550                 return 0;
 551
 552         if (comparefunc == NULL)
 553                 return cmpobject(* (object **) v, * (object **) w);
 554
 555         /* Call the user-supplied comparison function */
 556         t = mkvalue("(OO)", * (object **) v, * (object **) w);
 557         if (t == NULL)
 558                 return 0;
 559         res = call_object(comparefunc, t);
 560         DECREF(t);
 561         if (res == NULL)
 562                 return 0;
 563         if (!is_intobject(res)) {
 564                 err_setstr(TypeError, "comparison function should return int");
 565                 i = 0;
 566         }
 567         else {
 568                 i = getintvalue(res);
 569                 if (i < 0)
 570                         i = -1;
 571                 else if (i > 0)
 572                         i = 1;
 573         }
 574         DECREF(res);
 575         return (int) i;
 576 }
 577
 578 static object *
 579 listsort(self, args)
 580         listobject *self;
 581         object *args;
 582 {
 583         object *save_comparefunc;
 584         if (self->ob_size <= 1) {
 585                 INCREF(None);
 586                 return None;
 587         }
 588         save_comparefunc = comparefunc;
 589         comparefunc = args;
 590         if (comparefunc != NULL) {
 591                 /* Test the comparison function for obvious errors */
 592                 (void) cmp((ANY *)&self->ob_item[0], (ANY *)&self->ob_item[1]);
 593                 if (err_occurred()) {
 594                         comparefunc = save_comparefunc;
 595                         return NULL;
 596                 }
 597         }
 598         qsort((char *)self->ob_item,
 599                                 (int) self->ob_size, sizeof(object *), cmp);
 600         comparefunc = save_comparefunc;
 601         if (err_occurred())
 602                 return NULL;
 603         INCREF(None);
 604         return None;
 605 }
 606
 607 static object *
 608 listreverse(self, args)
 609         listobject *self;
 610         object *args;
 611 {
 612         register object **p, **q;
 613         register object *tmp;
 614
 615         if (args != NULL) {
 616                 err_badarg();
 617                 return NULL;
 618         }
 619
 620         if (self->ob_size > 1) {
 621                 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
 622                                                 p < q; p++, q--) {
 623                         tmp = *p;
 624                         *p = *q;
 625                         *q = tmp;
 626                 }
 627         }
 628
 629         INCREF(None);
 630         return None;
 631 }
 632
 633 int
 634 reverselist(v)
 635         object *v;
 636 {
 637         if (v == NULL || !is_listobject(v)) {
 638                 err_badcall();
 639                 return -1;
 640         }
 641         v = listreverse((listobject *)v, (object *)NULL);
 642         if (v == NULL)
 643                 return -1;
 644         DECREF(v);
 645         return 0;
 646 }
 647
 648 int
 649 sortlist(v)
 650         object *v;
 651 {
 652         if (v == NULL || !is_listobject(v)) {
 653                 err_badcall();
 654                 return -1;
 655         }
 656         v = listsort((listobject *)v, (object *)NULL);
 657         if (v == NULL)
 658                 return -1;
 659         DECREF(v);
 660         return 0;
 661 }
 662
 663 object *
 664 listtuple(v)
 665         object *v;
 666 {
 667         object *w;
 668         object **p;
 669         int n;
 670         if (v == NULL || !is_listobject(v)) {
 671                 err_badcall();
 672                 return NULL;
 673         }
 674         n = ((listobject *)v)->ob_size;
 675         w = newtupleobject(n);
 676         if (w == NULL)
 677                 return NULL;
 678         p = ((tupleobject *)w)->ob_item;
 679         memcpy((ANY *)p,
 680                (ANY *)((listobject *)v)->ob_item,
 681                n*sizeof(object *));
 682         while (--n >= 0) {
 683                 INCREF(*p);
 684                 p++;
 685         }
 686         return w;
 687 }
 688
 689 static object *
 690 listindex(self, args)
 691         listobject *self;
 692         object *args;
 693 {
 694         int i;
 695
 696         if (args == NULL) {
 697                 err_badarg();
 698                 return NULL;
 699         }
 700         for (i = 0; i < self->ob_size; i++) {
 701                 if (cmpobject(self->ob_item[i], args) == 0)
 702                         return newintobject((long)i);
 703         }
 704         err_setstr(ValueError, "list.index(x): x not in list");
 705         return NULL;
 706 }
 707
 708 static object *
 709 listcount(self, args)
 710         listobject *self;
 711         object *args;
 712 {
 713         int count = 0;
 714         int i;
 715
 716         if (args == NULL) {
 717                 err_badarg();
 718                 return NULL;
 719         }
 720         for (i = 0; i < self->ob_size; i++) {
 721                 if (cmpobject(self->ob_item[i], args) == 0)
 722                         count++;
 723         }
 724         return newintobject((long)count);
 725 }
 726
 727 static object *
 728 listremove(self, args)
 729         listobject *self;
 730         object *args;
 731 {
 732         int i;
 733
 734         if (args == NULL) {
 735                 err_badarg();
 736                 return NULL;
 737         }
 738         for (i = 0; i < self->ob_size; i++) {
 739                 if (cmpobject(self->ob_item[i], args) == 0) {
 740                         if (list_ass_slice(self, i, i+1, (object *)NULL) != 0)
 741                                 return NULL;
 742                         INCREF(None);
 743                         return None;
 744                 }
 745
 746         }
 747         err_setstr(ValueError, "list.remove(x): x not in list");
 748         return NULL;
 749 }
 750
 751 static struct methodlist list_methods[] = {
 752         {"append",      (method)listappend},
 753         {"count",       (method)listcount},
 754         {"index",       (method)listindex},
 755         {"insert",      (method)listinsert},
 756         {"sort",        (method)listsort, 0},
 757         {"remove",      (method)listremove},
 758         {"reverse",     (method)listreverse},
 759         {NULL,          NULL}           /* sentinel */
 760 };
 761
 762 static object *
 763 list_getattr(f, name)
 764         listobject *f;
 765         char *name;
 766 {
 767         return findmethod(list_methods, (object *)f, name);
 768 }
 769
 770 static sequence_methods list_as_sequence = {
 771         (inquiry)list_length, /*sq_length*/
 772         (binaryfunc)list_concat, /*sq_concat*/
 773         (intargfunc)list_repeat, /*sq_repeat*/
 774         (intargfunc)list_item, /*sq_item*/
 775         (intintargfunc)list_slice, /*sq_slice*/
 776         (intobjargproc)list_ass_item, /*sq_ass_item*/
 777         (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
 778 };
 779
 780 typeobject Listtype = {
 781         OB_HEAD_INIT(&Typetype)
 782         0,
 783         "list",
 784         sizeof(listobject),
 785         0,
 786         (destructor)list_dealloc, /*tp_dealloc*/
 787         (printfunc)list_print, /*tp_print*/
 788         (getattrfunc)list_getattr, /*tp_getattr*/
 789         0,              /*tp_setattr*/
 790         (cmpfunc)list_compare, /*tp_compare*/
 791         (reprfunc)list_repr, /*tp_repr*/
 792         0,              /*tp_as_number*/
 793         &list_as_sequence,      /*tp_as_sequence*/
 794         0,              /*tp_as_mapping*/
 795 };