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