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