]>
Commit | Line | Data |
---|---|---|
4710c53d | 1 | \r |
2 | /* Tuple object implementation */\r | |
3 | \r | |
4 | #include "Python.h"\r | |
5 | \r | |
6 | /* Speed optimization to avoid frequent malloc/free of small tuples */\r | |
7 | #ifndef PyTuple_MAXSAVESIZE\r | |
8 | #define PyTuple_MAXSAVESIZE 20 /* Largest tuple to save on free list */\r | |
9 | #endif\r | |
10 | #ifndef PyTuple_MAXFREELIST\r | |
11 | #define PyTuple_MAXFREELIST 2000 /* Maximum number of tuples of each size to save */\r | |
12 | #endif\r | |
13 | \r | |
14 | #if PyTuple_MAXSAVESIZE > 0\r | |
15 | /* Entries 1 up to PyTuple_MAXSAVESIZE are free lists, entry 0 is the empty\r | |
16 | tuple () of which at most one instance will be allocated.\r | |
17 | */\r | |
18 | static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];\r | |
19 | static int numfree[PyTuple_MAXSAVESIZE];\r | |
20 | #endif\r | |
21 | #ifdef COUNT_ALLOCS\r | |
22 | Py_ssize_t fast_tuple_allocs;\r | |
23 | Py_ssize_t tuple_zero_allocs;\r | |
24 | #endif\r | |
25 | \r | |
26 | /* Debug statistic to count GC tracking of tuples.\r | |
27 | Please note that tuples are only untracked when considered by the GC, and\r | |
28 | many of them will be dead before. Therefore, a tracking rate close to 100%\r | |
29 | does not necessarily prove that the heuristic is inefficient.\r | |
30 | */\r | |
31 | #ifdef SHOW_TRACK_COUNT\r | |
32 | static Py_ssize_t count_untracked = 0;\r | |
33 | static Py_ssize_t count_tracked = 0;\r | |
34 | \r | |
35 | static void\r | |
36 | show_track(void)\r | |
37 | {\r | |
38 | fprintf(stderr, "Tuples created: %" PY_FORMAT_SIZE_T "d\n",\r | |
39 | count_tracked + count_untracked);\r | |
40 | fprintf(stderr, "Tuples tracked by the GC: %" PY_FORMAT_SIZE_T\r | |
41 | "d\n", count_tracked);\r | |
42 | fprintf(stderr, "%.2f%% tuple tracking rate\n\n",\r | |
43 | (100.0*count_tracked/(count_untracked+count_tracked)));\r | |
44 | }\r | |
45 | #endif\r | |
46 | \r | |
47 | \r | |
48 | PyObject *\r | |
49 | PyTuple_New(register Py_ssize_t size)\r | |
50 | {\r | |
51 | register PyTupleObject *op;\r | |
52 | Py_ssize_t i;\r | |
53 | if (size < 0) {\r | |
54 | PyErr_BadInternalCall();\r | |
55 | return NULL;\r | |
56 | }\r | |
57 | #if PyTuple_MAXSAVESIZE > 0\r | |
58 | if (size == 0 && free_list[0]) {\r | |
59 | op = free_list[0];\r | |
60 | Py_INCREF(op);\r | |
61 | #ifdef COUNT_ALLOCS\r | |
62 | tuple_zero_allocs++;\r | |
63 | #endif\r | |
64 | return (PyObject *) op;\r | |
65 | }\r | |
66 | if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {\r | |
67 | free_list[size] = (PyTupleObject *) op->ob_item[0];\r | |
68 | numfree[size]--;\r | |
69 | #ifdef COUNT_ALLOCS\r | |
70 | fast_tuple_allocs++;\r | |
71 | #endif\r | |
72 | /* Inline PyObject_InitVar */\r | |
73 | #ifdef Py_TRACE_REFS\r | |
74 | Py_SIZE(op) = size;\r | |
75 | Py_TYPE(op) = &PyTuple_Type;\r | |
76 | #endif\r | |
77 | _Py_NewReference((PyObject *)op);\r | |
78 | }\r | |
79 | else\r | |
80 | #endif\r | |
81 | {\r | |
82 | Py_ssize_t nbytes = size * sizeof(PyObject *);\r | |
83 | /* Check for overflow */\r | |
84 | if (nbytes / sizeof(PyObject *) != (size_t)size ||\r | |
85 | (nbytes > PY_SSIZE_T_MAX - sizeof(PyTupleObject) - sizeof(PyObject *)))\r | |
86 | {\r | |
87 | return PyErr_NoMemory();\r | |
88 | }\r | |
89 | \r | |
90 | op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);\r | |
91 | if (op == NULL)\r | |
92 | return NULL;\r | |
93 | }\r | |
94 | for (i=0; i < size; i++)\r | |
95 | op->ob_item[i] = NULL;\r | |
96 | #if PyTuple_MAXSAVESIZE > 0\r | |
97 | if (size == 0) {\r | |
98 | free_list[0] = op;\r | |
99 | ++numfree[0];\r | |
100 | Py_INCREF(op); /* extra INCREF so that this is never freed */\r | |
101 | }\r | |
102 | #endif\r | |
103 | #ifdef SHOW_TRACK_COUNT\r | |
104 | count_tracked++;\r | |
105 | #endif\r | |
106 | _PyObject_GC_TRACK(op);\r | |
107 | return (PyObject *) op;\r | |
108 | }\r | |
109 | \r | |
110 | Py_ssize_t\r | |
111 | PyTuple_Size(register PyObject *op)\r | |
112 | {\r | |
113 | if (!PyTuple_Check(op)) {\r | |
114 | PyErr_BadInternalCall();\r | |
115 | return -1;\r | |
116 | }\r | |
117 | else\r | |
118 | return Py_SIZE(op);\r | |
119 | }\r | |
120 | \r | |
121 | PyObject *\r | |
122 | PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)\r | |
123 | {\r | |
124 | if (!PyTuple_Check(op)) {\r | |
125 | PyErr_BadInternalCall();\r | |
126 | return NULL;\r | |
127 | }\r | |
128 | if (i < 0 || i >= Py_SIZE(op)) {\r | |
129 | PyErr_SetString(PyExc_IndexError, "tuple index out of range");\r | |
130 | return NULL;\r | |
131 | }\r | |
132 | return ((PyTupleObject *)op) -> ob_item[i];\r | |
133 | }\r | |
134 | \r | |
135 | int\r | |
136 | PyTuple_SetItem(register PyObject *op, register Py_ssize_t i, PyObject *newitem)\r | |
137 | {\r | |
138 | register PyObject *olditem;\r | |
139 | register PyObject **p;\r | |
140 | if (!PyTuple_Check(op) || op->ob_refcnt != 1) {\r | |
141 | Py_XDECREF(newitem);\r | |
142 | PyErr_BadInternalCall();\r | |
143 | return -1;\r | |
144 | }\r | |
145 | if (i < 0 || i >= Py_SIZE(op)) {\r | |
146 | Py_XDECREF(newitem);\r | |
147 | PyErr_SetString(PyExc_IndexError,\r | |
148 | "tuple assignment index out of range");\r | |
149 | return -1;\r | |
150 | }\r | |
151 | p = ((PyTupleObject *)op) -> ob_item + i;\r | |
152 | olditem = *p;\r | |
153 | *p = newitem;\r | |
154 | Py_XDECREF(olditem);\r | |
155 | return 0;\r | |
156 | }\r | |
157 | \r | |
158 | void\r | |
159 | _PyTuple_MaybeUntrack(PyObject *op)\r | |
160 | {\r | |
161 | PyTupleObject *t;\r | |
162 | Py_ssize_t i, n;\r | |
163 | \r | |
164 | if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))\r | |
165 | return;\r | |
166 | t = (PyTupleObject *) op;\r | |
167 | n = Py_SIZE(t);\r | |
168 | for (i = 0; i < n; i++) {\r | |
169 | PyObject *elt = PyTuple_GET_ITEM(t, i);\r | |
170 | /* Tuple with NULL elements aren't\r | |
171 | fully constructed, don't untrack\r | |
172 | them yet. */\r | |
173 | if (!elt ||\r | |
174 | _PyObject_GC_MAY_BE_TRACKED(elt))\r | |
175 | return;\r | |
176 | }\r | |
177 | #ifdef SHOW_TRACK_COUNT\r | |
178 | count_tracked--;\r | |
179 | count_untracked++;\r | |
180 | #endif\r | |
181 | _PyObject_GC_UNTRACK(op);\r | |
182 | }\r | |
183 | \r | |
184 | PyObject *\r | |
185 | PyTuple_Pack(Py_ssize_t n, ...)\r | |
186 | {\r | |
187 | Py_ssize_t i;\r | |
188 | PyObject *o;\r | |
189 | PyObject *result;\r | |
190 | PyObject **items;\r | |
191 | va_list vargs;\r | |
192 | \r | |
193 | va_start(vargs, n);\r | |
194 | result = PyTuple_New(n);\r | |
195 | if (result == NULL)\r | |
196 | return NULL;\r | |
197 | items = ((PyTupleObject *)result)->ob_item;\r | |
198 | for (i = 0; i < n; i++) {\r | |
199 | o = va_arg(vargs, PyObject *);\r | |
200 | Py_INCREF(o);\r | |
201 | items[i] = o;\r | |
202 | }\r | |
203 | va_end(vargs);\r | |
204 | return result;\r | |
205 | }\r | |
206 | \r | |
207 | \r | |
208 | /* Methods */\r | |
209 | \r | |
210 | static void\r | |
211 | tupledealloc(register PyTupleObject *op)\r | |
212 | {\r | |
213 | register Py_ssize_t i;\r | |
214 | register Py_ssize_t len = Py_SIZE(op);\r | |
215 | PyObject_GC_UnTrack(op);\r | |
216 | Py_TRASHCAN_SAFE_BEGIN(op)\r | |
217 | if (len > 0) {\r | |
218 | i = len;\r | |
219 | while (--i >= 0)\r | |
220 | Py_XDECREF(op->ob_item[i]);\r | |
221 | #if PyTuple_MAXSAVESIZE > 0\r | |
222 | if (len < PyTuple_MAXSAVESIZE &&\r | |
223 | numfree[len] < PyTuple_MAXFREELIST &&\r | |
224 | Py_TYPE(op) == &PyTuple_Type)\r | |
225 | {\r | |
226 | op->ob_item[0] = (PyObject *) free_list[len];\r | |
227 | numfree[len]++;\r | |
228 | free_list[len] = op;\r | |
229 | goto done; /* return */\r | |
230 | }\r | |
231 | #endif\r | |
232 | }\r | |
233 | Py_TYPE(op)->tp_free((PyObject *)op);\r | |
234 | done:\r | |
235 | Py_TRASHCAN_SAFE_END(op)\r | |
236 | }\r | |
237 | \r | |
238 | static int\r | |
239 | tupleprint(PyTupleObject *op, FILE *fp, int flags)\r | |
240 | {\r | |
241 | Py_ssize_t i;\r | |
242 | Py_BEGIN_ALLOW_THREADS\r | |
243 | fprintf(fp, "(");\r | |
244 | Py_END_ALLOW_THREADS\r | |
245 | for (i = 0; i < Py_SIZE(op); i++) {\r | |
246 | if (i > 0) {\r | |
247 | Py_BEGIN_ALLOW_THREADS\r | |
248 | fprintf(fp, ", ");\r | |
249 | Py_END_ALLOW_THREADS\r | |
250 | }\r | |
251 | if (PyObject_Print(op->ob_item[i], fp, 0) != 0)\r | |
252 | return -1;\r | |
253 | }\r | |
254 | i = Py_SIZE(op);\r | |
255 | Py_BEGIN_ALLOW_THREADS\r | |
256 | if (i == 1)\r | |
257 | fprintf(fp, ",");\r | |
258 | fprintf(fp, ")");\r | |
259 | Py_END_ALLOW_THREADS\r | |
260 | return 0;\r | |
261 | }\r | |
262 | \r | |
263 | static PyObject *\r | |
264 | tuplerepr(PyTupleObject *v)\r | |
265 | {\r | |
266 | Py_ssize_t i, n;\r | |
267 | PyObject *s, *temp;\r | |
268 | PyObject *pieces, *result = NULL;\r | |
269 | \r | |
270 | n = Py_SIZE(v);\r | |
271 | if (n == 0)\r | |
272 | return PyString_FromString("()");\r | |
273 | \r | |
274 | /* While not mutable, it is still possible to end up with a cycle in a\r | |
275 | tuple through an object that stores itself within a tuple (and thus\r | |
276 | infinitely asks for the repr of itself). This should only be\r | |
277 | possible within a type. */\r | |
278 | i = Py_ReprEnter((PyObject *)v);\r | |
279 | if (i != 0) {\r | |
280 | return i > 0 ? PyString_FromString("(...)") : NULL;\r | |
281 | }\r | |
282 | \r | |
283 | pieces = PyTuple_New(n);\r | |
284 | if (pieces == NULL)\r | |
285 | return NULL;\r | |
286 | \r | |
287 | /* Do repr() on each element. */\r | |
288 | for (i = 0; i < n; ++i) {\r | |
289 | if (Py_EnterRecursiveCall(" while getting the repr of a tuple"))\r | |
290 | goto Done;\r | |
291 | s = PyObject_Repr(v->ob_item[i]);\r | |
292 | Py_LeaveRecursiveCall();\r | |
293 | if (s == NULL)\r | |
294 | goto Done;\r | |
295 | PyTuple_SET_ITEM(pieces, i, s);\r | |
296 | }\r | |
297 | \r | |
298 | /* Add "()" decorations to the first and last items. */\r | |
299 | assert(n > 0);\r | |
300 | s = PyString_FromString("(");\r | |
301 | if (s == NULL)\r | |
302 | goto Done;\r | |
303 | temp = PyTuple_GET_ITEM(pieces, 0);\r | |
304 | PyString_ConcatAndDel(&s, temp);\r | |
305 | PyTuple_SET_ITEM(pieces, 0, s);\r | |
306 | if (s == NULL)\r | |
307 | goto Done;\r | |
308 | \r | |
309 | s = PyString_FromString(n == 1 ? ",)" : ")");\r | |
310 | if (s == NULL)\r | |
311 | goto Done;\r | |
312 | temp = PyTuple_GET_ITEM(pieces, n-1);\r | |
313 | PyString_ConcatAndDel(&temp, s);\r | |
314 | PyTuple_SET_ITEM(pieces, n-1, temp);\r | |
315 | if (temp == NULL)\r | |
316 | goto Done;\r | |
317 | \r | |
318 | /* Paste them all together with ", " between. */\r | |
319 | s = PyString_FromString(", ");\r | |
320 | if (s == NULL)\r | |
321 | goto Done;\r | |
322 | result = _PyString_Join(s, pieces);\r | |
323 | Py_DECREF(s);\r | |
324 | \r | |
325 | Done:\r | |
326 | Py_DECREF(pieces);\r | |
327 | Py_ReprLeave((PyObject *)v);\r | |
328 | return result;\r | |
329 | }\r | |
330 | \r | |
331 | /* The addend 82520, was selected from the range(0, 1000000) for\r | |
332 | generating the greatest number of prime multipliers for tuples\r | |
333 | upto length eight:\r | |
334 | \r | |
335 | 1082527, 1165049, 1082531, 1165057, 1247581, 1330103, 1082533,\r | |
336 | 1330111, 1412633, 1165069, 1247599, 1495177, 1577699\r | |
337 | */\r | |
338 | \r | |
339 | static long\r | |
340 | tuplehash(PyTupleObject *v)\r | |
341 | {\r | |
342 | register long x, y;\r | |
343 | register Py_ssize_t len = Py_SIZE(v);\r | |
344 | register PyObject **p;\r | |
345 | long mult = 1000003L;\r | |
346 | x = 0x345678L;\r | |
347 | p = v->ob_item;\r | |
348 | while (--len >= 0) {\r | |
349 | y = PyObject_Hash(*p++);\r | |
350 | if (y == -1)\r | |
351 | return -1;\r | |
352 | x = (x ^ y) * mult;\r | |
353 | /* the cast might truncate len; that doesn't change hash stability */\r | |
354 | mult += (long)(82520L + len + len);\r | |
355 | }\r | |
356 | x += 97531L;\r | |
357 | if (x == -1)\r | |
358 | x = -2;\r | |
359 | return x;\r | |
360 | }\r | |
361 | \r | |
362 | static Py_ssize_t\r | |
363 | tuplelength(PyTupleObject *a)\r | |
364 | {\r | |
365 | return Py_SIZE(a);\r | |
366 | }\r | |
367 | \r | |
368 | static int\r | |
369 | tuplecontains(PyTupleObject *a, PyObject *el)\r | |
370 | {\r | |
371 | Py_ssize_t i;\r | |
372 | int cmp;\r | |
373 | \r | |
374 | for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)\r | |
375 | cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),\r | |
376 | Py_EQ);\r | |
377 | return cmp;\r | |
378 | }\r | |
379 | \r | |
380 | static PyObject *\r | |
381 | tupleitem(register PyTupleObject *a, register Py_ssize_t i)\r | |
382 | {\r | |
383 | if (i < 0 || i >= Py_SIZE(a)) {\r | |
384 | PyErr_SetString(PyExc_IndexError, "tuple index out of range");\r | |
385 | return NULL;\r | |
386 | }\r | |
387 | Py_INCREF(a->ob_item[i]);\r | |
388 | return a->ob_item[i];\r | |
389 | }\r | |
390 | \r | |
391 | static PyObject *\r | |
392 | tupleslice(register PyTupleObject *a, register Py_ssize_t ilow,\r | |
393 | register Py_ssize_t ihigh)\r | |
394 | {\r | |
395 | register PyTupleObject *np;\r | |
396 | PyObject **src, **dest;\r | |
397 | register Py_ssize_t i;\r | |
398 | Py_ssize_t len;\r | |
399 | if (ilow < 0)\r | |
400 | ilow = 0;\r | |
401 | if (ihigh > Py_SIZE(a))\r | |
402 | ihigh = Py_SIZE(a);\r | |
403 | if (ihigh < ilow)\r | |
404 | ihigh = ilow;\r | |
405 | if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {\r | |
406 | Py_INCREF(a);\r | |
407 | return (PyObject *)a;\r | |
408 | }\r | |
409 | len = ihigh - ilow;\r | |
410 | np = (PyTupleObject *)PyTuple_New(len);\r | |
411 | if (np == NULL)\r | |
412 | return NULL;\r | |
413 | src = a->ob_item + ilow;\r | |
414 | dest = np->ob_item;\r | |
415 | for (i = 0; i < len; i++) {\r | |
416 | PyObject *v = src[i];\r | |
417 | Py_INCREF(v);\r | |
418 | dest[i] = v;\r | |
419 | }\r | |
420 | return (PyObject *)np;\r | |
421 | }\r | |
422 | \r | |
423 | PyObject *\r | |
424 | PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)\r | |
425 | {\r | |
426 | if (op == NULL || !PyTuple_Check(op)) {\r | |
427 | PyErr_BadInternalCall();\r | |
428 | return NULL;\r | |
429 | }\r | |
430 | return tupleslice((PyTupleObject *)op, i, j);\r | |
431 | }\r | |
432 | \r | |
433 | static PyObject *\r | |
434 | tupleconcat(register PyTupleObject *a, register PyObject *bb)\r | |
435 | {\r | |
436 | register Py_ssize_t size;\r | |
437 | register Py_ssize_t i;\r | |
438 | PyObject **src, **dest;\r | |
439 | PyTupleObject *np;\r | |
440 | if (!PyTuple_Check(bb)) {\r | |
441 | PyErr_Format(PyExc_TypeError,\r | |
442 | "can only concatenate tuple (not \"%.200s\") to tuple",\r | |
443 | Py_TYPE(bb)->tp_name);\r | |
444 | return NULL;\r | |
445 | }\r | |
446 | #define b ((PyTupleObject *)bb)\r | |
447 | size = Py_SIZE(a) + Py_SIZE(b);\r | |
448 | if (size < 0)\r | |
449 | return PyErr_NoMemory();\r | |
450 | np = (PyTupleObject *) PyTuple_New(size);\r | |
451 | if (np == NULL) {\r | |
452 | return NULL;\r | |
453 | }\r | |
454 | src = a->ob_item;\r | |
455 | dest = np->ob_item;\r | |
456 | for (i = 0; i < Py_SIZE(a); i++) {\r | |
457 | PyObject *v = src[i];\r | |
458 | Py_INCREF(v);\r | |
459 | dest[i] = v;\r | |
460 | }\r | |
461 | src = b->ob_item;\r | |
462 | dest = np->ob_item + Py_SIZE(a);\r | |
463 | for (i = 0; i < Py_SIZE(b); i++) {\r | |
464 | PyObject *v = src[i];\r | |
465 | Py_INCREF(v);\r | |
466 | dest[i] = v;\r | |
467 | }\r | |
468 | return (PyObject *)np;\r | |
469 | #undef b\r | |
470 | }\r | |
471 | \r | |
472 | static PyObject *\r | |
473 | tuplerepeat(PyTupleObject *a, Py_ssize_t n)\r | |
474 | {\r | |
475 | Py_ssize_t i, j;\r | |
476 | Py_ssize_t size;\r | |
477 | PyTupleObject *np;\r | |
478 | PyObject **p, **items;\r | |
479 | if (n < 0)\r | |
480 | n = 0;\r | |
481 | if (Py_SIZE(a) == 0 || n == 1) {\r | |
482 | if (PyTuple_CheckExact(a)) {\r | |
483 | /* Since tuples are immutable, we can return a shared\r | |
484 | copy in this case */\r | |
485 | Py_INCREF(a);\r | |
486 | return (PyObject *)a;\r | |
487 | }\r | |
488 | if (Py_SIZE(a) == 0)\r | |
489 | return PyTuple_New(0);\r | |
490 | }\r | |
491 | size = Py_SIZE(a) * n;\r | |
492 | if (size/Py_SIZE(a) != n)\r | |
493 | return PyErr_NoMemory();\r | |
494 | np = (PyTupleObject *) PyTuple_New(size);\r | |
495 | if (np == NULL)\r | |
496 | return NULL;\r | |
497 | p = np->ob_item;\r | |
498 | items = a->ob_item;\r | |
499 | for (i = 0; i < n; i++) {\r | |
500 | for (j = 0; j < Py_SIZE(a); j++) {\r | |
501 | *p = items[j];\r | |
502 | Py_INCREF(*p);\r | |
503 | p++;\r | |
504 | }\r | |
505 | }\r | |
506 | return (PyObject *) np;\r | |
507 | }\r | |
508 | \r | |
509 | static PyObject *\r | |
510 | tupleindex(PyTupleObject *self, PyObject *args)\r | |
511 | {\r | |
512 | Py_ssize_t i, start=0, stop=Py_SIZE(self);\r | |
513 | PyObject *v;\r | |
514 | \r | |
515 | if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,\r | |
516 | _PyEval_SliceIndex, &start,\r | |
517 | _PyEval_SliceIndex, &stop))\r | |
518 | return NULL;\r | |
519 | if (start < 0) {\r | |
520 | start += Py_SIZE(self);\r | |
521 | if (start < 0)\r | |
522 | start = 0;\r | |
523 | }\r | |
524 | if (stop < 0) {\r | |
525 | stop += Py_SIZE(self);\r | |
526 | if (stop < 0)\r | |
527 | stop = 0;\r | |
528 | }\r | |
529 | for (i = start; i < stop && i < Py_SIZE(self); i++) {\r | |
530 | int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);\r | |
531 | if (cmp > 0)\r | |
532 | return PyInt_FromSsize_t(i);\r | |
533 | else if (cmp < 0)\r | |
534 | return NULL;\r | |
535 | }\r | |
536 | PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");\r | |
537 | return NULL;\r | |
538 | }\r | |
539 | \r | |
540 | static PyObject *\r | |
541 | tuplecount(PyTupleObject *self, PyObject *v)\r | |
542 | {\r | |
543 | Py_ssize_t count = 0;\r | |
544 | Py_ssize_t i;\r | |
545 | \r | |
546 | for (i = 0; i < Py_SIZE(self); i++) {\r | |
547 | int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);\r | |
548 | if (cmp > 0)\r | |
549 | count++;\r | |
550 | else if (cmp < 0)\r | |
551 | return NULL;\r | |
552 | }\r | |
553 | return PyInt_FromSsize_t(count);\r | |
554 | }\r | |
555 | \r | |
556 | static int\r | |
557 | tupletraverse(PyTupleObject *o, visitproc visit, void *arg)\r | |
558 | {\r | |
559 | Py_ssize_t i;\r | |
560 | \r | |
561 | for (i = Py_SIZE(o); --i >= 0; )\r | |
562 | Py_VISIT(o->ob_item[i]);\r | |
563 | return 0;\r | |
564 | }\r | |
565 | \r | |
566 | static PyObject *\r | |
567 | tuplerichcompare(PyObject *v, PyObject *w, int op)\r | |
568 | {\r | |
569 | PyTupleObject *vt, *wt;\r | |
570 | Py_ssize_t i;\r | |
571 | Py_ssize_t vlen, wlen;\r | |
572 | \r | |
573 | if (!PyTuple_Check(v) || !PyTuple_Check(w)) {\r | |
574 | Py_INCREF(Py_NotImplemented);\r | |
575 | return Py_NotImplemented;\r | |
576 | }\r | |
577 | \r | |
578 | vt = (PyTupleObject *)v;\r | |
579 | wt = (PyTupleObject *)w;\r | |
580 | \r | |
581 | vlen = Py_SIZE(vt);\r | |
582 | wlen = Py_SIZE(wt);\r | |
583 | \r | |
584 | /* Note: the corresponding code for lists has an "early out" test\r | |
585 | * here when op is EQ or NE and the lengths differ. That pays there,\r | |
586 | * but Tim was unable to find any real code where EQ/NE tuple\r | |
587 | * compares don't have the same length, so testing for it here would\r | |
588 | * have cost without benefit.\r | |
589 | */\r | |
590 | \r | |
591 | /* Search for the first index where items are different.\r | |
592 | * Note that because tuples are immutable, it's safe to reuse\r | |
593 | * vlen and wlen across the comparison calls.\r | |
594 | */\r | |
595 | for (i = 0; i < vlen && i < wlen; i++) {\r | |
596 | int k = PyObject_RichCompareBool(vt->ob_item[i],\r | |
597 | wt->ob_item[i], Py_EQ);\r | |
598 | if (k < 0)\r | |
599 | return NULL;\r | |
600 | if (!k)\r | |
601 | break;\r | |
602 | }\r | |
603 | \r | |
604 | if (i >= vlen || i >= wlen) {\r | |
605 | /* No more items to compare -- compare sizes */\r | |
606 | int cmp;\r | |
607 | PyObject *res;\r | |
608 | switch (op) {\r | |
609 | case Py_LT: cmp = vlen < wlen; break;\r | |
610 | case Py_LE: cmp = vlen <= wlen; break;\r | |
611 | case Py_EQ: cmp = vlen == wlen; break;\r | |
612 | case Py_NE: cmp = vlen != wlen; break;\r | |
613 | case Py_GT: cmp = vlen > wlen; break;\r | |
614 | case Py_GE: cmp = vlen >= wlen; break;\r | |
615 | default: return NULL; /* cannot happen */\r | |
616 | }\r | |
617 | if (cmp)\r | |
618 | res = Py_True;\r | |
619 | else\r | |
620 | res = Py_False;\r | |
621 | Py_INCREF(res);\r | |
622 | return res;\r | |
623 | }\r | |
624 | \r | |
625 | /* We have an item that differs -- shortcuts for EQ/NE */\r | |
626 | if (op == Py_EQ) {\r | |
627 | Py_INCREF(Py_False);\r | |
628 | return Py_False;\r | |
629 | }\r | |
630 | if (op == Py_NE) {\r | |
631 | Py_INCREF(Py_True);\r | |
632 | return Py_True;\r | |
633 | }\r | |
634 | \r | |
635 | /* Compare the final item again using the proper operator */\r | |
636 | return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);\r | |
637 | }\r | |
638 | \r | |
639 | static PyObject *\r | |
640 | tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);\r | |
641 | \r | |
642 | static PyObject *\r | |
643 | tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r | |
644 | {\r | |
645 | PyObject *arg = NULL;\r | |
646 | static char *kwlist[] = {"sequence", 0};\r | |
647 | \r | |
648 | if (type != &PyTuple_Type)\r | |
649 | return tuple_subtype_new(type, args, kwds);\r | |
650 | if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))\r | |
651 | return NULL;\r | |
652 | \r | |
653 | if (arg == NULL)\r | |
654 | return PyTuple_New(0);\r | |
655 | else\r | |
656 | return PySequence_Tuple(arg);\r | |
657 | }\r | |
658 | \r | |
659 | static PyObject *\r | |
660 | tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r | |
661 | {\r | |
662 | PyObject *tmp, *newobj, *item;\r | |
663 | Py_ssize_t i, n;\r | |
664 | \r | |
665 | assert(PyType_IsSubtype(type, &PyTuple_Type));\r | |
666 | tmp = tuple_new(&PyTuple_Type, args, kwds);\r | |
667 | if (tmp == NULL)\r | |
668 | return NULL;\r | |
669 | assert(PyTuple_Check(tmp));\r | |
670 | newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));\r | |
671 | if (newobj == NULL)\r | |
672 | return NULL;\r | |
673 | for (i = 0; i < n; i++) {\r | |
674 | item = PyTuple_GET_ITEM(tmp, i);\r | |
675 | Py_INCREF(item);\r | |
676 | PyTuple_SET_ITEM(newobj, i, item);\r | |
677 | }\r | |
678 | Py_DECREF(tmp);\r | |
679 | return newobj;\r | |
680 | }\r | |
681 | \r | |
682 | PyDoc_STRVAR(tuple_doc,\r | |
683 | "tuple() -> empty tuple\n\\r | |
684 | tuple(iterable) -> tuple initialized from iterable's items\n\\r | |
685 | \n\\r | |
686 | If the argument is a tuple, the return value is the same object.");\r | |
687 | \r | |
688 | static PySequenceMethods tuple_as_sequence = {\r | |
689 | (lenfunc)tuplelength, /* sq_length */\r | |
690 | (binaryfunc)tupleconcat, /* sq_concat */\r | |
691 | (ssizeargfunc)tuplerepeat, /* sq_repeat */\r | |
692 | (ssizeargfunc)tupleitem, /* sq_item */\r | |
693 | (ssizessizeargfunc)tupleslice, /* sq_slice */\r | |
694 | 0, /* sq_ass_item */\r | |
695 | 0, /* sq_ass_slice */\r | |
696 | (objobjproc)tuplecontains, /* sq_contains */\r | |
697 | };\r | |
698 | \r | |
699 | static PyObject*\r | |
700 | tuplesubscript(PyTupleObject* self, PyObject* item)\r | |
701 | {\r | |
702 | if (PyIndex_Check(item)) {\r | |
703 | Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);\r | |
704 | if (i == -1 && PyErr_Occurred())\r | |
705 | return NULL;\r | |
706 | if (i < 0)\r | |
707 | i += PyTuple_GET_SIZE(self);\r | |
708 | return tupleitem(self, i);\r | |
709 | }\r | |
710 | else if (PySlice_Check(item)) {\r | |
711 | Py_ssize_t start, stop, step, slicelength, cur, i;\r | |
712 | PyObject* result;\r | |
713 | PyObject* it;\r | |
714 | PyObject **src, **dest;\r | |
715 | \r | |
716 | if (PySlice_GetIndicesEx((PySliceObject*)item,\r | |
717 | PyTuple_GET_SIZE(self),\r | |
718 | &start, &stop, &step, &slicelength) < 0) {\r | |
719 | return NULL;\r | |
720 | }\r | |
721 | \r | |
722 | if (slicelength <= 0) {\r | |
723 | return PyTuple_New(0);\r | |
724 | }\r | |
725 | else if (start == 0 && step == 1 &&\r | |
726 | slicelength == PyTuple_GET_SIZE(self) &&\r | |
727 | PyTuple_CheckExact(self)) {\r | |
728 | Py_INCREF(self);\r | |
729 | return (PyObject *)self;\r | |
730 | }\r | |
731 | else {\r | |
732 | result = PyTuple_New(slicelength);\r | |
733 | if (!result) return NULL;\r | |
734 | \r | |
735 | src = self->ob_item;\r | |
736 | dest = ((PyTupleObject *)result)->ob_item;\r | |
737 | for (cur = start, i = 0; i < slicelength;\r | |
738 | cur += step, i++) {\r | |
739 | it = src[cur];\r | |
740 | Py_INCREF(it);\r | |
741 | dest[i] = it;\r | |
742 | }\r | |
743 | \r | |
744 | return result;\r | |
745 | }\r | |
746 | }\r | |
747 | else {\r | |
748 | PyErr_Format(PyExc_TypeError,\r | |
749 | "tuple indices must be integers, not %.200s",\r | |
750 | Py_TYPE(item)->tp_name);\r | |
751 | return NULL;\r | |
752 | }\r | |
753 | }\r | |
754 | \r | |
755 | static PyObject *\r | |
756 | tuple_getnewargs(PyTupleObject *v)\r | |
757 | {\r | |
758 | return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));\r | |
759 | \r | |
760 | }\r | |
761 | \r | |
762 | static PyObject *\r | |
763 | tuple_sizeof(PyTupleObject *self)\r | |
764 | {\r | |
765 | Py_ssize_t res;\r | |
766 | \r | |
767 | res = PyTuple_Type.tp_basicsize + Py_SIZE(self) * sizeof(PyObject *);\r | |
768 | return PyInt_FromSsize_t(res);\r | |
769 | }\r | |
770 | \r | |
771 | PyDoc_STRVAR(index_doc,\r | |
772 | "T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"\r | |
773 | "Raises ValueError if the value is not present."\r | |
774 | );\r | |
775 | PyDoc_STRVAR(count_doc,\r | |
776 | "T.count(value) -> integer -- return number of occurrences of value");\r | |
777 | PyDoc_STRVAR(sizeof_doc,\r | |
778 | "T.__sizeof__() -- size of T in memory, in bytes");\r | |
779 | \r | |
780 | static PyMethodDef tuple_methods[] = {\r | |
781 | {"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},\r | |
782 | {"__sizeof__", (PyCFunction)tuple_sizeof, METH_NOARGS, sizeof_doc},\r | |
783 | {"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},\r | |
784 | {"count", (PyCFunction)tuplecount, METH_O, count_doc},\r | |
785 | {NULL, NULL} /* sentinel */\r | |
786 | };\r | |
787 | \r | |
788 | static PyMappingMethods tuple_as_mapping = {\r | |
789 | (lenfunc)tuplelength,\r | |
790 | (binaryfunc)tuplesubscript,\r | |
791 | 0\r | |
792 | };\r | |
793 | \r | |
794 | static PyObject *tuple_iter(PyObject *seq);\r | |
795 | \r | |
796 | PyTypeObject PyTuple_Type = {\r | |
797 | PyVarObject_HEAD_INIT(&PyType_Type, 0)\r | |
798 | "tuple",\r | |
799 | sizeof(PyTupleObject) - sizeof(PyObject *),\r | |
800 | sizeof(PyObject *),\r | |
801 | (destructor)tupledealloc, /* tp_dealloc */\r | |
802 | (printfunc)tupleprint, /* tp_print */\r | |
803 | 0, /* tp_getattr */\r | |
804 | 0, /* tp_setattr */\r | |
805 | 0, /* tp_compare */\r | |
806 | (reprfunc)tuplerepr, /* tp_repr */\r | |
807 | 0, /* tp_as_number */\r | |
808 | &tuple_as_sequence, /* tp_as_sequence */\r | |
809 | &tuple_as_mapping, /* tp_as_mapping */\r | |
810 | (hashfunc)tuplehash, /* tp_hash */\r | |
811 | 0, /* tp_call */\r | |
812 | 0, /* tp_str */\r | |
813 | PyObject_GenericGetAttr, /* tp_getattro */\r | |
814 | 0, /* tp_setattro */\r | |
815 | 0, /* tp_as_buffer */\r | |
816 | Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |\r | |
817 | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */\r | |
818 | tuple_doc, /* tp_doc */\r | |
819 | (traverseproc)tupletraverse, /* tp_traverse */\r | |
820 | 0, /* tp_clear */\r | |
821 | tuplerichcompare, /* tp_richcompare */\r | |
822 | 0, /* tp_weaklistoffset */\r | |
823 | tuple_iter, /* tp_iter */\r | |
824 | 0, /* tp_iternext */\r | |
825 | tuple_methods, /* tp_methods */\r | |
826 | 0, /* tp_members */\r | |
827 | 0, /* tp_getset */\r | |
828 | 0, /* tp_base */\r | |
829 | 0, /* tp_dict */\r | |
830 | 0, /* tp_descr_get */\r | |
831 | 0, /* tp_descr_set */\r | |
832 | 0, /* tp_dictoffset */\r | |
833 | 0, /* tp_init */\r | |
834 | 0, /* tp_alloc */\r | |
835 | tuple_new, /* tp_new */\r | |
836 | PyObject_GC_Del, /* tp_free */\r | |
837 | };\r | |
838 | \r | |
839 | /* The following function breaks the notion that tuples are immutable:\r | |
840 | it changes the size of a tuple. We get away with this only if there\r | |
841 | is only one module referencing the object. You can also think of it\r | |
842 | as creating a new tuple object and destroying the old one, only more\r | |
843 | efficiently. In any case, don't use this if the tuple may already be\r | |
844 | known to some other part of the code. */\r | |
845 | \r | |
846 | int\r | |
847 | _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)\r | |
848 | {\r | |
849 | register PyTupleObject *v;\r | |
850 | register PyTupleObject *sv;\r | |
851 | Py_ssize_t i;\r | |
852 | Py_ssize_t oldsize;\r | |
853 | \r | |
854 | v = (PyTupleObject *) *pv;\r | |
855 | if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||\r | |
856 | (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {\r | |
857 | *pv = 0;\r | |
858 | Py_XDECREF(v);\r | |
859 | PyErr_BadInternalCall();\r | |
860 | return -1;\r | |
861 | }\r | |
862 | oldsize = Py_SIZE(v);\r | |
863 | if (oldsize == newsize)\r | |
864 | return 0;\r | |
865 | \r | |
866 | if (oldsize == 0) {\r | |
867 | /* Empty tuples are often shared, so we should never\r | |
868 | resize them in-place even if we do own the only\r | |
869 | (current) reference */\r | |
870 | Py_DECREF(v);\r | |
871 | *pv = PyTuple_New(newsize);\r | |
872 | return *pv == NULL ? -1 : 0;\r | |
873 | }\r | |
874 | \r | |
875 | /* XXX UNREF/NEWREF interface should be more symmetrical */\r | |
876 | _Py_DEC_REFTOTAL;\r | |
877 | if (_PyObject_GC_IS_TRACKED(v))\r | |
878 | _PyObject_GC_UNTRACK(v);\r | |
879 | _Py_ForgetReference((PyObject *) v);\r | |
880 | /* DECREF items deleted by shrinkage */\r | |
881 | for (i = newsize; i < oldsize; i++) {\r | |
882 | Py_XDECREF(v->ob_item[i]);\r | |
883 | v->ob_item[i] = NULL;\r | |
884 | }\r | |
885 | sv = PyObject_GC_Resize(PyTupleObject, v, newsize);\r | |
886 | if (sv == NULL) {\r | |
887 | *pv = NULL;\r | |
888 | PyObject_GC_Del(v);\r | |
889 | return -1;\r | |
890 | }\r | |
891 | _Py_NewReference((PyObject *) sv);\r | |
892 | /* Zero out items added by growing */\r | |
893 | if (newsize > oldsize)\r | |
894 | memset(&sv->ob_item[oldsize], 0,\r | |
895 | sizeof(*sv->ob_item) * (newsize - oldsize));\r | |
896 | *pv = (PyObject *) sv;\r | |
897 | _PyObject_GC_TRACK(sv);\r | |
898 | return 0;\r | |
899 | }\r | |
900 | \r | |
901 | int\r | |
902 | PyTuple_ClearFreeList(void)\r | |
903 | {\r | |
904 | int freelist_size = 0;\r | |
905 | #if PyTuple_MAXSAVESIZE > 0\r | |
906 | int i;\r | |
907 | for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {\r | |
908 | PyTupleObject *p, *q;\r | |
909 | p = free_list[i];\r | |
910 | freelist_size += numfree[i];\r | |
911 | free_list[i] = NULL;\r | |
912 | numfree[i] = 0;\r | |
913 | while (p) {\r | |
914 | q = p;\r | |
915 | p = (PyTupleObject *)(p->ob_item[0]);\r | |
916 | PyObject_GC_Del(q);\r | |
917 | }\r | |
918 | }\r | |
919 | #endif\r | |
920 | return freelist_size;\r | |
921 | }\r | |
922 | \r | |
923 | void\r | |
924 | PyTuple_Fini(void)\r | |
925 | {\r | |
926 | #if PyTuple_MAXSAVESIZE > 0\r | |
927 | /* empty tuples are used all over the place and applications may\r | |
928 | * rely on the fact that an empty tuple is a singleton. */\r | |
929 | Py_XDECREF(free_list[0]);\r | |
930 | free_list[0] = NULL;\r | |
931 | \r | |
932 | (void)PyTuple_ClearFreeList();\r | |
933 | #endif\r | |
934 | #ifdef SHOW_TRACK_COUNT\r | |
935 | show_track();\r | |
936 | #endif\r | |
937 | }\r | |
938 | \r | |
939 | /*********************** Tuple Iterator **************************/\r | |
940 | \r | |
941 | typedef struct {\r | |
942 | PyObject_HEAD\r | |
943 | long it_index;\r | |
944 | PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */\r | |
945 | } tupleiterobject;\r | |
946 | \r | |
947 | static void\r | |
948 | tupleiter_dealloc(tupleiterobject *it)\r | |
949 | {\r | |
950 | _PyObject_GC_UNTRACK(it);\r | |
951 | Py_XDECREF(it->it_seq);\r | |
952 | PyObject_GC_Del(it);\r | |
953 | }\r | |
954 | \r | |
955 | static int\r | |
956 | tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)\r | |
957 | {\r | |
958 | Py_VISIT(it->it_seq);\r | |
959 | return 0;\r | |
960 | }\r | |
961 | \r | |
962 | static PyObject *\r | |
963 | tupleiter_next(tupleiterobject *it)\r | |
964 | {\r | |
965 | PyTupleObject *seq;\r | |
966 | PyObject *item;\r | |
967 | \r | |
968 | assert(it != NULL);\r | |
969 | seq = it->it_seq;\r | |
970 | if (seq == NULL)\r | |
971 | return NULL;\r | |
972 | assert(PyTuple_Check(seq));\r | |
973 | \r | |
974 | if (it->it_index < PyTuple_GET_SIZE(seq)) {\r | |
975 | item = PyTuple_GET_ITEM(seq, it->it_index);\r | |
976 | ++it->it_index;\r | |
977 | Py_INCREF(item);\r | |
978 | return item;\r | |
979 | }\r | |
980 | \r | |
981 | Py_DECREF(seq);\r | |
982 | it->it_seq = NULL;\r | |
983 | return NULL;\r | |
984 | }\r | |
985 | \r | |
986 | static PyObject *\r | |
987 | tupleiter_len(tupleiterobject *it)\r | |
988 | {\r | |
989 | Py_ssize_t len = 0;\r | |
990 | if (it->it_seq)\r | |
991 | len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;\r | |
992 | return PyInt_FromSsize_t(len);\r | |
993 | }\r | |
994 | \r | |
995 | PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");\r | |
996 | \r | |
997 | static PyMethodDef tupleiter_methods[] = {\r | |
998 | {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},\r | |
999 | {NULL, NULL} /* sentinel */\r | |
1000 | };\r | |
1001 | \r | |
1002 | PyTypeObject PyTupleIter_Type = {\r | |
1003 | PyVarObject_HEAD_INIT(&PyType_Type, 0)\r | |
1004 | "tupleiterator", /* tp_name */\r | |
1005 | sizeof(tupleiterobject), /* tp_basicsize */\r | |
1006 | 0, /* tp_itemsize */\r | |
1007 | /* methods */\r | |
1008 | (destructor)tupleiter_dealloc, /* tp_dealloc */\r | |
1009 | 0, /* tp_print */\r | |
1010 | 0, /* tp_getattr */\r | |
1011 | 0, /* tp_setattr */\r | |
1012 | 0, /* tp_compare */\r | |
1013 | 0, /* tp_repr */\r | |
1014 | 0, /* tp_as_number */\r | |
1015 | 0, /* tp_as_sequence */\r | |
1016 | 0, /* tp_as_mapping */\r | |
1017 | 0, /* tp_hash */\r | |
1018 | 0, /* tp_call */\r | |
1019 | 0, /* tp_str */\r | |
1020 | PyObject_GenericGetAttr, /* tp_getattro */\r | |
1021 | 0, /* tp_setattro */\r | |
1022 | 0, /* tp_as_buffer */\r | |
1023 | Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r | |
1024 | 0, /* tp_doc */\r | |
1025 | (traverseproc)tupleiter_traverse, /* tp_traverse */\r | |
1026 | 0, /* tp_clear */\r | |
1027 | 0, /* tp_richcompare */\r | |
1028 | 0, /* tp_weaklistoffset */\r | |
1029 | PyObject_SelfIter, /* tp_iter */\r | |
1030 | (iternextfunc)tupleiter_next, /* tp_iternext */\r | |
1031 | tupleiter_methods, /* tp_methods */\r | |
1032 | 0,\r | |
1033 | };\r | |
1034 | \r | |
1035 | static PyObject *\r | |
1036 | tuple_iter(PyObject *seq)\r | |
1037 | {\r | |
1038 | tupleiterobject *it;\r | |
1039 | \r | |
1040 | if (!PyTuple_Check(seq)) {\r | |
1041 | PyErr_BadInternalCall();\r | |
1042 | return NULL;\r | |
1043 | }\r | |
1044 | it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);\r | |
1045 | if (it == NULL)\r | |
1046 | return NULL;\r | |
1047 | it->it_index = 0;\r | |
1048 | Py_INCREF(seq);\r | |
1049 | it->it_seq = (PyTupleObject *)seq;\r | |
1050 | _PyObject_GC_TRACK(it);\r | |
1051 | return (PyObject *)it;\r | |
1052 | }\r |