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 or Corporation for National Research Initiatives or
  13 CNRI not be used in advertising or publicity pertaining to
  14 distribution of the software without specific, written prior
  15 permission.
  16
  17 While CWI is the initial source for this software, a modified version
  18 is made available by the Corporation for National Research Initiatives
  19 (CNRI) at the Internet address ftp://ftp.python.org.
  20
  21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28 PERFORMANCE OF THIS SOFTWARE.
  29
  30 ******************************************************************/
  31
  32 /* Tuple object implementation */
  33
  34 #include "Python.h"
  35
  36 #ifndef MAXSAVESIZE
  37 #define MAXSAVESIZE     20
  38 #endif
  39
  40 #if MAXSAVESIZE > 0
  41 /* Entries 1 upto MAXSAVESIZE are free lists, entry 0 is the empty
  42    tuple () of which at most one instance will be allocated.
  43 */
  44 static PyTupleObject *free_tuples[MAXSAVESIZE];
  45 #endif
  46 #ifdef COUNT_ALLOCS
  47 int fast_tuple_allocs;
  48 int tuple_zero_allocs;
  49 #endif
  50
  51 PyObject *
  52 PyTuple_New(size)
  53         register int size;
  54 {
  55         register int i;
  56         register PyTupleObject *op;
  57         if (size < 0) {
  58                 PyErr_BadInternalCall();
  59                 return NULL;
  60         }
  61 #if MAXSAVESIZE > 0
  62         if (size == 0 && free_tuples[0]) {
  63                 op = free_tuples[0];
  64                 Py_INCREF(op);
  65 #ifdef COUNT_ALLOCS
  66                 tuple_zero_allocs++;
  67 #endif
  68                 return (PyObject *) op;
  69         }
  70         if (0 < size && size < MAXSAVESIZE &&
  71             (op = free_tuples[size]) != NULL)
  72         {
  73                 free_tuples[size] = (PyTupleObject *) op->ob_item[0];
  74 #ifdef COUNT_ALLOCS
  75                 fast_tuple_allocs++;
  76 #endif
  77 #ifdef Py_TRACE_REFS
  78                 op->ob_type = &PyTuple_Type;
  79                 op->ob_size = size;
  80 #endif
  81         }
  82         else
  83 #endif
  84         {
  85                 op = (PyTupleObject *) malloc(
  86                         sizeof(PyTupleObject) + (size-1) * sizeof(PyObject *));
  87                 if (op == NULL)
  88                         return PyErr_NoMemory();
  89
  90                 op->ob_type = &PyTuple_Type;
  91                 op->ob_size = size;
  92         }
  93         for (i = 0; i < size; i++)
  94                 op->ob_item[i] = NULL;
  95         _Py_NewReference(op);
  96 #if MAXSAVESIZE > 0
  97         if (size == 0) {
  98                 free_tuples[0] = op;
  99                 Py_INCREF(op);  /* extra INCREF so that this is never freed */
 100         }
 101 #endif
 102         return (PyObject *) op;
 103 }
 104
 105 int
 106 PyTuple_Size(op)
 107         register PyObject *op;
 108 {
 109         if (!PyTuple_Check(op)) {
 110                 PyErr_BadInternalCall();
 111                 return -1;
 112         }
 113         else
 114                 return ((PyTupleObject *)op)->ob_size;
 115 }
 116
 117 PyObject *
 118 PyTuple_GetItem(op, i)
 119         register PyObject *op;
 120         register int i;
 121 {
 122         if (!PyTuple_Check(op)) {
 123                 PyErr_BadInternalCall();
 124                 return NULL;
 125         }
 126         if (i < 0 || i >= ((PyTupleObject *)op) -> ob_size) {
 127                 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
 128                 return NULL;
 129         }
 130         return ((PyTupleObject *)op) -> ob_item[i];
 131 }
 132
 133 int
 134 PyTuple_SetItem(op, i, newitem)
 135         register PyObject *op;
 136         register int i;
 137         PyObject *newitem;
 138 {
 139         register PyObject *olditem;
 140         register PyObject **p;
 141         if (!PyTuple_Check(op) || op->ob_refcnt != 1) {
 142                 Py_XDECREF(newitem);
 143                 PyErr_BadInternalCall();
 144                 return -1;
 145         }
 146         if (i < 0 || i >= ((PyTupleObject *)op) -> ob_size) {
 147                 Py_XDECREF(newitem);
 148                 PyErr_SetString(PyExc_IndexError,
 149                                 "tuple assignment index out of range");
 150                 return -1;
 151         }
 152         p = ((PyTupleObject *)op) -> ob_item + i;
 153         olditem = *p;
 154         *p = newitem;
 155         Py_XDECREF(olditem);
 156         return 0;
 157 }
 158
 159 /* Methods */
 160
 161 static void
 162 tupledealloc(op)
 163         register PyTupleObject *op;
 164 {
 165         register int i;
 166
 167         if (op->ob_size > 0) {
 168                 i = op->ob_size;
 169                 while (--i >= 0)
 170                         Py_XDECREF(op->ob_item[i]);
 171 #if MAXSAVESIZE > 0
 172                 if (op->ob_size < MAXSAVESIZE) {
 173                         op->ob_item[0] = (PyObject *) free_tuples[op->ob_size];
 174                         free_tuples[op->ob_size] = op;
 175                         return;
 176                 }
 177 #endif
 178         }
 179         free((ANY *)op);
 180 }
 181
 182 static int
 183 tupleprint(op, fp, flags)
 184         PyTupleObject *op;
 185         FILE *fp;
 186         int flags;
 187 {
 188         int i;
 189         fprintf(fp, "(");
 190         for (i = 0; i < op->ob_size; i++) {
 191                 if (i > 0)
 192                         fprintf(fp, ", ");
 193                 if (PyObject_Print(op->ob_item[i], fp, 0) != 0)
 194                         return -1;
 195         }
 196         if (op->ob_size == 1)
 197                 fprintf(fp, ",");
 198         fprintf(fp, ")");
 199         return 0;
 200 }
 201
 202 static PyObject *
 203 tuplerepr(v)
 204         PyTupleObject *v;
 205 {
 206         PyObject *s, *comma;
 207         int i;
 208         s = PyString_FromString("(");
 209         comma = PyString_FromString(", ");
 210         for (i = 0; i < v->ob_size && s != NULL; i++) {
 211                 if (i > 0)
 212                         PyString_Concat(&s, comma);
 213                 PyString_ConcatAndDel(&s, PyObject_Repr(v->ob_item[i]));
 214         }
 215         Py_DECREF(comma);
 216         if (v->ob_size == 1)
 217                 PyString_ConcatAndDel(&s, PyString_FromString(","));
 218         PyString_ConcatAndDel(&s, PyString_FromString(")"));
 219         return s;
 220 }
 221
 222 static int
 223 tuplecompare(v, w)
 224         register PyTupleObject *v, *w;
 225 {
 226         register int len =
 227                 (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
 228         register int i;
 229         for (i = 0; i < len; i++) {
 230                 int cmp = PyObject_Compare(v->ob_item[i], w->ob_item[i]);
 231                 if (cmp != 0)
 232                         return cmp;
 233         }
 234         return v->ob_size - w->ob_size;
 235 }
 236
 237 static long
 238 tuplehash(v)
 239         PyTupleObject *v;
 240 {
 241         register long x, y;
 242         register int len = v->ob_size;
 243         register PyObject **p;
 244         x = 0x345678L;
 245         p = v->ob_item;
 246         while (--len >= 0) {
 247                 y = PyObject_Hash(*p++);
 248                 if (y == -1)
 249                         return -1;
 250                 x = (1000003*x) ^ y;
 251         }
 252         x ^= v->ob_size;
 253         if (x == -1)
 254                 x = -2;
 255         return x;
 256 }
 257
 258 static int
 259 tuplelength(a)
 260         PyTupleObject *a;
 261 {
 262         return a->ob_size;
 263 }
 264
 265 static PyObject *
 266 tupleitem(a, i)
 267         register PyTupleObject *a;
 268         register int i;
 269 {
 270         if (i < 0 || i >= a->ob_size) {
 271                 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
 272                 return NULL;
 273         }
 274         Py_INCREF(a->ob_item[i]);
 275         return a->ob_item[i];
 276 }
 277
 278 static PyObject *
 279 tupleslice(a, ilow, ihigh)
 280         register PyTupleObject *a;
 281         register int ilow, ihigh;
 282 {
 283         register PyTupleObject *np;
 284         register int i;
 285         if (ilow < 0)
 286                 ilow = 0;
 287         if (ihigh > a->ob_size)
 288                 ihigh = a->ob_size;
 289         if (ihigh < ilow)
 290                 ihigh = ilow;
 291         if (ilow == 0 && ihigh == a->ob_size) {
 292                 /* XXX can only do this if tuples are immutable! */
 293                 Py_INCREF(a);
 294                 return (PyObject *)a;
 295         }
 296         np = (PyTupleObject *)PyTuple_New(ihigh - ilow);
 297         if (np == NULL)
 298                 return NULL;
 299         for (i = ilow; i < ihigh; i++) {
 300                 PyObject *v = a->ob_item[i];
 301                 Py_INCREF(v);
 302                 np->ob_item[i - ilow] = v;
 303         }
 304         return (PyObject *)np;
 305 }
 306
 307 PyObject *
 308 PyTuple_GetSlice(op, i, j)
 309         PyObject *op;
 310         int i, j;
 311 {
 312         if (op == NULL || !PyTuple_Check(op)) {
 313                 PyErr_BadInternalCall();
 314                 return NULL;
 315         }
 316         return tupleslice((PyTupleObject *)op, i, j);
 317 }
 318
 319 static PyObject *
 320 tupleconcat(a, bb)
 321         register PyTupleObject *a;
 322         register PyObject *bb;
 323 {
 324         register int size;
 325         register int i;
 326         PyTupleObject *np;
 327         if (!PyTuple_Check(bb)) {
 328                 PyErr_BadArgument();
 329                 return NULL;
 330         }
 331 #define b ((PyTupleObject *)bb)
 332         size = a->ob_size + b->ob_size;
 333         np = (PyTupleObject *) PyTuple_New(size);
 334         if (np == NULL) {
 335                 return NULL;
 336         }
 337         for (i = 0; i < a->ob_size; i++) {
 338                 PyObject *v = a->ob_item[i];
 339                 Py_INCREF(v);
 340                 np->ob_item[i] = v;
 341         }
 342         for (i = 0; i < b->ob_size; i++) {
 343                 PyObject *v = b->ob_item[i];
 344                 Py_INCREF(v);
 345                 np->ob_item[i + a->ob_size] = v;
 346         }
 347         return (PyObject *)np;
 348 #undef b
 349 }
 350
 351 static PyObject *
 352 tuplerepeat(a, n)
 353         PyTupleObject *a;
 354         int n;
 355 {
 356         int i, j;
 357         int size;
 358         PyTupleObject *np;
 359         PyObject **p;
 360         if (n < 0)
 361                 n = 0;
 362         if (a->ob_size*n == a->ob_size) {
 363                 /* Since tuples are immutable, we can return a shared
 364                    copy in this case */
 365                 Py_INCREF(a);
 366                 return (PyObject *)a;
 367         }
 368         size = a->ob_size * n;
 369         np = (PyTupleObject *) PyTuple_New(size);
 370         if (np == NULL)
 371                 return NULL;
 372         p = np->ob_item;
 373         for (i = 0; i < n; i++) {
 374                 for (j = 0; j < a->ob_size; j++) {
 375                         *p = a->ob_item[j];
 376                         Py_INCREF(*p);
 377                         p++;
 378                 }
 379         }
 380         return (PyObject *) np;
 381 }
 382
 383 static PySequenceMethods tuple_as_sequence = {
 384         (inquiry)tuplelength, /*sq_length*/
 385         (binaryfunc)tupleconcat, /*sq_concat*/
 386         (intargfunc)tuplerepeat, /*sq_repeat*/
 387         (intargfunc)tupleitem, /*sq_item*/
 388         (intintargfunc)tupleslice, /*sq_slice*/
 389         0,              /*sq_ass_item*/
 390         0,              /*sq_ass_slice*/
 391 };
 392
 393 PyTypeObject PyTuple_Type = {
 394         PyObject_HEAD_INIT(&PyType_Type)
 395         0,
 396         "tuple",
 397         sizeof(PyTupleObject) - sizeof(PyObject *),
 398         sizeof(PyObject *),
 399         (destructor)tupledealloc, /*tp_dealloc*/
 400         (printfunc)tupleprint, /*tp_print*/
 401         0,              /*tp_getattr*/
 402         0,              /*tp_setattr*/
 403         (cmpfunc)tuplecompare, /*tp_compare*/
 404         (reprfunc)tuplerepr, /*tp_repr*/
 405         0,              /*tp_as_number*/
 406         &tuple_as_sequence,     /*tp_as_sequence*/
 407         0,              /*tp_as_mapping*/
 408         (hashfunc)tuplehash, /*tp_hash*/
 409 };
 410
 411 /* The following function breaks the notion that tuples are immutable:
 412    it changes the size of a tuple.  We get away with this only if there
 413    is only one module referencing the object.  You can also think of it
 414    as creating a new tuple object and destroying the old one, only
 415    more efficiently.  In any case, don't use this if the tuple may
 416    already be known to some other part of the code...
 417    If last_is_sticky is set, the tuple will grow or shrink at the
 418    front, otherwise it will grow or shrink at the end. */
 419
 420 int
 421 _PyTuple_Resize(pv, newsize, last_is_sticky)
 422         PyObject **pv;
 423         int newsize;
 424         int last_is_sticky;
 425 {
 426         register PyTupleObject *v;
 427         register PyTupleObject *sv;
 428         int i;
 429         int sizediff;
 430
 431         v = (PyTupleObject *) *pv;
 432         if (v == NULL || !PyTuple_Check(v) || v->ob_refcnt != 1) {
 433                 *pv = 0;
 434                 Py_DECREF(v);
 435                 PyErr_BadInternalCall();
 436                 return -1;
 437         }
 438         sizediff = newsize - v->ob_size;
 439         if (sizediff == 0)
 440                 return 0;
 441         /* XXX UNREF/NEWREF interface should be more symmetrical */
 442 #ifdef Py_REF_DEBUG
 443         --_Py_RefTotal;
 444 #endif
 445         _Py_ForgetReference(v);
 446         if (last_is_sticky && sizediff < 0) {
 447                 /* shrinking:
 448                    move entries to the front and zero moved entries */
 449                 for (i = 0; i < newsize; i++) {
 450                         Py_XDECREF(v->ob_item[i]);
 451                         v->ob_item[i] = v->ob_item[i - sizediff];
 452                         v->ob_item[i - sizediff] = NULL;
 453                 }
 454         }
 455         for (i = newsize; i < v->ob_size; i++) {
 456                 Py_XDECREF(v->ob_item[i]);
 457                 v->ob_item[i] = NULL;
 458         }
 459         sv = (PyTupleObject *)
 460                 realloc((char *)v,
 461                         sizeof(PyTupleObject) + newsize * sizeof(PyObject *));
 462         *pv = (PyObject *) sv;
 463         if (sv == NULL) {
 464                 PyMem_DEL(v);
 465                 PyErr_NoMemory();
 466                 return -1;
 467         }
 468         _Py_NewReference(sv);
 469         for (i = sv->ob_size; i < newsize; i++)
 470                 sv->ob_item[i] = NULL;
 471         if (last_is_sticky && sizediff > 0) {
 472                 /* growing: move entries to the end and zero moved entries */
 473                 for (i = newsize - 1; i >= sizediff; i--) {
 474                         sv->ob_item[i] = sv->ob_item[i - sizediff];
 475                         sv->ob_item[i - sizediff] = NULL;
 476                 }
 477         }
 478         sv->ob_size = newsize;
 479         return 0;
 480 }
 481
 482 void
 483 PyTuple_Fini()
 484 {
 485 #if MAXSAVESIZE > 0
 486         int i;
 487
 488         Py_XDECREF(free_tuples[0]);
 489         free_tuples[0] = NULL;
 490
 491         for (i = 1; i < MAXSAVESIZE; i++) {
 492                 PyTupleObject *p, *q;
 493                 p = free_tuples[i];
 494                 free_tuples[i] = NULL;
 495                 while (p) {
 496                         q = p;
 497                         p = (PyTupleObject *)(p->ob_item[0]);
 498                         PyMem_DEL(q);
 499                 }
 500         }
 501 #endif
 502 }