From 756b3f3c15bd314ffa25299ca25465ae21e62a30 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Thu, 29 Jan 2004 06:37:52 +0000 Subject: * Move collections.deque() in from the sandbox * Add unittests, newsitem, and whatsnew * Apply to Queue.py mutex.py threading.py pydoc.py and shlex.py * Docs are forthcoming --- Doc/lib/libbisect.tex | 17 -- Doc/lib/libqueue.tex | 4 - Doc/whatsnew/whatsnew24.tex | 25 ++ Lib/Queue.py | 5 +- Lib/mutex.py | 6 +- Lib/pydoc.py | 9 +- Lib/shlex.py | 16 +- Lib/test/test_bisect.py | 17 -- Lib/test/test_deque.py | 337 +++++++++++++++++++++++++ Lib/threading.py | 5 +- Misc/NEWS | 7 + Modules/collectionsmodule.c | 582 ++++++++++++++++++++++++++++++++++++++++++++ PC/VC6/pythoncore.dsp | 4 + PC/config.c | 2 + setup.py | 2 + 15 files changed, 982 insertions(+), 56 deletions(-) create mode 100644 Lib/test/test_deque.py create mode 100644 Modules/collectionsmodule.c diff --git a/Doc/lib/libbisect.tex b/Doc/lib/libbisect.tex index 3241891..516e5cf 100644 --- a/Doc/lib/libbisect.tex +++ b/Doc/lib/libbisect.tex @@ -80,22 +80,5 @@ breakpoints: 85 and up is an `A', 75..84 is a `B', etc. 'C' >>> map(grade, [33, 99, 77, 44, 12, 88]) ['E', 'A', 'B', 'D', 'F', 'A'] -\end{verbatim} - -The bisect module can be used with the Queue module to implement a priority -queue (example courtesy of Fredrik Lundh): \index{Priority Queue} - -\begin{verbatim} -import Queue, bisect - -class PriorityQueue(Queue.Queue): - def _put(self, item): - bisect.insort(self.queue, item) -# usage -queue = PriorityQueue(0) -queue.put((2, "second")) -queue.put((1, "first")) -queue.put((3, "third")) -priority, value = queue.get() \end{verbatim} diff --git a/Doc/lib/libqueue.tex b/Doc/lib/libqueue.tex index 0770bfe..52c1125 100644 --- a/Doc/lib/libqueue.tex +++ b/Doc/lib/libqueue.tex @@ -12,10 +12,6 @@ information must be exchanged safely between multiple threads. The semantics. It depends on the availability of thread support in Python. -\begin{seealso} - \seemodule{bisect}{PriorityQueue example using the Queue class} -\end{seealso} - The \module{Queue} module defines the following class and exception: diff --git a/Doc/whatsnew/whatsnew24.tex b/Doc/whatsnew/whatsnew24.tex index f435b87..ed4a57f 100644 --- a/Doc/whatsnew/whatsnew24.tex +++ b/Doc/whatsnew/whatsnew24.tex @@ -322,6 +322,31 @@ euc-jisx0213, iso-2022-jp, iso-2022-jp-1, iso-2022-jp-2, \item Korean: cp949, euc-kr, johab, iso-2022-kr \end{itemize} +\item There is a new \module{collections} module which currently offers + just one new datatype, \class{deque}, which offers high-performance, + thread-safe, memory friendly appends and pops on either side of the + deque resulting in efficient stacks and queues: + +\begin{verbatim} +>>> from collections import deque +>>> d = deque('ghi') # make a new deque with three items +>>> d.append('j') # add a new entry to the right side +>>> d.appendleft('f') # add a new entry to the left side +>>> d # show the representation of the deque +deque(['f', 'g', 'h', 'i', 'j']) +>>> d.pop() # return and remove the rightmost item +'j' +>>> d.popleft() # return and remove the leftmost item +'f' +>>> list(d) # list the contents of the deque +['g', 'h', 'i'] +>>> 'h' in d # search the deque +True +\end{verbatim} + +Several modules now take advantage of \class{collections.deque()} for +improved performance: \module{Queue}, \module{mutex}, \module{shlex} +\module{threading}, and \module{pydoc}. \item The \module{heapq} module has been converted to C. The resulting ten-fold improvement in speed makes the module suitable for handling diff --git a/Lib/Queue.py b/Lib/Queue.py index 980aee6..44c9ca3 100644 --- a/Lib/Queue.py +++ b/Lib/Queue.py @@ -1,6 +1,7 @@ """A multi-producer, multi-consumer queue.""" from time import time as _time, sleep as _sleep +from collections import deque __all__ = ['Empty', 'Full', 'Queue'] @@ -184,7 +185,7 @@ class Queue: # Initialize the queue representation def _init(self, maxsize): self.maxsize = maxsize - self.queue = [] + self.queue = deque() def _qsize(self): return len(self.queue) @@ -203,4 +204,4 @@ class Queue: # Get an item from the queue def _get(self): - return self.queue.pop(0) + return self.queue.popleft() diff --git a/Lib/mutex.py b/Lib/mutex.py index e15710a..5d35bdf 100644 --- a/Lib/mutex.py +++ b/Lib/mutex.py @@ -12,11 +12,13 @@ Of course, no multi-threading is implied -- hence the funny interface for lock, where a function is called once the lock is aquired. """ +from collections import deque + class mutex: def __init__(self): """Create a new mutex -- initially unlocked.""" self.locked = 0 - self.queue = [] + self.queue = deque() def test(self): """Test the locked bit of the mutex.""" @@ -44,7 +46,7 @@ class mutex: """Unlock a mutex. If the queue is not empty, call the next function with its argument.""" if self.queue: - function, argument = self.queue.pop(0) + function, argument = self.queue.popleft() function(argument) else: self.locked = 0 diff --git a/Lib/pydoc.py b/Lib/pydoc.py index e53aa16..e6b53c1 100755 --- a/Lib/pydoc.py +++ b/Lib/pydoc.py @@ -55,6 +55,7 @@ Mynd you, m import sys, imp, os, re, types, inspect, __builtin__ from repr import Repr from string import expandtabs, find, join, lower, split, strip, rfind, rstrip +from collections import deque # --------------------------------------------------------- common routines @@ -685,7 +686,7 @@ class HTMLDoc(Doc): hr = HorizontalRule() # List the mro, if non-trivial. - mro = list(inspect.getmro(object)) + mro = deque(inspect.getmro(object)) if len(mro) > 2: hr.maybe() push('
Method resolution order:
\n') @@ -763,7 +764,7 @@ class HTMLDoc(Doc): while attrs: if mro: - thisclass = mro.pop(0) + thisclass = mro.popleft() else: thisclass = attrs[0][2] attrs, inherited = _split_list(attrs, lambda t: t[2] is thisclass) @@ -1083,7 +1084,7 @@ class TextDoc(Doc): push = contents.append # List the mro, if non-trivial. - mro = list(inspect.getmro(object)) + mro = deque(inspect.getmro(object)) if len(mro) > 2: push("Method resolution order:") for base in mro: @@ -1152,7 +1153,7 @@ class TextDoc(Doc): inspect.classify_class_attrs(object)) while attrs: if mro: - thisclass = mro.pop(0) + thisclass = mro.popleft() else: thisclass = attrs[0][2] attrs, inherited = _split_list(attrs, lambda t: t[2] is thisclass) diff --git a/Lib/shlex.py b/Lib/shlex.py index b302699..ccf9038 100644 --- a/Lib/shlex.py +++ b/Lib/shlex.py @@ -9,6 +9,7 @@ import os.path import sys +from collections import deque try: from cStringIO import StringIO @@ -45,11 +46,11 @@ class shlex: self.escape = '\\' self.escapedquotes = '"' self.state = ' ' - self.pushback = [] + self.pushback = deque() self.lineno = 1 self.debug = 0 self.token = '' - self.filestack = [] + self.filestack = deque() self.source = None if self.debug: print 'shlex: reading from %s, line %d' \ @@ -59,13 +60,13 @@ class shlex: "Push a token onto the stack popped by the get_token method" if self.debug >= 1: print "shlex: pushing token " + `tok` - self.pushback.insert(0, tok) + self.pushback.appendleft(tok) def push_source(self, newstream, newfile=None): "Push an input source onto the lexer's input source stack." if isinstance(newstream, basestring): newstream = StringIO(newstream) - self.filestack.insert(0, (self.infile, self.instream, self.lineno)) + self.filestack.appendleft((self.infile, self.instream, self.lineno)) self.infile = newfile self.instream = newstream self.lineno = 1 @@ -78,8 +79,7 @@ class shlex: def pop_source(self): "Pop the input source stack." self.instream.close() - (self.infile, self.instream, self.lineno) = self.filestack[0] - self.filestack = self.filestack[1:] + (self.infile, self.instream, self.lineno) = self.filestack.popleft() if self.debug: print 'shlex: popping to %s, line %d' \ % (self.instream, self.lineno) @@ -88,7 +88,7 @@ class shlex: def get_token(self): "Get a token from the input stream (or from stack if it's nonempty)" if self.pushback: - tok = self.pushback.pop(0) + tok = self.pushback.popleft() if self.debug >= 1: print "shlex: popping token " + `tok` return tok @@ -226,7 +226,7 @@ class shlex: or self.whitespace_split: self.token = self.token + nextchar else: - self.pushback.insert(0, nextchar) + self.pushback.appendleft(nextchar) if self.debug >= 2: print "shlex: I see punctuation in word state" self.state = ' ' diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py index 809d8af..6bb2112 100644 --- a/Lib/test/test_bisect.py +++ b/Lib/test/test_bisect.py @@ -170,23 +170,6 @@ This example uses bisect() to look up a letter grade for an exam total >>> map(grade, [33, 99, 77, 44, 12, 88]) ['E', 'A', 'B', 'D', 'F', 'A'] -The bisect module can be used with the Queue module to implement -a priority queue (example courtesy of Fredrik Lundh): - ->>> import Queue, bisect ->>> class PriorityQueue(Queue.Queue): -... def _put(self, item): -... bisect.insort(self.queue, item) -... ->>> queue = PriorityQueue(0) ->>> queue.put((2, "second")) ->>> queue.put((1, "first")) ->>> queue.put((3, "third")) ->>> queue.get() -(1, 'first') ->>> queue.get() -(2, 'second') - """ #------------------------------------------------------------------------------ diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py new file mode 100644 index 0000000..6221c91 --- /dev/null +++ b/Lib/test/test_deque.py @@ -0,0 +1,337 @@ +from collections 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_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_len(self): + d = deque('ab') + self.assertEqual(len(d), 2) + d.popleft() + self.assertEqual(len(d), 1) + d.pop() + self.assertEqual(len(d), 0) + self.assertRaises(LookupError, d.pop) + self.assertEqual(len(d), 0) + d.append('c') + self.assertEqual(len(d), 1) + d.appendleft('d') + self.assertEqual(len(d), 2) + d.clear() + self.assertEqual(len(d), 0) + + def test_underflow(self): + d = deque() + self.assertRaises(LookupError, d.pop) + self.assertRaises(LookupError, 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): + for size in (0, 1, 2, 100, 1000): + d = deque(xrange(size)) + append, pop = d.append, d.popleft + for i in xrange(size, BIG): + append(i) + x = pop() + if x != i - size: + self.assertEqual(x, i-size) + self.assertEqual(list(d), range(BIG-size, BIG)) + + def test_long_steadystate_queue_popright(self): + for size in (0, 1, 2, 100, 1000): + d = deque(reversed(xrange(size))) + append, pop = d.appendleft, d.pop + for i in xrange(size, BIG): + append(i) + x = pop() + if x != i - size: + self.assertEqual(x, i-size) + self.assertEqual(list(reversed(list(d))), range(BIG-size, 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 R(seqn): + 'Regular generator' + for i in seqn: + yield i + +class G: + 'Sequence using __getitem__' + def __init__(self, seqn): + self.seqn = seqn + def __getitem__(self, i): + return self.seqn[i] + +class I: + 'Sequence using iterator protocol' + def __init__(self, seqn): + self.seqn = seqn + self.i = 0 + def __iter__(self): + return self + def next(self): + if self.i >= len(self.seqn): raise StopIteration + v = self.seqn[self.i] + self.i += 1 + return v + +class Ig: + 'Sequence using iterator protocol defined with a generator' + def __init__(self, seqn): + self.seqn = seqn + self.i = 0 + def __iter__(self): + for val in self.seqn: + yield val + +class X: + 'Missing __getitem__ and __iter__' + def __init__(self, seqn): + self.seqn = seqn + self.i = 0 + def next(self): + if self.i >= len(self.seqn): raise StopIteration + v = self.seqn[self.i] + self.i += 1 + return v + +class N: + 'Iterator missing next()' + def __init__(self, seqn): + self.seqn = seqn + self.i = 0 + def __iter__(self): + return self + +class E: + 'Test propagation of exceptions' + def __init__(self, seqn): + self.seqn = seqn + self.i = 0 + def __iter__(self): + return self + def next(self): + 3/0 + +class S: + 'Test immediate stop' + def __init__(self, seqn): + pass + def __iter__(self): + return self + def next(self): + raise StopIteration + +from itertools import chain, imap +def L(seqn): + 'Test multiple tiers of iterators' + return chain(imap(lambda x:x, R(Ig(G(seqn))))) + + +class TestVariousIteratorArgs(unittest.TestCase): + + def test_constructor(self): + for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): + for g in (G, I, Ig, S, L, R): + self.assertEqual(list(deque(g(s))), list(g(s))) + self.assertRaises(TypeError, deque, X(s)) + self.assertRaises(TypeError, deque, N(s)) + self.assertRaises(ZeroDivisionError, deque, E(s)) + + def test_iter_with_altered_data(self): + d = deque('abcdefg') + it = iter(d) + d.pop() + self.assertRaises(RuntimeError, it.next) + +class Deque(deque): + pass + +class TestSubclass(unittest.TestCase): + + def test_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)) + + d.clear() + self.assertEqual(len(d), 0) + + def test_copy_pickle(self): + + d = Deque('abc') + + e = d.__copy__() + self.assertEqual(type(d), type(e)) + self.assertEqual(list(d), list(e)) + + e = Deque(d) + self.assertEqual(type(d), type(e)) + self.assertEqual(list(d), list(e)) + + s = pickle.dumps(d) + e = pickle.loads(s) + self.assertNotEqual(id(d), id(e)) + self.assertEqual(type(d), type(e)) + self.assertEqual(list(d), list(e)) + + +#============================================================================== + +def test_main(verbose=None): + import sys + from test import test_sets + test_classes = ( + TestBasic, + TestVariousIteratorArgs, + TestSubclass, + ) + + 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) diff --git a/Lib/threading.py b/Lib/threading.py index c5d5af3..6461adc 100644 --- a/Lib/threading.py +++ b/Lib/threading.py @@ -10,6 +10,7 @@ except ImportError: from time import time as _time, sleep as _sleep from traceback import format_exc as _format_exc +from collections import deque # Rename some stuff so "from threading import *" is safe __all__ = ['activeCount', 'Condition', 'currentThread', 'enumerate', 'Event', @@ -639,7 +640,7 @@ def _test(): self.rc = Condition(self.mon) self.wc = Condition(self.mon) self.limit = limit - self.queue = [] + self.queue = deque() def put(self, item): self.mon.acquire() @@ -657,7 +658,7 @@ def _test(): while not self.queue: self._note("get(): queue empty") self.rc.wait() - item = self.queue.pop(0) + item = self.queue.popleft() self._note("get(): got %s, %d left", item, len(self.queue)) self.wc.notify() self.mon.release() diff --git a/Misc/NEWS b/Misc/NEWS index fa5ef20..71a549e 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -121,6 +121,13 @@ Core and builtins Extension modules ----------------- +- Added a collections module containing a new datatype, deque(), + offering high-performance, thread-safe, memory friendly appends + and pops on either side of the deque. + +- Several modules now take advantage of collections.deque() for + improved performance: Queue, mutex, shlex, threading, and pydoc. + - The operator module has two new functions, attrgetter() and itemgetter() which are useful for creating fast data extractor functions for map(), list.sort(), itertools.groupby(), and diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c new file mode 100644 index 0000000..16c6e9a --- /dev/null +++ b/Modules/collectionsmodule.c @@ -0,0 +1,582 @@ +#include "Python.h" + +/* collections module implementation of a deque() datatype + Written and maintained by Raymond D. Hettinger + Copyright (c) 2004 Python Software Foundation. + All rights reserved. +*/ + +#define BLOCKLEN 46 + +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; + assert(deque->rightblock->rightlink == 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; + assert(deque->leftblock->leftlink == 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->len == 0) { + PyErr_SetString(PyExc_LookupError, "pop from an emtpy deque"); + return NULL; + } + item = deque->rightblock->data[deque->rightindex]; + deque->rightindex--; + deque->len--; + + 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 = BLOCKLEN / 2 + 1; + deque->rightindex = BLOCKLEN / 2; + } 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_LookupError, "pop from an emtpy deque"); + return NULL; + } + item = deque->leftblock->data[deque->leftindex]; + deque->leftindex++; + deque->len--; + + 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 = BLOCKLEN / 2 + 1; + deque->rightindex = BLOCKLEN / 2; + } else { + assert(deque->leftblock != deque->rightblock); + prevblock = deque->leftblock->rightlink; + assert(deque->leftblock != NULL); + 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 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); + if (item == NULL) + return -1; + Py_DECREF(item); + } + assert(deque->leftblock == deque->rightblock && + deque->leftindex > deque->rightindex); + 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) +{ + PyObject_GC_UnTrack(deque); + if (deque->leftblock != NULL) { + int err = deque_clear(deque); + assert(err == 0); + assert(deque->leftblock != NULL); + 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); + if (args == NULL) { + Py_DECREF(seq); + return NULL; + } + 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; + + 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) { + deque->rightindex++; + deque->len++; + if (deque->rightindex == BLOCKLEN) { + block *b = newblock(deque->rightblock, NULL); + if (b == NULL) { + Py_DECREF(it); + Py_DECREF(item); + return -1; + } + deque->rightblock->rightlink = b; + deque->rightblock = b; + deque->rightindex = 0; + } + deque->rightblock->data[deque->rightindex] = item; + } + 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, popleft_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 */ + "collections.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; + int len; +} 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; + it->len = deque->len; + 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; + + if (it->len != it->deque->len) { + it->len = -1; /* Make this state sticky */ + PyErr_SetString(PyExc_RuntimeError, + "deque changed size during iteration"); + 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 */ + "deque_iterator", /* 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, +"High performance data structures\n\ +"); + +PyMODINIT_FUNC +initcollections(void) +{ + PyObject *m; + + m = Py_InitModule3("collections", 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; +} diff --git a/PC/VC6/pythoncore.dsp b/PC/VC6/pythoncore.dsp index 56e8e37..5e0ba21 100644 --- a/PC/VC6/pythoncore.dsp +++ b/PC/VC6/pythoncore.dsp @@ -269,6 +269,10 @@ SOURCE=..\..\Python\codecs.c # End Source File # Begin Source File +SOURCE=..\..\Modules\collectionsmodule.c +# End Source File +# Begin Source File + SOURCE=..\..\Python\compile.c # End Source File # Begin Source File diff --git a/PC/config.c b/PC/config.c index a12f633..e618302 100644 --- a/PC/config.c +++ b/PC/config.c @@ -46,6 +46,7 @@ extern void initxxsubtype(void); extern void initzipimport(void); extern void init_random(void); extern void inititertools(void); +extern void initcollections(void); extern void initheapq(void); extern void init_bisect(void); extern void init_symtable(void); @@ -136,6 +137,7 @@ struct _inittab _PyImport_Inittab[] = { {"_bisect", init_bisect}, {"heapq", initheapq}, {"itertools", inititertools}, + {"collections", initcollections}, {"_symtable", init_symtable}, {"mmap", initmmap}, {"_csv", init_csv}, diff --git a/setup.py b/setup.py index 7e2fdd4..8439ef4 100644 --- a/setup.py +++ b/setup.py @@ -322,6 +322,8 @@ class PyBuildExt(build_ext): exts.append( Extension("_random", ["_randommodule.c"]) ) # fast iterator tools implemented in C exts.append( Extension("itertools", ["itertoolsmodule.c"]) ) + # high-performance collections + exts.append( Extension("collections", ["collectionsmodule.c"]) ) # bisect exts.append( Extension("_bisect", ["_bisectmodule.c"]) ) # heapq -- cgit v0.12