[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
rhettinger at projects.sourceforge.net
Mon Jan 26 00:25:41 EST 2004
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)
More information about the Python-checkins
mailing list