Python code coverage for Modules/_collectionsmodule.c

#	count	content
1	n/a	#include "Python.h"
2	n/a	#include "structmember.h"
3	n/a
4	n/a	#ifdef STDC_HEADERS
5	n/a	#include <stddef.h>
6	n/a	#else
7	n/a	#include <sys/types.h> /* For size_t */
8	n/a	#endif
9	n/a
10	n/a	/* collections module implementation of a deque() datatype
11	n/a	Written and maintained by Raymond D. Hettinger <python@rcn.com>
12	n/a	*/
13	n/a
14	n/a	/* The block length may be set to any number over 1. Larger numbers
15	n/a	* reduce the number of calls to the memory allocator, give faster
16	n/a	* indexing and rotation, and reduce the link to data overhead ratio.
17	n/a	* Making the block length a power of two speeds-up the modulo
18	n/a	* and division calculations in deque_item() and deque_ass_item().
19	n/a	*/
20	n/a
21	n/a	#define BLOCKLEN 64
22	n/a	#define CENTER ((BLOCKLEN - 1) / 2)
23	n/a
24	n/a	/* Data for deque objects is stored in a doubly-linked list of fixed
25	n/a	* length blocks. This assures that appends or pops never move any
26	n/a	* other data elements besides the one being appended or popped.
27	n/a	*
28	n/a	* Another advantage is that it completely avoids use of realloc(),
29	n/a	* resulting in more predictable performance.
30	n/a	*
31	n/a	* Textbook implementations of doubly-linked lists store one datum
32	n/a	* per link, but that gives them a 200% memory overhead (a prev and
33	n/a	* next link for each datum) and it costs one malloc() call per data
34	n/a	* element. By using fixed-length blocks, the link to data ratio is
35	n/a	* significantly improved and there are proportionally fewer calls
36	n/a	* to malloc() and free(). The data blocks of consecutive pointers
37	n/a	* also improve cache locality.
38	n/a	*
39	n/a	* The list of blocks is never empty, so d.leftblock and d.rightblock
40	n/a	* are never equal to NULL. The list is not circular.
41	n/a	*
42	n/a	* A deque d's first element is at d.leftblock[leftindex]
43	n/a	* and its last element is at d.rightblock[rightindex].
44	n/a	*
45	n/a	* Unlike Python slice indices, these indices are inclusive on both
46	n/a	* ends. This makes the algorithms for left and right operations
47	n/a	* more symmetrical and it simplifies the design.
48	n/a	*
49	n/a	* The indices, d.leftindex and d.rightindex are always in the range:
50	n/a	* 0 <= index < BLOCKLEN
51	n/a	*
52	n/a	* And their exact relationship is:
53	n/a	* (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
54	n/a	*
55	n/a	* Whenever d.leftblock == d.rightblock, then:
56	n/a	* d.leftindex + d.len - 1 == d.rightindex
57	n/a	*
58	n/a	* However, when d.leftblock != d.rightblock, the d.leftindex and
59	n/a	* d.rightindex become indices into distinct blocks and either may
60	n/a	* be larger than the other.
61	n/a	*
62	n/a	* Empty deques have:
63	n/a	* d.len == 0
64	n/a	* d.leftblock == d.rightblock
65	n/a	* d.leftindex == CENTER + 1
66	n/a	* d.rightindex == CENTER
67	n/a	*
68	n/a	* Checking for d.len == 0 is the intended way to see whether d is empty.
69	n/a	*/
70	n/a
71	n/a	typedef struct BLOCK {
72	n/a	struct BLOCK *leftlink;
73	n/a	PyObject *data[BLOCKLEN];
74	n/a	struct BLOCK *rightlink;
75	n/a	} block;
76	n/a
77	n/a	typedef struct {
78	n/a	PyObject_VAR_HEAD
79	n/a	block *leftblock;
80	n/a	block *rightblock;
81	n/a	Py_ssize_t leftindex; /* 0 <= leftindex < BLOCKLEN */
82	n/a	Py_ssize_t rightindex; /* 0 <= rightindex < BLOCKLEN */
83	n/a	size_t state; /* incremented whenever the indices move */
84	n/a	Py_ssize_t maxlen; /* maxlen is -1 for unbounded deques */
85	n/a	PyObject *weakreflist;
86	n/a	} dequeobject;
87	n/a
88	n/a	static PyTypeObject deque_type;
89	n/a
90	n/a	/* For debug builds, add error checking to track the endpoints
91	n/a	* in the chain of links. The goal is to make sure that link
92	n/a	* assignments only take place at endpoints so that links already
93	n/a	* in use do not get overwritten.
94	n/a	*
95	n/a	* CHECK_END should happen before each assignment to a block's link field.
96	n/a	* MARK_END should happen whenever a link field becomes a new endpoint.
97	n/a	* This happens when new blocks are added or whenever an existing
98	n/a	* block is freed leaving another existing block as the new endpoint.
99	n/a	*/
100	n/a
101	n/a	#ifndef NDEBUG
102	n/a	#define MARK_END(link) link = NULL;
103	n/a	#define CHECK_END(link) assert(link == NULL);
104	n/a	#define CHECK_NOT_END(link) assert(link != NULL);
105	n/a	#else
106	n/a	#define MARK_END(link)
107	n/a	#define CHECK_END(link)
108	n/a	#define CHECK_NOT_END(link)
109	n/a	#endif
110	n/a
111	n/a	/* A simple freelisting scheme is used to minimize calls to the memory
112	n/a	allocator. It accommodates common use cases where new blocks are being
113	n/a	added at about the same rate as old blocks are being freed.
114	n/a	*/
115	n/a
116	n/a	#define MAXFREEBLOCKS 16
117	n/a	static Py_ssize_t numfreeblocks = 0;
118	n/a	static block *freeblocks[MAXFREEBLOCKS];
119	n/a
120	n/a	static block *
121	n/a	newblock(void) {
122	n/a	block *b;
123	n/a	if (numfreeblocks) {
124	n/a	numfreeblocks--;
125	n/a	return freeblocks[numfreeblocks];
126	n/a	}
127	n/a	b = PyMem_Malloc(sizeof(block));
128	n/a	if (b != NULL) {
129	n/a	return b;
130	n/a	}
131	n/a	PyErr_NoMemory();
132	n/a	return NULL;
133	n/a	}
134	n/a
135	n/a	static void
136	n/a	freeblock(block *b)
137	n/a	{
138	n/a	if (numfreeblocks < MAXFREEBLOCKS) {
139	n/a	freeblocks[numfreeblocks] = b;
140	n/a	numfreeblocks++;
141	n/a	} else {
142	n/a	PyMem_Free(b);
143	n/a	}
144	n/a	}
145	n/a
146	n/a	static PyObject *
147	n/a	deque_new(PyTypeObject type, PyObject args, PyObject *kwds)
148	n/a	{
149	n/a	dequeobject *deque;
150	n/a	block *b;
151	n/a
152	n/a	/* create dequeobject structure */
153	n/a	deque = (dequeobject *)type->tp_alloc(type, 0);
154	n/a	if (deque == NULL)
155	n/a	return NULL;
156	n/a
157	n/a	b = newblock();
158	n/a	if (b == NULL) {
159	n/a	Py_DECREF(deque);
160	n/a	return NULL;
161	n/a	}
162	n/a	MARK_END(b->leftlink);
163	n/a	MARK_END(b->rightlink);
164	n/a
165	n/a	assert(BLOCKLEN >= 2);
166	n/a	Py_SIZE(deque) = 0;
167	n/a	deque->leftblock = b;
168	n/a	deque->rightblock = b;
169	n/a	deque->leftindex = CENTER + 1;
170	n/a	deque->rightindex = CENTER;
171	n/a	deque->state = 0;
172	n/a	deque->maxlen = -1;
173	n/a	deque->weakreflist = NULL;
174	n/a
175	n/a	return (PyObject *)deque;
176	n/a	}
177	n/a
178	n/a	static PyObject *
179	n/a	deque_pop(dequeobject deque, PyObject unused)
180	n/a	{
181	n/a	PyObject *item;
182	n/a	block *prevblock;
183	n/a
184	n/a	if (Py_SIZE(deque) == 0) {
185	n/a	PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
186	n/a	return NULL;
187	n/a	}
188	n/a	item = deque->rightblock->data[deque->rightindex];
189	n/a	deque->rightindex--;
190	n/a	Py_SIZE(deque)--;
191	n/a	deque->state++;
192	n/a
193	n/a	if (deque->rightindex < 0) {
194	n/a	if (Py_SIZE(deque)) {
195	n/a	prevblock = deque->rightblock->leftlink;
196	n/a	assert(deque->leftblock != deque->rightblock);
197	n/a	freeblock(deque->rightblock);
198	n/a	CHECK_NOT_END(prevblock);
199	n/a	MARK_END(prevblock->rightlink);
200	n/a	deque->rightblock = prevblock;
201	n/a	deque->rightindex = BLOCKLEN - 1;
202	n/a	} else {
203	n/a	assert(deque->leftblock == deque->rightblock);
204	n/a	assert(deque->leftindex == deque->rightindex+1);
205	n/a	/* re-center instead of freeing a block */
206	n/a	deque->leftindex = CENTER + 1;
207	n/a	deque->rightindex = CENTER;
208	n/a	}
209	n/a	}
210	n/a	return item;
211	n/a	}
212	n/a
213	n/a	PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
214	n/a
215	n/a	static PyObject *
216	n/a	deque_popleft(dequeobject deque, PyObject unused)
217	n/a	{
218	n/a	PyObject *item;
219	n/a	block *prevblock;
220	n/a
221	n/a	if (Py_SIZE(deque) == 0) {
222	n/a	PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
223	n/a	return NULL;
224	n/a	}
225	n/a	assert(deque->leftblock != NULL);
226	n/a	item = deque->leftblock->data[deque->leftindex];
227	n/a	deque->leftindex++;
228	n/a	Py_SIZE(deque)--;
229	n/a	deque->state++;
230	n/a
231	n/a	if (deque->leftindex == BLOCKLEN) {
232	n/a	if (Py_SIZE(deque)) {
233	n/a	assert(deque->leftblock != deque->rightblock);
234	n/a	prevblock = deque->leftblock->rightlink;
235	n/a	freeblock(deque->leftblock);
236	n/a	CHECK_NOT_END(prevblock);
237	n/a	MARK_END(prevblock->leftlink);
238	n/a	deque->leftblock = prevblock;
239	n/a	deque->leftindex = 0;
240	n/a	} else {
241	n/a	assert(deque->leftblock == deque->rightblock);
242	n/a	assert(deque->leftindex == deque->rightindex+1);
243	n/a	/* re-center instead of freeing a block */
244	n/a	deque->leftindex = CENTER + 1;
245	n/a	deque->rightindex = CENTER;
246	n/a	}
247	n/a	}
248	n/a	return item;
249	n/a	}
250	n/a
251	n/a	PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
252	n/a
253	n/a	/* The deque's size limit is d.maxlen. The limit can be zero or positive.
254	n/a	* If there is no limit, then d.maxlen == -1.
255	n/a	*
256	n/a	* After an item is added to a deque, we check to see if the size has
257	n/a	* grown past the limit. If it has, we get the size back down to the limit
258	n/a	* by popping an item off of the opposite end. The methods that can
259	n/a	* trigger this are append(), appendleft(), extend(), and extendleft().
260	n/a	*
261	n/a	* The macro to check whether a deque needs to be trimmed uses a single
262	n/a	* unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
263	n/a	*/
264	n/a
265	n/a	#define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))
266	n/a
267	n/a	static int
268	n/a	deque_append_internal(dequeobject deque, PyObject item, Py_ssize_t maxlen)
269	n/a	{
270	n/a	if (deque->rightindex == BLOCKLEN - 1) {
271	n/a	block *b = newblock();
272	n/a	if (b == NULL)
273	n/a	return -1;
274	n/a	b->leftlink = deque->rightblock;
275	n/a	CHECK_END(deque->rightblock->rightlink);
276	n/a	deque->rightblock->rightlink = b;
277	n/a	deque->rightblock = b;
278	n/a	MARK_END(b->rightlink);
279	n/a	deque->rightindex = -1;
280	n/a	}
281	n/a	Py_SIZE(deque)++;
282	n/a	deque->rightindex++;
283	n/a	deque->rightblock->data[deque->rightindex] = item;
284	n/a	if (NEEDS_TRIM(deque, maxlen)) {
285	n/a	PyObject *olditem = deque_popleft(deque, NULL);
286	n/a	Py_DECREF(olditem);
287	n/a	} else {
288	n/a	deque->state++;
289	n/a	}
290	n/a	return 0;
291	n/a	}
292	n/a
293	n/a	static PyObject *
294	n/a	deque_append(dequeobject deque, PyObject item)
295	n/a	{
296	n/a	Py_INCREF(item);
297	n/a	if (deque_append_internal(deque, item, deque->maxlen) < 0)
298	n/a	return NULL;
299	n/a	Py_RETURN_NONE;
300	n/a	}
301	n/a
302	n/a	PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
303	n/a
304	n/a	static int
305	n/a	deque_appendleft_internal(dequeobject deque, PyObject item, Py_ssize_t maxlen)
306	n/a	{
307	n/a	if (deque->leftindex == 0) {
308	n/a	block *b = newblock();
309	n/a	if (b == NULL)
310	n/a	return -1;
311	n/a	b->rightlink = deque->leftblock;
312	n/a	CHECK_END(deque->leftblock->leftlink);
313	n/a	deque->leftblock->leftlink = b;
314	n/a	deque->leftblock = b;
315	n/a	MARK_END(b->leftlink);
316	n/a	deque->leftindex = BLOCKLEN;
317	n/a	}
318	n/a	Py_SIZE(deque)++;
319	n/a	deque->leftindex--;
320	n/a	deque->leftblock->data[deque->leftindex] = item;
321	n/a	if (NEEDS_TRIM(deque, deque->maxlen)) {
322	n/a	PyObject *olditem = deque_pop(deque, NULL);
323	n/a	Py_DECREF(olditem);
324	n/a	} else {
325	n/a	deque->state++;
326	n/a	}
327	n/a	return 0;
328	n/a	}
329	n/a
330	n/a	static PyObject *
331	n/a	deque_appendleft(dequeobject deque, PyObject item)
332	n/a	{
333	n/a	Py_INCREF(item);
334	n/a	if (deque_appendleft_internal(deque, item, deque->maxlen) < 0)
335	n/a	return NULL;
336	n/a	Py_RETURN_NONE;
337	n/a	}
338	n/a
339	n/a	PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
340	n/a
341	n/a	static PyObject*
342	n/a	finalize_iterator(PyObject *it)
343	n/a	{
344	n/a	if (PyErr_Occurred()) {
345	n/a	if (PyErr_ExceptionMatches(PyExc_StopIteration))
346	n/a	PyErr_Clear();
347	n/a	else {
348	n/a	Py_DECREF(it);
349	n/a	return NULL;
350	n/a	}
351	n/a	}
352	n/a	Py_DECREF(it);
353	n/a	Py_RETURN_NONE;
354	n/a	}
355	n/a
356	n/a	/* Run an iterator to exhaustion. Shortcut for
357	n/a	the extend/extendleft methods when maxlen == 0. */
358	n/a	static PyObject*
359	n/a	consume_iterator(PyObject *it)
360	n/a	{
361	n/a	PyObject (iternext)(PyObject *);
362	n/a	PyObject *item;
363	n/a
364	n/a	iternext = *Py_TYPE(it)->tp_iternext;
365	n/a	while ((item = iternext(it)) != NULL) {
366	n/a	Py_DECREF(item);
367	n/a	}
368	n/a	return finalize_iterator(it);
369	n/a	}
370	n/a
371	n/a	static PyObject *
372	n/a	deque_extend(dequeobject deque, PyObject iterable)
373	n/a	{
374	n/a	PyObject it, item;
375	n/a	PyObject (iternext)(PyObject *);
376	n/a	Py_ssize_t maxlen = deque->maxlen;
377	n/a
378	n/a	/* Handle case where id(deque) == id(iterable) */
379	n/a	if ((PyObject *)deque == iterable) {
380	n/a	PyObject *result;
381	n/a	PyObject *s = PySequence_List(iterable);
382	n/a	if (s == NULL)
383	n/a	return NULL;
384	n/a	result = deque_extend(deque, s);
385	n/a	Py_DECREF(s);
386	n/a	return result;
387	n/a	}
388	n/a
389	n/a	it = PyObject_GetIter(iterable);
390	n/a	if (it == NULL)
391	n/a	return NULL;
392	n/a
393	n/a	if (maxlen == 0)
394	n/a	return consume_iterator(it);
395	n/a
396	n/a	/* Space saving heuristic. Start filling from the left */
397	n/a	if (Py_SIZE(deque) == 0) {
398	n/a	assert(deque->leftblock == deque->rightblock);
399	n/a	assert(deque->leftindex == deque->rightindex+1);
400	n/a	deque->leftindex = 1;
401	n/a	deque->rightindex = 0;
402	n/a	}
403	n/a
404	n/a	iternext = *Py_TYPE(it)->tp_iternext;
405	n/a	while ((item = iternext(it)) != NULL) {
406	n/a	if (deque->rightindex == BLOCKLEN - 1) {
407	n/a	block *b = newblock();
408	n/a	if (b == NULL) {
409	n/a	Py_DECREF(item);
410	n/a	Py_DECREF(it);
411	n/a	return NULL;
412	n/a	}
413	n/a	b->leftlink = deque->rightblock;
414	n/a	CHECK_END(deque->rightblock->rightlink);
415	n/a	deque->rightblock->rightlink = b;
416	n/a	deque->rightblock = b;
417	n/a	MARK_END(b->rightlink);
418	n/a	deque->rightindex = -1;
419	n/a	}
420	n/a	Py_SIZE(deque)++;
421	n/a	deque->rightindex++;
422	n/a	deque->rightblock->data[deque->rightindex] = item;
423	n/a	if (NEEDS_TRIM(deque, maxlen)) {
424	n/a	PyObject *olditem = deque_popleft(deque, NULL);
425	n/a	Py_DECREF(olditem);
426	n/a	} else {
427	n/a	deque->state++;
428	n/a	}
429	n/a	}
430	n/a	return finalize_iterator(it);
431	n/a	}
432	n/a
433	n/a	PyDoc_STRVAR(extend_doc,
434	n/a	"Extend the right side of the deque with elements from the iterable");
435	n/a
436	n/a	static PyObject *
437	n/a	deque_extendleft(dequeobject deque, PyObject iterable)
438	n/a	{
439	n/a	PyObject it, item;
440	n/a	PyObject (iternext)(PyObject *);
441	n/a	Py_ssize_t maxlen = deque->maxlen;
442	n/a
443	n/a	/* Handle case where id(deque) == id(iterable) */
444	n/a	if ((PyObject *)deque == iterable) {
445	n/a	PyObject *result;
446	n/a	PyObject *s = PySequence_List(iterable);
447	n/a	if (s == NULL)
448	n/a	return NULL;
449	n/a	result = deque_extendleft(deque, s);
450	n/a	Py_DECREF(s);
451	n/a	return result;
452	n/a	}
453	n/a
454	n/a	it = PyObject_GetIter(iterable);
455	n/a	if (it == NULL)
456	n/a	return NULL;
457	n/a
458	n/a	if (maxlen == 0)
459	n/a	return consume_iterator(it);
460	n/a
461	n/a	/* Space saving heuristic. Start filling from the right */
462	n/a	if (Py_SIZE(deque) == 0) {
463	n/a	assert(deque->leftblock == deque->rightblock);
464	n/a	assert(deque->leftindex == deque->rightindex+1);
465	n/a	deque->leftindex = BLOCKLEN - 1;
466	n/a	deque->rightindex = BLOCKLEN - 2;
467	n/a	}
468	n/a
469	n/a	iternext = *Py_TYPE(it)->tp_iternext;
470	n/a	while ((item = iternext(it)) != NULL) {
471	n/a	if (deque->leftindex == 0) {
472	n/a	block *b = newblock();
473	n/a	if (b == NULL) {
474	n/a	Py_DECREF(item);
475	n/a	Py_DECREF(it);
476	n/a	return NULL;
477	n/a	}
478	n/a	b->rightlink = deque->leftblock;
479	n/a	CHECK_END(deque->leftblock->leftlink);
480	n/a	deque->leftblock->leftlink = b;
481	n/a	deque->leftblock = b;
482	n/a	MARK_END(b->leftlink);
483	n/a	deque->leftindex = BLOCKLEN;
484	n/a	}
485	n/a	Py_SIZE(deque)++;
486	n/a	deque->leftindex--;
487	n/a	deque->leftblock->data[deque->leftindex] = item;
488	n/a	if (NEEDS_TRIM(deque, maxlen)) {
489	n/a	PyObject *olditem = deque_pop(deque, NULL);
490	n/a	Py_DECREF(olditem);
491	n/a	} else {
492	n/a	deque->state++;
493	n/a	}
494	n/a	}
495	n/a	return finalize_iterator(it);
496	n/a	}
497	n/a
498	n/a	PyDoc_STRVAR(extendleft_doc,
499	n/a	"Extend the left side of the deque with elements from the iterable");
500	n/a
501	n/a	static PyObject *
502	n/a	deque_inplace_concat(dequeobject deque, PyObject other)
503	n/a	{
504	n/a	PyObject *result;
505	n/a
506	n/a	result = deque_extend(deque, other);
507	n/a	if (result == NULL)
508	n/a	return result;
509	n/a	Py_INCREF(deque);
510	n/a	Py_DECREF(result);
511	n/a	return (PyObject *)deque;
512	n/a	}
513	n/a
514	n/a	static PyObject *
515	n/a	deque_copy(PyObject *deque)
516	n/a	{
517	n/a	dequeobject old_deque = (dequeobject )deque;
518	n/a	if (Py_TYPE(deque) == &deque_type) {
519	n/a	dequeobject *new_deque;
520	n/a	PyObject *rv;
521	n/a
522	n/a	new_deque = (dequeobject )deque_new(&deque_type, (PyObject )NULL, (PyObject *)NULL);
523	n/a	if (new_deque == NULL)
524	n/a	return NULL;
525	n/a	new_deque->maxlen = old_deque->maxlen;
526	n/a	/* Fast path for the deque_repeat() common case where len(deque) == 1 */
527	n/a	if (Py_SIZE(deque) == 1) {
528	n/a	PyObject *item = old_deque->leftblock->data[old_deque->leftindex];
529	n/a	rv = deque_append(new_deque, item);
530	n/a	} else {
531	n/a	rv = deque_extend(new_deque, deque);
532	n/a	}
533	n/a	if (rv != NULL) {
534	n/a	Py_DECREF(rv);
535	n/a	return (PyObject *)new_deque;
536	n/a	}
537	n/a	Py_DECREF(new_deque);
538	n/a	return NULL;
539	n/a	}
540	n/a	if (old_deque->maxlen < 0)
541	n/a	return PyObject_CallFunctionObjArgs((PyObject *)(Py_TYPE(deque)),
542	n/a	deque, NULL);
543	n/a	else
544	n/a	return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
545	n/a	deque, old_deque->maxlen, NULL);
546	n/a	}
547	n/a
548	n/a	PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
549	n/a
550	n/a	static PyObject *
551	n/a	deque_concat(dequeobject deque, PyObject other)
552	n/a	{
553	n/a	PyObject new_deque, result;
554	n/a	int rv;
555	n/a
556	n/a	rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
557	n/a	if (rv <= 0) {
558	n/a	if (rv == 0) {
559	n/a	PyErr_Format(PyExc_TypeError,
560	n/a	"can only concatenate deque (not \"%.200s\") to deque",
561	n/a	other->ob_type->tp_name);
562	n/a	}
563	n/a	return NULL;
564	n/a	}
565	n/a
566	n/a	new_deque = deque_copy((PyObject *)deque);
567	n/a	if (new_deque == NULL)
568	n/a	return NULL;
569	n/a	result = deque_extend((dequeobject *)new_deque, other);
570	n/a	if (result == NULL) {
571	n/a	Py_DECREF(new_deque);
572	n/a	return NULL;
573	n/a	}
574	n/a	Py_DECREF(result);
575	n/a	return new_deque;
576	n/a	}
577	n/a
578	n/a	static void
579	n/a	deque_clear(dequeobject *deque)
580	n/a	{
581	n/a	block *b;
582	n/a	block *prevblock;
583	n/a	block *leftblock;
584	n/a	Py_ssize_t leftindex;
585	n/a	Py_ssize_t n, m;
586	n/a	PyObject *item;
587	n/a	PyObject itemptr, limit;
588	n/a
589	n/a	if (Py_SIZE(deque) == 0)
590	n/a	return;
591	n/a
592	n/a	/* During the process of clearing a deque, decrefs can cause the
593	n/a	deque to mutate. To avoid fatal confusion, we have to make the
594	n/a	deque empty before clearing the blocks and never refer to
595	n/a	anything via deque->ref while clearing. (This is the same
596	n/a	technique used for clearing lists, sets, and dicts.)
597	n/a
598	n/a	Making the deque empty requires allocating a new empty block. In
599	n/a	the unlikely event that memory is full, we fall back to an
600	n/a	alternate method that doesn't require a new block. Repeating
601	n/a	pops in a while-loop is slower, possibly re-entrant (and a clever
602	n/a	adversary could cause it to never terminate).
603	n/a	*/
604	n/a
605	n/a	b = newblock();
606	n/a	if (b == NULL) {
607	n/a	PyErr_Clear();
608	n/a	goto alternate_method;
609	n/a	}
610	n/a
611	n/a	/* Remember the old size, leftblock, and leftindex */
612	n/a	n = Py_SIZE(deque);
613	n/a	leftblock = deque->leftblock;
614	n/a	leftindex = deque->leftindex;
615	n/a
616	n/a	/* Set the deque to be empty using the newly allocated block */
617	n/a	MARK_END(b->leftlink);
618	n/a	MARK_END(b->rightlink);
619	n/a	Py_SIZE(deque) = 0;
620	n/a	deque->leftblock = b;
621	n/a	deque->rightblock = b;
622	n/a	deque->leftindex = CENTER + 1;
623	n/a	deque->rightindex = CENTER;
624	n/a	deque->state++;
625	n/a
626	n/a	/* Now the old size, leftblock, and leftindex are disconnected from
627	n/a	the empty deque and we can use them to decref the pointers.
628	n/a	*/
629	n/a	m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex;
630	n/a	itemptr = &leftblock->data[leftindex];
631	n/a	limit = itemptr + m;
632	n/a	n -= m;
633	n/a	while (1) {
634	n/a	if (itemptr == limit) {
635	n/a	if (n == 0)
636	n/a	break;
637	n/a	CHECK_NOT_END(leftblock->rightlink);
638	n/a	prevblock = leftblock;
639	n/a	leftblock = leftblock->rightlink;
640	n/a	m = (n > BLOCKLEN) ? BLOCKLEN : n;
641	n/a	itemptr = leftblock->data;
642	n/a	limit = itemptr + m;
643	n/a	n -= m;
644	n/a	freeblock(prevblock);
645	n/a	}
646	n/a	item = *(itemptr++);
647	n/a	Py_DECREF(item);
648	n/a	}
649	n/a	CHECK_END(leftblock->rightlink);
650	n/a	freeblock(leftblock);
651	n/a	return;
652	n/a
653	n/a	alternate_method:
654	n/a	while (Py_SIZE(deque)) {
655	n/a	item = deque_pop(deque, NULL);
656	n/a	assert (item != NULL);
657	n/a	Py_DECREF(item);
658	n/a	}
659	n/a	}
660	n/a
661	n/a	static PyObject *
662	n/a	deque_clearmethod(dequeobject *deque)
663	n/a	{
664	n/a	deque_clear(deque);
665	n/a	Py_RETURN_NONE;
666	n/a	}
667	n/a
668	n/a	PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
669	n/a
670	n/a	static PyObject *
671	n/a	deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
672	n/a	{
673	n/a	Py_ssize_t i, m, size;
674	n/a	PyObject *seq;
675	n/a	PyObject *rv;
676	n/a
677	n/a	size = Py_SIZE(deque);
678	n/a	if (size == 0 \|\| n == 1) {
679	n/a	Py_INCREF(deque);
680	n/a	return (PyObject *)deque;
681	n/a	}
682	n/a
683	n/a	if (n <= 0) {
684	n/a	deque_clear(deque);
685	n/a	Py_INCREF(deque);
686	n/a	return (PyObject *)deque;
687	n/a	}
688	n/a
689	n/a	if (size == 1) {
690	n/a	/* common case, repeating a single element */
691	n/a	PyObject *item = deque->leftblock->data[deque->leftindex];
692	n/a
693	n/a	if (deque->maxlen >= 0 && n > deque->maxlen)
694	n/a	n = deque->maxlen;
695	n/a
696	n/a	deque->state++;
697	n/a	for (i = 0 ; i < n-1 ; ) {
698	n/a	if (deque->rightindex == BLOCKLEN - 1) {
699	n/a	block *b = newblock();
700	n/a	if (b == NULL) {
701	n/a	Py_SIZE(deque) += i;
702	n/a	return NULL;
703	n/a	}
704	n/a	b->leftlink = deque->rightblock;
705	n/a	CHECK_END(deque->rightblock->rightlink);
706	n/a	deque->rightblock->rightlink = b;
707	n/a	deque->rightblock = b;
708	n/a	MARK_END(b->rightlink);
709	n/a	deque->rightindex = -1;
710	n/a	}
711	n/a	m = n - 1 - i;
712	n/a	if (m > BLOCKLEN - 1 - deque->rightindex)
713	n/a	m = BLOCKLEN - 1 - deque->rightindex;
714	n/a	i += m;
715	n/a	while (m--) {
716	n/a	deque->rightindex++;
717	n/a	Py_INCREF(item);
718	n/a	deque->rightblock->data[deque->rightindex] = item;
719	n/a	}
720	n/a	}
721	n/a	Py_SIZE(deque) += i;
722	n/a	Py_INCREF(deque);
723	n/a	return (PyObject *)deque;
724	n/a	}
725	n/a
726	n/a	if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {
727	n/a	return PyErr_NoMemory();
728	n/a	}
729	n/a
730	n/a	seq = PySequence_List((PyObject *)deque);
731	n/a	if (seq == NULL)
732	n/a	return seq;
733	n/a
734	n/a	for (i = 0 ; i < n-1 ; i++) {
735	n/a	rv = deque_extend(deque, seq);
736	n/a	if (rv == NULL) {
737	n/a	Py_DECREF(seq);
738	n/a	return NULL;
739	n/a	}
740	n/a	Py_DECREF(rv);
741	n/a	}
742	n/a	Py_INCREF(deque);
743	n/a	Py_DECREF(seq);
744	n/a	return (PyObject *)deque;
745	n/a	}
746	n/a
747	n/a	static PyObject *
748	n/a	deque_repeat(dequeobject *deque, Py_ssize_t n)
749	n/a	{
750	n/a	dequeobject *new_deque;
751	n/a	PyObject *rv;
752	n/a
753	n/a	new_deque = (dequeobject )deque_copy((PyObject ) deque);
754	n/a	if (new_deque == NULL)
755	n/a	return NULL;
756	n/a	rv = deque_inplace_repeat(new_deque, n);
757	n/a	Py_DECREF(new_deque);
758	n/a	return rv;
759	n/a	}
760	n/a
761	n/a	/* The rotate() method is part of the public API and is used internally
762	n/a	as a primitive for other methods.
763	n/a
764	n/a	Rotation by 1 or -1 is a common case, so any optimizations for high
765	n/a	volume rotations should take care not to penalize the common case.
766	n/a
767	n/a	Conceptually, a rotate by one is equivalent to a pop on one side and an
768	n/a	append on the other. However, a pop/append pair is unnecessarily slow
769	n/a	because it requires an incref/decref pair for an object located randomly
770	n/a	in memory. It is better to just move the object pointer from one block
771	n/a	to the next without changing the reference count.
772	n/a
773	n/a	When moving batches of pointers, it is tempting to use memcpy() but that
774	n/a	proved to be slower than a simple loop for a variety of reasons.
775	n/a	Memcpy() cannot know in advance that we're copying pointers instead of
776	n/a	bytes, that the source and destination are pointer aligned and
777	n/a	non-overlapping, that moving just one pointer is a common case, that we
778	n/a	never need to move more than BLOCKLEN pointers, and that at least one
779	n/a	pointer is always moved.
780	n/a
781	n/a	For high volume rotations, newblock() and freeblock() are never called
782	n/a	more than once. Previously emptied blocks are immediately reused as a
783	n/a	destination block. If a block is left-over at the end, it is freed.
784	n/a	*/
785	n/a
786	n/a	static int
787	n/a	_deque_rotate(dequeobject *deque, Py_ssize_t n)
788	n/a	{
789	n/a	block *b = NULL;
790	n/a	block *leftblock = deque->leftblock;
791	n/a	block *rightblock = deque->rightblock;
792	n/a	Py_ssize_t leftindex = deque->leftindex;
793	n/a	Py_ssize_t rightindex = deque->rightindex;
794	n/a	Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
795	n/a	int rv = -1;
796	n/a
797	n/a	if (len <= 1)
798	n/a	return 0;
799	n/a	if (n > halflen \|\| n < -halflen) {
800	n/a	n %= len;
801	n/a	if (n > halflen)
802	n/a	n -= len;
803	n/a	else if (n < -halflen)
804	n/a	n += len;
805	n/a	}
806	n/a	assert(len > 1);
807	n/a	assert(-halflen <= n && n <= halflen);
808	n/a
809	n/a	deque->state++;
810	n/a	while (n > 0) {
811	n/a	if (leftindex == 0) {
812	n/a	if (b == NULL) {
813	n/a	b = newblock();
814	n/a	if (b == NULL)
815	n/a	goto done;
816	n/a	}
817	n/a	b->rightlink = leftblock;
818	n/a	CHECK_END(leftblock->leftlink);
819	n/a	leftblock->leftlink = b;
820	n/a	leftblock = b;
821	n/a	MARK_END(b->leftlink);
822	n/a	leftindex = BLOCKLEN;
823	n/a	b = NULL;
824	n/a	}
825	n/a	assert(leftindex > 0);
826	n/a	{
827	n/a	PyObject src, dest;
828	n/a	Py_ssize_t m = n;
829	n/a
830	n/a	if (m > rightindex + 1)
831	n/a	m = rightindex + 1;
832	n/a	if (m > leftindex)
833	n/a	m = leftindex;
834	n/a	assert (m > 0 && m <= len);
835	n/a	rightindex -= m;
836	n/a	leftindex -= m;
837	n/a	src = &rightblock->data[rightindex + 1];
838	n/a	dest = &leftblock->data[leftindex];
839	n/a	n -= m;
840	n/a	do {
841	n/a	(dest++) = (src++);
842	n/a	} while (--m);
843	n/a	}
844	n/a	if (rightindex < 0) {
845	n/a	assert(leftblock != rightblock);
846	n/a	assert(b == NULL);
847	n/a	b = rightblock;
848	n/a	CHECK_NOT_END(rightblock->leftlink);
849	n/a	rightblock = rightblock->leftlink;
850	n/a	MARK_END(rightblock->rightlink);
851	n/a	rightindex = BLOCKLEN - 1;
852	n/a	}
853	n/a	}
854	n/a	while (n < 0) {
855	n/a	if (rightindex == BLOCKLEN - 1) {
856	n/a	if (b == NULL) {
857	n/a	b = newblock();
858	n/a	if (b == NULL)
859	n/a	goto done;
860	n/a	}
861	n/a	b->leftlink = rightblock;
862	n/a	CHECK_END(rightblock->rightlink);
863	n/a	rightblock->rightlink = b;
864	n/a	rightblock = b;
865	n/a	MARK_END(b->rightlink);
866	n/a	rightindex = -1;
867	n/a	b = NULL;
868	n/a	}
869	n/a	assert (rightindex < BLOCKLEN - 1);
870	n/a	{
871	n/a	PyObject src, dest;
872	n/a	Py_ssize_t m = -n;
873	n/a
874	n/a	if (m > BLOCKLEN - leftindex)
875	n/a	m = BLOCKLEN - leftindex;
876	n/a	if (m > BLOCKLEN - 1 - rightindex)
877	n/a	m = BLOCKLEN - 1 - rightindex;
878	n/a	assert (m > 0 && m <= len);
879	n/a	src = &leftblock->data[leftindex];
880	n/a	dest = &rightblock->data[rightindex + 1];
881	n/a	leftindex += m;
882	n/a	rightindex += m;
883	n/a	n += m;
884	n/a	do {
885	n/a	(dest++) = (src++);
886	n/a	} while (--m);
887	n/a	}
888	n/a	if (leftindex == BLOCKLEN) {
889	n/a	assert(leftblock != rightblock);
890	n/a	assert(b == NULL);
891	n/a	b = leftblock;
892	n/a	CHECK_NOT_END(leftblock->rightlink);
893	n/a	leftblock = leftblock->rightlink;
894	n/a	MARK_END(leftblock->leftlink);
895	n/a	leftindex = 0;
896	n/a	}
897	n/a	}
898	n/a	rv = 0;
899	n/a	done:
900	n/a	if (b != NULL)
901	n/a	freeblock(b);
902	n/a	deque->leftblock = leftblock;
903	n/a	deque->rightblock = rightblock;
904	n/a	deque->leftindex = leftindex;
905	n/a	deque->rightindex = rightindex;
906	n/a
907	n/a	return rv;
908	n/a	}
909	n/a
910	n/a	static PyObject *
911	n/a	deque_rotate(dequeobject deque, PyObject *args, Py_ssize_t nargs,
912	n/a	PyObject *kwnames)
913	n/a	{
914	n/a	Py_ssize_t n=1;
915	n/a
916	n/a	if (!_PyArg_NoStackKeywords("rotate", kwnames)) {
917	n/a	return NULL;
918	n/a	}
919	n/a	if (!_PyArg_ParseStack(args, nargs, "\|n:rotate", &n)) {
920	n/a	return NULL;
921	n/a	}
922	n/a
923	n/a	if (!_deque_rotate(deque, n))
924	n/a	Py_RETURN_NONE;
925	n/a	return NULL;
926	n/a	}
927	n/a
928	n/a	PyDoc_STRVAR(rotate_doc,
929	n/a	"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
930	n/a
931	n/a	static PyObject *
932	n/a	deque_reverse(dequeobject deque, PyObject unused)
933	n/a	{
934	n/a	block *leftblock = deque->leftblock;
935	n/a	block *rightblock = deque->rightblock;
936	n/a	Py_ssize_t leftindex = deque->leftindex;
937	n/a	Py_ssize_t rightindex = deque->rightindex;
938	n/a	Py_ssize_t n = Py_SIZE(deque) >> 1;
939	n/a	PyObject *tmp;
940	n/a
941	n/a	n++;
942	n/a	while (--n) {
943	n/a	/* Validate that pointers haven't met in the middle */
944	n/a	assert(leftblock != rightblock \|\| leftindex < rightindex);
945	n/a	CHECK_NOT_END(leftblock);
946	n/a	CHECK_NOT_END(rightblock);
947	n/a
948	n/a	/* Swap */
949	n/a	tmp = leftblock->data[leftindex];
950	n/a	leftblock->data[leftindex] = rightblock->data[rightindex];
951	n/a	rightblock->data[rightindex] = tmp;
952	n/a
953	n/a	/* Advance left block/index pair */
954	n/a	leftindex++;
955	n/a	if (leftindex == BLOCKLEN) {
956	n/a	leftblock = leftblock->rightlink;
957	n/a	leftindex = 0;
958	n/a	}
959	n/a
960	n/a	/* Step backwards with the right block/index pair */
961	n/a	rightindex--;
962	n/a	if (rightindex < 0) {
963	n/a	rightblock = rightblock->leftlink;
964	n/a	rightindex = BLOCKLEN - 1;
965	n/a	}
966	n/a	}
967	n/a	Py_RETURN_NONE;
968	n/a	}
969	n/a
970	n/a	PyDoc_STRVAR(reverse_doc,
971	n/a	"D.reverse() -- reverse IN PLACE");
972	n/a
973	n/a	static PyObject *
974	n/a	deque_count(dequeobject deque, PyObject v)
975	n/a	{
976	n/a	block *b = deque->leftblock;
977	n/a	Py_ssize_t index = deque->leftindex;
978	n/a	Py_ssize_t n = Py_SIZE(deque);
979	n/a	Py_ssize_t count = 0;
980	n/a	size_t start_state = deque->state;
981	n/a	PyObject *item;
982	n/a	int cmp;
983	n/a
984	n/a	n++;
985	n/a	while (--n) {
986	n/a	CHECK_NOT_END(b);
987	n/a	item = b->data[index];
988	n/a	cmp = PyObject_RichCompareBool(item, v, Py_EQ);
989	n/a	if (cmp < 0)
990	n/a	return NULL;
991	n/a	count += cmp;
992	n/a
993	n/a	if (start_state != deque->state) {
994	n/a	PyErr_SetString(PyExc_RuntimeError,
995	n/a	"deque mutated during iteration");
996	n/a	return NULL;
997	n/a	}
998	n/a
999	n/a	/* Advance left block/index pair */
1000	n/a	index++;
1001	n/a	if (index == BLOCKLEN) {
1002	n/a	b = b->rightlink;
1003	n/a	index = 0;
1004	n/a	}
1005	n/a	}
1006	n/a	return PyLong_FromSsize_t(count);
1007	n/a	}
1008	n/a
1009	n/a	PyDoc_STRVAR(count_doc,
1010	n/a	"D.count(value) -> integer -- return number of occurrences of value");
1011	n/a
1012	n/a	static int
1013	n/a	deque_contains(dequeobject deque, PyObject v)
1014	n/a	{
1015	n/a	block *b = deque->leftblock;
1016	n/a	Py_ssize_t index = deque->leftindex;
1017	n/a	Py_ssize_t n = Py_SIZE(deque);
1018	n/a	size_t start_state = deque->state;
1019	n/a	PyObject *item;
1020	n/a	int cmp;
1021	n/a
1022	n/a	n++;
1023	n/a	while (--n) {
1024	n/a	CHECK_NOT_END(b);
1025	n/a	item = b->data[index];
1026	n/a	cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1027	n/a	if (cmp) {
1028	n/a	return cmp;
1029	n/a	}
1030	n/a	if (start_state != deque->state) {
1031	n/a	PyErr_SetString(PyExc_RuntimeError,
1032	n/a	"deque mutated during iteration");
1033	n/a	return -1;
1034	n/a	}
1035	n/a	index++;
1036	n/a	if (index == BLOCKLEN) {
1037	n/a	b = b->rightlink;
1038	n/a	index = 0;
1039	n/a	}
1040	n/a	}
1041	n/a	return 0;
1042	n/a	}
1043	n/a
1044	n/a	static Py_ssize_t
1045	n/a	deque_len(dequeobject *deque)
1046	n/a	{
1047	n/a	return Py_SIZE(deque);
1048	n/a	}
1049	n/a
1050	n/a	static PyObject *
1051	n/a	deque_index(dequeobject deque, PyObject *args, Py_ssize_t nargs,
1052	n/a	PyObject *kwnames)
1053	n/a	{
1054	n/a	Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
1055	n/a	PyObject v, item;
1056	n/a	block *b = deque->leftblock;
1057	n/a	Py_ssize_t index = deque->leftindex;
1058	n/a	size_t start_state = deque->state;
1059	n/a	int cmp;
1060	n/a
1061	n/a	if (!_PyArg_NoStackKeywords("index", kwnames)) {
1062	n/a	return NULL;
1063	n/a	}
1064	n/a	if (!_PyArg_ParseStack(args, nargs, "O\|O&O&:index", &v,
1065	n/a	_PyEval_SliceIndex, &start,
1066	n/a	_PyEval_SliceIndex, &stop)) {
1067	n/a	return NULL;
1068	n/a	}
1069	n/a
1070	n/a	if (start < 0) {
1071	n/a	start += Py_SIZE(deque);
1072	n/a	if (start < 0)
1073	n/a	start = 0;
1074	n/a	}
1075	n/a	if (stop < 0) {
1076	n/a	stop += Py_SIZE(deque);
1077	n/a	if (stop < 0)
1078	n/a	stop = 0;
1079	n/a	}
1080	n/a	if (stop > Py_SIZE(deque))
1081	n/a	stop = Py_SIZE(deque);
1082	n/a	if (start > stop)
1083	n/a	start = stop;
1084	n/a	assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
1085	n/a
1086	n/a	/* XXX Replace this loop with faster code from deque_item() */
1087	n/a	for (i=0 ; i<start ; i++) {
1088	n/a	index++;
1089	n/a	if (index == BLOCKLEN) {
1090	n/a	b = b->rightlink;
1091	n/a	index = 0;
1092	n/a	}
1093	n/a	}
1094	n/a
1095	n/a	n = stop - i + 1;
1096	n/a	while (--n) {
1097	n/a	CHECK_NOT_END(b);
1098	n/a	item = b->data[index];
1099	n/a	cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1100	n/a	if (cmp > 0)
1101	n/a	return PyLong_FromSsize_t(stop - n);
1102	n/a	if (cmp < 0)
1103	n/a	return NULL;
1104	n/a	if (start_state != deque->state) {
1105	n/a	PyErr_SetString(PyExc_RuntimeError,
1106	n/a	"deque mutated during iteration");
1107	n/a	return NULL;
1108	n/a	}
1109	n/a	index++;
1110	n/a	if (index == BLOCKLEN) {
1111	n/a	b = b->rightlink;
1112	n/a	index = 0;
1113	n/a	}
1114	n/a	}
1115	n/a	PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1116	n/a	return NULL;
1117	n/a	}
1118	n/a
1119	n/a	PyDoc_STRVAR(index_doc,
1120	n/a	"D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
1121	n/a	"Raises ValueError if the value is not present.");
1122	n/a
1123	n/a	/* insert(), remove(), and delitem() are implemented in terms of
1124	n/a	rotate() for simplicity and reasonable performance near the end
1125	n/a	points. If for some reason these methods become popular, it is not
1126	n/a	hard to re-implement this using direct data movement (similar to
1127	n/a	the code used in list slice assignments) and achieve a performance
1128	n/a	boost (by moving each pointer only once instead of twice).
1129	n/a	*/
1130	n/a
1131	n/a	static PyObject *
1132	n/a	deque_insert(dequeobject deque, PyObject *args, Py_ssize_t nargs,
1133	n/a	PyObject *kwnames)
1134	n/a	{
1135	n/a	Py_ssize_t index;
1136	n/a	Py_ssize_t n = Py_SIZE(deque);
1137	n/a	PyObject *value;
1138	n/a	PyObject *rv;
1139	n/a
1140	n/a	if (!_PyArg_NoStackKeywords("insert", kwnames)) {
1141	n/a	return NULL;
1142	n/a	}
1143	n/a	if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) {
1144	n/a	return NULL;
1145	n/a	}
1146	n/a
1147	n/a	if (deque->maxlen == Py_SIZE(deque)) {
1148	n/a	PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
1149	n/a	return NULL;
1150	n/a	}
1151	n/a	if (index >= n)
1152	n/a	return deque_append(deque, value);
1153	n/a	if (index <= -n \|\| index == 0)
1154	n/a	return deque_appendleft(deque, value);
1155	n/a	if (_deque_rotate(deque, -index))
1156	n/a	return NULL;
1157	n/a	if (index < 0)
1158	n/a	rv = deque_append(deque, value);
1159	n/a	else
1160	n/a	rv = deque_appendleft(deque, value);
1161	n/a	if (rv == NULL)
1162	n/a	return NULL;
1163	n/a	Py_DECREF(rv);
1164	n/a	if (_deque_rotate(deque, index))
1165	n/a	return NULL;
1166	n/a	Py_RETURN_NONE;
1167	n/a	}
1168	n/a
1169	n/a	PyDoc_STRVAR(insert_doc,
1170	n/a	"D.insert(index, object) -- insert object before index");
1171	n/a
1172	n/a	static PyObject *
1173	n/a	deque_remove(dequeobject deque, PyObject value)
1174	n/a	{
1175	n/a	Py_ssize_t i, n=Py_SIZE(deque);
1176	n/a
1177	n/a	for (i=0 ; i<n ; i++) {
1178	n/a	PyObject *item = deque->leftblock->data[deque->leftindex];
1179	n/a	int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
1180	n/a
1181	n/a	if (Py_SIZE(deque) != n) {
1182	n/a	PyErr_SetString(PyExc_IndexError,
1183	n/a	"deque mutated during remove().");
1184	n/a	return NULL;
1185	n/a	}
1186	n/a	if (cmp > 0) {
1187	n/a	PyObject *tgt = deque_popleft(deque, NULL);
1188	n/a	assert (tgt != NULL);
1189	n/a	if (_deque_rotate(deque, i))
1190	n/a	return NULL;
1191	n/a	Py_DECREF(tgt);
1192	n/a	Py_RETURN_NONE;
1193	n/a	}
1194	n/a	else if (cmp < 0) {
1195	n/a	_deque_rotate(deque, i);
1196	n/a	return NULL;
1197	n/a	}
1198	n/a	_deque_rotate(deque, -1);
1199	n/a	}
1200	n/a	PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
1201	n/a	return NULL;
1202	n/a	}
1203	n/a
1204	n/a	PyDoc_STRVAR(remove_doc,
1205	n/a	"D.remove(value) -- remove first occurrence of value.");
1206	n/a
1207	n/a	static int
1208	n/a	valid_index(Py_ssize_t i, Py_ssize_t limit)
1209	n/a	{
1210	n/a	/* The cast to size_t lets us use just a single comparison
1211	n/a	to check whether i is in the range: 0 <= i < limit */
1212	n/a	return (size_t) i < (size_t) limit;
1213	n/a	}
1214	n/a
1215	n/a	static PyObject *
1216	n/a	deque_item(dequeobject *deque, Py_ssize_t i)
1217	n/a	{
1218	n/a	block *b;
1219	n/a	PyObject *item;
1220	n/a	Py_ssize_t n, index=i;
1221	n/a
1222	n/a	if (!valid_index(i, Py_SIZE(deque))) {
1223	n/a	PyErr_SetString(PyExc_IndexError, "deque index out of range");
1224	n/a	return NULL;
1225	n/a	}
1226	n/a
1227	n/a	if (i == 0) {
1228	n/a	i = deque->leftindex;
1229	n/a	b = deque->leftblock;
1230	n/a	} else if (i == Py_SIZE(deque) - 1) {
1231	n/a	i = deque->rightindex;
1232	n/a	b = deque->rightblock;
1233	n/a	} else {
1234	n/a	i += deque->leftindex;
1235	n/a	n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1236	n/a	i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1237	n/a	if (index < (Py_SIZE(deque) >> 1)) {
1238	n/a	b = deque->leftblock;
1239	n/a	n++;
1240	n/a	while (--n)
1241	n/a	b = b->rightlink;
1242	n/a	} else {
1243	n/a	n = (Py_ssize_t)(
1244	n/a	((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1245	n/a	/ BLOCKLEN - n);
1246	n/a	b = deque->rightblock;
1247	n/a	n++;
1248	n/a	while (--n)
1249	n/a	b = b->leftlink;
1250	n/a	}
1251	n/a	}
1252	n/a	item = b->data[i];
1253	n/a	Py_INCREF(item);
1254	n/a	return item;
1255	n/a	}
1256	n/a
1257	n/a	static int
1258	n/a	deque_del_item(dequeobject *deque, Py_ssize_t i)
1259	n/a	{
1260	n/a	PyObject *item;
1261	n/a	int rv;
1262	n/a
1263	n/a	assert (i >= 0 && i < Py_SIZE(deque));
1264	n/a	if (_deque_rotate(deque, -i))
1265	n/a	return -1;
1266	n/a	item = deque_popleft(deque, NULL);
1267	n/a	rv = _deque_rotate(deque, i);
1268	n/a	assert (item != NULL);
1269	n/a	Py_DECREF(item);
1270	n/a	return rv;
1271	n/a	}
1272	n/a
1273	n/a	static int
1274	n/a	deque_ass_item(dequeobject deque, Py_ssize_t i, PyObject v)
1275	n/a	{
1276	n/a	PyObject *old_value;
1277	n/a	block *b;
1278	n/a	Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
1279	n/a
1280	n/a	if (!valid_index(i, len)) {
1281	n/a	PyErr_SetString(PyExc_IndexError, "deque index out of range");
1282	n/a	return -1;
1283	n/a	}
1284	n/a	if (v == NULL)
1285	n/a	return deque_del_item(deque, i);
1286	n/a
1287	n/a	i += deque->leftindex;
1288	n/a	n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1289	n/a	i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1290	n/a	if (index <= halflen) {
1291	n/a	b = deque->leftblock;
1292	n/a	n++;
1293	n/a	while (--n)
1294	n/a	b = b->rightlink;
1295	n/a	} else {
1296	n/a	n = (Py_ssize_t)(
1297	n/a	((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1298	n/a	/ BLOCKLEN - n);
1299	n/a	b = deque->rightblock;
1300	n/a	n++;
1301	n/a	while (--n)
1302	n/a	b = b->leftlink;
1303	n/a	}
1304	n/a	Py_INCREF(v);
1305	n/a	old_value = b->data[i];
1306	n/a	b->data[i] = v;
1307	n/a	Py_DECREF(old_value);
1308	n/a	return 0;
1309	n/a	}
1310	n/a
1311	n/a	static void
1312	n/a	deque_dealloc(dequeobject *deque)
1313	n/a	{
1314	n/a	PyObject_GC_UnTrack(deque);
1315	n/a	if (deque->weakreflist != NULL)
1316	n/a	PyObject_ClearWeakRefs((PyObject *) deque);
1317	n/a	if (deque->leftblock != NULL) {
1318	n/a	deque_clear(deque);
1319	n/a	assert(deque->leftblock != NULL);
1320	n/a	freeblock(deque->leftblock);
1321	n/a	}
1322	n/a	deque->leftblock = NULL;
1323	n/a	deque->rightblock = NULL;
1324	n/a	Py_TYPE(deque)->tp_free(deque);
1325	n/a	}
1326	n/a
1327	n/a	static int
1328	n/a	deque_traverse(dequeobject deque, visitproc visit, void arg)
1329	n/a	{
1330	n/a	block *b;
1331	n/a	PyObject *item;
1332	n/a	Py_ssize_t index;
1333	n/a	Py_ssize_t indexlo = deque->leftindex;
1334	n/a	Py_ssize_t indexhigh;
1335	n/a
1336	n/a	for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1337	n/a	for (index = indexlo; index < BLOCKLEN ; index++) {
1338	n/a	item = b->data[index];
1339	n/a	Py_VISIT(item);
1340	n/a	}
1341	n/a	indexlo = 0;
1342	n/a	}
1343	n/a	indexhigh = deque->rightindex;
1344	n/a	for (index = indexlo; index <= indexhigh; index++) {
1345	n/a	item = b->data[index];
1346	n/a	Py_VISIT(item);
1347	n/a	}
1348	n/a	return 0;
1349	n/a	}
1350	n/a
1351	n/a	static PyObject *
1352	n/a	deque_reduce(dequeobject *deque)
1353	n/a	{
1354	n/a	PyObject dict, it;
1355	n/a	_Py_IDENTIFIER(__dict__);
1356	n/a
1357	n/a	dict = _PyObject_GetAttrId((PyObject *)deque, &PyId___dict__);
1358	n/a	if (dict == NULL) {
1359	n/a	if (!PyErr_ExceptionMatches(PyExc_AttributeError)) {
1360	n/a	return NULL;
1361	n/a	}
1362	n/a	PyErr_Clear();
1363	n/a	dict = Py_None;
1364	n/a	Py_INCREF(dict);
1365	n/a	}
1366	n/a
1367	n/a	it = PyObject_GetIter((PyObject *)deque);
1368	n/a	if (it == NULL) {
1369	n/a	Py_DECREF(dict);
1370	n/a	return NULL;
1371	n/a	}
1372	n/a
1373	n/a	if (deque->maxlen < 0) {
1374	n/a	return Py_BuildValue("O()NN", Py_TYPE(deque), dict, it);
1375	n/a	}
1376	n/a	else {
1377	n/a	return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, dict, it);
1378	n/a	}
1379	n/a	}
1380	n/a
1381	n/a	PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1382	n/a
1383	n/a	static PyObject *
1384	n/a	deque_repr(PyObject *deque)
1385	n/a	{
1386	n/a	PyObject aslist, result;
1387	n/a	int i;
1388	n/a
1389	n/a	i = Py_ReprEnter(deque);
1390	n/a	if (i != 0) {
1391	n/a	if (i < 0)
1392	n/a	return NULL;
1393	n/a	return PyUnicode_FromString("[...]");
1394	n/a	}
1395	n/a
1396	n/a	aslist = PySequence_List(deque);
1397	n/a	if (aslist == NULL) {
1398	n/a	Py_ReprLeave(deque);
1399	n/a	return NULL;
1400	n/a	}
1401	n/a	if (((dequeobject *)deque)->maxlen >= 0)
1402	n/a	result = PyUnicode_FromFormat("deque(%R, maxlen=%zd)",
1403	n/a	aslist, ((dequeobject *)deque)->maxlen);
1404	n/a	else
1405	n/a	result = PyUnicode_FromFormat("deque(%R)", aslist);
1406	n/a	Py_ReprLeave(deque);
1407	n/a	Py_DECREF(aslist);
1408	n/a	return result;
1409	n/a	}
1410	n/a
1411	n/a	static PyObject *
1412	n/a	deque_richcompare(PyObject v, PyObject w, int op)
1413	n/a	{
1414	n/a	PyObject it1=NULL, it2=NULL, x, y;
1415	n/a	Py_ssize_t vs, ws;
1416	n/a	int b, cmp=-1;
1417	n/a
1418	n/a	if (!PyObject_TypeCheck(v, &deque_type) \|\|
1419	n/a	!PyObject_TypeCheck(w, &deque_type)) {
1420	n/a	Py_RETURN_NOTIMPLEMENTED;
1421	n/a	}
1422	n/a
1423	n/a	/* Shortcuts */
1424	n/a	vs = Py_SIZE((dequeobject *)v);
1425	n/a	ws = Py_SIZE((dequeobject *)w);
1426	n/a	if (op == Py_EQ) {
1427	n/a	if (v == w)
1428	n/a	Py_RETURN_TRUE;
1429	n/a	if (vs != ws)
1430	n/a	Py_RETURN_FALSE;
1431	n/a	}
1432	n/a	if (op == Py_NE) {
1433	n/a	if (v == w)
1434	n/a	Py_RETURN_FALSE;
1435	n/a	if (vs != ws)
1436	n/a	Py_RETURN_TRUE;
1437	n/a	}
1438	n/a
1439	n/a	/* Search for the first index where items are different */
1440	n/a	it1 = PyObject_GetIter(v);
1441	n/a	if (it1 == NULL)
1442	n/a	goto done;
1443	n/a	it2 = PyObject_GetIter(w);
1444	n/a	if (it2 == NULL)
1445	n/a	goto done;
1446	n/a	for (;;) {
1447	n/a	x = PyIter_Next(it1);
1448	n/a	if (x == NULL && PyErr_Occurred())
1449	n/a	goto done;
1450	n/a	y = PyIter_Next(it2);
1451	n/a	if (x == NULL \|\| y == NULL)
1452	n/a	break;
1453	n/a	b = PyObject_RichCompareBool(x, y, Py_EQ);
1454	n/a	if (b == 0) {
1455	n/a	cmp = PyObject_RichCompareBool(x, y, op);
1456	n/a	Py_DECREF(x);
1457	n/a	Py_DECREF(y);
1458	n/a	goto done;
1459	n/a	}
1460	n/a	Py_DECREF(x);
1461	n/a	Py_DECREF(y);
1462	n/a	if (b < 0)
1463	n/a	goto done;
1464	n/a	}
1465	n/a	/* We reached the end of one deque or both */
1466	n/a	Py_XDECREF(x);
1467	n/a	Py_XDECREF(y);
1468	n/a	if (PyErr_Occurred())
1469	n/a	goto done;
1470	n/a	switch (op) {
1471	n/a	case Py_LT: cmp = y != NULL; break; /* if w was longer */
1472	n/a	case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1473	n/a	case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1474	n/a	case Py_NE: cmp = x != y; break; /* if one deque continues */
1475	n/a	case Py_GT: cmp = x != NULL; break; /* if v was longer */
1476	n/a	case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1477	n/a	}
1478	n/a
1479	n/a	done:
1480	n/a	Py_XDECREF(it1);
1481	n/a	Py_XDECREF(it2);
1482	n/a	if (cmp == 1)
1483	n/a	Py_RETURN_TRUE;
1484	n/a	if (cmp == 0)
1485	n/a	Py_RETURN_FALSE;
1486	n/a	return NULL;
1487	n/a	}
1488	n/a
1489	n/a	static int
1490	n/a	deque_init(dequeobject deque, PyObject args, PyObject *kwdargs)
1491	n/a	{
1492	n/a	PyObject *iterable = NULL;
1493	n/a	PyObject *maxlenobj = NULL;
1494	n/a	Py_ssize_t maxlen = -1;
1495	n/a	char *kwlist[] = {"iterable", "maxlen", 0};
1496	n/a
1497	n/a	if (kwdargs == NULL) {
1498	n/a	if (!PyArg_UnpackTuple(args, "deque()", 0, 2, &iterable, &maxlenobj))
1499	n/a	return -1;
1500	n/a	} else {
1501	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "\|OO:deque", kwlist,
1502	n/a	&iterable, &maxlenobj))
1503	n/a	return -1;
1504	n/a	}
1505	n/a	if (maxlenobj != NULL && maxlenobj != Py_None) {
1506	n/a	maxlen = PyLong_AsSsize_t(maxlenobj);
1507	n/a	if (maxlen == -1 && PyErr_Occurred())
1508	n/a	return -1;
1509	n/a	if (maxlen < 0) {
1510	n/a	PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1511	n/a	return -1;
1512	n/a	}
1513	n/a	}
1514	n/a	deque->maxlen = maxlen;
1515	n/a	if (Py_SIZE(deque) > 0)
1516	n/a	deque_clear(deque);
1517	n/a	if (iterable != NULL) {
1518	n/a	PyObject *rv = deque_extend(deque, iterable);
1519	n/a	if (rv == NULL)
1520	n/a	return -1;
1521	n/a	Py_DECREF(rv);
1522	n/a	}
1523	n/a	return 0;
1524	n/a	}
1525	n/a
1526	n/a	static PyObject *
1527	n/a	deque_sizeof(dequeobject deque, void unused)
1528	n/a	{
1529	n/a	Py_ssize_t res;
1530	n/a	Py_ssize_t blocks;
1531	n/a
1532	n/a	res = _PyObject_SIZE(Py_TYPE(deque));
1533	n/a	blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1534	n/a	assert(deque->leftindex + Py_SIZE(deque) - 1 ==
1535	n/a	(blocks - 1) * BLOCKLEN + deque->rightindex);
1536	n/a	res += blocks * sizeof(block);
1537	n/a	return PyLong_FromSsize_t(res);
1538	n/a	}
1539	n/a
1540	n/a	PyDoc_STRVAR(sizeof_doc,
1541	n/a	"D.__sizeof__() -- size of D in memory, in bytes");
1542	n/a
1543	n/a	static int
1544	n/a	deque_bool(dequeobject *deque)
1545	n/a	{
1546	n/a	return Py_SIZE(deque) != 0;
1547	n/a	}
1548	n/a
1549	n/a	static PyObject *
1550	n/a	deque_get_maxlen(dequeobject *deque)
1551	n/a	{
1552	n/a	if (deque->maxlen < 0)
1553	n/a	Py_RETURN_NONE;
1554	n/a	return PyLong_FromSsize_t(deque->maxlen);
1555	n/a	}
1556	n/a
1557	n/a
1558	n/a	/* deque object ********************************************************/
1559	n/a
1560	n/a	static PyGetSetDef deque_getset[] = {
1561	n/a	{"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1562	n/a	"maximum size of a deque or None if unbounded"},
1563	n/a	{0}
1564	n/a	};
1565	n/a
1566	n/a	static PySequenceMethods deque_as_sequence = {
1567	n/a	(lenfunc)deque_len, /* sq_length */
1568	n/a	(binaryfunc)deque_concat, /* sq_concat */
1569	n/a	(ssizeargfunc)deque_repeat, /* sq_repeat */
1570	n/a	(ssizeargfunc)deque_item, /* sq_item */
1571	n/a	0, /* sq_slice */
1572	n/a	(ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1573	n/a	0, /* sq_ass_slice */
1574	n/a	(objobjproc)deque_contains, /* sq_contains */
1575	n/a	(binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1576	n/a	(ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
1577	n/a	};
1578	n/a
1579	n/a	static PyNumberMethods deque_as_number = {
1580	n/a	0, /* nb_add */
1581	n/a	0, /* nb_subtract */
1582	n/a	0, /* nb_multiply */
1583	n/a	0, /* nb_remainder */
1584	n/a	0, /* nb_divmod */
1585	n/a	0, /* nb_power */
1586	n/a	0, /* nb_negative */
1587	n/a	0, /* nb_positive */
1588	n/a	0, /* nb_absolute */
1589	n/a	(inquiry)deque_bool, /* nb_bool */
1590	n/a	0, /* nb_invert */
1591	n/a	};
1592	n/a
1593	n/a	static PyObject deque_iter(dequeobject deque);
1594	n/a	static PyObject deque_reviter(dequeobject deque);
1595	n/a	PyDoc_STRVAR(reversed_doc,
1596	n/a	"D.__reversed__() -- return a reverse iterator over the deque");
1597	n/a
1598	n/a	static PyMethodDef deque_methods[] = {
1599	n/a	{"append", (PyCFunction)deque_append,
1600	n/a	METH_O, append_doc},
1601	n/a	{"appendleft", (PyCFunction)deque_appendleft,
1602	n/a	METH_O, appendleft_doc},
1603	n/a	{"clear", (PyCFunction)deque_clearmethod,
1604	n/a	METH_NOARGS, clear_doc},
1605	n/a	{"__copy__", (PyCFunction)deque_copy,
1606	n/a	METH_NOARGS, copy_doc},
1607	n/a	{"copy", (PyCFunction)deque_copy,
1608	n/a	METH_NOARGS, copy_doc},
1609	n/a	{"count", (PyCFunction)deque_count,
1610	n/a	METH_O, count_doc},
1611	n/a	{"extend", (PyCFunction)deque_extend,
1612	n/a	METH_O, extend_doc},
1613	n/a	{"extendleft", (PyCFunction)deque_extendleft,
1614	n/a	METH_O, extendleft_doc},
1615	n/a	{"index", (PyCFunction)deque_index,
1616	n/a	METH_FASTCALL, index_doc},
1617	n/a	{"insert", (PyCFunction)deque_insert,
1618	n/a	METH_FASTCALL, insert_doc},
1619	n/a	{"pop", (PyCFunction)deque_pop,
1620	n/a	METH_NOARGS, pop_doc},
1621	n/a	{"popleft", (PyCFunction)deque_popleft,
1622	n/a	METH_NOARGS, popleft_doc},
1623	n/a	{"__reduce__", (PyCFunction)deque_reduce,
1624	n/a	METH_NOARGS, reduce_doc},
1625	n/a	{"remove", (PyCFunction)deque_remove,
1626	n/a	METH_O, remove_doc},
1627	n/a	{"__reversed__", (PyCFunction)deque_reviter,
1628	n/a	METH_NOARGS, reversed_doc},
1629	n/a	{"reverse", (PyCFunction)deque_reverse,
1630	n/a	METH_NOARGS, reverse_doc},
1631	n/a	{"rotate", (PyCFunction)deque_rotate,
1632	n/a	METH_FASTCALL, rotate_doc},
1633	n/a	{"__sizeof__", (PyCFunction)deque_sizeof,
1634	n/a	METH_NOARGS, sizeof_doc},
1635	n/a	{NULL, NULL} /* sentinel */
1636	n/a	};
1637	n/a
1638	n/a	PyDoc_STRVAR(deque_doc,
1639	n/a	"deque([iterable[, maxlen]]) --> deque object\n\
1640	n/a	\n\
1641	n/a	A list-like sequence optimized for data accesses near its endpoints.");
1642	n/a
1643	n/a	static PyTypeObject deque_type = {
1644	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1645	n/a	"collections.deque", /* tp_name */
1646	n/a	sizeof(dequeobject), /* tp_basicsize */
1647	n/a	0, /* tp_itemsize */
1648	n/a	/* methods */
1649	n/a	(destructor)deque_dealloc, /* tp_dealloc */
1650	n/a	0, /* tp_print */
1651	n/a	0, /* tp_getattr */
1652	n/a	0, /* tp_setattr */
1653	n/a	0, /* tp_reserved */
1654	n/a	deque_repr, /* tp_repr */
1655	n/a	&deque_as_number, /* tp_as_number */
1656	n/a	&deque_as_sequence, /* tp_as_sequence */
1657	n/a	0, /* tp_as_mapping */
1658	n/a	PyObject_HashNotImplemented, /* tp_hash */
1659	n/a	0, /* tp_call */
1660	n/a	0, /* tp_str */
1661	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1662	n/a	0, /* tp_setattro */
1663	n/a	0, /* tp_as_buffer */
1664	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_BASETYPE \| Py_TPFLAGS_HAVE_GC,
1665	n/a	/* tp_flags */
1666	n/a	deque_doc, /* tp_doc */
1667	n/a	(traverseproc)deque_traverse, /* tp_traverse */
1668	n/a	(inquiry)deque_clear, /* tp_clear */
1669	n/a	(richcmpfunc)deque_richcompare, /* tp_richcompare */
1670	n/a	offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1671	n/a	(getiterfunc)deque_iter, /* tp_iter */
1672	n/a	0, /* tp_iternext */
1673	n/a	deque_methods, /* tp_methods */
1674	n/a	0, /* tp_members */
1675	n/a	deque_getset, /* tp_getset */
1676	n/a	0, /* tp_base */
1677	n/a	0, /* tp_dict */
1678	n/a	0, /* tp_descr_get */
1679	n/a	0, /* tp_descr_set */
1680	n/a	0, /* tp_dictoffset */
1681	n/a	(initproc)deque_init, /* tp_init */
1682	n/a	PyType_GenericAlloc, /* tp_alloc */
1683	n/a	deque_new, /* tp_new */
1684	n/a	PyObject_GC_Del, /* tp_free */
1685	n/a	};
1686	n/a
1687	n/a	/********************* Deque Iterator ************************/
1688	n/a
1689	n/a	typedef struct {
1690	n/a	PyObject_HEAD
1691	n/a	block *b;
1692	n/a	Py_ssize_t index;
1693	n/a	dequeobject *deque;
1694	n/a	size_t state; /* state when the iterator is created */
1695	n/a	Py_ssize_t counter; /* number of items remaining for iteration */
1696	n/a	} dequeiterobject;
1697	n/a
1698	n/a	static PyTypeObject dequeiter_type;
1699	n/a
1700	n/a	static PyObject *
1701	n/a	deque_iter(dequeobject *deque)
1702	n/a	{
1703	n/a	dequeiterobject *it;
1704	n/a
1705	n/a	it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1706	n/a	if (it == NULL)
1707	n/a	return NULL;
1708	n/a	it->b = deque->leftblock;
1709	n/a	it->index = deque->leftindex;
1710	n/a	Py_INCREF(deque);
1711	n/a	it->deque = deque;
1712	n/a	it->state = deque->state;
1713	n/a	it->counter = Py_SIZE(deque);
1714	n/a	PyObject_GC_Track(it);
1715	n/a	return (PyObject *)it;
1716	n/a	}
1717	n/a
1718	n/a	static int
1719	n/a	dequeiter_traverse(dequeiterobject dio, visitproc visit, void arg)
1720	n/a	{
1721	n/a	Py_VISIT(dio->deque);
1722	n/a	return 0;
1723	n/a	}
1724	n/a
1725	n/a	static void
1726	n/a	dequeiter_dealloc(dequeiterobject *dio)
1727	n/a	{
1728	n/a	Py_XDECREF(dio->deque);
1729	n/a	PyObject_GC_Del(dio);
1730	n/a	}
1731	n/a
1732	n/a	static PyObject *
1733	n/a	dequeiter_next(dequeiterobject *it)
1734	n/a	{
1735	n/a	PyObject *item;
1736	n/a
1737	n/a	if (it->deque->state != it->state) {
1738	n/a	it->counter = 0;
1739	n/a	PyErr_SetString(PyExc_RuntimeError,
1740	n/a	"deque mutated during iteration");
1741	n/a	return NULL;
1742	n/a	}
1743	n/a	if (it->counter == 0)
1744	n/a	return NULL;
1745	n/a	assert (!(it->b == it->deque->rightblock &&
1746	n/a	it->index > it->deque->rightindex));
1747	n/a
1748	n/a	item = it->b->data[it->index];
1749	n/a	it->index++;
1750	n/a	it->counter--;
1751	n/a	if (it->index == BLOCKLEN && it->counter > 0) {
1752	n/a	CHECK_NOT_END(it->b->rightlink);
1753	n/a	it->b = it->b->rightlink;
1754	n/a	it->index = 0;
1755	n/a	}
1756	n/a	Py_INCREF(item);
1757	n/a	return item;
1758	n/a	}
1759	n/a
1760	n/a	static PyObject *
1761	n/a	dequeiter_new(PyTypeObject type, PyObject args, PyObject *kwds)
1762	n/a	{
1763	n/a	Py_ssize_t i, index=0;
1764	n/a	PyObject *deque;
1765	n/a	dequeiterobject *it;
1766	n/a	if (!PyArg_ParseTuple(args, "O!\|n", &deque_type, &deque, &index))
1767	n/a	return NULL;
1768	n/a	assert(type == &dequeiter_type);
1769	n/a
1770	n/a	it = (dequeiterobject)deque_iter((dequeobject )deque);
1771	n/a	if (!it)
1772	n/a	return NULL;
1773	n/a	/* consume items from the queue */
1774	n/a	for(i=0; i<index; i++) {
1775	n/a	PyObject *item = dequeiter_next(it);
1776	n/a	if (item) {
1777	n/a	Py_DECREF(item);
1778	n/a	} else {
1779	n/a	if (it->counter) {
1780	n/a	Py_DECREF(it);
1781	n/a	return NULL;
1782	n/a	} else
1783	n/a	break;
1784	n/a	}
1785	n/a	}
1786	n/a	return (PyObject*)it;
1787	n/a	}
1788	n/a
1789	n/a	static PyObject *
1790	n/a	dequeiter_len(dequeiterobject *it)
1791	n/a	{
1792	n/a	return PyLong_FromSsize_t(it->counter);
1793	n/a	}
1794	n/a
1795	n/a	PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1796	n/a
1797	n/a	static PyObject *
1798	n/a	dequeiter_reduce(dequeiterobject *it)
1799	n/a	{
1800	n/a	return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
1801	n/a	}
1802	n/a
1803	n/a	static PyMethodDef dequeiter_methods[] = {
1804	n/a	{"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1805	n/a	{"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
1806	n/a	{NULL, NULL} /* sentinel */
1807	n/a	};
1808	n/a
1809	n/a	static PyTypeObject dequeiter_type = {
1810	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1811	n/a	"_collections._deque_iterator", /* tp_name */
1812	n/a	sizeof(dequeiterobject), /* tp_basicsize */
1813	n/a	0, /* tp_itemsize */
1814	n/a	/* methods */
1815	n/a	(destructor)dequeiter_dealloc, /* tp_dealloc */
1816	n/a	0, /* tp_print */
1817	n/a	0, /* tp_getattr */
1818	n/a	0, /* tp_setattr */
1819	n/a	0, /* tp_reserved */
1820	n/a	0, /* tp_repr */
1821	n/a	0, /* tp_as_number */
1822	n/a	0, /* tp_as_sequence */
1823	n/a	0, /* tp_as_mapping */
1824	n/a	0, /* tp_hash */
1825	n/a	0, /* tp_call */
1826	n/a	0, /* tp_str */
1827	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1828	n/a	0, /* tp_setattro */
1829	n/a	0, /* tp_as_buffer */
1830	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
1831	n/a	0, /* tp_doc */
1832	n/a	(traverseproc)dequeiter_traverse, /* tp_traverse */
1833	n/a	0, /* tp_clear */
1834	n/a	0, /* tp_richcompare */
1835	n/a	0, /* tp_weaklistoffset */
1836	n/a	PyObject_SelfIter, /* tp_iter */
1837	n/a	(iternextfunc)dequeiter_next, /* tp_iternext */
1838	n/a	dequeiter_methods, /* tp_methods */
1839	n/a	0, /* tp_members */
1840	n/a	0, /* tp_getset */
1841	n/a	0, /* tp_base */
1842	n/a	0, /* tp_dict */
1843	n/a	0, /* tp_descr_get */
1844	n/a	0, /* tp_descr_set */
1845	n/a	0, /* tp_dictoffset */
1846	n/a	0, /* tp_init */
1847	n/a	0, /* tp_alloc */
1848	n/a	dequeiter_new, /* tp_new */
1849	n/a	0,
1850	n/a	};
1851	n/a
1852	n/a	/********************* Deque Reverse Iterator ************************/
1853	n/a
1854	n/a	static PyTypeObject dequereviter_type;
1855	n/a
1856	n/a	static PyObject *
1857	n/a	deque_reviter(dequeobject *deque)
1858	n/a	{
1859	n/a	dequeiterobject *it;
1860	n/a
1861	n/a	it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1862	n/a	if (it == NULL)
1863	n/a	return NULL;
1864	n/a	it->b = deque->rightblock;
1865	n/a	it->index = deque->rightindex;
1866	n/a	Py_INCREF(deque);
1867	n/a	it->deque = deque;
1868	n/a	it->state = deque->state;
1869	n/a	it->counter = Py_SIZE(deque);
1870	n/a	PyObject_GC_Track(it);
1871	n/a	return (PyObject *)it;
1872	n/a	}
1873	n/a
1874	n/a	static PyObject *
1875	n/a	dequereviter_next(dequeiterobject *it)
1876	n/a	{
1877	n/a	PyObject *item;
1878	n/a	if (it->counter == 0)
1879	n/a	return NULL;
1880	n/a
1881	n/a	if (it->deque->state != it->state) {
1882	n/a	it->counter = 0;
1883	n/a	PyErr_SetString(PyExc_RuntimeError,
1884	n/a	"deque mutated during iteration");
1885	n/a	return NULL;
1886	n/a	}
1887	n/a	assert (!(it->b == it->deque->leftblock &&
1888	n/a	it->index < it->deque->leftindex));
1889	n/a
1890	n/a	item = it->b->data[it->index];
1891	n/a	it->index--;
1892	n/a	it->counter--;
1893	n/a	if (it->index < 0 && it->counter > 0) {
1894	n/a	CHECK_NOT_END(it->b->leftlink);
1895	n/a	it->b = it->b->leftlink;
1896	n/a	it->index = BLOCKLEN - 1;
1897	n/a	}
1898	n/a	Py_INCREF(item);
1899	n/a	return item;
1900	n/a	}
1901	n/a
1902	n/a	static PyObject *
1903	n/a	dequereviter_new(PyTypeObject type, PyObject args, PyObject *kwds)
1904	n/a	{
1905	n/a	Py_ssize_t i, index=0;
1906	n/a	PyObject *deque;
1907	n/a	dequeiterobject *it;
1908	n/a	if (!PyArg_ParseTuple(args, "O!\|n", &deque_type, &deque, &index))
1909	n/a	return NULL;
1910	n/a	assert(type == &dequereviter_type);
1911	n/a
1912	n/a	it = (dequeiterobject)deque_reviter((dequeobject )deque);
1913	n/a	if (!it)
1914	n/a	return NULL;
1915	n/a	/* consume items from the queue */
1916	n/a	for(i=0; i<index; i++) {
1917	n/a	PyObject *item = dequereviter_next(it);
1918	n/a	if (item) {
1919	n/a	Py_DECREF(item);
1920	n/a	} else {
1921	n/a	if (it->counter) {
1922	n/a	Py_DECREF(it);
1923	n/a	return NULL;
1924	n/a	} else
1925	n/a	break;
1926	n/a	}
1927	n/a	}
1928	n/a	return (PyObject*)it;
1929	n/a	}
1930	n/a
1931	n/a	static PyTypeObject dequereviter_type = {
1932	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1933	n/a	"_collections._deque_reverse_iterator", /* tp_name */
1934	n/a	sizeof(dequeiterobject), /* tp_basicsize */
1935	n/a	0, /* tp_itemsize */
1936	n/a	/* methods */
1937	n/a	(destructor)dequeiter_dealloc, /* tp_dealloc */
1938	n/a	0, /* tp_print */
1939	n/a	0, /* tp_getattr */
1940	n/a	0, /* tp_setattr */
1941	n/a	0, /* tp_reserved */
1942	n/a	0, /* tp_repr */
1943	n/a	0, /* tp_as_number */
1944	n/a	0, /* tp_as_sequence */
1945	n/a	0, /* tp_as_mapping */
1946	n/a	0, /* tp_hash */
1947	n/a	0, /* tp_call */
1948	n/a	0, /* tp_str */
1949	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1950	n/a	0, /* tp_setattro */
1951	n/a	0, /* tp_as_buffer */
1952	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
1953	n/a	0, /* tp_doc */
1954	n/a	(traverseproc)dequeiter_traverse, /* tp_traverse */
1955	n/a	0, /* tp_clear */
1956	n/a	0, /* tp_richcompare */
1957	n/a	0, /* tp_weaklistoffset */
1958	n/a	PyObject_SelfIter, /* tp_iter */
1959	n/a	(iternextfunc)dequereviter_next, /* tp_iternext */
1960	n/a	dequeiter_methods, /* tp_methods */
1961	n/a	0, /* tp_members */
1962	n/a	0, /* tp_getset */
1963	n/a	0, /* tp_base */
1964	n/a	0, /* tp_dict */
1965	n/a	0, /* tp_descr_get */
1966	n/a	0, /* tp_descr_set */
1967	n/a	0, /* tp_dictoffset */
1968	n/a	0, /* tp_init */
1969	n/a	0, /* tp_alloc */
1970	n/a	dequereviter_new, /* tp_new */
1971	n/a	0,
1972	n/a	};
1973	n/a
1974	n/a	/* defaultdict type *********************************************************/
1975	n/a
1976	n/a	typedef struct {
1977	n/a	PyDictObject dict;
1978	n/a	PyObject *default_factory;
1979	n/a	} defdictobject;
1980	n/a
1981	n/a	static PyTypeObject defdict_type; /* Forward */
1982	n/a
1983	n/a	PyDoc_STRVAR(defdict_missing_doc,
1984	n/a	"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1985	n/a	if self.default_factory is None: raise KeyError((key,))\n\
1986	n/a	self[key] = value = self.default_factory()\n\
1987	n/a	return value\n\
1988	n/a	");
1989	n/a
1990	n/a	static PyObject *
1991	n/a	defdict_missing(defdictobject dd, PyObject key)
1992	n/a	{
1993	n/a	PyObject *factory = dd->default_factory;
1994	n/a	PyObject *value;
1995	n/a	if (factory == NULL \|\| factory == Py_None) {
1996	n/a	/* XXX Call dict.__missing__(key) */
1997	n/a	PyObject *tup;
1998	n/a	tup = PyTuple_Pack(1, key);
1999	n/a	if (!tup) return NULL;
2000	n/a	PyErr_SetObject(PyExc_KeyError, tup);
2001	n/a	Py_DECREF(tup);
2002	n/a	return NULL;
2003	n/a	}
2004	n/a	value = PyEval_CallObject(factory, NULL);
2005	n/a	if (value == NULL)
2006	n/a	return value;
2007	n/a	if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
2008	n/a	Py_DECREF(value);
2009	n/a	return NULL;
2010	n/a	}
2011	n/a	return value;
2012	n/a	}
2013	n/a
2014	n/a	PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
2015	n/a
2016	n/a	static PyObject *
2017	n/a	defdict_copy(defdictobject *dd)
2018	n/a	{
2019	n/a	/* This calls the object's class. That only works for subclasses
2020	n/a	whose class constructor has the same signature. Subclasses that
2021	n/a	define a different constructor signature must override copy().
2022	n/a	*/
2023	n/a
2024	n/a	if (dd->default_factory == NULL)
2025	n/a	return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
2026	n/a	return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
2027	n/a	dd->default_factory, dd, NULL);
2028	n/a	}
2029	n/a
2030	n/a	static PyObject *
2031	n/a	defdict_reduce(defdictobject *dd)
2032	n/a	{
2033	n/a	/* __reduce__ must return a 5-tuple as follows:
2034	n/a
2035	n/a	- factory function
2036	n/a	- tuple of args for the factory function
2037	n/a	- additional state (here None)
2038	n/a	- sequence iterator (here None)
2039	n/a	- dictionary iterator (yielding successive (key, value) pairs
2040	n/a
2041	n/a	This API is used by pickle.py and copy.py.
2042	n/a
2043	n/a	For this to be useful with pickle.py, the default_factory
2044	n/a	must be picklable; e.g., None, a built-in, or a global
2045	n/a	function in a module or package.
2046	n/a
2047	n/a	Both shallow and deep copying are supported, but for deep
2048	n/a	copying, the default_factory must be deep-copyable; e.g. None,
2049	n/a	or a built-in (functions are not copyable at this time).
2050	n/a
2051	n/a	This only works for subclasses as long as their constructor
2052	n/a	signature is compatible; the first argument must be the
2053	n/a	optional default_factory, defaulting to None.
2054	n/a	*/
2055	n/a	PyObject *args;
2056	n/a	PyObject *items;
2057	n/a	PyObject *iter;
2058	n/a	PyObject *result;
2059	n/a	_Py_IDENTIFIER(items);
2060	n/a
2061	n/a	if (dd->default_factory == NULL \|\| dd->default_factory == Py_None)
2062	n/a	args = PyTuple_New(0);
2063	n/a	else
2064	n/a	args = PyTuple_Pack(1, dd->default_factory);
2065	n/a	if (args == NULL)
2066	n/a	return NULL;
2067	n/a	items = _PyObject_CallMethodId((PyObject *)dd, &PyId_items, NULL);
2068	n/a	if (items == NULL) {
2069	n/a	Py_DECREF(args);
2070	n/a	return NULL;
2071	n/a	}
2072	n/a	iter = PyObject_GetIter(items);
2073	n/a	if (iter == NULL) {
2074	n/a	Py_DECREF(items);
2075	n/a	Py_DECREF(args);
2076	n/a	return NULL;
2077	n/a	}
2078	n/a	result = PyTuple_Pack(5, Py_TYPE(dd), args,
2079	n/a	Py_None, Py_None, iter);
2080	n/a	Py_DECREF(iter);
2081	n/a	Py_DECREF(items);
2082	n/a	Py_DECREF(args);
2083	n/a	return result;
2084	n/a	}
2085	n/a
2086	n/a	static PyMethodDef defdict_methods[] = {
2087	n/a	{"__missing__", (PyCFunction)defdict_missing, METH_O,
2088	n/a	defdict_missing_doc},
2089	n/a	{"copy", (PyCFunction)defdict_copy, METH_NOARGS,
2090	n/a	defdict_copy_doc},
2091	n/a	{"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
2092	n/a	defdict_copy_doc},
2093	n/a	{"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
2094	n/a	reduce_doc},
2095	n/a	{NULL}
2096	n/a	};
2097	n/a
2098	n/a	static PyMemberDef defdict_members[] = {
2099	n/a	{"default_factory", T_OBJECT,
2100	n/a	offsetof(defdictobject, default_factory), 0,
2101	n/a	PyDoc_STR("Factory for default value called by __missing__().")},
2102	n/a	{NULL}
2103	n/a	};
2104	n/a
2105	n/a	static void
2106	n/a	defdict_dealloc(defdictobject *dd)
2107	n/a	{
2108	n/a	Py_CLEAR(dd->default_factory);
2109	n/a	PyDict_Type.tp_dealloc((PyObject *)dd);
2110	n/a	}
2111	n/a
2112	n/a	static PyObject *
2113	n/a	defdict_repr(defdictobject *dd)
2114	n/a	{
2115	n/a	PyObject *baserepr;
2116	n/a	PyObject *defrepr;
2117	n/a	PyObject *result;
2118	n/a	baserepr = PyDict_Type.tp_repr((PyObject *)dd);
2119	n/a	if (baserepr == NULL)
2120	n/a	return NULL;
2121	n/a	if (dd->default_factory == NULL)
2122	n/a	defrepr = PyUnicode_FromString("None");
2123	n/a	else
2124	n/a	{
2125	n/a	int status = Py_ReprEnter(dd->default_factory);
2126	n/a	if (status != 0) {
2127	n/a	if (status < 0) {
2128	n/a	Py_DECREF(baserepr);
2129	n/a	return NULL;
2130	n/a	}
2131	n/a	defrepr = PyUnicode_FromString("...");
2132	n/a	}
2133	n/a	else
2134	n/a	defrepr = PyObject_Repr(dd->default_factory);
2135	n/a	Py_ReprLeave(dd->default_factory);
2136	n/a	}
2137	n/a	if (defrepr == NULL) {
2138	n/a	Py_DECREF(baserepr);
2139	n/a	return NULL;
2140	n/a	}
2141	n/a	result = PyUnicode_FromFormat("defaultdict(%U, %U)",
2142	n/a	defrepr, baserepr);
2143	n/a	Py_DECREF(defrepr);
2144	n/a	Py_DECREF(baserepr);
2145	n/a	return result;
2146	n/a	}
2147	n/a
2148	n/a	static int
2149	n/a	defdict_traverse(PyObject self, visitproc visit, void arg)
2150	n/a	{
2151	n/a	Py_VISIT(((defdictobject *)self)->default_factory);
2152	n/a	return PyDict_Type.tp_traverse(self, visit, arg);
2153	n/a	}
2154	n/a
2155	n/a	static int
2156	n/a	defdict_tp_clear(defdictobject *dd)
2157	n/a	{
2158	n/a	Py_CLEAR(dd->default_factory);
2159	n/a	return PyDict_Type.tp_clear((PyObject *)dd);
2160	n/a	}
2161	n/a
2162	n/a	static int
2163	n/a	defdict_init(PyObject self, PyObject args, PyObject *kwds)
2164	n/a	{
2165	n/a	defdictobject dd = (defdictobject )self;
2166	n/a	PyObject *olddefault = dd->default_factory;
2167	n/a	PyObject *newdefault = NULL;
2168	n/a	PyObject *newargs;
2169	n/a	int result;
2170	n/a	if (args == NULL \|\| !PyTuple_Check(args))
2171	n/a	newargs = PyTuple_New(0);
2172	n/a	else {
2173	n/a	Py_ssize_t n = PyTuple_GET_SIZE(args);
2174	n/a	if (n > 0) {
2175	n/a	newdefault = PyTuple_GET_ITEM(args, 0);
2176	n/a	if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2177	n/a	PyErr_SetString(PyExc_TypeError,
2178	n/a	"first argument must be callable or None");
2179	n/a	return -1;
2180	n/a	}
2181	n/a	}
2182	n/a	newargs = PySequence_GetSlice(args, 1, n);
2183	n/a	}
2184	n/a	if (newargs == NULL)
2185	n/a	return -1;
2186	n/a	Py_XINCREF(newdefault);
2187	n/a	dd->default_factory = newdefault;
2188	n/a	result = PyDict_Type.tp_init(self, newargs, kwds);
2189	n/a	Py_DECREF(newargs);
2190	n/a	Py_XDECREF(olddefault);
2191	n/a	return result;
2192	n/a	}
2193	n/a
2194	n/a	PyDoc_STRVAR(defdict_doc,
2195	n/a	"defaultdict(default_factory[, ...]) --> dict with default factory\n\
2196	n/a	\n\
2197	n/a	The default factory is called without arguments to produce\n\
2198	n/a	a new value when a key is not present, in __getitem__ only.\n\
2199	n/a	A defaultdict compares equal to a dict with the same items.\n\
2200	n/a	All remaining arguments are treated the same as if they were\n\
2201	n/a	passed to the dict constructor, including keyword arguments.\n\
2202	n/a	");
2203	n/a
2204	n/a	/* See comment in xxsubtype.c */
2205	n/a	#define DEFERRED_ADDRESS(ADDR) 0
2206	n/a
2207	n/a	static PyTypeObject defdict_type = {
2208	n/a	PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2209	n/a	"collections.defaultdict", /* tp_name */
2210	n/a	sizeof(defdictobject), /* tp_basicsize */
2211	n/a	0, /* tp_itemsize */
2212	n/a	/* methods */
2213	n/a	(destructor)defdict_dealloc, /* tp_dealloc */
2214	n/a	0, /* tp_print */
2215	n/a	0, /* tp_getattr */
2216	n/a	0, /* tp_setattr */
2217	n/a	0, /* tp_reserved */
2218	n/a	(reprfunc)defdict_repr, /* tp_repr */
2219	n/a	0, /* tp_as_number */
2220	n/a	0, /* tp_as_sequence */
2221	n/a	0, /* tp_as_mapping */
2222	n/a	0, /* tp_hash */
2223	n/a	0, /* tp_call */
2224	n/a	0, /* tp_str */
2225	n/a	PyObject_GenericGetAttr, /* tp_getattro */
2226	n/a	0, /* tp_setattro */
2227	n/a	0, /* tp_as_buffer */
2228	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_BASETYPE \| Py_TPFLAGS_HAVE_GC,
2229	n/a	/* tp_flags */
2230	n/a	defdict_doc, /* tp_doc */
2231	n/a	defdict_traverse, /* tp_traverse */
2232	n/a	(inquiry)defdict_tp_clear, /* tp_clear */
2233	n/a	0, /* tp_richcompare */
2234	n/a	0, /* tp_weaklistoffset*/
2235	n/a	0, /* tp_iter */
2236	n/a	0, /* tp_iternext */
2237	n/a	defdict_methods, /* tp_methods */
2238	n/a	defdict_members, /* tp_members */
2239	n/a	0, /* tp_getset */
2240	n/a	DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2241	n/a	0, /* tp_dict */
2242	n/a	0, /* tp_descr_get */
2243	n/a	0, /* tp_descr_set */
2244	n/a	0, /* tp_dictoffset */
2245	n/a	defdict_init, /* tp_init */
2246	n/a	PyType_GenericAlloc, /* tp_alloc */
2247	n/a	0, /* tp_new */
2248	n/a	PyObject_GC_Del, /* tp_free */
2249	n/a	};
2250	n/a
2251	n/a	/* helper function for Counter *********************************************/
2252	n/a
2253	n/a	PyDoc_STRVAR(_count_elements_doc,
2254	n/a	"_count_elements(mapping, iterable) -> None\n\
2255	n/a	\n\
2256	n/a	Count elements in the iterable, updating the mapping");
2257	n/a
2258	n/a	static PyObject *
2259	n/a	_count_elements(PyObject self, PyObject args)
2260	n/a	{
2261	n/a	_Py_IDENTIFIER(get);
2262	n/a	_Py_IDENTIFIER(__setitem__);
2263	n/a	PyObject it, iterable, mapping, oldval;
2264	n/a	PyObject *newval = NULL;
2265	n/a	PyObject *key = NULL;
2266	n/a	PyObject *zero = NULL;
2267	n/a	PyObject *one = NULL;
2268	n/a	PyObject *bound_get = NULL;
2269	n/a	PyObject *mapping_get;
2270	n/a	PyObject *dict_get;
2271	n/a	PyObject *mapping_setitem;
2272	n/a	PyObject *dict_setitem;
2273	n/a
2274	n/a	if (!PyArg_UnpackTuple(args, "_count_elements", 2, 2, &mapping, &iterable))
2275	n/a	return NULL;
2276	n/a
2277	n/a	it = PyObject_GetIter(iterable);
2278	n/a	if (it == NULL)
2279	n/a	return NULL;
2280	n/a
2281	n/a	one = PyLong_FromLong(1);
2282	n/a	if (one == NULL)
2283	n/a	goto done;
2284	n/a
2285	n/a	/* Only take the fast path when get() and __setitem__()
2286	n/a	* have not been overridden.
2287	n/a	*/
2288	n/a	mapping_get = _PyType_LookupId(Py_TYPE(mapping), &PyId_get);
2289	n/a	dict_get = _PyType_LookupId(&PyDict_Type, &PyId_get);
2290	n/a	mapping_setitem = _PyType_LookupId(Py_TYPE(mapping), &PyId___setitem__);
2291	n/a	dict_setitem = _PyType_LookupId(&PyDict_Type, &PyId___setitem__);
2292	n/a
2293	n/a	if (mapping_get != NULL && mapping_get == dict_get &&
2294	n/a	mapping_setitem != NULL && mapping_setitem == dict_setitem) {
2295	n/a	while (1) {
2296	n/a	/* Fast path advantages:
2297	n/a	1. Eliminate double hashing
2298	n/a	(by re-using the same hash for both the get and set)
2299	n/a	2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2300	n/a	(argument tuple creation and parsing)
2301	n/a	3. Avoid indirection through a bound method object
2302	n/a	(creates another argument tuple)
2303	n/a	4. Avoid initial increment from zero
2304	n/a	(reuse an existing one-object instead)
2305	n/a	*/
2306	n/a	Py_hash_t hash;
2307	n/a
2308	n/a	key = PyIter_Next(it);
2309	n/a	if (key == NULL)
2310	n/a	break;
2311	n/a
2312	n/a	if (!PyUnicode_CheckExact(key) \|\|
2313	n/a	(hash = ((PyASCIIObject *) key)->hash) == -1)
2314	n/a	{
2315	n/a	hash = PyObject_Hash(key);
2316	n/a	if (hash == -1)
2317	n/a	goto done;
2318	n/a	}
2319	n/a
2320	n/a	oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
2321	n/a	if (oldval == NULL) {
2322	n/a	if (PyErr_Occurred())
2323	n/a	goto done;
2324	n/a	if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0)
2325	n/a	goto done;
2326	n/a	} else {
2327	n/a	newval = PyNumber_Add(oldval, one);
2328	n/a	if (newval == NULL)
2329	n/a	goto done;
2330	n/a	if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
2331	n/a	goto done;
2332	n/a	Py_CLEAR(newval);
2333	n/a	}
2334	n/a	Py_DECREF(key);
2335	n/a	}
2336	n/a	} else {
2337	n/a	bound_get = _PyObject_GetAttrId(mapping, &PyId_get);
2338	n/a	if (bound_get == NULL)
2339	n/a	goto done;
2340	n/a
2341	n/a	zero = PyLong_FromLong(0);
2342	n/a	if (zero == NULL)
2343	n/a	goto done;
2344	n/a
2345	n/a	while (1) {
2346	n/a	key = PyIter_Next(it);
2347	n/a	if (key == NULL)
2348	n/a	break;
2349	n/a	oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
2350	n/a	if (oldval == NULL)
2351	n/a	break;
2352	n/a	newval = PyNumber_Add(oldval, one);
2353	n/a	Py_DECREF(oldval);
2354	n/a	if (newval == NULL)
2355	n/a	break;
2356	n/a	if (PyObject_SetItem(mapping, key, newval) < 0)
2357	n/a	break;
2358	n/a	Py_CLEAR(newval);
2359	n/a	Py_DECREF(key);
2360	n/a	}
2361	n/a	}
2362	n/a
2363	n/a	done:
2364	n/a	Py_DECREF(it);
2365	n/a	Py_XDECREF(key);
2366	n/a	Py_XDECREF(newval);
2367	n/a	Py_XDECREF(bound_get);
2368	n/a	Py_XDECREF(zero);
2369	n/a	Py_XDECREF(one);
2370	n/a	if (PyErr_Occurred())
2371	n/a	return NULL;
2372	n/a	Py_RETURN_NONE;
2373	n/a	}
2374	n/a
2375	n/a	/* module level code ********************************************************/
2376	n/a
2377	n/a	PyDoc_STRVAR(module_doc,
2378	n/a	"High performance data structures.\n\
2379	n/a	- deque: ordered collection accessible from endpoints only\n\
2380	n/a	- defaultdict: dict subclass with a default value factory\n\
2381	n/a	");
2382	n/a
2383	n/a	static struct PyMethodDef module_functions[] = {
2384	n/a	{"_count_elements", _count_elements, METH_VARARGS, _count_elements_doc},
2385	n/a	{NULL, NULL} /* sentinel */
2386	n/a	};
2387	n/a
2388	n/a	static struct PyModuleDef _collectionsmodule = {
2389	n/a	PyModuleDef_HEAD_INIT,
2390	n/a	"_collections",
2391	n/a	module_doc,
2392	n/a	-1,
2393	n/a	module_functions,
2394	n/a	NULL,
2395	n/a	NULL,
2396	n/a	NULL,
2397	n/a	NULL
2398	n/a	};
2399	n/a
2400	n/a	PyMODINIT_FUNC
2401	n/a	PyInit__collections(void)
2402	n/a	{
2403	n/a	PyObject *m;
2404	n/a
2405	n/a	m = PyModule_Create(&_collectionsmodule);
2406	n/a	if (m == NULL)
2407	n/a	return NULL;
2408	n/a
2409	n/a	if (PyType_Ready(&deque_type) < 0)
2410	n/a	return NULL;
2411	n/a	Py_INCREF(&deque_type);
2412	n/a	PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
2413	n/a
2414	n/a	defdict_type.tp_base = &PyDict_Type;
2415	n/a	if (PyType_Ready(&defdict_type) < 0)
2416	n/a	return NULL;
2417	n/a	Py_INCREF(&defdict_type);
2418	n/a	PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
2419	n/a
2420	n/a	Py_INCREF(&PyODict_Type);
2421	n/a	PyModule_AddObject(m, "OrderedDict", (PyObject *)&PyODict_Type);
2422	n/a
2423	n/a	if (PyType_Ready(&dequeiter_type) < 0)
2424	n/a	return NULL;
2425	n/a	Py_INCREF(&dequeiter_type);
2426	n/a	PyModule_AddObject(m, "_deque_iterator", (PyObject *)&dequeiter_type);
2427	n/a
2428	n/a	if (PyType_Ready(&dequereviter_type) < 0)
2429	n/a	return NULL;
2430	n/a	Py_INCREF(&dequereviter_type);
2431	n/a	PyModule_AddObject(m, "_deque_reverse_iterator", (PyObject *)&dequereviter_type);
2432	n/a
2433	n/a	return m;
2434	n/a	}