| 1 |
"""A multi-producer, multi-consumer queue.""" |
| 2 |
|
| 3 |
from time import time as _time |
| 4 |
|
| 5 |
from collections import deque |
| 6 |
|
| 7 |
__all__ = ['Empty', 'Full', 'Queue'] |
| 8 |
|
| 9 |
class Empty(Exception): |
| 10 |
"Exception raised by Queue.get(block=0)/get_nowait()." |
| 11 |
pass |
| 12 |
|
| 13 |
class Full(Exception): |
| 14 |
"Exception raised by Queue.put(block=0)/put_nowait()." |
| 15 |
pass |
| 16 |
|
| 17 |
class Queue: |
| 18 |
"""Create a queue object with a given maximum size. |
| 19 |
|
| 20 |
If maxsize is <= 0, the queue size is infinite. |
| 21 |
""" |
| 22 |
def __init__(self, maxsize=0): |
| 23 |
try: |
| 24 |
import threading |
| 25 |
except ImportError: |
| 26 |
import dummy_threading as threading |
| 27 |
self._init(maxsize) |
| 28 |
# mutex must be held whenever the queue is mutating. All methods |
| 29 |
# that acquire mutex must release it before returning. mutex |
| 30 |
# is shared between the three conditions, so acquiring and |
| 31 |
# releasing the conditions also acquires and releases mutex. |
| 32 |
self.mutex = threading.Lock() |
| 33 |
# Notify not_empty whenever an item is added to the queue; a |
| 34 |
# thread waiting to get is notified then. |
| 35 |
self.not_empty = threading.Condition(self.mutex) |
| 36 |
# Notify not_full whenever an item is removed from the queue; |
| 37 |
# a thread waiting to put is notified then. |
| 38 |
self.not_full = threading.Condition(self.mutex) |
| 39 |
# Notify all_tasks_done whenever the number of unfinished tasks |
| 40 |
# drops to zero; thread waiting to join() is notified to resume |
| 41 |
self.all_tasks_done = threading.Condition(self.mutex) |
| 42 |
self.unfinished_tasks = 0 |
| 43 |
|
| 44 |
def task_done(self): |
| 45 |
"""Indicate that a formerly enqueued task is complete. |
| 46 |
|
| 47 |
Used by Queue consumer threads. For each get() used to fetch a task, |
| 48 |
a subsequent call to task_done() tells the queue that the processing |
| 49 |
on the task is complete. |
| 50 |
|
| 51 |
If a join() is currently blocking, it will resume when all items |
| 52 |
have been processed (meaning that a task_done() call was received |
| 53 |
for every item that had been put() into the queue). |
| 54 |
|
| 55 |
Raises a ValueError if called more times than there were items |
| 56 |
placed in the queue. |
| 57 |
""" |
| 58 |
self.all_tasks_done.acquire() |
| 59 |
try: |
| 60 |
unfinished = self.unfinished_tasks - 1 |
| 61 |
if unfinished <= 0: |
| 62 |
if unfinished < 0: |
| 63 |
raise ValueError('task_done() called too many times') |
| 64 |
self.all_tasks_done.notifyAll() |
| 65 |
self.unfinished_tasks = unfinished |
| 66 |
finally: |
| 67 |
self.all_tasks_done.release() |
| 68 |
|
| 69 |
def join(self): |
| 70 |
"""Blocks until all items in the Queue have been gotten and processed. |
| 71 |
|
| 72 |
The count of unfinished tasks goes up whenever an item is added to the |
| 73 |
queue. The count goes down whenever a consumer thread calls task_done() |
| 74 |
to indicate the item was retrieved and all work on it is complete. |
| 75 |
|
| 76 |
When the count of unfinished tasks drops to zero, join() unblocks. |
| 77 |
""" |
| 78 |
self.all_tasks_done.acquire() |
| 79 |
try: |
| 80 |
while self.unfinished_tasks: |
| 81 |
self.all_tasks_done.wait() |
| 82 |
finally: |
| 83 |
self.all_tasks_done.release() |
| 84 |
|
| 85 |
def qsize(self): |
| 86 |
"""Return the approximate size of the queue (not reliable!).""" |
| 87 |
self.mutex.acquire() |
| 88 |
n = self._qsize() |
| 89 |
self.mutex.release() |
| 90 |
return n |
| 91 |
|
| 92 |
def empty(self): |
| 93 |
"""Return True if the queue is empty, False otherwise (not reliable!).""" |
| 94 |
self.mutex.acquire() |
| 95 |
n = self._empty() |
| 96 |
self.mutex.release() |
| 97 |
return n |
| 98 |
|
| 99 |
def full(self): |
| 100 |
"""Return True if the queue is full, False otherwise (not reliable!).""" |
| 101 |
self.mutex.acquire() |
| 102 |
n = self._full() |
| 103 |
self.mutex.release() |
| 104 |
return n |
| 105 |
|
| 106 |
def put(self, item, block=True, timeout=None): |
| 107 |
"""Put an item into the queue. |
| 108 |
|
| 109 |
If optional args 'block' is true and 'timeout' is None (the default), |
| 110 |
block if necessary until a free slot is available. If 'timeout' is |
| 111 |
a positive number, it blocks at most 'timeout' seconds and raises |
| 112 |
the Full exception if no free slot was available within that time. |
| 113 |
Otherwise ('block' is false), put an item on the queue if a free slot |
| 114 |
is immediately available, else raise the Full exception ('timeout' |
| 115 |
is ignored in that case). |
| 116 |
""" |
| 117 |
self.not_full.acquire() |
| 118 |
try: |
| 119 |
if not block: |
| 120 |
if self._full(): |
| 121 |
raise Full |
| 122 |
elif timeout is None: |
| 123 |
while self._full(): |
| 124 |
self.not_full.wait() |
| 125 |
else: |
| 126 |
if timeout < 0: |
| 127 |
raise ValueError("'timeout' must be a positive number") |
| 128 |
endtime = _time() + timeout |
| 129 |
while self._full(): |
| 130 |
remaining = endtime - _time() |
| 131 |
if remaining <= 0.0: |
| 132 |
raise Full |
| 133 |
self.not_full.wait(remaining) |
| 134 |
self._put(item) |
| 135 |
self.unfinished_tasks += 1 |
| 136 |
self.not_empty.notify() |
| 137 |
finally: |
| 138 |
self.not_full.release() |
| 139 |
|
| 140 |
def put_nowait(self, item): |
| 141 |
"""Put an item into the queue without blocking. |
| 142 |
|
| 143 |
Only enqueue the item if a free slot is immediately available. |
| 144 |
Otherwise raise the Full exception. |
| 145 |
""" |
| 146 |
return self.put(item, False) |
| 147 |
|
| 148 |
def get(self, block=True, timeout=None): |
| 149 |
"""Remove and return an item from the queue. |
| 150 |
|
| 151 |
If optional args 'block' is true and 'timeout' is None (the default), |
| 152 |
block if necessary until an item is available. If 'timeout' is |
| 153 |
a positive number, it blocks at most 'timeout' seconds and raises |
| 154 |
the Empty exception if no item was available within that time. |
| 155 |
Otherwise ('block' is false), return an item if one is immediately |
| 156 |
available, else raise the Empty exception ('timeout' is ignored |
| 157 |
in that case). |
| 158 |
""" |
| 159 |
self.not_empty.acquire() |
| 160 |
try: |
| 161 |
if not block: |
| 162 |
if self._empty(): |
| 163 |
raise Empty |
| 164 |
elif timeout is None: |
| 165 |
while self._empty(): |
| 166 |
self.not_empty.wait() |
| 167 |
else: |
| 168 |
if timeout < 0: |
| 169 |
raise ValueError("'timeout' must be a positive number") |
| 170 |
endtime = _time() + timeout |
| 171 |
while self._empty(): |
| 172 |
remaining = endtime - _time() |
| 173 |
if remaining <= 0.0: |
| 174 |
raise Empty |
| 175 |
self.not_empty.wait(remaining) |
| 176 |
item = self._get() |
| 177 |
self.not_full.notify() |
| 178 |
return item |
| 179 |
finally: |
| 180 |
self.not_empty.release() |
| 181 |
|
| 182 |
def get_nowait(self): |
| 183 |
"""Remove and return an item from the queue without blocking. |
| 184 |
|
| 185 |
Only get an item if one is immediately available. Otherwise |
| 186 |
raise the Empty exception. |
| 187 |
""" |
| 188 |
return self.get(False) |
| 189 |
|
| 190 |
# Override these methods to implement other queue organizations |
| 191 |
# (e.g. stack or priority queue). |
| 192 |
# These will only be called with appropriate locks held |
| 193 |
|
| 194 |
# Initialize the queue representation |
| 195 |
def _init(self, maxsize): |
| 196 |
self.maxsize = maxsize |
| 197 |
self.queue = deque() |
| 198 |
|
| 199 |
def _qsize(self): |
| 200 |
return len(self.queue) |
| 201 |
|
| 202 |
# Check whether the queue is empty |
| 203 |
def _empty(self): |
| 204 |
return not self.queue |
| 205 |
|
| 206 |
# Check whether the queue is full |
| 207 |
def _full(self): |
| 208 |
return self.maxsize > 0 and len(self.queue) == self.maxsize |
| 209 |
|
| 210 |
# Put a new item in the queue |
| 211 |
def _put(self, item): |
| 212 |
self.queue.append(item) |
| 213 |
|
| 214 |
# Get an item from the queue |
| 215 |
def _get(self): |
| 216 |
return self.queue.popleft() |