[Python-checkins] python/nondist/sandbox/collections dequemodule.c, NONE, 1.1 setup.py, NONE, 1.1 test_deque.py, NONE, 1.1

[rhettinger at projects.sourceforge.net]

Update of /cvsroot/python/python/nondist/sandbox/collections
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12759/collections

Added Files:
	dequemodule.c setup.py test_deque.py 
Log Message:
* Start a sandbox area for collections.
* Add a module for high-speed deque implementation.



--- NEW FILE: dequemodule.c ---
#include "Python.h"

/* deque module implementation 
   Written and maintained by Raymond D. Hettinger <python at rcn.com>
   Copyright (c) 2004 Python Software Foundation.
   All rights reserved.
*/

#define BLOCKLEN 30

typedef struct BLOCK {
	struct BLOCK *leftlink;
	struct BLOCK *rightlink;
	PyObject *data[BLOCKLEN];
} block;

static block *newblock(block *leftlink, block *rightlink){
	block *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;
	int rightindex;
	int len;
} dequeobject;

static PyObject *
deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	dequeobject *deque;
	block *b;

	/* create dequeobject structure */
	deque = (dequeobject *)type->tp_alloc(type, 0);
	if (deque == NULL)
		return NULL;
	
	b = newblock(NULL, NULL);
	if (b == NULL) {
		Py_DECREF(deque);
		return NULL;
	}

	deque->leftblock = b;
	deque->rightblock = b;
	deque->leftindex = BLOCKLEN / 2 + 1;
	deque->rightindex = BLOCKLEN / 2;
	deque->len = 0;

	return (PyObject *)deque;
}

static PyObject *
deque_append(dequeobject *deque, PyObject *item)
{
	deque->rightindex++;
	deque->len++;
	if (deque->rightindex == BLOCKLEN) {
		block *b = newblock(deque->rightblock, NULL);
		if (b == NULL)
			return NULL;
		deque->rightblock->rightlink = b;
		deque->rightblock = b;
		deque->rightindex = 0;
	}
	Py_INCREF(item);
	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->leftindex--;
	deque->len++;
	if (deque->leftindex == -1) {
		block *b = newblock(NULL, deque->leftblock);
		if (b == NULL)
			return NULL;
		deque->leftblock->leftlink = b;
		deque->leftblock = b;
		deque->leftindex = BLOCKLEN - 1;
	}
	Py_INCREF(item);
	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->leftblock == deque->rightblock &&
		deque->leftindex > deque->rightindex) {
		PyErr_SetString(PyExc_IndexError, "pop from an emtpy deque");
		return NULL;
	}
	item = deque->rightblock->data[deque->rightindex];
	deque->rightindex--;
	deque->len--;

	if (deque->rightindex == -1) {
		prevblock = deque->rightblock->leftlink;
		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->leftblock == deque->rightblock &&
		deque->leftindex > deque->rightindex) {
		PyErr_SetString(PyExc_IndexError, "pop from an emtpy deque");
		return NULL;
	}
	item = deque->leftblock->data[deque->leftindex];
	deque->leftindex++;
	deque->len--;

	if (deque->leftindex == BLOCKLEN) {
		prevblock = deque->leftblock->rightlink;
		PyMem_Free(deque->leftblock);
		prevblock->leftlink = NULL;
		deque->leftblock = prevblock;
		deque->leftindex = 0;
	}
	return item;
}

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

static int
deque_len(dequeobject *deque)
{
	return deque->len;
}

static int
deque_clear(dequeobject *deque)
{
	PyObject *item;

	while (deque_len(deque)) {
		item = deque_pop(deque, NULL);
		Py_DECREF(item);
	}
	return 0;
}

static PyObject *
deque_clearmethod(dequeobject *deque)
{
	if (deque_clear(deque) == -1)
		return NULL;
	Py_RETURN_NONE;
}

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

static void
deque_dealloc(dequeobject *deque)	// XXX ? any uncomfortable assumptions
{
	PyObject_GC_UnTrack(deque);
	deque_clear(deque);
	PyMem_Free(deque->leftblock);
	deque->leftblock = NULL;
	deque->rightblock = NULL;
	deque->ob_type->tp_free(deque);
}

static int
set_traverse(dequeobject *deque, visitproc visit, void *arg)
{
	block * b = deque->leftblock;
	int index = deque->leftindex;
	int err;
	PyObject *item;

	while (b != deque->rightblock || index <= deque->rightindex) {
		item = b->data[index];
		index++;
		if (index == BLOCKLEN && b->rightlink != NULL) {
			b = b->rightlink;
			index = 0;
		}
		err = visit(item, arg);
		if (err) 
			return err;
	}
	return 0;
}

