Context Navigation

← Previous Revision
Next Revision →
Normal
Revision Log

tupleobject.c

Last change on this file was 391, checked in by dmik, 11 years ago
python: Merge vendor 2.7.6 to trunk.
Property svn:eol-style set to `native`
File size: 29.2 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: python/trunk/Objects/tupleobject.c

Download in other formats: