#include "Python.h"#include "structmember.h" /* collections module implementation of a deque() datatype   Written and maintained by Raymond D. Hettinger <python@rcn.com>   Copyright (c) 2004 Python Software Foundation.   All rights reserved.*/ /* The block length may be set to any number over 1.  Larger numbers * reduce the number of calls to the memory allocator but take more * memory.  Ideally, BLOCKLEN should be set with an eye to the * length of a cache line. */ #define BLOCKLEN 62#define CENTER ((BLOCKLEN - 1) / 2) /* A `dequeobject` is composed of a doubly-linked list of `block` nodes. * This list is not circular (the leftmost block has leftlink==NULL, * and the rightmost block has rightlink==NULL).  A deque d's first * element is at d.leftblock[leftindex] and its last element is at * d.rightblock[rightindex]; note that, unlike as for Python slice * indices, these indices are inclusive on both ends.  By being inclusive * on both ends, algorithms for left and right operations become * symmetrical which simplifies the design. * * The list of blocks is never empty, so d.leftblock and d.rightblock * are never equal to NULL. * * The indices, d.leftindex and d.rightindex are always in the range *     0 <= index < BLOCKLEN. * Their exact relationship is: *     (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex. * * Empty deques have d.len == 0; d.leftblock==d.rightblock; * d.leftindex == CENTER+1; and d.rightindex == CENTER. * Checking for d.len == 0 is the intended way to see whether d is empty. * * Whenever d.leftblock == d.rightblock, *     d.leftindex + d.len - 1 == d.rightindex. * * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex * become indices into distinct blocks and either may be larger than the * other. */ typedef struct BLOCK {	struct BLOCK *leftlink;	struct BLOCK *rightlink;	PyObject *data[BLOCKLEN];} block; static block *newblock(block *leftlink, block *rightlink, int len) {	block *b;	/* To prevent len from overflowing INT_MAX on 64-bit machines, we	 * refuse to allocate new blocks if the current len is dangerously	 * close.  There is some extra margin to prevent spurious arithmetic	 * overflows at various places.  The following check ensures that	 * the blocks allocated to the deque, in the worst case, can only	 * have INT_MAX-2 entries in total.	 */	if (len >= INT_MAX - 2*BLOCKLEN) {		PyErr_SetString(PyExc_OverflowError,				"cannot add more blocks to the deque");		return NULL;	}	b = PyMem_Malloc(sizeof(block));	if (b == NULL) {		PyErr_NoMemory();		return NULL;	}	b->leftlink = leftlink;	b->rightlink = rightlink;	return b;} typedef struct {	PyObject_HEAD	block *leftblock;	block *rightblock;	int leftindex;	/* in range(BLOCKLEN) */	int rightindex;	/* in range(BLOCKLEN) */	int len;	long state;	/* incremented whenever the indices move */	PyObject *weakreflist; /* List of weak references */} dequeobject; static PyTypeObject deque_type; static PyObject *deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds){	dequeobject *deque;	block *b; 	if (type == &deque_type && !_PyArg_NoKeywords("deque()", kwds))		return NULL; 	/* create dequeobject structure */	deque = (dequeobject *)type->tp_alloc(type, 0);	if (deque == NULL)		return NULL; 	b = newblock(NULL, NULL, 0);	if (b == NULL) {		Py_DECREF(deque);		return NULL;	} 	assert(BLOCKLEN >= 2);	deque->leftblock = b;	deque->rightblock = b;	deque->leftindex = CENTER + 1;	deque->rightindex = CENTER;	deque->len = 0;	deque->state = 0;	deque->weakreflist = NULL; 	return (PyObject *)deque;} static PyObject *deque_append(dequeobject *deque, PyObject *item){	deque->state++;	if (deque->rightindex == BLOCKLEN-1) {		block *b = newblock(deque->rightblock, NULL, deque->len);		if (b == NULL)			return NULL;		assert(deque->rightblock->rightlink == NULL);		deque->rightblock->rightlink = b;		deque->rightblock = b;		deque->rightindex = -1;	}	Py_INCREF(item);	deque->len++;	deque->rightindex++;	deque->rightblock->data[deque->rightindex] = item;	Py_RETURN_NONE;} PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque."); static PyObject *deque_appendleft(dequeobject *deque, PyObject *item){	deque->state++;	if (deque->leftindex == 0) {		block *b = newblock(NULL, deque->leftblock, deque->len);		if (b == NULL)			return NULL;		assert(deque->leftblock->leftlink == NULL);		deque->leftblock->leftlink = b;		deque->leftblock = b;		deque->leftindex = BLOCKLEN;	}	Py_INCREF(item);	deque->len++;	deque->leftindex--;	deque->leftblock->data[deque->leftindex] = item;	Py_RETURN_NONE;} PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque."); static PyObject *deque_pop(dequeobject *deque, PyObject *unused){	PyObject *item;	block *prevblock; 	if (deque->len == 0) {		PyErr_SetString(PyExc_IndexError, "pop from an empty deque");		return NULL;	}	item = deque->rightblock->data[deque->rightindex];	deque->rightindex--;	deque->len--;	deque->state++; 	if (deque->rightindex == -1) {		if (deque->len == 0) {			assert(deque->leftblock == deque->rightblock);			assert(deque->leftindex == deque->rightindex+1);			/* re-center instead of freeing a block */			deque->leftindex = CENTER + 1;			deque->rightindex = CENTER;		} else {			prevblock = deque->rightblock->leftlink;			assert(deque->leftblock != deque->rightblock);			PyMem_Free(deque->rightblock);			prevblock->rightlink = NULL;			deque->rightblock = prevblock;			deque->rightindex = BLOCKLEN - 1;		}	}	return item;} PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element."); static PyObject *deque_popleft(dequeobject *deque, PyObject *unused){	PyObject *item;	block *prevblock; 	if (deque->len == 0) {		PyErr_SetString(PyExc_IndexError, "pop from an empty deque");		return NULL;	}	assert(deque->leftblock != NULL);	item = deque->leftblock->data[deque->leftindex];	deque->leftindex++;	deque->len--;	deque->state++; 	if (deque->leftindex == BLOCKLEN) {		if (deque->len == 0) {			assert(deque->leftblock == deque->rightblock);			assert(deque->leftindex == deque->rightindex+1);			/* re-center instead of freeing a block */			deque->leftindex = CENTER + 1;			deque->rightindex = CENTER;		} else {			assert(deque->leftblock != deque->rightblock);			prevblock = deque->leftblock->rightlink;			PyMem_Free(deque->leftblock);			assert(prevblock != NULL);			prevblock->leftlink = NULL;			deque->leftblock = prevblock;			deque->leftindex = 0;		}	}	return item;} PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element."); static PyObject *deque_extend(dequeobject *deque, PyObject *iterable){	PyObject *it, *item; 	it = PyObject_GetIter(iterable);	if (it == NULL)		return NULL; 	while ((item = PyIter_Next(it)) != NULL) {		deque->state++;		if (deque->rightindex == BLOCKLEN-1) {			block *b = newblock(deque->rightblock, NULL,					    deque->len);			if (b == NULL) {				Py_DECREF(item);				Py_DECREF(it);				return NULL;			}			assert(deque->rightblock->rightlink == NULL);			deque->rightblock->rightlink = b;			deque->rightblock = b;			deque->rightindex = -1;		}		deque->len++;		deque->rightindex++;		deque->rightblock->data[deque->rightindex] = item;	}	Py_DECREF(it);	if (PyErr_Occurred())		return NULL;	Py_RETURN_NONE;} PyDoc_STRVAR(extend_doc,"Extend the right side of the deque with elements from the iterable"); static PyObject *deque_extendleft(dequeobject *deque, PyObject *iterable){	PyObject *it, *item; 	it = PyObject_GetIter(iterable);	if (it == NULL)		return NULL; 	while ((item = PyIter_Next(it)) != NULL) {		deque->state++;		if (deque->leftindex == 0) {			block *b = newblock(NULL, deque->leftblock,					    deque->len);			if (b == NULL) {				Py_DECREF(item);				Py_DECREF(it);				return NULL;			}			assert(deque->leftblock->leftlink == NULL);			deque->leftblock->leftlink = b;			deque->leftblock = b;			deque->leftindex = BLOCKLEN;		}		deque->len++;		deque->leftindex--;		deque->leftblock->data[deque->leftindex] = item;	}	Py_DECREF(it);	if (PyErr_Occurred())		return NULL;	Py_RETURN_NONE;} PyDoc_STRVAR(extendleft_doc,"Extend the left side of the deque with elements from the iterable"); static int_deque_rotate(dequeobject *deque, Py_ssize_t n){	int i, len=deque->len, halflen=(len+1)>>1;	PyObject *item, *rv; 	if (len == 0)		return 0;	if (n > halflen || n < -halflen) {		n %= len;		if (n > halflen)			n -= len;		else if (n < -halflen)			n += len;	} 	for (i=0 ; i<n ; i++) {		item = deque_pop(deque, NULL);		assert (item != NULL);		rv = deque_appendleft(deque, item);		Py_DECREF(item);		if (rv == NULL)			return -1;		Py_DECREF(rv);	}	for (i=0 ; i>n ; i--) {		item = deque_popleft(deque, NULL);		assert (item != NULL);		rv = deque_append(deque, item);		Py_DECREF(item);		if (rv == NULL)			return -1;		Py_DECREF(rv);	}	return 0;} static PyObject *deque_rotate(dequeobject *deque, PyObject *args){	int n=1; 	if (!PyArg_ParseTuple(args, "|i:rotate", &n))		return NULL;	if (_deque_rotate(deque, n) == 0)		Py_RETURN_NONE;	return NULL;} PyDoc_STRVAR(rotate_doc,"Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left."); static Py_ssize_tdeque_len(dequeobject *deque){	return deque->len;} static PyObject *deque_remove(dequeobject *deque, PyObject *value){	Py_ssize_t i, n=deque->len; 	for (i=0 ; i<n ; i++) {		PyObject *item = deque->leftblock->data[deque->leftindex];		int cmp = PyObject_RichCompareBool(item, value, Py_EQ); 		if (deque->len != n) {			PyErr_SetString(PyExc_IndexError,				"deque mutated during remove().");			return NULL;		}		if (cmp > 0) {			PyObject *tgt = deque_popleft(deque, NULL);			assert (tgt != NULL);			Py_DECREF(tgt);			if (_deque_rotate(deque, i) == -1)				return NULL;			Py_RETURN_NONE;		}		else if (cmp < 0) {			_deque_rotate(deque, i);			return NULL;		}		_deque_rotate(deque, -1);	}	PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");	return NULL;} PyDoc_STRVAR(remove_doc,"D.remove(value) -- remove first occurrence of value."); static intdeque_clear(dequeobject *deque){	PyObject *item; 	while (deque->len) {		item = deque_pop(deque, NULL);		assert (item != NULL);		Py_DECREF(item);	}	assert(deque->leftblock == deque->rightblock &&	       deque->leftindex - 1 == deque->rightindex &&	       deque->len == 0);	return 0;} static PyObject *deque_item(dequeobject *deque, int i){	block *b;	PyObject *item;	int n, index=i; 	if (i < 0 || i >= deque->len) {		PyErr_SetString(PyExc_IndexError,				"deque index out of range");		return NULL;	} 	if (i == 0) {		i = deque->leftindex;		b = deque->leftblock;	} else if (i == deque->len - 1) {		i = deque->rightindex;		b = deque->rightblock;	} else {		i += deque->leftindex;		n = i / BLOCKLEN;		i %= BLOCKLEN;		if (index < (deque->len >> 1)) {			b = deque->leftblock;			while (n--)				b = b->rightlink;		} else {			n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;			b = deque->rightblock;			while (n--)				b = b->leftlink;		}	}	item = b->data[i];	Py_INCREF(item);	return item;} /* delitem() implemented in terms of rotate for simplicity and reasonable   performance near the end points.  If for some reason this method becomes   popular, it is not hard to re-implement this using direct data movement   (similar to code in list slice assignment) and achieve a two or threefold   performance boost.*/ static intdeque_del_item(dequeobject *deque, Py_ssize_t i){	PyObject *item; 	assert (i >= 0 && i < deque->len);	if (_deque_rotate(deque, -i) == -1)		return -1; 	item = deque_popleft(deque, NULL);	assert (item != NULL);	Py_DECREF(item); 	return _deque_rotate(deque, i);} static intdeque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v){	PyObject *old_value;	block *b;	Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i; 	if (i < 0 || i >= len) {		PyErr_SetString(PyExc_IndexError,				"deque index out of range");		return -1;	}	if (v == NULL)		return deque_del_item(deque, i);

Lines 1–500 of 1370. Load more