Objects/tupleobject.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 /* Tuple object implementation */
  26
  27 #include "allobjects.h"
  28
  29 #ifndef MAXSAVESIZE
  30 #define MAXSAVESIZE     20
  31 #endif
  32
  33 #if MAXSAVESIZE > 0
  34 /* Entries 1 upto MAXSAVESIZE are free lists, entry 0 is the empty
  35    tuple () of which at most one instance will be allocated.
  36 */
  37 static tupleobject *free_tuples[MAXSAVESIZE];
  38 #endif
  39 #ifdef COUNT_ALLOCS
  40 int fast_tuple_allocs;
  41 int tuple_zero_allocs;
  42 #endif
  43
  44 object *
  45 newtupleobject(size)
  46         register int size;
  47 {
  48         register int i;
  49         register tupleobject *op;
  50         if (size < 0) {
  51                 err_badcall();
  52                 return NULL;
  53         }
  54 #if MAXSAVESIZE > 0
  55         if (size == 0 && free_tuples[0]) {
  56                 op = free_tuples[0];
  57                 INCREF(op);
  58 #ifdef COUNT_ALLOCS
  59                 tuple_zero_allocs++;
  60 #endif
  61                 return (object *) op;
  62         }
  63         if (0 < size && size < MAXSAVESIZE && (op = free_tuples[size]) != NULL) {
  64                 free_tuples[size] = (tupleobject *) op->ob_item[0];
  65 #ifdef COUNT_ALLOCS
  66                 fast_tuple_allocs++;
  67 #endif
  68         } else
  69 #endif
  70         {
  71                 op = (tupleobject *)
  72                         malloc(sizeof(tupleobject) + size * sizeof(object *));
  73                 if (op == NULL)
  74                         return err_nomem();
  75         }
  76         op->ob_type = &Tupletype;
  77         op->ob_size = size;
  78         for (i = 0; i < size; i++)
  79                 op->ob_item[i] = NULL;
  80         NEWREF(op);
  81 #if MAXSAVESIZE > 0
  82         if (size == 0) {
  83                 free_tuples[0] = op;
  84                 INCREF(op);     /* extra INCREF so that this is never freed */
  85         }
  86 #endif
  87         return (object *) op;
  88 }
  89
  90 int
  91 gettuplesize(op)
  92         register object *op;
  93 {
  94         if (!is_tupleobject(op)) {
  95                 err_badcall();
  96                 return -1;
  97         }
  98         else
  99                 return ((tupleobject *)op)->ob_size;
 100 }
 101
 102 object *
 103 gettupleitem(op, i)
 104         register object *op;
 105         register int i;
 106 {
 107         if (!is_tupleobject(op)) {
 108                 err_badcall();
 109                 return NULL;
 110         }
 111         if (i < 0 || i >= ((tupleobject *)op) -> ob_size) {
 112                 err_setstr(IndexError, "tuple index out of range");
 113                 return NULL;
 114         }
 115         return ((tupleobject *)op) -> ob_item[i];
 116 }
 117
 118 int
 119 settupleitem(op, i, newitem)
 120         register object *op;
 121         register int i;
 122         object *newitem;
 123 {
 124         register object *olditem;
 125         register object **p;
 126         if (!is_tupleobject(op)) {
 127                 XDECREF(newitem);
 128                 err_badcall();
 129                 return -1;
 130         }
 131         if (i < 0 || i >= ((tupleobject *)op) -> ob_size) {
 132                 XDECREF(newitem);
 133                 err_setstr(IndexError, "tuple assignment index out of range");
 134                 return -1;
 135         }
 136         p = ((tupleobject *)op) -> ob_item + i;
 137         olditem = *p;
 138         *p = newitem;
 139         XDECREF(olditem);
 140         return 0;
 141 }
 142
 143 /* Methods */
 144
 145 static void
 146 tupledealloc(op)
 147         register tupleobject *op;
 148 {
 149         register int i;
 150         for (i = 0; i < op->ob_size; i++)
 151                 XDECREF(op->ob_item[i]);
 152 #if MAXSAVESIZE > 0
 153         if (0 < op->ob_size && op->ob_size < MAXSAVESIZE) {
 154                 op->ob_item[0] = (object *) free_tuples[op->ob_size];
 155                 free_tuples[op->ob_size] = op;
 156         } else
 157 #endif
 158                 free((ANY *)op);
 159 }
 160
 161 static int
 162 tupleprint(op, fp, flags)
 163         tupleobject *op;
 164         FILE *fp;
 165         int flags;
 166 {
 167         int i;
 168         fprintf(fp, "(");
 169         for (i = 0; i < op->ob_size; i++) {
 170                 if (i > 0)
 171                         fprintf(fp, ", ");
 172                 if (printobject(op->ob_item[i], fp, 0) != 0)
 173                         return -1;
 174         }
 175         if (op->ob_size == 1)
 176                 fprintf(fp, ",");
 177         fprintf(fp, ")");
 178         return 0;
 179 }
 180
 181 static object *
 182 tuplerepr(v)
 183         tupleobject *v;
 184 {
 185         object *s, *comma;
 186         int i;
 187         s = newstringobject("(");
 188         comma = newstringobject(", ");
 189         for (i = 0; i < v->ob_size && s != NULL; i++) {
 190                 if (i > 0)
 191                         joinstring(&s, comma);
 192                 joinstring_decref(&s, reprobject(v->ob_item[i]));
 193         }
 194         DECREF(comma);
 195         if (v->ob_size == 1)
 196                 joinstring_decref(&s, newstringobject(","));
 197         joinstring_decref(&s, newstringobject(")"));
 198         return s;
 199 }
 200
 201 static int
 202 tuplecompare(v, w)
 203         register tupleobject *v, *w;
 204 {
 205         register int len =
 206                 (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
 207         register int i;
 208         for (i = 0; i < len; i++) {
 209                 int cmp = cmpobject(v->ob_item[i], w->ob_item[i]);
 210                 if (cmp != 0)
 211                         return cmp;
 212         }
 213         return v->ob_size - w->ob_size;
 214 }
 215
 216 static long
 217 tuplehash(v)
 218         tupleobject *v;
 219 {
 220         register long x, y;
 221         register int len = v->ob_size;
 222         register object **p;
 223         x = 0x345678L;
 224         p = v->ob_item;
 225         while (--len >= 0) {
 226                 y = hashobject(*p++);
 227                 if (y == -1)
 228                         return -1;
 229                 x = (x + x + x) ^ y;
 230         }
 231         x ^= v->ob_size;
 232         if (x == -1)
 233                 x = -2;
 234         return x;
 235 }
 236
 237 static int
 238 tuplelength(a)
 239         tupleobject *a;
 240 {
 241         return a->ob_size;
 242 }
 243
 244 static object *
 245 tupleitem(a, i)
 246         register tupleobject *a;
 247         register int i;
 248 {
 249         if (i < 0 || i >= a->ob_size) {
 250                 err_setstr(IndexError, "tuple index out of range");
 251                 return NULL;
 252         }
 253         INCREF(a->ob_item[i]);
 254         return a->ob_item[i];
 255 }
 256
 257 static object *
 258 tupleslice(a, ilow, ihigh)
 259         register tupleobject *a;
 260         register int ilow, ihigh;
 261 {
 262         register tupleobject *np;
 263         register int i;
 264         if (ilow < 0)
 265                 ilow = 0;
 266         if (ihigh > a->ob_size)
 267                 ihigh = a->ob_size;
 268         if (ihigh < ilow)
 269                 ihigh = ilow;
 270         if (ilow == 0 && ihigh == a->ob_size) {
 271                 /* XXX can only do this if tuples are immutable! */
 272                 INCREF(a);
 273                 return (object *)a;
 274         }
 275         np = (tupleobject *)newtupleobject(ihigh - ilow);
 276         if (np == NULL)
 277                 return NULL;
 278         for (i = ilow; i < ihigh; i++) {
 279                 object *v = a->ob_item[i];
 280                 INCREF(v);
 281                 np->ob_item[i - ilow] = v;
 282         }
 283         return (object *)np;
 284 }
 285
 286 object *
 287 gettupleslice(op, i, j)
 288         object *op;
 289         int i, j;
 290 {
 291         if (op == NULL || !is_tupleobject(op)) {
 292                 err_badcall();
 293                 return NULL;
 294         }
 295         return tupleslice((tupleobject *)op, i, j);
 296 }
 297
 298 static object *
 299 tupleconcat(a, bb)
 300         register tupleobject *a;
 301         register object *bb;
 302 {
 303         register int size;
 304         register int i;
 305         tupleobject *np;
 306         if (!is_tupleobject(bb)) {
 307                 err_badarg();
 308                 return NULL;
 309         }
 310 #define b ((tupleobject *)bb)
 311         size = a->ob_size + b->ob_size;
 312         np = (tupleobject *) newtupleobject(size);
 313         if (np == NULL) {
 314                 return NULL;
 315         }
 316         for (i = 0; i < a->ob_size; i++) {
 317                 object *v = a->ob_item[i];
 318                 INCREF(v);
 319                 np->ob_item[i] = v;
 320         }
 321         for (i = 0; i < b->ob_size; i++) {
 322                 object *v = b->ob_item[i];
 323                 INCREF(v);
 324                 np->ob_item[i + a->ob_size] = v;
 325         }
 326         return (object *)np;
 327 #undef b
 328 }
 329
 330 static object *
 331 tuplerepeat(a, n)
 332         tupleobject *a;
 333         int n;
 334 {
 335         int i, j;
 336         int size;
 337         tupleobject *np;
 338         object **p;
 339         if (n < 0)
 340                 n = 0;
 341         if (a->ob_size*n == a->ob_size) {
 342                 /* Since tuples are immutable, we can return a shared
 343                    copy in this case */
 344                 INCREF(a);
 345                 return (object *)a;
 346         }
 347         size = a->ob_size * n;
 348         np = (tupleobject *) newtupleobject(size);
 349         if (np == NULL)
 350                 return NULL;
 351         p = np->ob_item;
 352         for (i = 0; i < n; i++) {
 353                 for (j = 0; j < a->ob_size; j++) {
 354                         *p = a->ob_item[j];
 355                         INCREF(*p);
 356                         p++;
 357                 }
 358         }
 359         return (object *) np;
 360 }
 361
 362 static sequence_methods tuple_as_sequence = {
 363         (inquiry)tuplelength, /*sq_length*/
 364         (binaryfunc)tupleconcat, /*sq_concat*/
 365         (intargfunc)tuplerepeat, /*sq_repeat*/
 366         (intargfunc)tupleitem, /*sq_item*/
 367         (intintargfunc)tupleslice, /*sq_slice*/
 368         0,              /*sq_ass_item*/
 369         0,              /*sq_ass_slice*/
 370 };
 371
 372 typeobject Tupletype = {
 373         OB_HEAD_INIT(&Typetype)
 374         0,
 375         "tuple",
 376         sizeof(tupleobject) - sizeof(object *),
 377         sizeof(object *),
 378         (destructor)tupledealloc, /*tp_dealloc*/
 379         (printfunc)tupleprint, /*tp_print*/
 380         0,              /*tp_getattr*/
 381         0,              /*tp_setattr*/
 382         (cmpfunc)tuplecompare, /*tp_compare*/
 383         (reprfunc)tuplerepr, /*tp_repr*/
 384         0,              /*tp_as_number*/
 385         &tuple_as_sequence,     /*tp_as_sequence*/
 386         0,              /*tp_as_mapping*/
 387         (hashfunc)tuplehash, /*tp_hash*/
 388 };
 389
 390 /* The following function breaks the notion that tuples are immutable:
 391    it changes the size of a tuple.  We get away with this only if there
 392    is only one module referencing the object.  You can also think of it
 393    as creating a new tuple object and destroying the old one, only
 394    more efficiently.  In any case, don't use this if the tuple may
 395    already be known to some other part of the code...
 396    If last_is_sticky is set, the tuple will grow or shrink at the
 397    front, otherwise it will grow or shrink at the end. */
 398
 399 int
 400 resizetuple(pv, newsize, last_is_sticky)
 401         object **pv;
 402         int newsize;
 403         int last_is_sticky;
 404 {
 405         register tupleobject *v;
 406         register tupleobject *sv;
 407         int i;
 408         int sizediff;
 409
 410         v = (tupleobject *) *pv;
 411         sizediff = newsize - v->ob_size;
 412         if (!is_tupleobject(v) || v->ob_refcnt != 1) {
 413                 *pv = 0;
 414                 DECREF(v);
 415                 err_badcall();
 416                 return -1;
 417         }
 418         if (sizediff == 0)
 419                 return 0;
 420         /* XXX UNREF/NEWREF interface should be more symmetrical */
 421 #ifdef REF_DEBUG
 422         --ref_total;
 423 #endif
 424         UNREF(v);
 425         if (last_is_sticky && sizediff < 0) {
 426                 /* shrinking: move entries to the front and zero moved entries */
 427                 for (i = 0; i < newsize; i++) {
 428                         XDECREF(v->ob_item[i]);
 429                         v->ob_item[i] = v->ob_item[i - sizediff];
 430                         v->ob_item[i - sizediff] = NULL;
 431                 }
 432         }
 433         for (i = newsize; i < v->ob_size; i++) {
 434                 XDECREF(v->ob_item[i]);
 435                 v->ob_item[i] = NULL;
 436         }
 437         sv = (tupleobject *)
 438                 realloc((char *)v,
 439                         sizeof(tupleobject) + newsize * sizeof(object *));
 440         *pv = (object *) sv;
 441         if (sv == NULL) {
 442                 DEL(v);
 443                 err_nomem();
 444                 return -1;
 445         }
 446         NEWREF(sv);
 447         for (i = sv->ob_size; i < newsize; i++)
 448                 sv->ob_item[i] = NULL;
 449         if (last_is_sticky && sizediff > 0) {
 450                 /* growing: move entries to the end and zero moved entries */
 451                 for (i = newsize - 1; i >= sizediff; i--) {
 452                         sv->ob_item[i] = sv->ob_item[i - sizediff];
 453                         sv->ob_item[i - sizediff] = NULL;
 454                 }
 455         }
 456         sv->ob_size = newsize;
 457         return 0;
 458 }