1/*
2 * This file is part of the MicroPython project, http://micropython.org/
3 *
4 * The MIT License (MIT)
5 *
6 * Copyright (c) 2014 Damien P. George
7 * Copyright (c) 2016-2017 Paul Sokolovsky
8 *
9 * Permission is hereby granted, free of charge, to any person obtaining a copy
10 * of this software and associated documentation files (the "Software"), to deal
11 * in the Software without restriction, including without limitation the rights
12 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 * copies of the Software, and to permit persons to whom the Software is
14 * furnished to do so, subject to the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 * THE SOFTWARE.
26 */
27
28#include <string.h>
29
30#include "py/objlist.h"
31#include "py/runtime.h"
32#include "py/smallint.h"
33
34#if MICROPY_PY_UTIMEQ
35
36#define MODULO MICROPY_PY_UTIME_TICKS_PERIOD
37
38#define DEBUG 0
39
40// the algorithm here is modelled on CPython's heapq.py
41
42struct qentry {
43 mp_uint_t time;
44 mp_uint_t id;
45 mp_obj_t callback;
46 mp_obj_t args;
47};
48
49typedef struct _mp_obj_utimeq_t {
50 mp_obj_base_t base;
51 mp_uint_t alloc;
52 mp_uint_t len;
53 struct qentry items[];
54} mp_obj_utimeq_t;
55
56STATIC mp_uint_t utimeq_id;
57
58STATIC mp_obj_utimeq_t *utimeq_get_heap(mp_obj_t heap_in) {
59 return MP_OBJ_TO_PTR(heap_in);
60}
61
62STATIC bool time_less_than(struct qentry *item, struct qentry *parent) {
63 mp_uint_t item_tm = item->time;
64 mp_uint_t parent_tm = parent->time;
65 mp_uint_t res = parent_tm - item_tm;
66 if (res == 0) {
67 // TODO: This actually should use the same "ring" logic
68 // as for time, to avoid artifacts when id's overflow.
69 return item->id < parent->id;
70 }
71 if ((mp_int_t)res < 0) {
72 res += MODULO;
73 }
74 return res && res < (MODULO / 2);
75}
76
77STATIC mp_obj_t utimeq_make_new(const mp_obj_type_t *type, size_t n_args, size_t n_kw, const mp_obj_t *args) {
78 mp_arg_check_num(n_args, n_kw, 1, 1, false);
79 mp_uint_t alloc = mp_obj_get_int(args[0]);
80 mp_obj_utimeq_t *o = m_new_obj_var(mp_obj_utimeq_t, struct qentry, alloc);
81 o->base.type = type;
82 memset(o->items, 0, sizeof(*o->items) * alloc);
83 o->alloc = alloc;
84 o->len = 0;
85 return MP_OBJ_FROM_PTR(o);
86}
87
88STATIC void utimeq_heap_siftdown(mp_obj_utimeq_t *heap, mp_uint_t start_pos, mp_uint_t pos) {
89 struct qentry item = heap->items[pos];
90 while (pos > start_pos) {
91 mp_uint_t parent_pos = (pos - 1) >> 1;
92 struct qentry *parent = &heap->items[parent_pos];
93 bool lessthan = time_less_than(&item, parent);
94 if (lessthan) {
95 heap->items[pos] = *parent;
96 pos = parent_pos;
97 } else {
98 break;
99 }
100 }
101 heap->items[pos] = item;
102}
103
104STATIC void utimeq_heap_siftup(mp_obj_utimeq_t *heap, mp_uint_t pos) {
105 mp_uint_t start_pos = pos;
106 mp_uint_t end_pos = heap->len;
107 struct qentry item = heap->items[pos];
108 for (mp_uint_t child_pos = 2 * pos + 1; child_pos < end_pos; child_pos = 2 * pos + 1) {
109 // choose right child if it's <= left child
110 if (child_pos + 1 < end_pos) {
111 bool lessthan = time_less_than(&heap->items[child_pos], &heap->items[child_pos + 1]);
112 if (!lessthan) {
113 child_pos += 1;
114 }
115 }
116 // bubble up the smaller child
117 heap->items[pos] = heap->items[child_pos];
118 pos = child_pos;
119 }
120 heap->items[pos] = item;
121 utimeq_heap_siftdown(heap, start_pos, pos);
122}
123
124STATIC mp_obj_t mod_utimeq_heappush(size_t n_args, const mp_obj_t *args) {
125 (void)n_args;
126 mp_obj_t heap_in = args[0];
127 mp_obj_utimeq_t *heap = utimeq_get_heap(heap_in);
128 if (heap->len == heap->alloc) {
129 mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("queue overflow"));
130 }
131 mp_uint_t l = heap->len;
132 heap->items[l].time = MP_OBJ_SMALL_INT_VALUE(args[1]);
133 heap->items[l].id = utimeq_id++;
134 heap->items[l].callback = args[2];
135 heap->items[l].args = args[3];
136 utimeq_heap_siftdown(heap, 0, heap->len);
137 heap->len++;
138 return mp_const_none;
139}
140STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(mod_utimeq_heappush_obj, 4, 4, mod_utimeq_heappush);
141
142STATIC mp_obj_t mod_utimeq_heappop(mp_obj_t heap_in, mp_obj_t list_ref) {
143 mp_obj_utimeq_t *heap = utimeq_get_heap(heap_in);
144 if (heap->len == 0) {
145 mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("empty heap"));
146 }
147 mp_obj_list_t *ret = MP_OBJ_TO_PTR(list_ref);
148 if (!mp_obj_is_type(list_ref, &mp_type_list) || ret->len < 3) {
149 mp_raise_TypeError(NULL);
150 }
151
152 struct qentry *item = &heap->items[0];
153 ret->items[0] = MP_OBJ_NEW_SMALL_INT(item->time);
154 ret->items[1] = item->callback;
155 ret->items[2] = item->args;
156 heap->len -= 1;
157 heap->items[0] = heap->items[heap->len];
158 heap->items[heap->len].callback = MP_OBJ_NULL; // so we don't retain a pointer
159 heap->items[heap->len].args = MP_OBJ_NULL;
160 if (heap->len) {
161 utimeq_heap_siftup(heap, 0);
162 }
163 return mp_const_none;
164}
165STATIC MP_DEFINE_CONST_FUN_OBJ_2(mod_utimeq_heappop_obj, mod_utimeq_heappop);
166
167STATIC mp_obj_t mod_utimeq_peektime(mp_obj_t heap_in) {
168 mp_obj_utimeq_t *heap = utimeq_get_heap(heap_in);
169 if (heap->len == 0) {
170 mp_raise_msg(&mp_type_IndexError, MP_ERROR_TEXT("empty heap"));
171 }
172
173 struct qentry *item = &heap->items[0];
174 return MP_OBJ_NEW_SMALL_INT(item->time);
175}
176STATIC MP_DEFINE_CONST_FUN_OBJ_1(mod_utimeq_peektime_obj, mod_utimeq_peektime);
177
178#if DEBUG
179STATIC mp_obj_t mod_utimeq_dump(mp_obj_t heap_in) {
180 mp_obj_utimeq_t *heap = utimeq_get_heap(heap_in);
181 for (int i = 0; i < heap->len; i++) {
182 printf(UINT_FMT "\t%p\t%p\n", heap->items[i].time,
183 MP_OBJ_TO_PTR(heap->items[i].callback), MP_OBJ_TO_PTR(heap->items[i].args));
184 }
185 return mp_const_none;
186}
187STATIC MP_DEFINE_CONST_FUN_OBJ_1(mod_utimeq_dump_obj, mod_utimeq_dump);
188#endif
189
190STATIC mp_obj_t utimeq_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
191 mp_obj_utimeq_t *self = MP_OBJ_TO_PTR(self_in);
192 switch (op) {
193 case MP_UNARY_OP_BOOL:
194 return mp_obj_new_bool(self->len != 0);
195 case MP_UNARY_OP_LEN:
196 return MP_OBJ_NEW_SMALL_INT(self->len);
197 default:
198 return MP_OBJ_NULL; // op not supported
199 }
200}
201
202STATIC const mp_rom_map_elem_t utimeq_locals_dict_table[] = {
203 { MP_ROM_QSTR(MP_QSTR_push), MP_ROM_PTR(&mod_utimeq_heappush_obj) },
204 { MP_ROM_QSTR(MP_QSTR_pop), MP_ROM_PTR(&mod_utimeq_heappop_obj) },
205 { MP_ROM_QSTR(MP_QSTR_peektime), MP_ROM_PTR(&mod_utimeq_peektime_obj) },
206 #if DEBUG
207 { MP_ROM_QSTR(MP_QSTR_dump), MP_ROM_PTR(&mod_utimeq_dump_obj) },
208 #endif
209};
210
211STATIC MP_DEFINE_CONST_DICT(utimeq_locals_dict, utimeq_locals_dict_table);
212
213STATIC const mp_obj_type_t utimeq_type = {
214 { &mp_type_type },
215 .name = MP_QSTR_utimeq,
216 .make_new = utimeq_make_new,
217 .unary_op = utimeq_unary_op,
218 .locals_dict = (void *)&utimeq_locals_dict,
219};
220
221STATIC const mp_rom_map_elem_t mp_module_utimeq_globals_table[] = {
222 { MP_ROM_QSTR(MP_QSTR___name__), MP_ROM_QSTR(MP_QSTR_utimeq) },
223 { MP_ROM_QSTR(MP_QSTR_utimeq), MP_ROM_PTR(&utimeq_type) },
224};
225
226STATIC MP_DEFINE_CONST_DICT(mp_module_utimeq_globals, mp_module_utimeq_globals_table);
227
228const mp_obj_module_t mp_module_utimeq = {
229 .base = { &mp_type_module },
230 .globals = (mp_obj_dict_t *)&mp_module_utimeq_globals,
231};
232
233#endif // MICROPY_PY_UTIMEQ
234