[Python-checkins] python/dist/src/Modules collectionsmodule.c, 1.11, 1.12

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Modules
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv31246

Modified Files:
	collectionsmodule.c 
Log Message:
Improve deque iteration.
* The default __reversed__ performed badly, so reintroduced a custom
  reverse iterator.
* Added length transparency to improve speed with map(), list(), etc.



Index: collectionsmodule.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Modules/collectionsmodule.c,v
retrieving revision 1.11
retrieving revision 1.12
diff -C2 -d -r1.11 -r1.12
*** collectionsmodule.c	4 Mar 2004 08:00:54 -0000	1.11
--- collectionsmodule.c	18 Mar 2004 11:04:57 -0000	1.12
***************
*** 646,649 ****
--- 646,652 ----
  
  static PyObject *deque_iter(dequeobject *deque);
+ static PyObject *deque_reviter(dequeobject *deque);
+ PyDoc_STRVAR(reversed_doc, 
+ 	"D.__reversed__() -- return a reverse iterator over the deque");
  
  static PyMethodDef deque_methods[] = {
***************
*** 666,669 ****
--- 669,674 ----
  	{"__reduce__",	(PyCFunction)deque_reduce,	
  		METH_NOARGS,	 reduce_doc},
+ 	{"__reversed__",	(PyCFunction)deque_reviter,	
+ 		METH_NOARGS,	 reversed_doc},
  	{"rotate",		(PyCFunction)deque_rotate,	
  		METH_VARARGS,	rotate_doc},
***************
*** 728,731 ****
--- 733,737 ----
  	dequeobject *deque;
  	int len;
+ 	int counter;
  } dequeiterobject;
  
***************
*** 745,748 ****
--- 751,755 ----
  	it->deque = deque;
  	it->len = deque->len;
+ 	it->counter = deque->len;
  	return (PyObject *)it;
  }
***************
*** 775,782 ****
--- 782,801 ----
  		it->index = 0;
  	}
+ 	it->counter--;
  	Py_INCREF(item);
  	return item;
  }
  
+ static int
+ dequeiter_len(dequeiterobject *it)
+ {
+ 	return it->counter;
+ }
+ 
+ static PySequenceMethods dequeiter_as_sequence = {
+ 	(inquiry)dequeiter_len,		/* sq_length */
+ 	0,				/* sq_concat */
+ };
+ 
  PyTypeObject dequeiter_type = {
  	PyObject_HEAD_INIT(NULL)
***************
*** 793,797 ****
  	0,					/* tp_repr */
  	0,					/* tp_as_number */
! 	0,					/* tp_as_sequence */
  	0,					/* tp_as_mapping */
  	0,					/* tp_hash */
--- 812,816 ----
  	0,					/* tp_repr */
  	0,					/* tp_as_number */
! 	&dequeiter_as_sequence,			/* tp_as_sequence */
  	0,					/* tp_as_mapping */
  	0,					/* tp_hash */
***************
*** 812,815 ****
--- 831,913 ----
  };
  
+ /*********************** Deque Reverse Iterator **************************/
+ 
+ PyTypeObject dequereviter_type;
+ 
+ static PyObject *
+ deque_reviter(dequeobject *deque)
+ {
+ 	dequeiterobject *it;
+ 
+ 	it = PyObject_New(dequeiterobject, &dequereviter_type);
+ 	if (it == NULL)
+ 		return NULL;
+ 	it->b = deque->rightblock;
+ 	it->index = deque->rightindex;
+ 	Py_INCREF(deque);
+ 	it->deque = deque;
+ 	it->len = deque->len;
+ 	it->counter = deque->len;
+ 	return (PyObject *)it;
+ }
+ 
+ static PyObject *
+ dequereviter_next(dequeiterobject *it)
+ {
+ 	PyObject *item;
+ 	if (it->b == it->deque->leftblock && it->index < it->deque->leftindex)
+ 		return NULL;
+ 
+ 	if (it->len != it->deque->len) {
+ 		it->len = -1; /* Make this state sticky */
+ 		PyErr_SetString(PyExc_RuntimeError,
+ 				"deque changed size during iteration");
+ 		return NULL;
+ 	}
+ 
+ 	item = it->b->data[it->index];
+ 	it->index--;
+ 	if (it->index == -1 && it->b->leftlink != NULL) {
+ 		it->b = it->b->leftlink;
+ 		it->index = BLOCKLEN - 1;
+ 	}
+ 	it->counter--;
+ 	Py_INCREF(item);
+ 	return item;
+ }
+ 
+ PyTypeObject dequereviter_type = {
+ 	PyObject_HEAD_INIT(NULL)
+ 	0,					/* ob_size */
+ 	"deque_reverse_iterator",		/* tp_name */
+ 	sizeof(dequeiterobject),		/* tp_basicsize */
+ 	0,					/* tp_itemsize */
+ 	/* methods */
+ 	(destructor)dequeiter_dealloc,		/* tp_dealloc */
+ 	0,					/* tp_print */
+ 	0,					/* tp_getattr */
+ 	0,					/* tp_setattr */
+ 	0,					/* tp_compare */
+ 	0,					/* tp_repr */
+ 	0,					/* tp_as_number */
+ 	&dequeiter_as_sequence,			/* tp_as_sequence */
+ 	0,					/* tp_as_mapping */
+ 	0,					/* tp_hash */
+ 	0,					/* tp_call */
+ 	0,					/* tp_str */
+ 	PyObject_GenericGetAttr,		/* tp_getattro */
+ 	0,					/* tp_setattro */
+ 	0,					/* tp_as_buffer */
+ 	Py_TPFLAGS_DEFAULT,			/* tp_flags */
+ 	0,					/* tp_doc */
+ 	0,					/* tp_traverse */
+ 	0,					/* tp_clear */
+ 	0,					/* tp_richcompare */
+ 	0,					/* tp_weaklistoffset */
+ 	PyObject_SelfIter,			/* tp_iter */
+ 	(iternextfunc)dequereviter_next,	/* tp_iternext */
+ 	0,
+ };
+ 
  /* module level code ********************************************************/
  
***************
*** 833,836 ****
--- 931,937 ----
  		return;	
  
+ 	if (PyType_Ready(&dequereviter_type) < 0)
+ 		return;
+ 
  	return;
  }