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