1 #include "Python.h"
2 #include "structmember.h" /* offsetof */
3 #include "pythread.h"
4
5 /*[clinic input]
6 module _queue
7 class _queue.SimpleQueue "simplequeueobject *" "&PySimpleQueueType"
8 [clinic start generated code]*/
9 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=cf49af81bcbbbea6]*/
10
11 static PyTypeObject PySimpleQueueType; /* forward decl */
12
13 static PyObject *EmptyError;
14
15
16 typedef struct {
17 PyObject_HEAD
18 PyThread_type_lock lock;
19 int locked;
20 PyObject *lst;
21 Py_ssize_t lst_pos;
22 PyObject *weakreflist;
23 } simplequeueobject;
24
25
26 static void
simplequeue_dealloc(simplequeueobject * self)27 simplequeue_dealloc(simplequeueobject *self)
28 {
29 PyObject_GC_UnTrack(self);
30 if (self->lock != NULL) {
31 /* Unlock the lock so it's safe to free it */
32 if (self->locked > 0)
33 PyThread_release_lock(self->lock);
34 PyThread_free_lock(self->lock);
35 }
36 Py_XDECREF(self->lst);
37 if (self->weakreflist != NULL)
38 PyObject_ClearWeakRefs((PyObject *) self);
39 Py_TYPE(self)->tp_free(self);
40 }
41
42 static int
simplequeue_traverse(simplequeueobject * self,visitproc visit,void * arg)43 simplequeue_traverse(simplequeueobject *self, visitproc visit, void *arg)
44 {
45 Py_VISIT(self->lst);
46 return 0;
47 }
48
49 /*[clinic input]
50 @classmethod
51 _queue.SimpleQueue.__new__ as simplequeue_new
52
53 Simple, unbounded, reentrant FIFO queue.
54 [clinic start generated code]*/
55
56 static PyObject *
simplequeue_new_impl(PyTypeObject * type)57 simplequeue_new_impl(PyTypeObject *type)
58 /*[clinic end generated code: output=ba97740608ba31cd input=a0674a1643e3e2fb]*/
59 {
60 simplequeueobject *self;
61
62 self = (simplequeueobject *) type->tp_alloc(type, 0);
63 if (self != NULL) {
64 self->weakreflist = NULL;
65 self->lst = PyList_New(0);
66 self->lock = PyThread_allocate_lock();
67 self->lst_pos = 0;
68 if (self->lock == NULL) {
69 Py_DECREF(self);
70 PyErr_SetString(PyExc_MemoryError, "can't allocate lock");
71 return NULL;
72 }
73 if (self->lst == NULL) {
74 Py_DECREF(self);
75 return NULL;
76 }
77 }
78
79 return (PyObject *) self;
80 }
81
82 /*[clinic input]
83 _queue.SimpleQueue.put
84 item: object
85 block: bool = True
86 timeout: object = None
87
88 Put the item on the queue.
89
90 The optional 'block' and 'timeout' arguments are ignored, as this method
91 never blocks. They are provided for compatibility with the Queue class.
92
93 [clinic start generated code]*/
94
95 static PyObject *
_queue_SimpleQueue_put_impl(simplequeueobject * self,PyObject * item,int block,PyObject * timeout)96 _queue_SimpleQueue_put_impl(simplequeueobject *self, PyObject *item,
97 int block, PyObject *timeout)
98 /*[clinic end generated code: output=4333136e88f90d8b input=6e601fa707a782d5]*/
99 {
100 /* BEGIN GIL-protected critical section */
101 if (PyList_Append(self->lst, item) < 0)
102 return NULL;
103 if (self->locked) {
104 /* A get() may be waiting, wake it up */
105 self->locked = 0;
106 PyThread_release_lock(self->lock);
107 }
108 /* END GIL-protected critical section */
109 Py_RETURN_NONE;
110 }
111
112 /*[clinic input]
113 _queue.SimpleQueue.put_nowait
114 item: object
115
116 Put an item into the queue without blocking.
117
118 This is exactly equivalent to `put(item)` and is only provided
119 for compatibility with the Queue class.
120
121 [clinic start generated code]*/
122
123 static PyObject *
_queue_SimpleQueue_put_nowait_impl(simplequeueobject * self,PyObject * item)124 _queue_SimpleQueue_put_nowait_impl(simplequeueobject *self, PyObject *item)
125 /*[clinic end generated code: output=0990536715efb1f1 input=36b1ea96756b2ece]*/
126 {
127 return _queue_SimpleQueue_put_impl(self, item, 0, Py_None);
128 }
129
130 static PyObject *
simplequeue_pop_item(simplequeueobject * self)131 simplequeue_pop_item(simplequeueobject *self)
132 {
133 Py_ssize_t count, n;
134 PyObject *item;
135
136 n = PyList_GET_SIZE(self->lst);
137 assert(self->lst_pos < n);
138
139 item = PyList_GET_ITEM(self->lst, self->lst_pos);
140 Py_INCREF(Py_None);
141 PyList_SET_ITEM(self->lst, self->lst_pos, Py_None);
142 self->lst_pos += 1;
143 count = n - self->lst_pos;
144 if (self->lst_pos > count) {
145 /* The list is more than 50% empty, reclaim space at the beginning */
146 if (PyList_SetSlice(self->lst, 0, self->lst_pos, NULL)) {
147 /* Undo pop */
148 self->lst_pos -= 1;
149 PyList_SET_ITEM(self->lst, self->lst_pos, item);
150 return NULL;
151 }
152 self->lst_pos = 0;
153 }
154 return item;
155 }
156
157 /*[clinic input]
158 _queue.SimpleQueue.get
159 block: bool = True
160 timeout: object = None
161
162 Remove and return an item from the queue.
163
164 If optional args 'block' is true and 'timeout' is None (the default),
165 block if necessary until an item is available. If 'timeout' is
166 a non-negative number, it blocks at most 'timeout' seconds and raises
167 the Empty exception if no item was available within that time.
168 Otherwise ('block' is false), return an item if one is immediately
169 available, else raise the Empty exception ('timeout' is ignored
170 in that case).
171
172 [clinic start generated code]*/
173
174 static PyObject *
_queue_SimpleQueue_get_impl(simplequeueobject * self,int block,PyObject * timeout)175 _queue_SimpleQueue_get_impl(simplequeueobject *self, int block,
176 PyObject *timeout)
177 /*[clinic end generated code: output=ec82a7157dcccd1a input=4bf691f9f01fa297]*/
178 {
179 _PyTime_t endtime = 0;
180 _PyTime_t timeout_val;
181 PyObject *item;
182 PyLockStatus r;
183 PY_TIMEOUT_T microseconds;
184
185 if (block == 0) {
186 /* Non-blocking */
187 microseconds = 0;
188 }
189 else if (timeout != Py_None) {
190 /* With timeout */
191 if (_PyTime_FromSecondsObject(&timeout_val,
192 timeout, _PyTime_ROUND_CEILING) < 0)
193 return NULL;
194 if (timeout_val < 0) {
195 PyErr_SetString(PyExc_ValueError,
196 "'timeout' must be a non-negative number");
197 return NULL;
198 }
199 microseconds = _PyTime_AsMicroseconds(timeout_val,
200 _PyTime_ROUND_CEILING);
201 if (microseconds >= PY_TIMEOUT_MAX) {
202 PyErr_SetString(PyExc_OverflowError,
203 "timeout value is too large");
204 return NULL;
205 }
206 endtime = _PyTime_GetMonotonicClock() + timeout_val;
207 }
208 else {
209 /* Infinitely blocking */
210 microseconds = -1;
211 }
212
213 /* put() signals the queue to be non-empty by releasing the lock.
214 * So we simply try to acquire the lock in a loop, until the condition
215 * (queue non-empty) becomes true.
216 */
217 while (self->lst_pos == PyList_GET_SIZE(self->lst)) {
218 /* First a simple non-blocking try without releasing the GIL */
219 r = PyThread_acquire_lock_timed(self->lock, 0, 0);
220 if (r == PY_LOCK_FAILURE && microseconds != 0) {
221 Py_BEGIN_ALLOW_THREADS
222 r = PyThread_acquire_lock_timed(self->lock, microseconds, 1);
223 Py_END_ALLOW_THREADS
224 }
225 if (r == PY_LOCK_INTR && Py_MakePendingCalls() < 0) {
226 return NULL;
227 }
228 if (r == PY_LOCK_FAILURE) {
229 /* Timed out */
230 PyErr_SetNone(EmptyError);
231 return NULL;
232 }
233 self->locked = 1;
234 /* Adjust timeout for next iteration (if any) */
235 if (endtime > 0) {
236 timeout_val = endtime - _PyTime_GetMonotonicClock();
237 microseconds = _PyTime_AsMicroseconds(timeout_val, _PyTime_ROUND_CEILING);
238 }
239 }
240 /* BEGIN GIL-protected critical section */
241 assert(self->lst_pos < PyList_GET_SIZE(self->lst));
242 item = simplequeue_pop_item(self);
243 if (self->locked) {
244 PyThread_release_lock(self->lock);
245 self->locked = 0;
246 }
247 /* END GIL-protected critical section */
248
249 return item;
250 }
251
252 /*[clinic input]
253 _queue.SimpleQueue.get_nowait
254
255 Remove and return an item from the queue without blocking.
256
257 Only get an item if one is immediately available. Otherwise
258 raise the Empty exception.
259 [clinic start generated code]*/
260
261 static PyObject *
_queue_SimpleQueue_get_nowait_impl(simplequeueobject * self)262 _queue_SimpleQueue_get_nowait_impl(simplequeueobject *self)
263 /*[clinic end generated code: output=a89731a75dbe4937 input=6fe5102db540a1b9]*/
264 {
265 return _queue_SimpleQueue_get_impl(self, 0, Py_None);
266 }
267
268 /*[clinic input]
269 _queue.SimpleQueue.empty -> bool
270
271 Return True if the queue is empty, False otherwise (not reliable!).
272 [clinic start generated code]*/
273
274 static int
_queue_SimpleQueue_empty_impl(simplequeueobject * self)275 _queue_SimpleQueue_empty_impl(simplequeueobject *self)
276 /*[clinic end generated code: output=1a02a1b87c0ef838 input=1a98431c45fd66f9]*/
277 {
278 return self->lst_pos == PyList_GET_SIZE(self->lst);
279 }
280
281 /*[clinic input]
282 _queue.SimpleQueue.qsize -> Py_ssize_t
283
284 Return the approximate size of the queue (not reliable!).
285 [clinic start generated code]*/
286
287 static Py_ssize_t
_queue_SimpleQueue_qsize_impl(simplequeueobject * self)288 _queue_SimpleQueue_qsize_impl(simplequeueobject *self)
289 /*[clinic end generated code: output=f9dcd9d0a90e121e input=7a74852b407868a1]*/
290 {
291 return PyList_GET_SIZE(self->lst) - self->lst_pos;
292 }
293
294
295 #include "clinic/_queuemodule.c.h"
296
297
298 static PyMethodDef simplequeue_methods[] = {
299 _QUEUE_SIMPLEQUEUE_EMPTY_METHODDEF
300 _QUEUE_SIMPLEQUEUE_GET_METHODDEF
301 _QUEUE_SIMPLEQUEUE_GET_NOWAIT_METHODDEF
302 _QUEUE_SIMPLEQUEUE_PUT_METHODDEF
303 _QUEUE_SIMPLEQUEUE_PUT_NOWAIT_METHODDEF
304 _QUEUE_SIMPLEQUEUE_QSIZE_METHODDEF
305 {NULL, NULL} /* sentinel */
306 };
307
308
309 static PyTypeObject PySimpleQueueType = {
310 PyVarObject_HEAD_INIT(NULL, 0)
311 "_queue.SimpleQueue", /*tp_name*/
312 sizeof(simplequeueobject), /*tp_basicsize*/
313 0, /*tp_itemsize*/
314 /* methods */
315 (destructor)simplequeue_dealloc, /*tp_dealloc*/
316 0, /*tp_vectorcall_offset*/
317 0, /*tp_getattr*/
318 0, /*tp_setattr*/
319 0, /*tp_as_async*/
320 0, /*tp_repr*/
321 0, /*tp_as_number*/
322 0, /*tp_as_sequence*/
323 0, /*tp_as_mapping*/
324 0, /*tp_hash*/
325 0, /*tp_call*/
326 0, /*tp_str*/
327 0, /*tp_getattro*/
328 0, /*tp_setattro*/
329 0, /*tp_as_buffer*/
330 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE
331 | Py_TPFLAGS_HAVE_GC, /* tp_flags */
332 simplequeue_new__doc__, /*tp_doc*/
333 (traverseproc)simplequeue_traverse, /*tp_traverse*/
334 0, /*tp_clear*/
335 0, /*tp_richcompare*/
336 offsetof(simplequeueobject, weakreflist), /*tp_weaklistoffset*/
337 0, /*tp_iter*/
338 0, /*tp_iternext*/
339 simplequeue_methods, /*tp_methods*/
340 0, /* tp_members */
341 0, /* tp_getset */
342 0, /* tp_base */
343 0, /* tp_dict */
344 0, /* tp_descr_get */
345 0, /* tp_descr_set */
346 0, /* tp_dictoffset */
347 0, /* tp_init */
348 0, /* tp_alloc */
349 simplequeue_new /* tp_new */
350 };
351
352
353 /* Initialization function */
354
355 PyDoc_STRVAR(queue_module_doc,
356 "C implementation of the Python queue module.\n\
357 This module is an implementation detail, please do not use it directly.");
358
359 static struct PyModuleDef queuemodule = {
360 PyModuleDef_HEAD_INIT,
361 "_queue",
362 queue_module_doc,
363 -1,
364 NULL,
365 NULL,
366 NULL,
367 NULL,
368 NULL
369 };
370
371
372 PyMODINIT_FUNC
PyInit__queue(void)373 PyInit__queue(void)
374 {
375 PyObject *m;
376
377 /* Create the module */
378 m = PyModule_Create(&queuemodule);
379 if (m == NULL)
380 return NULL;
381
382 EmptyError = PyErr_NewExceptionWithDoc(
383 "_queue.Empty",
384 "Exception raised by Queue.get(block=0)/get_nowait().",
385 NULL, NULL);
386 if (EmptyError == NULL)
387 return NULL;
388
389 Py_INCREF(EmptyError);
390 if (PyModule_AddObject(m, "Empty", EmptyError) < 0)
391 return NULL;
392
393 if (PyType_Ready(&PySimpleQueueType) < 0)
394 return NULL;
395 Py_INCREF(&PySimpleQueueType);
396 if (PyModule_AddObject(m, "SimpleQueue", (PyObject *)&PySimpleQueueType) < 0)
397 return NULL;
398
399 return m;
400 }
401