Objects/listobject.c

   1 /***********************************************************
   2 Copyright 1991, 1992, 1993, 1994 by Stichting Mathematisch Centrum,
   3 Amsterdam, 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
  31 object *
  32 newlistobject(size)
  33         int size;
  34 {
  35         int i;
  36         listobject *op;
  37         size_t nbytes;
  38         if (size < 0) {
  39                 err_badcall();
  40                 return NULL;
  41         }
  42         nbytes = size * sizeof(object *);
  43         /* Check for overflow */
  44         if (nbytes / sizeof(object *) != size) {
  45                 return err_nomem();
  46         }
  47         op = (listobject *) malloc(sizeof(listobject));
  48         if (op == NULL) {
  49                 return err_nomem();
  50         }
  51         if (size <= 0) {
  52                 op->ob_item = NULL;
  53         }
  54         else {
  55                 op->ob_item = (object **) malloc(nbytes);
  56                 if (op->ob_item == NULL) {
  57                         free((ANY *)op);
  58                         return err_nomem();
  59                 }
  60         }
  61         op->ob_type = &Listtype;
  62         op->ob_size = size;
  63         for (i = 0; i < size; i++)
  64                 op->ob_item[i] = NULL;
  65         NEWREF(op);
  66         return (object *) op;
  67 }
  68
  69 int
  70 getlistsize(op)
  71         object *op;
  72 {
  73         if (!is_listobject(op)) {
  74                 err_badcall();
  75                 return -1;
  76         }
  77         else
  78                 return ((listobject *)op) -> ob_size;
  79 }
  80
  81 object *
  82 getlistitem(op, i)
  83         object *op;
  84         int i;
  85 {
  86         if (!is_listobject(op)) {
  87                 err_badcall();
  88                 return NULL;
  89         }
  90         if (i < 0 || i >= ((listobject *)op) -> ob_size) {
  91                 err_setstr(IndexError, "list index out of range");
  92                 return NULL;
  93         }
  94         return ((listobject *)op) -> ob_item[i];
  95 }
  96
  97 int
  98 setlistitem(op, i, newitem)
  99         register object *op;
 100         register int i;
 101         register object *newitem;
 102 {
 103         register object *olditem;
 104         if (!is_listobject(op)) {
 105                 XDECREF(newitem);
 106                 err_badcall();
 107                 return -1;
 108         }
 109         if (i < 0 || i >= ((listobject *)op) -> ob_size) {
 110                 XDECREF(newitem);
 111                 err_setstr(IndexError, "list assignment index out of range");
 112                 return -1;
 113         }
 114         olditem = ((listobject *)op) -> ob_item[i];
 115         ((listobject *)op) -> ob_item[i] = newitem;
 116         XDECREF(olditem);
 117         return 0;
 118 }
 119
 120 static int
 121 ins1(self, where, v)
 122         listobject *self;
 123         int where;
 124         object *v;
 125 {
 126         int i;
 127         object **items;
 128         if (v == NULL) {
 129                 err_badcall();
 130                 return -1;
 131         }
 132         items = self->ob_item;
 133         RESIZE(items, object *, self->ob_size+1);
 134         if (items == NULL) {
 135                 err_nomem();
 136                 return -1;
 137         }
 138         if (where < 0)
 139                 where = 0;
 140         if (where > self->ob_size)
 141                 where = self->ob_size;
 142         for (i = self->ob_size; --i >= where; )
 143                 items[i+1] = items[i];
 144         INCREF(v);
 145         items[where] = v;
 146         self->ob_item = items;
 147         self->ob_size++;
 148         return 0;
 149 }
 150
 151 int
 152 inslistitem(op, where, newitem)
 153         object *op;
 154         int where;
 155         object *newitem;
 156 {
 157         if (!is_listobject(op)) {
 158                 err_badcall();
 159                 return -1;
 160         }
 161         return ins1((listobject *)op, where, newitem);
 162 }
 163
 164 int
 165 addlistitem(op, newitem)
 166         object *op;
 167         object *newitem;
 168 {
 169         if (!is_listobject(op)) {
 170                 err_badcall();
 171                 return -1;
 172         }
 173         return ins1((listobject *)op,
 174                 (int) ((listobject *)op)->ob_size, newitem);
 175 }
 176
 177 /* Methods */
 178
 179 static void
 180 list_dealloc(op)
 181         listobject *op;
 182 {
 183         int i;
 184         for (i = 0; i < op->ob_size; i++) {
 185                 XDECREF(op->ob_item[i]);
 186         }
 187         if (op->ob_item != NULL)
 188                 free((ANY *)op->ob_item);
 189         free((ANY *)op);
 190 }
 191
 192 static int
 193 list_print(op, fp, flags)
 194         listobject *op;
 195         FILE *fp;
 196         int flags;
 197 {
 198         int i;
 199         fprintf(fp, "[");
 200         for (i = 0; i < op->ob_size; i++) {
 201                 if (i > 0)
 202                         fprintf(fp, ", ");
 203                 if (printobject(op->ob_item[i], fp, 0) != 0)
 204                         return -1;
 205         }
 206         fprintf(fp, "]");
 207         return 0;
 208 }
 209
 210 static object *
 211 list_repr(v)
 212         listobject *v;
 213 {
 214         object *s, *comma;
 215         int i;
 216         s = newstringobject("[");
 217         comma = newstringobject(", ");
 218         for (i = 0; i < v->ob_size && s != NULL; i++) {
 219                 if (i > 0)
 220                         joinstring(&s, comma);
 221                 joinstring_decref(&s, reprobject(v->ob_item[i]));
 222         }
 223         XDECREF(comma);
 224         joinstring_decref(&s, newstringobject("]"));
 225         return s;
 226 }
 227
 228 static int
 229 list_compare(v, w)
 230         listobject *v, *w;
 231 {
 232         int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
 233         int i;
 234         for (i = 0; i < len; i++) {
 235                 int cmp = cmpobject(v->ob_item[i], w->ob_item[i]);
 236                 if (cmp != 0)
 237                         return cmp;
 238         }
 239         return v->ob_size - w->ob_size;
 240 }
 241
 242 static int
 243 list_length(a)
 244         listobject *a;
 245 {
 246         return a->ob_size;
 247 }
 248
 249 static object *
 250 list_item(a, i)
 251         listobject *a;
 252         int i;
 253 {
 254         if (i < 0 || i >= a->ob_size) {
 255                 err_setstr(IndexError, "list index out of range");
 256                 return NULL;
 257         }
 258         INCREF(a->ob_item[i]);
 259         return a->ob_item[i];
 260 }
 261
 262 static object *
 263 list_slice(a, ilow, ihigh)
 264         listobject *a;
 265         int ilow, ihigh;
 266 {
 267         listobject *np;
 268         int i;
 269         if (ilow < 0)
 270                 ilow = 0;
 271         else if (ilow > a->ob_size)
 272                 ilow = a->ob_size;
 273         if (ihigh < 0)
 274                 ihigh = 0;
 275         if (ihigh < ilow)
 276                 ihigh = ilow;
 277         else if (ihigh > a->ob_size)
 278                 ihigh = a->ob_size;
 279         np = (listobject *) newlistobject(ihigh - ilow);
 280         if (np == NULL)
 281                 return NULL;
 282         for (i = ilow; i < ihigh; i++) {
 283                 object *v = a->ob_item[i];
 284                 INCREF(v);
 285                 np->ob_item[i - ilow] = v;
 286         }
 287         return (object *)np;
 288 }
 289
 290 object *
 291 getlistslice(a, ilow, ihigh)
 292         object *a;
 293         int ilow, ihigh;
 294 {
 295         if (!is_listobject(a)) {
 296                 err_badcall();
 297                 return NULL;
 298         }
 299         return list_slice((listobject *)a, ilow, ihigh);
 300 }
 301
 302 static object *
 303 list_concat(a, bb)
 304         listobject *a;
 305         object *bb;
 306 {
 307         int size;
 308         int i;
 309         listobject *np;
 310         if (!is_listobject(bb)) {
 311                 err_badarg();
 312                 return NULL;
 313         }
 314 #define b ((listobject *)bb)
 315         size = a->ob_size + b->ob_size;
 316         np = (listobject *) newlistobject(size);
 317         if (np == NULL) {
 318                 return NULL;
 319         }
 320         for (i = 0; i < a->ob_size; i++) {
 321                 object *v = a->ob_item[i];
 322                 INCREF(v);
 323                 np->ob_item[i] = v;
 324         }
 325         for (i = 0; i < b->ob_size; i++) {
 326                 object *v = b->ob_item[i];
 327                 INCREF(v);
 328                 np->ob_item[i + a->ob_size] = v;
 329         }
 330         return (object *)np;
 331 #undef b
 332 }
 333
 334 static object *
 335 list_repeat(a, n)
 336         listobject *a;
 337         int n;
 338 {
 339         int i, j;
 340         int size;
 341         listobject *np;
 342         object **p;
 343         if (n < 0)
 344                 n = 0;
 345         size = a->ob_size * n;
 346         np = (listobject *) newlistobject(size);
 347         if (np == NULL)
 348                 return NULL;
 349         p = np->ob_item;
 350         for (i = 0; i < n; i++) {
 351                 for (j = 0; j < a->ob_size; j++) {
 352                         *p = a->ob_item[j];
 353                         INCREF(*p);
 354                         p++;
 355                 }
 356         }
 357         return (object *) np;
 358 }
 359
 360 static int
 361 list_ass_slice(a, ilow, ihigh, v)
 362         listobject *a;
 363         int ilow, ihigh;
 364         object *v;
 365 {
 366         object **item;
 367         int n; /* Size of replacement list */
 368         int d; /* Change in size */
 369         int k; /* Loop index */
 370 #define b ((listobject *)v)
 371         if (v == NULL)
 372                 n = 0;
 373         else if (is_listobject(v)) {
 374                 n = b->ob_size;
 375                 if (a == b) {
 376                         /* Special case "a[i:j] = a" -- copy b first */
 377                         int ret;
 378                         v = list_slice(b, 0, n);
 379                         ret = list_ass_slice(a, ilow, ihigh, v);
 380                         DECREF(v);
 381                         return ret;
 382                 }
 383         }
 384         else {
 385                 err_badarg();
 386                 return -1;
 387         }
 388         if (ilow < 0)
 389                 ilow = 0;
 390         else if (ilow > a->ob_size)
 391                 ilow = a->ob_size;
 392         if (ihigh < 0)
 393                 ihigh = 0;
 394         if (ihigh < ilow)
 395                 ihigh = ilow;
 396         else if (ihigh > a->ob_size)
 397                 ihigh = a->ob_size;
 398         item = a->ob_item;
 399         d = n - (ihigh-ilow);
 400         if (d <= 0) { /* Delete -d items; XDECREF ihigh-ilow items */
 401                 for (k = ilow; k < ihigh; k++)
 402                         XDECREF(item[k]);
 403                 if (d < 0) {
 404                         for (/*k = ihigh*/; k < a->ob_size; k++)
 405                                 item[k+d] = item[k];
 406                         a->ob_size += d;
 407                         RESIZE(item, object *, a->ob_size); /* Can't fail */
 408                         a->ob_item = item;
 409                 }
 410         }
 411         else { /* Insert d items; XDECREF ihigh-ilow items */
 412                 RESIZE(item, object *, a->ob_size + d);
 413                 if (item == NULL) {
 414                         err_nomem();
 415                         return -1;
 416                 }
 417                 for (k = a->ob_size; --k >= ihigh; )
 418                         item[k+d] = item[k];
 419                 for (/*k = ihigh-1*/; k >= ilow; --k)
 420                         XDECREF(item[k]);
 421                 a->ob_item = item;
 422                 a->ob_size += d;
 423         }
 424         for (k = 0; k < n; k++, ilow++) {
 425                 object *w = b->ob_item[k];
 426                 XINCREF(w);
 427                 item[ilow] = w;
 428         }
 429         return 0;
 430 #undef b
 431 }
 432
 433 int
 434 setlistslice(a, ilow, ihigh, v)
 435         object *a;
 436         int ilow, ihigh;
 437         object *v;
 438 {
 439         if (!is_listobject(a)) {
 440                 err_badcall();
 441                 return -1;
 442         }
 443         return list_ass_slice((listobject *)a, ilow, ihigh, v);
 444 }
 445
 446 static int
 447 list_ass_item(a, i, v)
 448         listobject *a;
 449         int i;
 450         object *v;
 451 {
 452         if (i < 0 || i >= a->ob_size) {
 453                 err_setstr(IndexError, "list assignment index out of range");
 454                 return -1;
 455         }
 456         if (v == NULL)
 457                 return list_ass_slice(a, i, i+1, v);
 458         INCREF(v);
 459         DECREF(a->ob_item[i]);
 460         a->ob_item[i] = v;
 461         return 0;
 462 }
 463
 464 static object *
 465 ins(self, where, v)
 466         listobject *self;
 467         int where;
 468         object *v;
 469 {
 470         if (ins1(self, where, v) != 0)
 471                 return NULL;
 472         INCREF(None);
 473         return None;
 474 }
 475
 476 static object *
 477 listinsert(self, args)
 478         listobject *self;
 479         object *args;
 480 {
 481         int i;
 482         object *v;
 483         if (!getargs(args, "(iO)", &i, &v))
 484                 return NULL;
 485         return ins(self, i, v);
 486 }
 487
 488 static object *
 489 listappend(self, args)
 490         listobject *self;
 491         object *args;
 492 {
 493         object *v;
 494         if (!getargs(args, "O", &v))
 495                 return NULL;
 496         return ins(self, (int) self->ob_size, v);
 497 }
 498
 499 static object *comparefunc;
 500
 501 static int
 502 cmp(v, w)
 503 #ifdef __STDC__
 504         const void *v, *w;
 505 #else
 506         char *v, *w;
 507 #endif
 508 {
 509         object *t, *res;
 510         long i;
 511
 512         if (err_occurred())
 513                 return 0;
 514
 515         if (comparefunc == NULL)
 516                 return cmpobject(* (object **) v, * (object **) w);
 517
 518         /* Call the user-supplied comparison function */
 519         t = mkvalue("OO", * (object **) v, * (object **) w);
 520         if (t == NULL)
 521                 return 0;
 522         res = call_object(comparefunc, t);
 523         DECREF(t);
 524         if (res == NULL)
 525                 return 0;
 526         if (!is_intobject(res)) {
 527                 err_setstr(TypeError, "comparison function should return int");
 528                 i = 0;
 529         }
 530         else {
 531                 i = getintvalue(res);
 532                 if (i < 0)
 533                         i = -1;
 534                 else if (i > 0)
 535                         i = 1;
 536         }
 537         DECREF(res);
 538         return (int) i;
 539 }
 540
 541 static object *
 542 listsort(self, args)
 543         listobject *self;
 544         object *args;
 545 {
 546         object *save_comparefunc;
 547         if (self->ob_size <= 1) {
 548                 INCREF(None);
 549                 return None;
 550         }
 551         save_comparefunc = comparefunc;
 552         comparefunc = args;
 553         if (comparefunc != NULL) {
 554                 /* Test the comparison function for obvious errors */
 555                 (void) cmp(&self->ob_item[0], &self->ob_item[1]);
 556                 if (err_occurred()) {
 557                         comparefunc = save_comparefunc;
 558                         return NULL;
 559                 }
 560         }
 561         qsort((char *)self->ob_item,
 562                                 (int) self->ob_size, sizeof(object *), cmp);
 563         comparefunc = save_comparefunc;
 564         if (err_occurred())
 565                 return NULL;
 566         INCREF(None);
 567         return None;
 568 }
 569
 570 static object *
 571 listreverse(self, args)
 572         listobject *self;
 573         object *args;
 574 {
 575         register object **p, **q;
 576         register object *tmp;
 577
 578         if (args != NULL) {
 579                 err_badarg();
 580                 return NULL;
 581         }
 582
 583         if (self->ob_size > 1) {
 584                 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
 585                                                 p < q; p++, q--) {
 586                         tmp = *p;
 587                         *p = *q;
 588                         *q = tmp;
 589                 }
 590         }
 591
 592         INCREF(None);
 593         return None;
 594 }
 595
 596 int
 597 sortlist(v)
 598         object *v;
 599 {
 600         if (v == NULL || !is_listobject(v)) {
 601                 err_badcall();
 602                 return -1;
 603         }
 604         v = listsort((listobject *)v, (object *)NULL);
 605         if (v == NULL)
 606                 return -1;
 607         DECREF(v);
 608         return 0;
 609 }
 610
 611 static object *
 612 listindex(self, args)
 613         listobject *self;
 614         object *args;
 615 {
 616         int i;
 617
 618         if (args == NULL) {
 619                 err_badarg();
 620                 return NULL;
 621         }
 622         for (i = 0; i < self->ob_size; i++) {
 623                 if (cmpobject(self->ob_item[i], args) == 0)
 624                         return newintobject((long)i);
 625         }
 626         err_setstr(ValueError, "list.index(x): x not in list");
 627         return NULL;
 628 }
 629
 630 static object *
 631 listcount(self, args)
 632         listobject *self;
 633         object *args;
 634 {
 635         int count = 0;
 636         int i;
 637
 638         if (args == NULL) {
 639                 err_badarg();
 640                 return NULL;
 641         }
 642         for (i = 0; i < self->ob_size; i++) {
 643                 if (cmpobject(self->ob_item[i], args) == 0)
 644                         count++;
 645         }
 646         return newintobject((long)count);
 647 }
 648
 649 static object *
 650 listremove(self, args)
 651         listobject *self;
 652         object *args;
 653 {
 654         int i;
 655
 656         if (args == NULL) {
 657                 err_badarg();
 658                 return NULL;
 659         }
 660         for (i = 0; i < self->ob_size; i++) {
 661                 if (cmpobject(self->ob_item[i], args) == 0) {
 662                         if (list_ass_slice(self, i, i+1, (object *)NULL) != 0)
 663                                 return NULL;
 664                         INCREF(None);
 665                         return None;
 666                 }
 667
 668         }
 669         err_setstr(ValueError, "list.remove(x): x not in list");
 670         return NULL;
 671 }
 672
 673 static struct methodlist list_methods[] = {
 674         {"append",      (method)listappend},
 675         {"count",       (method)listcount},
 676         {"index",       (method)listindex},
 677         {"insert",      (method)listinsert},
 678         {"sort",        (method)listsort},
 679         {"remove",      (method)listremove},
 680         {"reverse",     (method)listreverse},
 681         {NULL,          NULL}           /* sentinel */
 682 };
 683
 684 static object *
 685 list_getattr(f, name)
 686         listobject *f;
 687         char *name;
 688 {
 689         return findmethod(list_methods, (object *)f, name);
 690 }
 691
 692 static sequence_methods list_as_sequence = {
 693         (inquiry)list_length, /*sq_length*/
 694         (binaryfunc)list_concat, /*sq_concat*/
 695         (intargfunc)list_repeat, /*sq_repeat*/
 696         (intargfunc)list_item, /*sq_item*/
 697         (intintargfunc)list_slice, /*sq_slice*/
 698         (intobjargproc)list_ass_item, /*sq_ass_item*/
 699         (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
 700 };
 701
 702 typeobject Listtype = {
 703         OB_HEAD_INIT(&Typetype)
 704         0,
 705         "list",
 706         sizeof(listobject),
 707         0,
 708         (destructor)list_dealloc, /*tp_dealloc*/
 709         (printfunc)list_print, /*tp_print*/
 710         (getattrfunc)list_getattr, /*tp_getattr*/
 711         0,              /*tp_setattr*/
 712         (cmpfunc)list_compare, /*tp_compare*/
 713         (reprfunc)list_repr, /*tp_repr*/
 714         0,              /*tp_as_number*/
 715         &list_as_sequence,      /*tp_as_sequence*/
 716         0,              /*tp_as_mapping*/
 717 };