Mercurial > cpython-lru_cache-weakref

annotate Lib/queue.py @ 74006:88198b93ff2f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Issue #13560: Add PyUnicode_EncodeLocale() * Use PyUnicode_EncodeLocale() in time.strftime() if wcsftime() is not available * Document my last changes in Misc/NEWS
author Victor Stinner <victor.stinner@haypocalc.com>
date Sat, 17 Dec 2011 04:13:41 +0100
parents bc6cce4ab3c6
children c68426b241ca
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
1 """A multi-producer, multi-consumer queue."""
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
2
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
3 from time import time as _time
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
4 try:
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
5 import threading as _threading
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
6 except ImportError:
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
7 import dummy_threading as _threading
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
8 from collections import deque
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
9 import heapq
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):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
14 "Exception raised by Queue.get(block=0)/get_nowait()."
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):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
18 "Exception raised by Queue.put(block=0)/put_nowait()."
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:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
22 """Create a queue object with a given maximum size.
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.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
25 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
26 def __init__(self, maxsize=0):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
27 self.maxsize = maxsize
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
28 self._init(maxsize)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
29 # 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
30 # that acquire mutex must release it before returning. mutex
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
31 # is shared between the three conditions, so acquiring and
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
32 # releasing the conditions also acquires and releases mutex.
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
33 self.mutex = _threading.Lock()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
34 # 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
35 # thread waiting to get is notified then.
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
36 self.not_empty = _threading.Condition(self.mutex)
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
37 # 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
38 # a thread waiting to put is notified then.
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
39 self.not_full = _threading.Condition(self.mutex)
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
40 # Notify all_tasks_done whenever the number of unfinished tasks
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
41 # drops to zero; thread waiting to join() is notified to resume
52259
e41f5a89f5c0 port the queue change r70405
Benjamin Peterson <benjamin@python.org>
parents: 52045
diff changeset
42 self.all_tasks_done = _threading.Condition(self.mutex)
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
43 self.unfinished_tasks = 0
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
44
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
45 def task_done(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
46 """Indicate that a formerly enqueued task is complete.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
47
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
48 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
49 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
50 on the task is complete.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
51
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
52 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
53 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
54 for every item that had been put() into the queue).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
55
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
56 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
57 placed in the queue.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
58 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
59 self.all_tasks_done.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
60 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
61 unfinished = self.unfinished_tasks - 1
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
62 if unfinished <= 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
63 if unfinished < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
64 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
65 self.all_tasks_done.notify_all()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
66 self.unfinished_tasks = unfinished
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
67 finally:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
68 self.all_tasks_done.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
69
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
70 def join(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
71 """Blocks until all items in the Queue have been gotten and processed.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
72
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
73 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
74 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
75 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
76
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
77 When the count of unfinished tasks drops to zero, join() unblocks.
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 self.all_tasks_done.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
80 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
81 while self.unfinished_tasks:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
82 self.all_tasks_done.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
83 finally:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
84 self.all_tasks_done.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
85
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
86 def qsize(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
87 """Return the approximate size of the queue (not reliable!)."""
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
88 self.mutex.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
89 n = self._qsize()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
90 self.mutex.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
91 return n
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
92
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
93 def empty(self):
52045
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
94 """Return True if the queue is empty, False otherwise (not reliable!).
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
95
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
96 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
97 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
98 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
99 qsize() can be used.
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
100
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
101 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
102 completed, the preferred technique is to use the join() method.
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
103
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
104 """
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
105 self.mutex.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
106 n = not self._qsize()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
107 self.mutex.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
108 return n
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
109
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
110 def full(self):
52045
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
111 """Return True if the queue is full, False otherwise (not reliable!).
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
112
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
113 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
114 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
115 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
116 qsize() can be used.
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
117
aef5cfe73358 Document the suggested alternative to emtpy() and full().
Raymond Hettinger <python@rcn.com>
parents: 47615
diff changeset
118 """
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
119 self.mutex.acquire()
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
120 n = 0 < self.maxsize <= self._qsize()
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
121 self.mutex.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
122 return n
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
123
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
124 def put(self, item, block=True, timeout=None):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
125 """Put an item into the queue.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
126
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
127 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
128 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
129 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
130 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
131 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
132 is immediately available, else raise the Full exception ('timeout'
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
133 is ignored in that case).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
134 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
135 self.not_full.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
136 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
137 if self.maxsize > 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
138 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
139 if self._qsize() >= self.maxsize:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
140 raise Full
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
141 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
142 while self._qsize() >= self.maxsize:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
143 self.not_full.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
144 elif timeout < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
145 raise ValueError("'timeout' must be a positive number")
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
146 else:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
147 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
148 while self._qsize() >= self.maxsize:
46899
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
149 remaining = endtime - _time()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
150 if remaining <= 0.0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
151 raise Full
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
152 self.not_full.wait(remaining)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
153 self._put(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
154 self.unfinished_tasks += 1
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
155 self.not_empty.notify()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
156 finally:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
157 self.not_full.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
158
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
159 def put_nowait(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
160 """Put an item into the queue without blocking.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
161
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
162 Only enqueue the item if a free slot is immediately available.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
163 Otherwise raise the Full exception.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
164 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
165 return self.put(item, False)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
166
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
167 def get(self, block=True, timeout=None):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
168 """Remove and return an item from the queue.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
169
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
170 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
171 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
172 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
173 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
174 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
175 available, else raise the Empty exception ('timeout' is ignored
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
176 in that case).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
177 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
178 self.not_empty.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
179 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
180 if not block:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
181 if not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
182 raise Empty
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
183 elif timeout is None:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
184 while not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
185 self.not_empty.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
186 elif timeout < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
187 raise ValueError("'timeout' must be a positive number")
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
188 else:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
189 endtime = _time() + timeout
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
190 while not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
191 remaining = endtime - _time()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
192 if remaining <= 0.0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
193 raise Empty
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
194 self.not_empty.wait(remaining)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
195 item = self._get()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
196 self.not_full.notify()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
197 return item
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
198 finally:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
199 self.not_empty.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
200
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
201 def get_nowait(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
202 """Remove and return an item from the queue without blocking.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
203
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
204 Only get an item if one is immediately available. Otherwise
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
205 raise the Empty exception.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
206 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
207 return self.get(False)
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 # Override these methods to implement other queue organizations
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
210 # (e.g. stack or priority queue).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
211 # These will only be called with appropriate locks held
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 # Initialize the queue representation
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
214 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
215 self.queue = deque()
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 def _qsize(self, len=len):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
218 return len(self.queue)
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 # Put a new item in the queue
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
221 def _put(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
222 self.queue.append(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
223
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
224 # Get an item from the queue
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
225 def _get(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
226 return self.queue.popleft()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
227
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
228
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
229 class PriorityQueue(Queue):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
230 '''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
231
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
232 Entries are typically tuples of the form: (priority number, data).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
233 '''
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
234
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
235 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
236 self.queue = []
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
237
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
238 def _qsize(self, len=len):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
239 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
240
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
241 def _put(self, item, heappush=heapq.heappush):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
242 heappush(self.queue, item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
243
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
244 def _get(self, heappop=heapq.heappop):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
245 return heappop(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
246
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
247
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
248 class LifoQueue(Queue):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
249 '''Variant of Queue that retrieves most recently added entries first.'''
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
250
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
251 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
252 self.queue = []
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
253
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
254 def _qsize(self, len=len):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
255 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
256
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
257 def _put(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
258 self.queue.append(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
259
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
260 def _get(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
261 return self.queue.pop()