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
214 if (block == 0) {
215 /* Non-blocking */
216 microseconds = 0;
217 }
218 else if (timeout_obj != Py_None) {
219 /* With timeout */
220 if (_PyTime_FromSecondsObject(&timeout,
221 timeout_obj, _PyTime_ROUND_CEILING) < 0) {
222 return NULL;
223 }
224 if (timeout < 0) {
225 PyErr_SetString(PyExc_ValueError,
226 "'timeout' must be a non-negative number");
227 return NULL;
228 }
229 microseconds = _PyTime_AsMicroseconds(timeout,
230 _PyTime_ROUND_CEILING);
231 if (microseconds > PY_TIMEOUT_MAX) {
232 PyErr_SetString(PyExc_OverflowError,
233 "timeout value is too large");
234 return NULL;
235 }
236 endtime = _PyDeadline_Init(timeout);
237 }
238 else {
239 /* Infinitely blocking */
240 microseconds = -1;
241 }
242
243 /* put() signals the queue to be non-empty by releasing the lock.
244 * So we simply try to acquire the lock in a loop, until the condition
245 * (queue non-empty) becomes true.
246 */
247 while (self->lst_pos == PyList_GET_SIZE(self->lst)) {
248 /* First a simple non-blocking try without releasing the GIL */
249 r = PyThread_acquire_lock_timed(self->lock, 0, 0);
250 if (r == PY_LOCK_FAILURE && microseconds != 0) {
251 Py_BEGIN_ALLOW_THREADS
252 r = PyThread_acquire_lock_timed(self->lock, microseconds, 1);
253 Py_END_ALLOW_THREADS
254 }
255
256 if (r == PY_LOCK_INTR && Py_MakePendingCalls() < 0) {
257 return NULL;
258 }
259 if (r == PY_LOCK_FAILURE) {
260 PyObject *module = PyType_GetModule(cls);
261 simplequeue_state *state = simplequeue_get_state(module);
262 /* Timed out */
263 PyErr_SetNone(state->EmptyError);
264 return NULL;
265 }
266 self->locked = 1;
267
268 /* Adjust timeout for next iteration (if any) */
269 if (microseconds > 0) {
270 timeout = _PyDeadline_Get(endtime);
271 microseconds = _PyTime_AsMicroseconds(timeout,
272 _PyTime_ROUND_CEILING);
273 }
274 }
275
276 /* BEGIN GIL-protected critical section */
277 assert(self->lst_pos < PyList_GET_SIZE(self->lst));
278 item = simplequeue_pop_item(self);
279 if (self->locked) {
280 PyThread_release_lock(self->lock);
281 self->locked = 0;
282 }
283 /* END GIL-protected critical section */
284
285 return item;
286 }
287
288 /*[clinic input]
289 _queue.SimpleQueue.get_nowait
290
291 cls: defining_class
292 /
293
294 Remove and return an item from the queue without blocking.
295
296 Only get an item if one is immediately available. Otherwise
297 raise the Empty exception.
298 [clinic start generated code]*/
299
300 static PyObject *
301 _queue_SimpleQueue_get_nowait_impl(simplequeueobject *self,
302 PyTypeObject *cls)
303 /*[clinic end generated code: output=620c58e2750f8b8a input=842f732bf04216d3]*/
304 {
305 return _queue_SimpleQueue_get_impl(self, cls, 0, Py_None);
306 }
307
308 /*[clinic input]
309 _queue.SimpleQueue.empty -> bool
310
311 Return True if the queue is empty, False otherwise (not reliable!).
312 [clinic start generated code]*/
313
314 static int
315 _queue_SimpleQueue_empty_impl(simplequeueobject *self)
316 /*[clinic end generated code: output=1a02a1b87c0ef838 input=1a98431c45fd66f9]*/
317 {
318 return self->lst_pos == PyList_GET_SIZE(self->lst);
319 }
320
321 /*[clinic input]
322 _queue.SimpleQueue.qsize -> Py_ssize_t
323
324 Return the approximate size of the queue (not reliable!).
325 [clinic start generated code]*/
326
327 static Py_ssize_t
328 _queue_SimpleQueue_qsize_impl(simplequeueobject *self)
329 /*[clinic end generated code: output=f9dcd9d0a90e121e input=7a74852b407868a1]*/
330 {
331 return PyList_GET_SIZE(self->lst) - self->lst_pos;
332 }
333
334 static int
335 queue_traverse(PyObject *m, visitproc visit, void *arg)
336 {
337 simplequeue_state *state = simplequeue_get_state(m);
338 Py_VISIT(state->SimpleQueueType);
339 Py_VISIT(state->EmptyError);
340 return 0;
341 }
342
343 static int
344 queue_clear(PyObject *m)
345 {
346 simplequeue_state *state = simplequeue_get_state(m);
347 Py_CLEAR(state->SimpleQueueType);
348 Py_CLEAR(state->EmptyError);
349 return 0;
350 }
351
352 static void
353 queue_free(void *m)
354 {
355 queue_clear((PyObject *)m);
356 }
357
358 #include "clinic/_queuemodule.c.h"
359
360
361 static PyMethodDef simplequeue_methods[] = {
362 _QUEUE_SIMPLEQUEUE_EMPTY_METHODDEF
363 _QUEUE_SIMPLEQUEUE_GET_METHODDEF
364 _QUEUE_SIMPLEQUEUE_GET_NOWAIT_METHODDEF
365 _QUEUE_SIMPLEQUEUE_PUT_METHODDEF
366 _QUEUE_SIMPLEQUEUE_PUT_NOWAIT_METHODDEF
367 _QUEUE_SIMPLEQUEUE_QSIZE_METHODDEF
368 {"__class_getitem__", Py_GenericAlias,
369 METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
370 {NULL, NULL} /* sentinel */
371 };
372
373 static struct PyMemberDef simplequeue_members[] = {
374 {"__weaklistoffset__", T_PYSSIZET, offsetof(simplequeueobject, weakreflist), READONLY},
375 {NULL},
376 };
377
378 static PyType_Slot simplequeue_slots[] = {
379 {Py_tp_dealloc, simplequeue_dealloc},
380 {Py_tp_doc, (void *)simplequeue_new__doc__},
381 {Py_tp_traverse, simplequeue_traverse},
382 {Py_tp_clear, simplequeue_clear},
383 {Py_tp_members, simplequeue_members},
384 {Py_tp_methods, simplequeue_methods},
385 {Py_tp_new, simplequeue_new},
386 {0, NULL},
387 };
388
389 static PyType_Spec simplequeue_spec = {
390 .name = "_queue.SimpleQueue",
391 .basicsize = sizeof(simplequeueobject),
392 .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |
393 Py_TPFLAGS_IMMUTABLETYPE),
394 .slots = simplequeue_slots,
395 };
396
397
398 /* Initialization function */
399
400 PyDoc_STRVAR(queue_module_doc,
401 "C implementation of the Python queue module.\n\
402 This module is an implementation detail, please do not use it directly.");
403
404 static int
405 queuemodule_exec(PyObject *module)
406 {
407 simplequeue_state *state = simplequeue_get_state(module);
408
409 state->EmptyError = PyErr_NewExceptionWithDoc(
410 "_queue.Empty",
411 "Exception raised by Queue.get(block=0)/get_nowait().",
412 NULL, NULL);
413 if (state->EmptyError == NULL) {
414 return -1;
415 }
416 if (PyModule_AddObjectRef(module, "Empty", state->EmptyError) < 0) {
417 return -1;
418 }
419
420 state->SimpleQueueType = (PyTypeObject *)PyType_FromModuleAndSpec(
421 module, &simplequeue_spec, NULL);
422 if (state->SimpleQueueType == NULL) {
423 return -1;
424 }
425 if (PyModule_AddType(module, state->SimpleQueueType) < 0) {
426 return -1;
427 }
428
429 return 0;
430 }
431
432 static PyModuleDef_Slot queuemodule_slots[] = {
433 {Py_mod_exec, queuemodule_exec},
434 {0, NULL}
435 };
436
437
438 static struct PyModuleDef queuemodule = {
439 .m_base = PyModuleDef_HEAD_INIT,
440 .m_name = "_queue",
441 .m_doc = queue_module_doc,
442 .m_size = sizeof(simplequeue_state),
443 .m_slots = queuemodule_slots,
444 .m_traverse = queue_traverse,
445 .m_clear = queue_clear,
446 .m_free = queue_free,
447 };
448
449
450 PyMODINIT_FUNC
451 PyInit__queue(void)
452 {
453 return PyModuleDef_Init(&queuemodule);
454 }