Mercurial > cpython-lru_cache-weakref

annotate Lib/queue.py @ 49961:e793fc3c8abe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
More 3.0 -> 3.1 transistion in the Windows and OS/2 build files
author Christian Heimes <christian@cheimes.de>
date Thu, 04 Dec 2008 14:27:25 +0000
parents 045f83a1b864
children cabb0ddcb88e aef5cfe73358
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
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
4 from collections import deque
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
5 import heapq
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
6
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
7 __all__ = ['Empty', 'Full', 'Queue', 'PriorityQueue', 'LifoQueue']
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
8
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
9 class Empty(Exception):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
10 "Exception raised by Queue.get(block=0)/get_nowait()."
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
11 pass
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 Full(Exception):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
14 "Exception raised by Queue.put(block=0)/put_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 Queue:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
18 """Create a queue object with a given maximum size.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
19
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
20 If maxsize is <= 0, the queue size is infinite.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
21 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
22 def __init__(self, maxsize=0):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
23 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
24 import threading
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
25 except ImportError:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
26 import dummy_threading as threading
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.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
33 self.mutex = threading.Lock()
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.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
36 self.not_empty = threading.Condition(self.mutex)
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.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
39 self.not_full = threading.Condition(self.mutex)
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
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
42 self.all_tasks_done = threading.Condition(self.mutex)
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):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
94 """Return True if the queue is empty, False otherwise (not reliable!)."""
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
95 self.mutex.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
96 n = not self._qsize()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
97 self.mutex.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
98 return n
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
99
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
100 def full(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
101 """Return True if the queue is full, False otherwise (not reliable!)."""
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
102 self.mutex.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
103 n = 0 < self.maxsize == self._qsize()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
104 self.mutex.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
105 return n
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
106
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
107 def put(self, item, block=True, timeout=None):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
108 """Put an item into the queue.
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 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
111 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
112 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
113 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
114 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
115 is immediately available, else raise the Full exception ('timeout'
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
116 is ignored in that case).
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 self.not_full.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
119 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
120 if self.maxsize > 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
121 if not block:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
122 if self._qsize() == self.maxsize:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
123 raise Full
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
124 elif timeout is None:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
125 while self._qsize() == self.maxsize:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
126 self.not_full.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
127 elif timeout < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
128 raise ValueError("'timeout' must be a positive number")
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
129 else:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
130 endtime = _time() + timeout
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
131 while self._qsize() == self.maxsize:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
132 remaining = endtime - _time()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
133 if remaining <= 0.0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
134 raise Full
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
135 self.not_full.wait(remaining)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
136 self._put(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
137 self.unfinished_tasks += 1
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
138 self.not_empty.notify()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
139 finally:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
140 self.not_full.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
141
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
142 def put_nowait(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
143 """Put an item into the queue without blocking.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
144
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
145 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
146 Otherwise raise the Full exception.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
147 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
148 return self.put(item, False)
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 def get(self, block=True, timeout=None):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
151 """Remove and return an item from the queue.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
152
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
153 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
154 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
155 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
156 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
157 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
158 available, else raise the Empty exception ('timeout' is ignored
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
159 in that case).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
160 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
161 self.not_empty.acquire()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
162 try:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
163 if not block:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
164 if not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
165 raise Empty
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
166 elif timeout is None:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
167 while not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
168 self.not_empty.wait()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
169 elif timeout < 0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
170 raise ValueError("'timeout' must be a positive number")
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
171 else:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
172 endtime = _time() + timeout
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
173 while not self._qsize():
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
174 remaining = endtime - _time()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
175 if remaining <= 0.0:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
176 raise Empty
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
177 self.not_empty.wait(remaining)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
178 item = self._get()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
179 self.not_full.notify()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
180 return item
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
181 finally:
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
182 self.not_empty.release()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
183
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
184 def get_nowait(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
185 """Remove and return an item from the queue without blocking.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
186
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
187 Only get an item if one is immediately available. Otherwise
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
188 raise the Empty exception.
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
189 """
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
190 return self.get(False)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
191
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
192 # Override these methods to implement other queue organizations
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
193 # (e.g. stack or priority queue).
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
194 # These will only be called with appropriate locks held
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
195
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
196 # Initialize the queue representation
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
197 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
198 self.queue = deque()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
199
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
200 def _qsize(self, len=len):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
201 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
202
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
203 # Put a new item in the queue
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
204 def _put(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
205 self.queue.append(item)
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 # Get an item from the queue
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
208 def _get(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
209 return self.queue.popleft()
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
210
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
211
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
212 class PriorityQueue(Queue):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
213 '''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
214
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
215 Entries are typically tuples of the form: (priority number, data).
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
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
218 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
219 self.queue = []
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
220
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
221 def _qsize(self, len=len):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
222 return len(self.queue)
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 def _put(self, item, heappush=heapq.heappush):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
225 heappush(self.queue, item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
226
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
227 def _get(self, heappop=heapq.heappop):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
228 return heappop(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
229
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
230
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
231 class LifoQueue(Queue):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
232 '''Variant of Queue that retrieves most recently added entries first.'''
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 def _init(self, maxsize):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
235 self.queue = []
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
236
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
237 def _qsize(self, len=len):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
238 return len(self.queue)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
239
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
240 def _put(self, item):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
241 self.queue.append(item)
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
242
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
243 def _get(self):
bd2c95c165ea Rename Queue module to queue.
Alexandre Vassalotti <alexandre@peadrop.com>
parents:
diff changeset
244 return self.queue.pop()