1 #include "Python.h"

     2 #include "structmember.h"

     3 

     4 /* collections module implementation of a deque() datatype

     5    Written and maintained by Raymond D. Hettinger <python@rcn.com>

     6    Copyright (c) 2004 Python Software Foundation.

     7    All rights reserved.

     8 */

     9 

    10 /* The block length may be set to any number over 1.  Larger numbers

    11  * reduce the number of calls to the memory allocator but take more

    12  * memory.  Ideally, BLOCKLEN should be set with an eye to the

    13  * length of a cache line.

    14  */

    15 

    16 #define BLOCKLEN 62

    17 #define CENTER ((BLOCKLEN - 1) / 2)

    18 

    19 /* A `dequeobject` is composed of a doubly-linked list of `block` nodes.

    20  * This list is not circular (the leftmost block has leftlink==NULL,

    21  * and the rightmost block has rightlink==NULL).  A deque d's first

    22  * element is at d.leftblock[leftindex] and its last element is at

    23  * d.rightblock[rightindex]; note that, unlike as for Python slice

    24  * indices, these indices are inclusive on both ends.  By being inclusive

    25  * on both ends, algorithms for left and right operations become

    26  * symmetrical which simplifies the design.

    27  *

    28  * The list of blocks is never empty, so d.leftblock and d.rightblock

    29  * are never equal to NULL.

    30  *

    31  * The indices, d.leftindex and d.rightindex are always in the range

    32  *     0 <= index < BLOCKLEN.

    33  * Their exact relationship is:

    34  *     (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.

    35  *

    36  * Empty deques have d.len == 0; d.leftblock==d.rightblock;

    37  * d.leftindex == CENTER+1; and d.rightindex == CENTER.

    38  * Checking for d.len == 0 is the intended way to see whether d is empty.

    39  *

    40  * Whenever d.leftblock == d.rightblock,

    41  *     d.leftindex + d.len - 1 == d.rightindex.

    42  *

    43  * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex

    44  * become indices into distinct blocks and either may be larger than the

    45  * other.

    46  */

    47 

    48 typedef struct BLOCK {

    49 	struct BLOCK *leftlink;

    50 	struct BLOCK *rightlink;

    51 	PyObject *data[BLOCKLEN];

    52 } block;

    53 

    54 #define MAXFREEBLOCKS 10

    55 static Py_ssize_t numfreeblocks = 0;

    56 static block *freeblocks[MAXFREEBLOCKS];

    57 

    58 static block *

    59 newblock(block *leftlink, block *rightlink, Py_ssize_t len) {

    60 	block *b;

    61 	/* To prevent len from overflowing PY_SSIZE_T_MAX on 64-bit machines, we

    62 	 * refuse to allocate new blocks if the current len is dangerously

    63 	 * close.  There is some extra margin to prevent spurious arithmetic

    64 	 * overflows at various places.  The following check ensures that

    65 	 * the blocks allocated to the deque, in the worst case, can only

    66 	 * have PY_SSIZE_T_MAX-2 entries in total.

    67 	 */

    68 	if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) {

    69 		PyErr_SetString(PyExc_OverflowError,

    70 				"cannot add more blocks to the deque");

    71 		return NULL;

    72 	}

    73 	if (numfreeblocks) {

    74 		numfreeblocks -= 1;

    75 		b = freeblocks[numfreeblocks];

    76 	} else {

    77 		b = PyMem_Malloc(sizeof(block));

    78 		if (b == NULL) {

    79 			PyErr_NoMemory();

    80 			return NULL;

    81 		}

    82 	}

    83 	b->leftlink = leftlink;

    84 	b->rightlink = rightlink;

    85 	return b;

    86 }

    87 

    88 static void

    89 freeblock(block *b)

    90 {

    91 	if (numfreeblocks < MAXFREEBLOCKS) {

    92 		freeblocks[numfreeblocks] = b;

    93 		numfreeblocks++;

    94 	} else {

    95 		PyMem_Free(b);

    96 	}

    97 }

    98 

    99 typedef struct {

   100 	PyObject_HEAD

   101 	block *leftblock;

   102 	block *rightblock;

   103 	Py_ssize_t leftindex;	/* in range(BLOCKLEN) */

   104 	Py_ssize_t rightindex;	/* in range(BLOCKLEN) */

   105 	Py_ssize_t len;

   106 	Py_ssize_t maxlen;

   107 	long state;	/* incremented whenever the indices move */

   108 	PyObject *weakreflist; /* List of weak references */

   109 } dequeobject;

   110 

   111 /* The deque's size limit is d.maxlen.  The limit can be zero or positive.

   112  * If there is no limit, then d.maxlen == -1.

   113  * 

   114  * After an item is added to a deque, we check to see if the size has grown past

   115  * the limit. If it has, we get the size back down to the limit by popping an

   116  * item off of the opposite end.  The methods that can trigger this are append(),

   117  * appendleft(), extend(), and extendleft().

   118  */

   119 

   120 #define TRIM(d, popfunction)                               	\

   121     if (d->maxlen != -1 && d->len > d->maxlen) {              	\

   122             PyObject *rv = popfunction(d, NULL);                \

   123             assert(rv != NULL  &&  d->len <= d->maxlen);        \

   124             Py_DECREF(rv);                                      \

   125     }

   126 

   127 static PyTypeObject deque_type;

   128 

   129 static PyObject *

   130 deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   131 {

   132 	dequeobject *deque;

   133 	block *b;

   134 

   135 	/* create dequeobject structure */

   136 	deque = (dequeobject *)type->tp_alloc(type, 0);

   137 	if (deque == NULL)

   138 		return NULL;

   139 

   140 	b = newblock(NULL, NULL, 0);

   141 	if (b == NULL) {

   142 		Py_DECREF(deque);

   143 		return NULL;

   144 	}

   145 

   146 	assert(BLOCKLEN >= 2);

   147 	deque->leftblock = b;

   148 	deque->rightblock = b;

   149 	deque->leftindex = CENTER + 1;

   150 	deque->rightindex = CENTER;

   151 	deque->len = 0;

   152 	deque->state = 0;

   153 	deque->weakreflist = NULL;

   154 	deque->maxlen = -1;

   155 

   156 	return (PyObject *)deque;

   157 }

   158 

   159 static PyObject *

   160 deque_pop(dequeobject *deque, PyObject *unused)

   161 {

   162 	PyObject *item;

   163 	block *prevblock;

   164 

   165 	if (deque->len == 0) {

   166 		PyErr_SetString(PyExc_IndexError, "pop from an empty deque");

   167 		return NULL;

   168 	}

   169 	item = deque->rightblock->data[deque->rightindex];

   170 	deque->rightindex--;

   171 	deque->len--;

   172 	deque->state++;

   173 

   174 	if (deque->rightindex == -1) {

   175 		if (deque->len == 0) {

   176 			assert(deque->leftblock == deque->rightblock);

   177 			assert(deque->leftindex == deque->rightindex+1);

   178 			/* re-center instead of freeing a block */

   179 			deque->leftindex = CENTER + 1;

   180 			deque->rightindex = CENTER;

   181 		} else {

   182 			prevblock = deque->rightblock->leftlink;

   183 			assert(deque->leftblock != deque->rightblock);

   184 			freeblock(deque->rightblock);

   185 			prevblock->rightlink = NULL;

   186 			deque->rightblock = prevblock;

   187 			deque->rightindex = BLOCKLEN - 1;

   188 		}

   189 	}

   190 	return item;

   191 }

   192 

   193 PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");

   194 

   195 static PyObject *

   196 deque_popleft(dequeobject *deque, PyObject *unused)

   197 {

   198 	PyObject *item;

   199 	block *prevblock;

   200 

   201 	if (deque->len == 0) {

   202 		PyErr_SetString(PyExc_IndexError, "pop from an empty deque");

   203 		return NULL;

   204 	}

   205 	assert(deque->leftblock != NULL);

   206 	item = deque->leftblock->data[deque->leftindex];

   207 	deque->leftindex++;

   208 	deque->len--;

   209 	deque->state++;

   210 

   211 	if (deque->leftindex == BLOCKLEN) {

   212 		if (deque->len == 0) {

   213 			assert(deque->leftblock == deque->rightblock);

   214 			assert(deque->leftindex == deque->rightindex+1);

   215 			/* re-center instead of freeing a block */

   216 			deque->leftindex = CENTER + 1;

   217 			deque->rightindex = CENTER;

   218 		} else {

   219 			assert(deque->leftblock != deque->rightblock);

   220 			prevblock = deque->leftblock->rightlink;

   221 			freeblock(deque->leftblock);

   222 			assert(prevblock != NULL);

   223 			prevblock->leftlink = NULL;

   224 			deque->leftblock = prevblock;

   225 			deque->leftindex = 0;

   226 		}

   227 	}

   228 	return item;

   229 }

   230 

   231 PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");

   232 

   233 static PyObject *

   234 deque_append(dequeobject *deque, PyObject *item)

   235 {

   236 	deque->state++;

   237 	if (deque->rightindex == BLOCKLEN-1) {

   238 		block *b = newblock(deque->rightblock, NULL, deque->len);

   239 		if (b == NULL)

   240 			return NULL;

   241 		assert(deque->rightblock->rightlink == NULL);

   242 		deque->rightblock->rightlink = b;

   243 		deque->rightblock = b;

   244 		deque->rightindex = -1;

   245 	}

   246 	Py_INCREF(item);

   247 	deque->len++;

   248 	deque->rightindex++;

   249 	deque->rightblock->data[deque->rightindex] = item;

   250 	TRIM(deque, deque_popleft);

   251 	Py_RETURN_NONE;

   252 }

   253 

   254 PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");

   255 

   256 static PyObject *

   257 deque_appendleft(dequeobject *deque, PyObject *item)

   258 {

   259 	deque->state++;

   260 	if (deque->leftindex == 0) {

   261 		block *b = newblock(NULL, deque->leftblock, deque->len);

   262 		if (b == NULL)

   263 			return NULL;

   264 		assert(deque->leftblock->leftlink == NULL);

   265 		deque->leftblock->leftlink = b;

   266 		deque->leftblock = b;

   267 		deque->leftindex = BLOCKLEN;

   268 	}

   269 	Py_INCREF(item);

   270 	deque->len++;

   271 	deque->leftindex--;

   272 	deque->leftblock->data[deque->leftindex] = item;

   273 	TRIM(deque, deque_pop);

   274 	Py_RETURN_NONE;

   275 }

   276 

   277 PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");

   278 

   279 static PyObject *

   280 deque_extend(dequeobject *deque, PyObject *iterable)

   281 {

   282 	PyObject *it, *item;

   283 

   284 	it = PyObject_GetIter(iterable);

   285 	if (it == NULL)

   286 		return NULL;

   287 

   288 	while ((item = PyIter_Next(it)) != NULL) {

   289 		deque->state++;

   290 		if (deque->rightindex == BLOCKLEN-1) {

   291 			block *b = newblock(deque->rightblock, NULL,

   292 					    deque->len);

   293 			if (b == NULL) {

   294 				Py_DECREF(item);

   295 				Py_DECREF(it);

   296 				return NULL;

   297 			}

   298 			assert(deque->rightblock->rightlink == NULL);

   299 			deque->rightblock->rightlink = b;

   300 			deque->rightblock = b;

   301 			deque->rightindex = -1;

   302 		}

   303 		deque->len++;

   304 		deque->rightindex++;

   305 		deque->rightblock->data[deque->rightindex] = item;

   306 		TRIM(deque, deque_popleft);               

   307 	}

   308 	Py_DECREF(it);

   309 	if (PyErr_Occurred())

   310 		return NULL;

   311 	Py_RETURN_NONE;

   312 }

   313 

   314 PyDoc_STRVAR(extend_doc,

   315 "Extend the right side of the deque with elements from the iterable");

   316 

   317 static PyObject *

   318 deque_extendleft(dequeobject *deque, PyObject *iterable)

   319 {

   320 	PyObject *it, *item;

   321 

   322 	it = PyObject_GetIter(iterable);

   323 	if (it == NULL)

   324 		return NULL;

   325 

   326 	while ((item = PyIter_Next(it)) != NULL) {

   327 		deque->state++;

   328 		if (deque->leftindex == 0) {

   329 			block *b = newblock(NULL, deque->leftblock,

   330 					    deque->len);

   331 			if (b == NULL) {

   332 				Py_DECREF(item);

   333 				Py_DECREF(it);

   334 				return NULL;

   335 			}

   336 			assert(deque->leftblock->leftlink == NULL);

   337 			deque->leftblock->leftlink = b;

   338 			deque->leftblock = b;

   339 			deque->leftindex = BLOCKLEN;

   340 		}

   341 		deque->len++;

   342 		deque->leftindex--;

   343 		deque->leftblock->data[deque->leftindex] = item;

   344 		TRIM(deque, deque_pop);               

   345 	}

   346 	Py_DECREF(it);

   347 	if (PyErr_Occurred())

   348 		return NULL;

   349 	Py_RETURN_NONE;

   350 }

   351 

   352 PyDoc_STRVAR(extendleft_doc,

   353 "Extend the left side of the deque with elements from the iterable");

   354 

   355 static int

   356 _deque_rotate(dequeobject *deque, Py_ssize_t n)

   357 {

   358 	Py_ssize_t i, len=deque->len, halflen=(len+1)>>1;

   359 	PyObject *item, *rv;

   360 

   361 	if (len == 0)

   362 		return 0;

   363 	if (n > halflen || n < -halflen) {

   364 		n %= len;

   365 		if (n > halflen)

   366 			n -= len;

   367 		else if (n < -halflen)

   368 			n += len;

   369 	}

   370 

   371 	for (i=0 ; i<n ; i++) {

   372 		item = deque_pop(deque, NULL);

   373 		assert (item != NULL);

   374 		rv = deque_appendleft(deque, item);

   375 		Py_DECREF(item);

   376 		if (rv == NULL)

   377 			return -1;

   378 		Py_DECREF(rv);

   379 	}

   380 	for (i=0 ; i>n ; i--) {

   381 		item = deque_popleft(deque, NULL);

   382 		assert (item != NULL);

   383 		rv = deque_append(deque, item);

   384 		Py_DECREF(item);

   385 		if (rv == NULL)

   386 			return -1;

   387 		Py_DECREF(rv);

   388 	}

   389 	return 0;

   390 }

   391 

   392 static PyObject *

   393 deque_rotate(dequeobject *deque, PyObject *args)

   394 {

   395 	Py_ssize_t n=1;

   396 

   397 	if (!PyArg_ParseTuple(args, "|n:rotate", &n))

   398 		return NULL;

   399 	if (_deque_rotate(deque, n) == 0)

   400 		Py_RETURN_NONE;

   401 	return NULL;

   402 }

   403 

   404 PyDoc_STRVAR(rotate_doc,

   405 "Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.");

   406 

   407 static Py_ssize_t

   408 deque_len(dequeobject *deque)

   409 {

   410 	return deque->len;

   411 }

   412 

   413 static PyObject *

   414 deque_remove(dequeobject *deque, PyObject *value)

   415 {

   416 	Py_ssize_t i, n=deque->len;

   417 

   418 	for (i=0 ; i<n ; i++) {

   419 		PyObject *item = deque->leftblock->data[deque->leftindex];

   420 		int cmp = PyObject_RichCompareBool(item, value, Py_EQ);

   421 

   422 		if (deque->len != n) {

   423 			PyErr_SetString(PyExc_IndexError,

   424 				"deque mutated during remove().");

   425 			return NULL;

   426 		}

   427 		if (cmp > 0) {

   428 			PyObject *tgt = deque_popleft(deque, NULL);

   429 			assert (tgt != NULL);

   430 			Py_DECREF(tgt);

   431 			if (_deque_rotate(deque, i) == -1)

   432 				return NULL;

   433 			Py_RETURN_NONE;

   434 		}

   435 		else if (cmp < 0) {

   436 			_deque_rotate(deque, i);

   437 			return NULL;

   438 		}

   439 		_deque_rotate(deque, -1);

   440 	}

   441 	PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");

   442 	return NULL;

   443 }

   444 

   445 PyDoc_STRVAR(remove_doc,

   446 "D.remove(value) -- remove first occurrence of value.");

   447 

   448 static int

   449 deque_clear(dequeobject *deque)

   450 {

   451 	PyObject *item;

   452 

   453 	while (deque->len) {

   454 		item = deque_pop(deque, NULL);

   455 		assert (item != NULL);

   456 		Py_DECREF(item);

   457 	}

   458 	assert(deque->leftblock == deque->rightblock &&

   459 	       deque->leftindex - 1 == deque->rightindex &&

   460 	       deque->len == 0);

   461 	return 0;

   462 }

   463 

   464 static PyObject *

   465 deque_item(dequeobject *deque, Py_ssize_t i)

   466 {

   467 	block *b;

   468 	PyObject *item;

   469 	Py_ssize_t n, index=i;

   470 

   471 	if (i < 0 || i >= deque->len) {

   472 		PyErr_SetString(PyExc_IndexError,

   473 				"deque index out of range");

   474 		return NULL;

   475 	}

   476 

   477 	if (i == 0) {

   478 		i = deque->leftindex;

   479 		b = deque->leftblock;

   480 	} else if (i == deque->len - 1) {

   481 		i = deque->rightindex;

   482 		b = deque->rightblock;

   483 	} else {

   484 		i += deque->leftindex;

   485 		n = i / BLOCKLEN;

   486 		i %= BLOCKLEN;

   487 		if (index < (deque->len >> 1)) {

   488 			b = deque->leftblock;

   489 			while (n--)

   490 				b = b->rightlink;

   491 		} else {

   492 			n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;

   493 			b = deque->rightblock;

   494 			while (n--)

   495 				b = b->leftlink;

   496 		}

   497 	}

   498 	item = b->data[i];

   499 	Py_INCREF(item);

   500 	return item;

   501 }

   502 

   503 /* delitem() implemented in terms of rotate for simplicity and reasonable

   504    performance near the end points.  If for some reason this method becomes

   505    popular, it is not hard to re-implement this using direct data movement

   506    (similar to code in list slice assignment) and achieve a two or threefold

   507    performance boost.

   508 */

   509 

   510 static int

   511 deque_del_item(dequeobject *deque, Py_ssize_t i)

   512 {

   513 	PyObject *item;

   514 

   515 	assert (i >= 0 && i < deque->len);

   516 	if (_deque_rotate(deque, -i) == -1)

   517 		return -1;

   518 

   519 	item = deque_popleft(deque, NULL);

   520 	assert (item != NULL);

   521 	Py_DECREF(item);

   522 

   523 	return _deque_rotate(deque, i);

   524 }

   525 

   526 static int

   527 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)

   528 {

   529 	PyObject *old_value;

   530 	block *b;

   531 	Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;

   532 

   533 	if (i < 0 || i >= len) {

   534 		PyErr_SetString(PyExc_IndexError,

   535 				"deque index out of range");

   536 		return -1;

   537 	}

   538 	if (v == NULL)

   539 		return deque_del_item(deque, i);

   540 

   541 	i += deque->leftindex;

   542 	n = i / BLOCKLEN;

   543 	i %= BLOCKLEN;

   544 	if (index <= halflen) {

   545 		b = deque->leftblock;

   546 		while (n--)

   547 			b = b->rightlink;

   548 	} else {

   549 		n = (deque->leftindex + len - 1) / BLOCKLEN - n;

   550 		b = deque->rightblock;

   551 		while (n--)

   552 			b = b->leftlink;

   553 	}

   554 	Py_INCREF(v);

   555 	old_value = b->data[i];

   556 	b->data[i] = v;

   557 	Py_DECREF(old_value);

   558 	return 0;

   559 }

   560 

   561 static PyObject *

   562 deque_clearmethod(dequeobject *deque)

   563 {

   564 	int rv;

   565 

   566 	rv = deque_clear(deque);

   567 	assert (rv != -1);

   568 	Py_RETURN_NONE;

   569 }

   570 

   571 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");

   572 

   573 static void

   574 deque_dealloc(dequeobject *deque)

   575 {

   576 	PyObject_GC_UnTrack(deque);

   577 	if (deque->weakreflist != NULL)

   578 		PyObject_ClearWeakRefs((PyObject *) deque);

   579 	if (deque->leftblock != NULL) {

   580 		deque_clear(deque);

   581 		assert(deque->leftblock != NULL);

   582 		freeblock(deque->leftblock);

   583 	}

   584 	deque->leftblock = NULL;

   585 	deque->rightblock = NULL;

   586 	Py_TYPE(deque)->tp_free(deque);

   587 }

   588 

   589 static int

   590 deque_traverse(dequeobject *deque, visitproc visit, void *arg)

   591 {

   592 	block *b;

   593 	PyObject *item;

   594 	Py_ssize_t index;

   595 	Py_ssize_t indexlo = deque->leftindex;

   596 

   597 	for (b = deque->leftblock; b != NULL; b = b->rightlink) {

   598 		const Py_ssize_t indexhi = b == deque->rightblock ?

   599 					 deque->rightindex :

   600 				    	 BLOCKLEN - 1;

   601 

   602 		for (index = indexlo; index <= indexhi; ++index) {

   603 			item = b->data[index];

   604 			Py_VISIT(item);

   605 		}

   606 		indexlo = 0;

   607 	}

   608 	return 0;

   609 }

   610 

   611 static PyObject *

   612 deque_copy(PyObject *deque)

   613 {

   614 	if (((dequeobject *)deque)->maxlen == -1)

   615 		return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);

   616 	else

   617 		return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",

   618 			deque, ((dequeobject *)deque)->maxlen, NULL);

   619 }

   620 

   621 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");

   622 

   623 static PyObject *

   624 deque_reduce(dequeobject *deque)

   625 {

   626 	PyObject *dict, *result, *aslist;

   627 

   628 	dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");

   629 	if (dict == NULL)

   630 		PyErr_Clear();

   631 	aslist = PySequence_List((PyObject *)deque);

   632 	if (aslist == NULL) {

   633 		Py_XDECREF(dict);

   634 		return NULL;

   635 	}

   636 	if (dict == NULL) {

   637 		if (deque->maxlen == -1)

   638 			result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);

   639 		else

   640 			result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);

   641 	} else {

   642 		if (deque->maxlen == -1)

   643 			result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);

   644 		else

   645 			result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);

   646 	}

   647 	Py_XDECREF(dict);

   648 	Py_DECREF(aslist);

   649 	return result;

   650 }

   651 

   652 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");

   653 

   654 static PyObject *

   655 deque_repr(PyObject *deque)

   656 {

   657 	PyObject *aslist, *result, *fmt;

   658 	int i;

   659 

   660 	i = Py_ReprEnter(deque);

   661 	if (i != 0) {

   662 		if (i < 0)

   663 			return NULL;

   664 		return PyString_FromString("[...]");

   665 	}

   666 

   667 	aslist = PySequence_List(deque);

   668 	if (aslist == NULL) {

   669 		Py_ReprLeave(deque);

   670 		return NULL;

   671 	}

   672 	if (((dequeobject *)deque)->maxlen != -1)

   673 		fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)", 

   674 					((dequeobject *)deque)->maxlen);

   675 	else

   676 		fmt = PyString_FromString("deque(%r)");  

   677 	if (fmt == NULL) {

   678 		Py_DECREF(aslist);

   679 		Py_ReprLeave(deque);

   680 		return NULL;

   681 	}

   682 	result = PyString_Format(fmt, aslist);

   683 	Py_DECREF(fmt);

   684 	Py_DECREF(aslist);

   685 	Py_ReprLeave(deque);

   686 	return result;

   687 }

   688 

   689 static int

   690 deque_tp_print(PyObject *deque, FILE *fp, int flags)

   691 {

   692 	PyObject *it, *item;

   693 	char *emit = "";	/* No separator emitted on first pass */

   694 	char *separator = ", ";

   695 	int i;

   696 

   697 	i = Py_ReprEnter(deque);

   698 	if (i != 0) {

   699 		if (i < 0)

   700 			return i;

   701 		Py_BEGIN_ALLOW_THREADS

   702 		fputs("[...]", fp);

   703 		Py_END_ALLOW_THREADS

   704 		return 0;

   705 	}

   706 

   707 	it = PyObject_GetIter(deque);

   708 	if (it == NULL)

   709 		return -1;

   710 

   711 	Py_BEGIN_ALLOW_THREADS

   712 	fputs("deque([", fp);

   713 	Py_END_ALLOW_THREADS

   714 	while ((item = PyIter_Next(it)) != NULL) {

   715 		Py_BEGIN_ALLOW_THREADS

   716 		fputs(emit, fp);

   717 		Py_END_ALLOW_THREADS

   718 		emit = separator;

   719 		if (PyObject_Print(item, fp, 0) != 0) {

   720 			Py_DECREF(item);

   721 			Py_DECREF(it);

   722 			Py_ReprLeave(deque);

   723 			return -1;

   724 		}

   725 		Py_DECREF(item);

   726 	}

   727 	Py_ReprLeave(deque);

   728 	Py_DECREF(it);

   729 	if (PyErr_Occurred())

   730 		return -1;

   731 

   732 	Py_BEGIN_ALLOW_THREADS

   733 	if (((dequeobject *)deque)->maxlen == -1)

   734 		fputs("])", fp);

   735 	else

   736 		fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen);

   737 	Py_END_ALLOW_THREADS

   738 	return 0;

   739 }

   740 

   741 static PyObject *

   742 deque_richcompare(PyObject *v, PyObject *w, int op)

   743 {

   744 	PyObject *it1=NULL, *it2=NULL, *x, *y;

   745 	Py_ssize_t vs, ws;

   746 	int b, cmp=-1;

   747 

   748 	if (!PyObject_TypeCheck(v, &deque_type) ||

   749 	    !PyObject_TypeCheck(w, &deque_type)) {

   750 		Py_INCREF(Py_NotImplemented);

   751 		return Py_NotImplemented;

   752 	}

   753 

   754 	/* Shortcuts */

   755 	vs = ((dequeobject *)v)->len;

   756 	ws = ((dequeobject *)w)->len;

   757 	if (op == Py_EQ) {

   758 		if (v == w)

   759 			Py_RETURN_TRUE;

   760 		if (vs != ws)

   761 			Py_RETURN_FALSE;

   762 	}

   763 	if (op == Py_NE) {

   764 		if (v == w)

   765 			Py_RETURN_FALSE;

   766 		if (vs != ws)

   767 			Py_RETURN_TRUE;

   768 	}

   769 

   770 	/* Search for the first index where items are different */

   771 	it1 = PyObject_GetIter(v);

   772 	if (it1 == NULL)

   773 		goto done;

   774 	it2 = PyObject_GetIter(w);

   775 	if (it2 == NULL)

   776 		goto done;

   777 	for (;;) {

   778 		x = PyIter_Next(it1);

   779 		if (x == NULL && PyErr_Occurred())

   780 			goto done;

   781 		y = PyIter_Next(it2);

   782 		if (x == NULL || y == NULL)

   783 			break;

   784 		b = PyObject_RichCompareBool(x, y, Py_EQ);

   785 		if (b == 0) {

   786 			cmp = PyObject_RichCompareBool(x, y, op);

   787 			Py_DECREF(x);

   788 			Py_DECREF(y);

   789 			goto done;

   790 		}

   791 		Py_DECREF(x);

   792 		Py_DECREF(y);

   793 		if (b == -1)

   794 			goto done;

   795 	}

   796 	/* We reached the end of one deque or both */

   797 	Py_XDECREF(x);

   798 	Py_XDECREF(y);

   799 	if (PyErr_Occurred())

   800 		goto done;

   801 	switch (op) {

   802 	case Py_LT: cmp = y != NULL; break;  /* if w was longer */

   803 	case Py_LE: cmp = x == NULL; break;  /* if v was not longer */

   804 	case Py_EQ: cmp = x == y;    break;  /* if we reached the end of both */

   805 	case Py_NE: cmp = x != y;    break;  /* if one deque continues */

   806 	case Py_GT: cmp = x != NULL; break;  /* if v was longer */

   807 	case Py_GE: cmp = y == NULL; break;  /* if w was not longer */

   808 	}

   809 

   810 done:

   811 	Py_XDECREF(it1);

   812 	Py_XDECREF(it2);

   813 	if (cmp == 1)

   814 		Py_RETURN_TRUE;

   815 	if (cmp == 0)

   816 		Py_RETURN_FALSE;

   817 	return NULL;

   818 }

   819 

   820 static int

   821 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)

   822 {

   823 	PyObject *iterable = NULL;

   824 	PyObject *maxlenobj = NULL;

   825 	Py_ssize_t maxlen = -1;

   826 	char *kwlist[] = {"iterable", "maxlen", 0};

   827 

   828 	if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))

   829 		return -1;

   830 	if (maxlenobj != NULL && maxlenobj != Py_None) {

   831 		maxlen = PyInt_AsSsize_t(maxlenobj);

   832 		if (maxlen == -1 && PyErr_Occurred())

   833 			return -1;

   834 		if (maxlen < 0) {

   835 			PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");

   836 			return -1;

   837 		}

   838 	}

   839 	deque->maxlen = maxlen;

   840 	deque_clear(deque);

   841 	if (iterable != NULL) {

   842 		PyObject *rv = deque_extend(deque, iterable);

   843 		if (rv == NULL)

   844 			return -1;

   845 		Py_DECREF(rv);

   846 	}

   847 	return 0;

   848 }

   849 

   850 static PySequenceMethods deque_as_sequence = {

   851 	(lenfunc)deque_len,		/* sq_length */

   852 	0,				/* sq_concat */

   853 	0,				/* sq_repeat */

   854 	(ssizeargfunc)deque_item,	/* sq_item */

   855 	0,				/* sq_slice */

   856 	(ssizeobjargproc)deque_ass_item,	/* sq_ass_item */

   857 };

   858 

   859 /* deque object ********************************************************/

   860 

   861 static PyObject *deque_iter(dequeobject *deque);

   862 static PyObject *deque_reviter(dequeobject *deque);

   863 PyDoc_STRVAR(reversed_doc,

   864 	"D.__reversed__() -- return a reverse iterator over the deque");

   865 

   866 static PyMethodDef deque_methods[] = {

   867 	{"append",		(PyCFunction)deque_append,

   868 		METH_O,		 append_doc},

   869 	{"appendleft",		(PyCFunction)deque_appendleft,

   870 		METH_O,		 appendleft_doc},

   871 	{"clear",		(PyCFunction)deque_clearmethod,

   872 		METH_NOARGS,	 clear_doc},

   873 	{"__copy__",		(PyCFunction)deque_copy,

   874 		METH_NOARGS,	 copy_doc},

   875 	{"extend",		(PyCFunction)deque_extend,

   876 		METH_O,		 extend_doc},

   877 	{"extendleft",		(PyCFunction)deque_extendleft,

   878 		METH_O,		 extendleft_doc},

   879 	{"pop",			(PyCFunction)deque_pop,

   880 		METH_NOARGS,	 pop_doc},

   881 	{"popleft",		(PyCFunction)deque_popleft,

   882 		METH_NOARGS,	 popleft_doc},

   883 	{"__reduce__",	(PyCFunction)deque_reduce,

   884 		METH_NOARGS,	 reduce_doc},

   885 	{"remove",		(PyCFunction)deque_remove,

   886 		METH_O,		 remove_doc},

   887 	{"__reversed__",	(PyCFunction)deque_reviter,

   888 		METH_NOARGS,	 reversed_doc},

   889 	{"rotate",		(PyCFunction)deque_rotate,

   890 		METH_VARARGS,	rotate_doc},

   891 	{NULL,		NULL}	/* sentinel */

   892 };

   893 

   894 PyDoc_STRVAR(deque_doc,

   895 "deque(iterable[, maxlen]) --> deque object\n\

   896 \n\

   897 Build an ordered collection accessible from endpoints only.");

   898 

   899 static PyTypeObject deque_type = {

   900 	PyVarObject_HEAD_INIT(NULL, 0)

   901 	"collections.deque",		/* tp_name */

   902 	sizeof(dequeobject),		/* tp_basicsize */

   903 	0,				/* tp_itemsize */

   904 	/* methods */

   905 	(destructor)deque_dealloc,	/* tp_dealloc */

   906 	deque_tp_print,			/* tp_print */

   907 	0,				/* tp_getattr */

   908 	0,				/* tp_setattr */

   909 	0,				/* tp_compare */

   910 	deque_repr,			/* tp_repr */

   911 	0,				/* tp_as_number */

   912 	&deque_as_sequence,		/* tp_as_sequence */

   913 	0,				/* tp_as_mapping */

   914 	(hashfunc)PyObject_HashNotImplemented,	/* tp_hash */

   915 	0,				/* tp_call */

   916 	0,				/* tp_str */

   917 	PyObject_GenericGetAttr,	/* tp_getattro */

   918 	0,				/* tp_setattro */

   919 	0,				/* tp_as_buffer */

   920 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |

   921 		Py_TPFLAGS_HAVE_WEAKREFS,	/* tp_flags */

   922 	deque_doc,			/* tp_doc */

   923 	(traverseproc)deque_traverse,	/* tp_traverse */

   924 	(inquiry)deque_clear,		/* tp_clear */

   925 	(richcmpfunc)deque_richcompare,	/* tp_richcompare */

   926 	offsetof(dequeobject, weakreflist),	/* tp_weaklistoffset*/

   927 	(getiterfunc)deque_iter,	/* tp_iter */

   928 	0,				/* tp_iternext */

   929 	deque_methods,			/* tp_methods */

   930 	0,				/* tp_members */

   931 	0,				/* tp_getset */

   932 	0,				/* tp_base */

   933 	0,				/* tp_dict */

   934 	0,				/* tp_descr_get */

   935 	0,				/* tp_descr_set */

   936 	0,				/* tp_dictoffset */

   937 	(initproc)deque_init,		/* tp_init */

   938 	PyType_GenericAlloc,		/* tp_alloc */

   939 	deque_new,			/* tp_new */

   940 	PyObject_GC_Del,		/* tp_free */

   941 };

   942 

   943 /*********************** Deque Iterator **************************/

   944 

   945 typedef struct {

   946 	PyObject_HEAD

   947 	Py_ssize_t index;

   948 	block *b;

   949 	dequeobject *deque;

   950 	long state;	/* state when the iterator is created */

   951 	Py_ssize_t counter;    /* number of items remaining for iteration */

   952 } dequeiterobject;

   953 

   954 static PyTypeObject dequeiter_type;

   955 

   956 static PyObject *

   957 deque_iter(dequeobject *deque)

   958 {

   959 	dequeiterobject *it;

   960 

   961 	it = PyObject_New(dequeiterobject, &dequeiter_type);

   962 	if (it == NULL)

   963 		return NULL;

   964 	it->b = deque->leftblock;

   965 	it->index = deque->leftindex;

   966 	Py_INCREF(deque);

   967 	it->deque = deque;

   968 	it->state = deque->state;

   969 	it->counter = deque->len;

   970 	return (PyObject *)it;

   971 }

   972 

   973 static void

   974 dequeiter_dealloc(dequeiterobject *dio)

   975 {

   976 	Py_XDECREF(dio->deque);

   977 	Py_TYPE(dio)->tp_free(dio);

   978 }

   979 

   980 static PyObject *

   981 dequeiter_next(dequeiterobject *it)

   982 {

   983 	PyObject *item;

   984 

   985 	if (it->deque->state != it->state) {

   986 		it->counter = 0;

   987 		PyErr_SetString(PyExc_RuntimeError,

   988 				"deque mutated during iteration");

   989 		return NULL;

   990 	}

   991 	if (it->counter == 0)

   992 		return NULL;        

   993 	assert (!(it->b == it->deque->rightblock &&

   994 		  it->index > it->deque->rightindex));

   995 

   996 	item = it->b->data[it->index];

   997 	it->index++;

   998 	it->counter--;

   999 	if (it->index == BLOCKLEN && it->counter > 0) {

  1000 		assert (it->b->rightlink != NULL);

  1001 		it->b = it->b->rightlink;

  1002 		it->index = 0;

  1003 	}

  1004 	Py_INCREF(item);

  1005 	return item;

  1006 }

  1007 

  1008 static PyObject *

  1009 dequeiter_len(dequeiterobject *it)

  1010 {

  1011 	return PyInt_FromLong(it->counter);

  1012 }

  1013 

  1014 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");

  1015 

  1016 static PyMethodDef dequeiter_methods[] = {

  1017 	{"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},

  1018  	{NULL,		NULL}		/* sentinel */

  1019 };

  1020 

  1021 static PyTypeObject dequeiter_type = {

  1022 	PyVarObject_HEAD_INIT(NULL, 0)

  1023 	"deque_iterator",			/* tp_name */

  1024 	sizeof(dequeiterobject),		/* tp_basicsize */

  1025 	0,					/* tp_itemsize */

  1026 	/* methods */

  1027 	(destructor)dequeiter_dealloc,		/* tp_dealloc */

  1028 	0,					/* tp_print */

  1029 	0,					/* tp_getattr */

  1030 	0,					/* tp_setattr */

  1031 	0,					/* tp_compare */

  1032 	0,					/* tp_repr */

  1033 	0,					/* tp_as_number */

  1034 	0,					/* tp_as_sequence */

  1035 	0,					/* tp_as_mapping */

  1036 	0,					/* tp_hash */

  1037 	0,					/* tp_call */

  1038 	0,					/* tp_str */

  1039 	PyObject_GenericGetAttr,		/* tp_getattro */

  1040 	0,					/* tp_setattro */

  1041 	0,					/* tp_as_buffer */

  1042 	Py_TPFLAGS_DEFAULT,			/* tp_flags */

  1043 	0,					/* tp_doc */

  1044 	0,					/* tp_traverse */

  1045 	0,					/* tp_clear */

  1046 	0,					/* tp_richcompare */

  1047 	0,					/* tp_weaklistoffset */

  1048 	PyObject_SelfIter,			/* tp_iter */

  1049 	(iternextfunc)dequeiter_next,		/* tp_iternext */

  1050 	dequeiter_methods,			/* tp_methods */

  1051 	0,

  1052 };

  1053 

  1054 /*********************** Deque Reverse Iterator **************************/

  1055 

  1056 static PyTypeObject dequereviter_type;

  1057 

  1058 static PyObject *

  1059 deque_reviter(dequeobject *deque)

  1060 {

  1061 	dequeiterobject *it;

  1062 

  1063 	it = PyObject_New(dequeiterobject, &dequereviter_type);

  1064 	if (it == NULL)

  1065 		return NULL;

  1066 	it->b = deque->rightblock;

  1067 	it->index = deque->rightindex;

  1068 	Py_INCREF(deque);

  1069 	it->deque = deque;

  1070 	it->state = deque->state;

  1071 	it->counter = deque->len;

  1072 	return (PyObject *)it;

  1073 }

  1074 

  1075 static PyObject *

  1076 dequereviter_next(dequeiterobject *it)

  1077 {

  1078 	PyObject *item;

  1079 	if (it->counter == 0)

  1080 		return NULL;

  1081 

  1082 	if (it->deque->state != it->state) {

  1083 		it->counter = 0;

  1084 		PyErr_SetString(PyExc_RuntimeError,

  1085 				"deque mutated during iteration");

  1086 		return NULL;

  1087 	}

  1088 	assert (!(it->b == it->deque->leftblock &&

  1089 		  it->index < it->deque->leftindex));

  1090 

  1091 	item = it->b->data[it->index];

  1092 	it->index--;

  1093 	it->counter--;

  1094 	if (it->index == -1 && it->counter > 0) {

  1095 		assert (it->b->leftlink != NULL);

  1096 		it->b = it->b->leftlink;

  1097 		it->index = BLOCKLEN - 1;

  1098 	}

  1099 	Py_INCREF(item);

  1100 	return item;

  1101 }

  1102 

  1103 static PyTypeObject dequereviter_type = {

  1104 	PyVarObject_HEAD_INIT(NULL, 0)

  1105 	"deque_reverse_iterator",		/* tp_name */

  1106 	sizeof(dequeiterobject),		/* tp_basicsize */

  1107 	0,					/* tp_itemsize */

  1108 	/* methods */

  1109 	(destructor)dequeiter_dealloc,		/* tp_dealloc */

  1110 	0,					/* tp_print */

  1111 	0,					/* tp_getattr */

  1112 	0,					/* tp_setattr */

  1113 	0,					/* tp_compare */

  1114 	0,					/* tp_repr */

  1115 	0,					/* tp_as_number */

  1116 	0,					/* tp_as_sequence */

  1117 	0,					/* tp_as_mapping */

  1118 	0,					/* tp_hash */

  1119 	0,					/* tp_call */

  1120 	0,					/* tp_str */

  1121 	PyObject_GenericGetAttr,		/* tp_getattro */

  1122 	0,					/* tp_setattro */

  1123 	0,					/* tp_as_buffer */

  1124 	Py_TPFLAGS_DEFAULT,			/* tp_flags */

  1125 	0,					/* tp_doc */

  1126 	0,					/* tp_traverse */

  1127 	0,					/* tp_clear */

  1128 	0,					/* tp_richcompare */

  1129 	0,					/* tp_weaklistoffset */

  1130 	PyObject_SelfIter,			/* tp_iter */

  1131 	(iternextfunc)dequereviter_next,	/* tp_iternext */

  1132 	dequeiter_methods,			/* tp_methods */

  1133 	0,

  1134 };

  1135