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