static long
deque_nohash(PyObject *self)
{
	PyErr_SetString(PyExc_TypeError, "deque objects are unhashable");
	return -1;
}

static PyObject *
deque_copy(PyObject *deque)
{
	return PyObject_CallFunctionObjArgs((PyObject *)(deque->ob_type), 
		deque, NULL);
}

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

static PyObject *
deque_reduce(dequeobject *deque)
{
	PyObject *seq, *args, *result;

	seq = PySequence_Tuple((PyObject *)deque);
	if (seq == NULL)
		return NULL;
	args = PyTuple_Pack(1, seq);
	result = PyTuple_Pack(2, deque->ob_type, args);
	Py_DECREF(seq);
	Py_DECREF(args);
	return result;
}

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

static PyObject *
deque_repr(PyObject *deque)
{
	PyObject *aslist, *result, *fmt;
	int i;

	i = Py_ReprEnter(deque);
	if (i != 0) {
		if (i < 0)
			return NULL;
		return PyString_FromString("[...]");
	}

	aslist = PySequence_List(deque);
	if (aslist == NULL) {
		Py_ReprLeave(deque);
		return NULL;
	}

	fmt = PyString_FromString("deque(%r)");
	if (fmt == NULL) {
		Py_DECREF(aslist);
		Py_ReprLeave(deque);
		return NULL;
	}
	result = PyString_Format(fmt, aslist);
	Py_DECREF(fmt);
	Py_DECREF(aslist);
	Py_ReprLeave(deque);
	return result;
}

static int
deque_tp_print(PyObject *deque, FILE *fp, int flags)
{
	PyObject *it, *item;
	int pos=0;
	char *emit = "";	/* No separator emitted on first pass */
	char *separator = ", ";
	int i;

	i = Py_ReprEnter(deque);
	if (i != 0) {
		if (i < 0)
			return i;
		fputs("[...]", fp);
		return 0;
	}

	it = PyObject_GetIter(deque);
	if (it == NULL)
		return -1;

	fputs("deque([", fp);
	while ((item = PyIter_Next(it)) != NULL) {
		fputs(emit, fp);
		emit = separator;
		if (PyObject_Print(item, fp, 0) != 0) {
			Py_DECREF(item);
			Py_DECREF(it);
			Py_ReprLeave(deque);
			return -1;
		}
		Py_DECREF(item);
	}
	Py_ReprLeave(deque);
	Py_DECREF(it);
	if (PyErr_Occurred()) 
		return -1;
	fputs("])", fp);
	return 0;
}

static int
deque_init(dequeobject *deque, PyObject *args, PyObject *kwds)
{
	PyObject *iterable = NULL, *it, *item, *rv;

	if (!PyArg_UnpackTuple(args, "deque", 0, 1, &iterable))
		return -1;

	if (iterable != NULL) {
		it = PyObject_GetIter(iterable);
		if (it == NULL)
			return -1;

		while ((item = PyIter_Next(it)) != NULL) {
			assert (item != NULL);
			rv = deque_append(deque, item);
			Py_DECREF(item);
			if (rv == NULL)
				return -1;
			Py_DECREF(rv);
		}
		Py_DECREF(it);
		if (PyErr_Occurred()) 
			return -1;
	}
	return 0;
}

static PySequenceMethods deque_as_sequence = {
	(inquiry)deque_len,		/* sq_length */
	0,				/* sq_concat */
};

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

static PyObject *deque_iter(dequeobject *deque);

static PyMethodDef deque_methods[] = {
	{"append",		(PyCFunction)deque_append,	
		METH_O,		 append_doc},
	{"appendleft",		(PyCFunction)deque_appendleft,	
		METH_O,		 appendleft_doc},
	{"clear",		(PyCFunction)deque_clearmethod,	
		METH_NOARGS,	 clear_doc},
	{"__copy__",		(PyCFunction)deque_copy,	
		METH_NOARGS,	 copy_doc},
	{"pop",			(PyCFunction)deque_pop,	
		METH_NOARGS,	 pop_doc},
	{"popleft",		(PyCFunction)deque_popleft,	
		METH_NOARGS,	 pop_doc},
	{"__reduce__",	(PyCFunction)deque_reduce,	
		METH_NOARGS,	 reduce_doc},
	{NULL,		NULL}	/* sentinel */
};

PyDoc_STRVAR(deque_doc,
"deque(iterable) --> deque object\n\
\n\
Build an ordered collection accessible from endpoints only.");

