Mercurial > cpython-lru_cache-weakref

annotate Lib/Queue.py @ 46567:ffeecbebf3ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Block 2.6-only doc change.
author Georg Brandl <georg@python.org>
date Sat, 26 Apr 2008 18:28:08 +0000
parents b469e90273eb
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
11691
e34991022571 Mass patch by Ka-Ping Yee:
Guido van Rossum <guido@python.org>
parents: 11267
diff changeset
1 """A multi-producer, multi-consumer queue."""
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
2
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
3 from time import time as _time
31436
63fa60f2d61c * Move collections.deque() in from the sandbox
Raymond Hettinger <python@rcn.com>
parents: 29711
diff changeset
4 from collections import deque
44716
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
5 import heapq
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
6
44716
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
7 __all__ = ['Empty', 'Full', 'Queue', 'PriorityQueue', 'LifoQueue']
29711
58132c813d7b Add __all__ .
Brett Cannon <bcannon@gmail.com>
parents: 26892
diff changeset
8
15902
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
9 class Empty(Exception):
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
10 "Exception raised by Queue.get(block=0)/get_nowait()."
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
11 pass
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
12
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
13 class Full(Exception):
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
14 "Exception raised by Queue.put(block=0)/put_nowait()."
eef321b6e41c Variant of Skip's patch 103246 (Remove unneeded string exception compat from Queue).
Tim Peters <tim.peters@gmail.com>
parents: 13050
diff changeset
15 pass
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
16
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
17 class Queue:
39442
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
18 """Create a queue object with a given maximum size.
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
19
39442
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
20 If maxsize is <= 0, the queue size is infinite.
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
21 """
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
22 def __init__(self, maxsize=0):
26892
95510f0a0624 Use the dummy_thread module in Queue.py and tempfile.py.
Guido van Rossum <guido@python.org>
parents: 25796
diff changeset
23 try:
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
24 import threading
26892
95510f0a0624 Use the dummy_thread module in Queue.py and tempfile.py.
Guido van Rossum <guido@python.org>
parents: 25796
diff changeset
25 except ImportError:
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
26 import dummy_threading as threading
44675
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
27 self.maxsize = maxsize
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
28 self._init(maxsize)
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
29 # mutex must be held whenever the queue is mutating. All methods
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
30 # that acquire mutex must release it before returning. mutex
40450
cc992d75d5b3 Four months of trunk changes (including a few releases...)
Thomas Wouters <thomas@python.org>
parents: 39442
diff changeset
31 # is shared between the three conditions, so acquiring and
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
32 # releasing the conditions also acquires and releases mutex.
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
33 self.mutex = threading.Lock()
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
34 # Notify not_empty whenever an item is added to the queue; a
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
35 # thread waiting to get is notified then.
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
36 self.not_empty = threading.Condition(self.mutex)
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
37 # Notify not_full whenever an item is removed from the queue;
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
38 # a thread waiting to put is notified then.
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
39 self.not_full = threading.Condition(self.mutex)
37879
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
40 # Notify all_tasks_done whenever the number of unfinished tasks
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
41 # drops to zero; thread waiting to join() is notified to resume
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
42 self.all_tasks_done = threading.Condition(self.mutex)
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
43 self.unfinished_tasks = 0
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
44
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
45 def task_done(self):
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
46 """Indicate that a formerly enqueued task is complete.
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
47
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
48 Used by Queue consumer threads. For each get() used to fetch a task,
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
49 a subsequent call to task_done() tells the queue that the processing
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
50 on the task is complete.
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
51
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
52 If a join() is currently blocking, it will resume when all items
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
53 have been processed (meaning that a task_done() call was received
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
54 for every item that had been put() into the queue).
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
55
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
56 Raises a ValueError if called more times than there were items
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
57 placed in the queue.
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
58 """
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
59 self.all_tasks_done.acquire()
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
60 try:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
61 unfinished = self.unfinished_tasks - 1
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
62 if unfinished <= 0:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
63 if unfinished < 0:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
64 raise ValueError('task_done() called too many times')
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
65 self.all_tasks_done.notifyAll()
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
66 self.unfinished_tasks = unfinished
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
67 finally:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
68 self.all_tasks_done.release()
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
69
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
70 def join(self):
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
71 """Blocks until all items in the Queue have been gotten and processed.
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
72
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
73 The count of unfinished tasks goes up whenever an item is added to the
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
74 queue. The count goes down whenever a consumer thread calls task_done()
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
75 to indicate the item was retrieved and all work on it is complete.
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
76
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
77 When the count of unfinished tasks drops to zero, join() unblocks.
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
78 """
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
79 self.all_tasks_done.acquire()
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
80 try:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
81 while self.unfinished_tasks:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
82 self.all_tasks_done.wait()
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
83 finally:
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
84 self.all_tasks_done.release()
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
85
6612
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
86 def qsize(self):
10120
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
87 """Return the approximate size of the queue (not reliable!)."""
8197
3a55b4c5e3c7 Replace all calls to acquire_lock() and release_lock() with acquire()
Guido van Rossum <guido@python.org>
parents: 7926
diff changeset
88 self.mutex.acquire()
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
89 n = self._qsize()
8197
3a55b4c5e3c7 Replace all calls to acquire_lock() and release_lock() with acquire()
Guido van Rossum <guido@python.org>
parents: 7926
diff changeset
90 self.mutex.release()
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
91 return n
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
92
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
93 def put(self, item, block=True, timeout=None):
7926
e29d435ab142 Clarify that put *blocks* when the queue is full. Add some blank
Guido van Rossum <guido@python.org>
parents: 7755
diff changeset
94 """Put an item into the queue.
e29d435ab142 Clarify that put *blocks* when the queue is full. Add some blank
Guido van Rossum <guido@python.org>
parents: 7755
diff changeset
95
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
96 If optional args 'block' is true and 'timeout' is None (the default),
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
97 block if necessary until a free slot is available. If 'timeout' is
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
98 a positive number, it blocks at most 'timeout' seconds and raises
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
99 the Full exception if no free slot was available within that time.
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
100 Otherwise ('block' is false), put an item on the queue if a free slot
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
101 is immediately available, else raise the Full exception ('timeout'
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
102 is ignored in that case).
10120
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
103 """
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
104 self.not_full.acquire()
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
105 try:
44695
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
106 if self.maxsize > 0:
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
107 if not block:
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
108 if self._qsize() == self.maxsize:
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
109 raise Full
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
110 elif timeout is None:
44675
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
111 while self._qsize() == self.maxsize:
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
112 self.not_full.wait()
44695
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
113 elif timeout < 0:
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
114 raise ValueError("'timeout' must be a positive number")
44695
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
115 else:
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
116 endtime = _time() + timeout
44675
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
117 while self._qsize() == self.maxsize:
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
118 remaining = endtime - _time()
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
119 if remaining <= 0.0:
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
120 raise Full
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
121 self.not_full.wait(remaining)
23160
c548e726b3bc Fix bug 544473 - "Queue module can deadlock".
Mark Hammond <mhammond@skippinet.com.au>
parents: 16657
diff changeset
122 self._put(item)
37879
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 32625
diff changeset
123 self.unfinished_tasks += 1
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
124 self.not_empty.notify()
23160
c548e726b3bc Fix bug 544473 - "Queue module can deadlock".
Mark Hammond <mhammond@skippinet.com.au>
parents: 16657
diff changeset
125 finally:
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
126 self.not_full.release()
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
127
10120
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
128 def put_nowait(self, item):
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
129 """Put an item into the queue without blocking.
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
130
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
131 Only enqueue the item if a free slot is immediately available.
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
132 Otherwise raise the Full exception.
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
133 """
32625
d42efc2b45e9 Simplified the new get/get_nowait/put/put_nowait implementations a bit.
Tim Peters <tim.peters@gmail.com>
parents: 32624
diff changeset
134 return self.put(item, False)
7926
e29d435ab142 Clarify that put *blocks* when the queue is full. Add some blank
Guido van Rossum <guido@python.org>
parents: 7755
diff changeset
135
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
136 def get(self, block=True, timeout=None):
10120
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
137 """Remove and return an item from the queue.
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
138
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
139 If optional args 'block' is true and 'timeout' is None (the default),
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
140 block if necessary until an item is available. If 'timeout' is
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
141 a positive number, it blocks at most 'timeout' seconds and raises
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
142 the Empty exception if no item was available within that time.
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
143 Otherwise ('block' is false), return an item if one is immediately
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
144 available, else raise the Empty exception ('timeout' is ignored
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
145 in that case).
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
146 """
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
147 self.not_empty.acquire()
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
148 try:
32625
d42efc2b45e9 Simplified the new get/get_nowait/put/put_nowait implementations a bit.
Tim Peters <tim.peters@gmail.com>
parents: 32624
diff changeset
149 if not block:
44675
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
150 if not self._qsize():
32625
d42efc2b45e9 Simplified the new get/get_nowait/put/put_nowait implementations a bit.
Tim Peters <tim.peters@gmail.com>
parents: 32624
diff changeset
151 raise Empty
d42efc2b45e9 Simplified the new get/get_nowait/put/put_nowait implementations a bit.
Tim Peters <tim.peters@gmail.com>
parents: 32624
diff changeset
152 elif timeout is None:
44675
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
153 while not self._qsize():
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
154 self.not_empty.wait()
44695
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
155 elif timeout < 0:
6e5675ca2559 Refactor if/elif chain for clarity and speed
Raymond Hettinger <python@rcn.com>
parents: 44675
diff changeset
156 raise ValueError("'timeout' must be a positive number")
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
157 else:
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
158 endtime = _time() + timeout
44675
627f2e2273b9 Remove Queue.empty() and Queue.full() in favor of using qsize() or trapping the Empty and Full exceptions.
Raymond Hettinger <python@rcn.com>
parents: 40450
diff changeset
159 while not self._qsize():
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
160 remaining = endtime - _time()
32625
d42efc2b45e9 Simplified the new get/get_nowait/put/put_nowait implementations a bit.
Tim Peters <tim.peters@gmail.com>
parents: 32624
diff changeset
161 if remaining <= 0.0:
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
162 raise Empty
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
163 self.not_empty.wait(remaining)
23160
c548e726b3bc Fix bug 544473 - "Queue module can deadlock".
Mark Hammond <mhammond@skippinet.com.au>
parents: 16657
diff changeset
164 item = self._get()
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
165 self.not_full.notify()
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
166 return item
23160
c548e726b3bc Fix bug 544473 - "Queue module can deadlock".
Mark Hammond <mhammond@skippinet.com.au>
parents: 16657
diff changeset
167 finally:
32624
73016bd01a71 Bug #788520: Queue class has logic error when non-blocking
Tim Peters <tim.peters@gmail.com>
parents: 31436
diff changeset
168 self.not_empty.release()
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
169
6612
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
170 def get_nowait(self):
10120
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
171 """Remove and return an item from the queue without blocking.
7926
e29d435ab142 Clarify that put *blocks* when the queue is full. Add some blank
Guido van Rossum <guido@python.org>
parents: 7755
diff changeset
172
25796
3eafbde56b21 Patch #572628: Optional timeouts for put and get.
Martin v. Löwis <martin@v.loewis.de>
parents: 24058
diff changeset
173 Only get an item if one is immediately available. Otherwise
10120
5b15642e7bdf Tim Peters:
Guido van Rossum <guido@python.org>
parents: 8197
diff changeset
174 raise the Empty exception.
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
175 """
32625
d42efc2b45e9 Simplified the new get/get_nowait/put/put_nowait implementations a bit.
Tim Peters <tim.peters@gmail.com>
parents: 32624
diff changeset
176 return self.get(False)
6612
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
177
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
178 # Override these methods to implement other queue organizations
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
179 # (e.g. stack or priority queue).
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
180 # These will only be called with appropriate locks held
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
181
6612
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
182 # Initialize the queue representation
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
183 def _init(self, maxsize):
31436
63fa60f2d61c * Move collections.deque() in from the sandbox
Raymond Hettinger <python@rcn.com>
parents: 29711
diff changeset
184 self.queue = deque()
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
185
44716
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
186 def _qsize(self, len=len):
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
187 return len(self.queue)
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
188
6612
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
189 # Put a new item in the queue
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
190 def _put(self, item):
7755
fb4b4d069cc7 Mass check-in after untabifying all files that need it.
Guido van Rossum <guido@python.org>
parents: 6612
diff changeset
191 self.queue.append(item)
995
f025eef93130 New module implementing a multi-everything queue.
Guido van Rossum <guido@python.org>
parents:
diff changeset
192
6612
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
193 # Get an item from the queue
4b2d8dc92db4 (Queue.Empty): When class based exceptions are in force, derive this
Barry Warsaw <barry@python.org>
parents: 1463
diff changeset
194 def _get(self):
31436
63fa60f2d61c * Move collections.deque() in from the sandbox
Raymond Hettinger <python@rcn.com>
parents: 29711
diff changeset
195 return self.queue.popleft()
44716
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
196
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
197
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
198 class PriorityQueue(Queue):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
199 '''Variant of Queue that retrieves open entries in priority order (lowest first).
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
200
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
201 Entries are typically tuples of the form: (priority number, data).
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
202 '''
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
203
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
204 def _init(self, maxsize):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
205 self.queue = []
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
206
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
207 def _qsize(self, len=len):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
208 return len(self.queue)
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
209
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
210 def _put(self, item, heappush=heapq.heappush):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
211 heappush(self.queue, item)
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
212
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
213 def _get(self, heappop=heapq.heappop):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
214 return heappop(self.queue)
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
215
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
216
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
217 class LifoQueue(Queue):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
218 '''Variant of Queue that retrieves most recently added entries first.'''
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
219
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
220 def _init(self, maxsize):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
221 self.queue = []
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
222
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
223 def _qsize(self, len=len):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
224 return len(self.queue)
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
225
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
226 def _put(self, item):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
227 self.queue.append(item)
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
228
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
229 def _get(self):
b469e90273eb Sync-up Queue.py with Py2.6
Raymond Hettinger <python@rcn.com>
parents: 44695
diff changeset
230 return self.queue.pop()