Guido van Rossum | 4acc25b | 2000-02-02 15:10:15 +0000 | [diff] [blame] | 1 | """A multi-producer, multi-consumer queue.""" |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 2 | |
Tim Peters | b8c9417 | 2001-01-15 22:53:46 +0000 | [diff] [blame] | 3 | class Empty(Exception): |
| 4 | "Exception raised by Queue.get(block=0)/get_nowait()." |
| 5 | pass |
| 6 | |
| 7 | class Full(Exception): |
| 8 | "Exception raised by Queue.put(block=0)/put_nowait()." |
| 9 | pass |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 10 | |
| 11 | class Queue: |
Guido van Rossum | a41c691 | 1999-09-09 14:54:28 +0000 | [diff] [blame] | 12 | def __init__(self, maxsize=0): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 13 | """Initialize a queue object with a given maximum size. |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 14 | |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 15 | If maxsize is <= 0, the queue size is infinite. |
| 16 | """ |
| 17 | import thread |
| 18 | self._init(maxsize) |
| 19 | self.mutex = thread.allocate_lock() |
| 20 | self.esema = thread.allocate_lock() |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 21 | self.esema.acquire() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 22 | self.fsema = thread.allocate_lock() |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 23 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 24 | def qsize(self): |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 25 | """Return the approximate size of the queue (not reliable!).""" |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 26 | self.mutex.acquire() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 27 | n = self._qsize() |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 28 | self.mutex.release() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 29 | return n |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 30 | |
| 31 | def empty(self): |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 32 | """Return 1 if the queue is empty, 0 otherwise (not reliable!).""" |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 33 | self.mutex.acquire() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 34 | n = self._empty() |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 35 | self.mutex.release() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 36 | return n |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 37 | |
| 38 | def full(self): |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 39 | """Return 1 if the queue is full, 0 otherwise (not reliable!).""" |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 40 | self.mutex.acquire() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 41 | n = self._full() |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 42 | self.mutex.release() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 43 | return n |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 44 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 45 | def put(self, item, block=1): |
Guido van Rossum | c09e6b1 | 1998-04-09 14:25:32 +0000 | [diff] [blame] | 46 | """Put an item into the queue. |
| 47 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 48 | If optional arg 'block' is 1 (the default), block if |
| 49 | necessary until a free slot is available. Otherwise (block |
| 50 | is 0), put an item on the queue if a free slot is immediately |
| 51 | available, else raise the Full exception. |
| 52 | """ |
| 53 | if block: |
| 54 | self.fsema.acquire() |
| 55 | elif not self.fsema.acquire(0): |
| 56 | raise Full |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 57 | self.mutex.acquire() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 58 | was_empty = self._empty() |
| 59 | self._put(item) |
| 60 | if was_empty: |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 61 | self.esema.release() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 62 | if not self._full(): |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 63 | self.fsema.release() |
| 64 | self.mutex.release() |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 65 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 66 | def put_nowait(self, item): |
| 67 | """Put an item into the queue without blocking. |
Guido van Rossum | c09e6b1 | 1998-04-09 14:25:32 +0000 | [diff] [blame] | 68 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 69 | Only enqueue the item if a free slot is immediately available. |
| 70 | Otherwise raise the Full exception. |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 71 | """ |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 72 | return self.put(item, 0) |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 73 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 74 | def get(self, block=1): |
| 75 | """Remove and return an item from the queue. |
Guido van Rossum | c09e6b1 | 1998-04-09 14:25:32 +0000 | [diff] [blame] | 76 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 77 | If optional arg 'block' is 1 (the default), block if |
| 78 | necessary until an item is available. Otherwise (block is 0), |
| 79 | return an item if one is immediately available, else raise the |
| 80 | Empty exception. |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 81 | """ |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 82 | if block: |
| 83 | self.esema.acquire() |
| 84 | elif not self.esema.acquire(0): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 85 | raise Empty |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 86 | self.mutex.acquire() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 87 | was_full = self._full() |
| 88 | item = self._get() |
| 89 | if was_full: |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 90 | self.fsema.release() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 91 | if not self._empty(): |
Guido van Rossum | 7e6d18c | 1998-04-29 14:29:32 +0000 | [diff] [blame] | 92 | self.esema.release() |
| 93 | self.mutex.release() |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 94 | return item |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 95 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 96 | def get_nowait(self): |
| 97 | """Remove and return an item from the queue without blocking. |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 98 | |
Guido van Rossum | 9e1721f | 1999-02-08 18:34:01 +0000 | [diff] [blame] | 99 | Only get an item if one is immediately available. Otherwise |
| 100 | raise the Empty exception. |
| 101 | """ |
| 102 | return self.get(0) |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 103 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 104 | # Override these methods to implement other queue organizations |
| 105 | # (e.g. stack or priority queue). |
| 106 | # These will only be called with appropriate locks held |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 107 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 108 | # Initialize the queue representation |
| 109 | def _init(self, maxsize): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 110 | self.maxsize = maxsize |
| 111 | self.queue = [] |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 112 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 113 | def _qsize(self): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 114 | return len(self.queue) |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 115 | |
Jeremy Hylton | a05e293 | 2000-06-28 14:48:01 +0000 | [diff] [blame] | 116 | # Check whether the queue is empty |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 117 | def _empty(self): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 118 | return not self.queue |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 119 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 120 | # Check whether the queue is full |
| 121 | def _full(self): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 122 | return self.maxsize > 0 and len(self.queue) == self.maxsize |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 123 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 124 | # Put a new item in the queue |
| 125 | def _put(self, item): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 126 | self.queue.append(item) |
Guido van Rossum | 9022fce | 1992-08-25 12:30:44 +0000 | [diff] [blame] | 127 | |
Barry Warsaw | 3d96d52 | 1997-11-20 19:56:38 +0000 | [diff] [blame] | 128 | # Get an item from the queue |
| 129 | def _get(self): |
Guido van Rossum | 45e2fbc | 1998-03-26 21:13:24 +0000 | [diff] [blame] | 130 | item = self.queue[0] |
| 131 | del self.queue[0] |
| 132 | return item |