PyTypeObject deque_type = {
	PyObject_HEAD_INIT(NULL)
	0,				/* ob_size */
	"deque.deque",			/* tp_name */
	sizeof(dequeobject),		/* tp_basicsize */
	0,				/* tp_itemsize */
	/* methods */
	(destructor)deque_dealloc,	/* tp_dealloc */
	(printfunc)deque_tp_print,	/* tp_print */
	0,				/* tp_getattr */
	0,				/* tp_setattr */
	0,				/* tp_compare */
	(reprfunc)deque_repr,		/* tp_repr */
	0,				/* tp_as_number */
	&deque_as_sequence,		/* tp_as_sequence */
	0,				/* tp_as_mapping */
	deque_nohash,			/* tp_hash */
	0,				/* tp_call */
	0,				/* tp_str */
	PyObject_GenericGetAttr,	/* tp_getattro */
	0,				/* tp_setattro */
	0,				/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,	/* tp_flags */
	deque_doc,			/* tp_doc */
	(traverseproc)set_traverse,	/* tp_traverse */
	(inquiry)deque_clear,		/* tp_clear */
	0,				/* tp_richcompare */
	0,				/* tp_weaklistoffset*/
	(getiterfunc)deque_iter,	/* tp_iter */
	0,				/* tp_iternext */
	deque_methods,			/* tp_methods */
	0,				/* tp_members */
	0,				/* tp_getset */
	0,				/* tp_base */
	0,				/* tp_dict */
	0,				/* tp_descr_get */
	0,				/* tp_descr_set */
	0,				/* tp_dictoffset */
	(initproc)deque_init,		/* tp_init */
	PyType_GenericAlloc,		/* tp_alloc */
	deque_new,			/* tp_new */
	PyObject_GC_Del,		/* tp_free */
};

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

typedef struct {
	PyObject_HEAD
	int index;
	block *b;
	dequeobject *deque;
} dequeiterobject;

PyTypeObject dequeiter_type;

static PyObject *
deque_iter(dequeobject *deque)
{
	dequeiterobject *it;

	it = PyObject_New(dequeiterobject, &dequeiter_type);
	if (it == NULL)
		return NULL;
	it->b = deque->leftblock;
	it->index = deque->leftindex;
	Py_INCREF(deque);
	it->deque = deque;
	return (PyObject *)it;
}

static void
dequeiter_dealloc(dequeiterobject *dio)
{
	Py_XDECREF(dio->deque);
	dio->ob_type->tp_free(dio);
}

static PyObject *
dequeiter_next(dequeiterobject *it)
{
	PyObject *item;
	if (it->b == it->deque->rightblock && it->index > it->deque->rightindex)
		return NULL;

	item = it->b->data[it->index];
	it->index++;
	if (it->index == BLOCKLEN && it->b->rightlink != NULL) {
		it->b = it->b->rightlink;
		it->index = 0;
	}
	Py_INCREF(item);
	return item;
}

PyTypeObject dequeiter_type = {
	PyObject_HEAD_INIT(NULL)
	0,					/* ob_size */
	"dequeerseiterator",			/* tp_name */
	sizeof(dequeiterobject),		/* tp_basicsize */
	0,					/* tp_itemsize */
	/* methods */
	(destructor)dequeiter_dealloc,		/* tp_dealloc */
	0,					/* tp_print */
	0,					/* tp_getattr */
	0,					/* tp_setattr */
	0,					/* tp_compare */
	0,					/* tp_repr */
	0,					/* tp_as_number */
	0,					/* tp_as_sequence */
	0,					/* tp_as_mapping */
	0,					/* tp_hash */
	0,					/* tp_call */
	0,					/* tp_str */
	PyObject_GenericGetAttr,		/* tp_getattro */
	0,					/* tp_setattro */
	0,					/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT,			/* tp_flags */
	0,					/* tp_doc */
	0,					/* tp_traverse */
	0,					/* tp_clear */
	0,					/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	PyObject_SelfIter,			/* tp_iter */
	(iternextfunc)dequeiter_next,		/* tp_iternext */
	0,
};

/* module level code ********************************************************/

PyDoc_STRVAR(module_doc,
"deque collection type.\n\
");

PyMODINIT_FUNC
initdeque(void)
{
	PyObject *m;

	m = Py_InitModule3("deque", NULL, module_doc);

	if (PyType_Ready(&deque_type) < 0)
		return;
	Py_INCREF(&deque_type);
	PyModule_AddObject(m, "deque", (PyObject *)&deque_type);

	if (PyType_Ready(&dequeiter_type) < 0)
		return;

	return;
}

--- NEW FILE: setup.py ---
from distutils.core import setup, Extension

setup(name="deque",
      ext_modules=[Extension("deque", ["dequemodule.c"])])

--- NEW FILE: test_deque.py ---
from deque import deque
import unittest
from test import test_support
import copy
import cPickle as pickle
from cStringIO import StringIO

BIG = 100000

