1 #include "Python.h"
2 #include "pycore_moduleobject.h" // _PyModule_GetState()
3 #include "structmember.h" // PyMemberDef
4 #include <stddef.h> // offsetof()
5
6 typedef struct {
7 PyTypeObject *SimpleQueueType;
8 PyObject *EmptyError;
9 } simplequeue_state;
10
11 static simplequeue_state *
simplequeue_get_state(PyObject * module)12 simplequeue_get_state(PyObject *module)
13 {
14 simplequeue_state *state = _PyModule_GetState(module);
15 assert(state);
16 return state;
17 }
18 static struct PyModuleDef queuemodule;
19 #define simplequeue_get_state_by_type(type) \
20 (simplequeue_get_state(_PyType_GetModuleByDef(type, &queuemodule)))
21
22 typedef 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]
32 module _queue
33 class _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
37 static int
simplequeue_clear(simplequeueobject * self)38 simplequeue_clear(simplequeueobject *self)
39 {
40 Py_CLEAR(self->lst);
41 return 0;
42 }
43
44 static void
simplequeue_dealloc(simplequeueobject * self)45 simplequeue_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
63 static int
simplequeue_traverse(simplequeueobject * self,visitproc visit,void * arg)64 simplequeue_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
75 Simple, unbounded, reentrant FIFO queue.
76 [clinic start generated code]*/
77
78 static PyObject *
simplequeue_new_impl(PyTypeObject * type)79 simplequeue_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
110 Put the item on the queue.
111
112 The optional 'block' and 'timeout' arguments are ignored, as this method
113 never blocks. They are provided for compatibility with the Queue class.
114
115 [clinic start generated code]*/
116
117 static PyObject *
_queue_SimpleQueue_put_impl(simplequeueobject * self,PyObject * item,int block,PyObject * timeout)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
138 Put an item into the queue without blocking.
139
140 This is exactly equivalent to `put(item)` and is only provided
141 for compatibility with the Queue class.
142
143 [clinic start generated code]*/
144
145 static PyObject *
_queue_SimpleQueue_put_nowait_impl(simplequeueobject * self,PyObject * item)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
152 static PyObject *
simplequeue_pop_item(simplequeueobject * self)153 simplequeue_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
187 Remove and return an item from the queue.
188
189 If optional args 'block' is true and 'timeout' is None (the default),
190 block if necessary until an item is available. If 'timeout' is
191 a non-negative number, it blocks at most 'timeout' seconds and raises
192 the Empty exception if no item was available within that time.
193 Otherwise ('block' is false), return an item if one is immediately
194 available, else raise the Empty exception ('timeout' is ignored
195 in that case).
196
197 [clinic start generated code]*/
198
199 static PyObject *
_queue_SimpleQueue_get_impl(simplequeueobject * self,PyTypeObject * cls,int block,PyObject * timeout)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
285 Remove and return an item from the queue without blocking.
286
287 Only get an item if one is immediately available. Otherwise
288 raise the Empty exception.
289 [clinic start generated code]*/
290
291 static PyObject *
_queue_SimpleQueue_get_nowait_impl(simplequeueobject * self,PyTypeObject * cls)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
302 Return True if the queue is empty, False otherwise (not reliable!).
303 [clinic start generated code]*/
304
305 static int
_queue_SimpleQueue_empty_impl(simplequeueobject * self)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
315 Return the approximate size of the queue (not reliable!).
316 [clinic start generated code]*/
317
318 static Py_ssize_t
_queue_SimpleQueue_qsize_impl(simplequeueobject * self)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
325 static int
queue_traverse(PyObject * m,visitproc visit,void * arg)326 queue_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
334 static int
queue_clear(PyObject * m)335 queue_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
343 static void
queue_free(void * m)344 queue_free(void *m)
345 {
346 queue_clear((PyObject *)m);
347 }
348
349 #include "clinic/_queuemodule.c.h"
350
351
352 static 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
364 static struct PyMemberDef simplequeue_members[] = {
365 {"__weaklistoffset__", T_PYSSIZET, offsetof(simplequeueobject, weakreflist), READONLY},
366 {NULL},
367 };
368
369 static 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
380 static 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
391 PyDoc_STRVAR(queue_module_doc,
392 "C implementation of the Python queue module.\n\
393 This module is an implementation detail, please do not use it directly.");
394
395 static int
queuemodule_exec(PyObject * module)396 queuemodule_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
423 static PyModuleDef_Slot queuemodule_slots[] = {
424 {Py_mod_exec, queuemodule_exec},
425 {0, NULL}
426 };
427
428
429 static 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
441 PyMODINIT_FUNC
PyInit__queue(void)442 PyInit__queue(void)
443 {
444 return PyModuleDef_Init(&queuemodule);
445 }
446