Mercurial > cpython-lru_cache-weakref

annotate Lib/queue.py @ 74917:76dfd1f08025

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
lib2to3 tests: Don't use deprecated API, switch to assertRegex()
author Victor Stinner <victor.stinner@haypocalc.com>
date Mon, 13 Feb 2012 23:31:26 +0100
parents 32eae3c48631
children d97ae725814c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
1 '''A multi-producer, multi-consumer queue.'''
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
2
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
3 try:
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
4 import threading
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
5 except ImportError:
74309
32eae3c48631 Fix nasty typo
Raymond Hettinger <python@rcn.com>
parents: 74307
diff changeset
6 import dummy_threading as threading
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
7 from collections import deque
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
8 from heapq import heappush, heappop
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
9 from time import time
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
10
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
11 __all__ = ['Empty', 'Full', 'Queue', 'PriorityQueue', 'LifoQueue']
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
12
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
13 class Empty(Exception):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
14 'Exception raised by Queue.get(block=0)/get_nowait().'
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
15 pass
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
16
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
17 class Full(Exception):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
18 'Exception raised by Queue.put(block=0)/put_nowait().'
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
19 pass
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
20
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
21 class Queue:
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
22 '''Create a queue object with a given maximum size.
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
23
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
24 If maxsize is <= 0, the queue size is infinite.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
25 '''
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
26
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
27 def __init__(self, maxsize=0):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
28 self.maxsize = maxsize
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
29 self._init(maxsize)
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
30
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
31 # mutex must be held whenever the queue is mutating. All methods
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
32 # that acquire mutex must release it before returning. mutex
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
33 # is shared between the three conditions, so acquiring and
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
34 # releasing the conditions also acquires and releases mutex.
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
35 self.mutex = threading.Lock()
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
36
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
37 # Notify not_empty whenever an item is added to the queue; a
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
38 # thread waiting to get is notified then.
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
39 self.not_empty = threading.Condition(self.mutex)
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
40
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
41 # Notify not_full whenever an item is removed from the queue;
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
42 # a thread waiting to put is notified then.
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
43 self.not_full = threading.Condition(self.mutex)
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
44
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
45 # Notify all_tasks_done whenever the number of unfinished tasks
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
46 # drops to zero; thread waiting to join() is notified to resume
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
47 self.all_tasks_done = threading.Condition(self.mutex)
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
48 self.unfinished_tasks = 0
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
49
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
50 def task_done(self):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
51 '''Indicate that a formerly enqueued task is complete.
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
52
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
53 Used by Queue consumer threads. For each get() used to fetch a task,
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
54 a subsequent call to task_done() tells the queue that the processing
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
55 on the task is complete.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
56
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
57 If a join() is currently blocking, it will resume when all items
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
58 have been processed (meaning that a task_done() call was received
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
59 for every item that had been put() into the queue).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
60
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
61 Raises a ValueError if called more times than there were items
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
62 placed in the queue.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
63 '''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
64 with self.all_tasks_done:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
65 unfinished = self.unfinished_tasks - 1
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
66 if unfinished <= 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
67 if unfinished < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
68 raise ValueError('task_done() called too many times')
47615
045f83a1b864 Merged revisions 64125 via svnmerge from
Benjamin Peterson <benjamin@python.org>
parents: 46899
diff changeset
69 self.all_tasks_done.notify_all()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
70 self.unfinished_tasks = unfinished
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
71
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
72 def join(self):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
73 '''Blocks until all items in the Queue have been gotten and processed.
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
74
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
75 The count of unfinished tasks goes up whenever an item is added to the
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
76 queue. The count goes down whenever a consumer thread calls task_done()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
77 to indicate the item was retrieved and all work on it is complete.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
78
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
79 When the count of unfinished tasks drops to zero, join() unblocks.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
80 '''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
81 with self.all_tasks_done:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
82 while self.unfinished_tasks:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
83 self.all_tasks_done.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
84
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
85 def qsize(self):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
86 '''Return the approximate size of the queue (not reliable!).'''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
87 with self.mutex:
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
88 return self._qsize()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
89
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
90 def empty(self):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
91 '''Return True if the queue is empty, False otherwise (not reliable!).
52045
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
92
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
93 This method is likely to be removed at some point. Use qsize() == 0
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
94 as a direct substitute, but be aware that either approach risks a race
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
95 condition where a queue can grow before the result of empty() or
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
96 qsize() can be used.
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
97
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
98 To create code that needs to wait for all queued tasks to be
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
99 completed, the preferred technique is to use the join() method.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
100 '''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
101 with self.mutex:
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
102 return not self._qsize()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
103
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
104 def full(self):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
105 '''Return True if the queue is full, False otherwise (not reliable!).
52045
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
106
65831
bc6cce4ab3c6 Issue 10110: Let Queue.put recognize a full queue when the maxsize parameter has been reduced.
Raymond Hettinger <python@rcn.com>
parents: 52259
diff changeset
107 This method is likely to be removed at some point. Use qsize() >= n
52045
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
108 as a direct substitute, but be aware that either approach risks a race
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
109 condition where a queue can shrink before the result of full() or
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
110 qsize() can be used.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
111 '''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
112 with self.mutex:
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
113 return 0 < self.maxsize <= self._qsize()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
114
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
115 def put(self, item, block=True, timeout=None):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
116 '''Put an item into the queue.
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
117
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
118 If optional args 'block' is true and 'timeout' is None (the default),
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
119 block if necessary until a free slot is available. If 'timeout' is
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
120 a positive number, it blocks at most 'timeout' seconds and raises
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
121 the Full exception if no free slot was available within that time.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
122 Otherwise ('block' is false), put an item on the queue if a free slot
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
123 is immediately available, else raise the Full exception ('timeout'
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
124 is ignored in that case).
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
125 '''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
126 with self.not_full:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
127 if self.maxsize > 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
128 if not block:
65831
bc6cce4ab3c6 Issue 10110: Let Queue.put recognize a full queue when the maxsize parameter has been reduced.
Raymond Hettinger <python@rcn.com>
parents: 52259
diff changeset
129 if self._qsize() >= self.maxsize:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
130 raise Full
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
131 elif timeout is None:
65831
bc6cce4ab3c6 Issue 10110: Let Queue.put recognize a full queue when the maxsize parameter has been reduced.
Raymond Hettinger <python@rcn.com>
parents: 52259
diff changeset
132 while self._qsize() >= self.maxsize:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
133 self.not_full.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
134 elif timeout < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
135 raise ValueError("'timeout' must be a positive number")
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
136 else:
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
137 endtime = time() + timeout
65831
bc6cce4ab3c6 Issue 10110: Let Queue.put recognize a full queue when the maxsize parameter has been reduced.
Raymond Hettinger <python@rcn.com>
parents: 52259
diff changeset
138 while self._qsize() >= self.maxsize:
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
139 remaining = endtime - time()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
140 if remaining <= 0.0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
141 raise Full
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
142 self.not_full.wait(remaining)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
143 self._put(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
144 self.unfinished_tasks += 1
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
145 self.not_empty.notify()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
146
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
147 def get(self, block=True, timeout=None):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
148 '''Remove and return an item from the queue.
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
149
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
150 If optional args 'block' is true and 'timeout' is None (the default),
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
151 block if necessary until an item is available. If 'timeout' is
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
152 a positive number, it blocks at most 'timeout' seconds and raises
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
153 the Empty exception if no item was available within that time.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
154 Otherwise ('block' is false), return an item if one is immediately
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
155 available, else raise the Empty exception ('timeout' is ignored
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
156 in that case).
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
157 '''
74298
c68426b241ca Simplify the code using with-statements.
Raymond Hettinger <python@rcn.com>
parents: 65831
diff changeset
158 with self.not_empty:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
159 if not block:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
160 if not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
161 raise Empty
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
162 elif timeout is None:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
163 while not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
164 self.not_empty.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
165 elif timeout < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
166 raise ValueError("'timeout' must be a positive number")
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
167 else:
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
168 endtime = time() + timeout
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
169 while not self._qsize():
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
170 remaining = endtime - time()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
171 if remaining <= 0.0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
172 raise Empty
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
173 self.not_empty.wait(remaining)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
174 item = self._get()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
175 self.not_full.notify()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
176 return item
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
177
74306
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
178 def put_nowait(self, item):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
179 '''Put an item into the queue without blocking.
74306
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
180
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
181 Only enqueue the item if a free slot is immediately available.
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
182 Otherwise raise the Full exception.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
183 '''
74306
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
184 return self.put(item, block=False)
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
185
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
186 def get_nowait(self):
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
187 '''Remove and return an item from the queue without blocking.
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
188
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
189 Only get an item if one is immediately available. Otherwise
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
190 raise the Empty exception.
74307
ca2a35140e6a Make the docstring style consistent.
Raymond Hettinger <python@rcn.com>
parents: 74306
diff changeset
191 '''
74306
07608e67bc01 Improve clarity with keyword argument for block. Move nowait methods together.
Raymond Hettinger <python@rcn.com>
parents: 74305
diff changeset
192 return self.get(block=False)
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
193
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
194 # Override these methods to implement other queue organizations
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
195 # (e.g. stack or priority queue).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
196 # These will only be called with appropriate locks held
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
197
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
198 # Initialize the queue representation
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
199 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
200 self.queue = deque()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
201
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
202 def _qsize(self):
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
203 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
204
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
205 # Put a new item in the queue
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
206 def _put(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
207 self.queue.append(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
208
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
209 # Get an item from the queue
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
210 def _get(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
211 return self.queue.popleft()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
212
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
213
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
214 class PriorityQueue(Queue):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
215 '''Variant of Queue that retrieves open entries in priority order (lowest first).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
216
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
217 Entries are typically tuples of the form: (priority number, data).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
218 '''
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
219
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
220 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
221 self.queue = []
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
222
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
223 def _qsize(self):
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
224 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
225
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
226 def _put(self, item):
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
227 heappush(self.queue, item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
228
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
229 def _get(self):
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
230 return heappop(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
231
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
232
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
233 class LifoQueue(Queue):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
234 '''Variant of Queue that retrieves most recently added entries first.'''
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
235
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
236 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
237 self.queue = []
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
238
74305
190ad17f5a87 Minor code clean-ups and beautifications.
Raymond Hettinger <python@rcn.com>
parents: 74298
diff changeset
239 def _qsize(self):
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
240 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
241
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
242 def _put(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
243 self.queue.append(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
244
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
245 def _get(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
246 return self.queue.pop()