class TestBasic(unittest.TestCase):

    def test_exercise_basics(self):
        d = deque(xrange(100))
        d.__init__(xrange(100, 200))
        for i in xrange(200, 400):
            d.append(i)
        for i in reversed(xrange(-200, 0)):
            d.appendleft(i)
        self.assertEqual(list(d), range(-200, 400))
        self.assertEqual(len(d), 600)

        left = [d.popleft() for i in xrange(250)]
        self.assertEqual(left, range(-200, 50))
        self.assertEqual(list(d), range(50, 400))

        right = [d.pop() for i in xrange(250)]
        right.reverse()
        self.assertEqual(right, range(150, 400))
        self.assertEqual(list(d), range(50, 150))

    def test_underflow(self):
        d = deque()
        self.assertRaises(IndexError, d.pop)  ## XXX should be lookuperror?
        self.assertRaises(IndexError, d.popleft)

    def test_clear(self):
        d = deque(xrange(100))
        self.assertEqual(len(d), 100)
        d.clear()
        self.assertEqual(len(d), 0)
        self.assertEqual(list(d), [])

    def test_repr(self):
        d = deque(xrange(200))
        e = eval(repr(d))
        self.assertEqual(list(d), list(e))
        d.append(d)
        self.assert_('...' in repr(d))

    def test_print(self):
        d = deque(xrange(200))
        d.append(d)
        f = StringIO()
        print >> f, d,
        self.assertEqual(f.getvalue(), repr(d))
        f.close()

    def test_hash(self):
        self.assertRaises(TypeError, hash, deque('abc'))

    def test_long_steadystate_queue_popleft(self):
        d = deque(xrange(100))
        append, pop = d.append, d.popleft
        for i in xrange(100, BIG):
            append(i)
            x = pop()
            if x != i - 100:
                self.assertEqual(x, i-100)
        self.assertEqual(list(d), range(BIG-100, BIG))

    def test_long_steadystate_queue_popright(self):
        d = deque(reversed(xrange(100)))
        append, pop = d.appendleft, d.pop
        for i in xrange(100, BIG):
            append(i)
            x = pop()
            if x != i - 100:
                self.assertEqual(x, i-100)
        self.assertEqual(list(reversed(list(d))), range(BIG-100, BIG))

    def test_big_queue_popleft(self):
        pass
        d = deque()
        append, pop = d.append, d.popleft
        for i in xrange(BIG):
            append(i)
        for i in xrange(BIG):
            x = pop()
            if x != i:
                self.assertEqual(x, i)

    def test_big_queue_popright(self):
        d = deque()
        append, pop = d.appendleft, d.pop
        for i in xrange(BIG):
            append(i)
        for i in xrange(BIG):
            x = pop()
            if x != i:
                self.assertEqual(x, i)

    def test_big_stack_right(self):
        d = deque()
        append, pop = d.append, d.pop
        for i in xrange(BIG):
            append(i)
        for i in reversed(xrange(BIG)):
            x = pop()
            if x != i:
                self.assertEqual(x, i)
        self.assertEqual(len(d), 0)

    def test_big_stack_left(self):
        d = deque()
        append, pop = d.appendleft, d.popleft
        for i in xrange(BIG):
            append(i)
        for i in reversed(xrange(BIG)):
            x = pop()
            if x != i:
                self.assertEqual(x, i)
        self.assertEqual(len(d), 0)

    def test_roundtrip_iter_init(self):
        d = deque(xrange(200))
        e = deque(d)
        self.assertNotEqual(id(d), id(e))
        self.assertEqual(list(d), list(e))

    def test_pickle(self):
        d = deque(xrange(200))
        s = pickle.dumps(d)
        e = pickle.loads(s)
        self.assertNotEqual(id(d), id(e))
        self.assertEqual(list(d), list(e))

    def test_deepcopy(self):
        mut = [10]
        d = deque([mut])
        e = copy.deepcopy(d)
        self.assertEqual(list(d), list(e))
        mut[0] = 11
        self.assertNotEqual(id(d), id(e))
        self.assertNotEqual(list(d), list(e))

    def test_copy(self):
        mut = [10]
        d = deque([mut])
        e = copy.copy(d)
        self.assertEqual(list(d), list(e))
        mut[0] = 11
        self.assertNotEqual(id(d), id(e))
        self.assertEqual(list(d), list(e))

#==============================================================================

def test_main(verbose=None):
    import sys
    from test import test_sets
    test_classes = (
        TestBasic,
    )

    test_support.run_unittest(*test_classes)

    # verify reference counting
    if verbose and hasattr(sys, "gettotalrefcount"):
        import gc
        counts = [None] * 5
        for i in xrange(len(counts)):
            test_support.run_unittest(*test_classes)
            gc.collect()
            counts[i] = sys.gettotalrefcount()
        print counts

if __name__ == "__main__":
    test_main(verbose=True)