8000 Add utimeq module · ayoy/pycom-micropython-sigfox@0b973ad · GitHub
[go: up one dir, main page]
Skip to content

Commit 0b973ad

Browse files
ayoyayoy
committed
Add utimeq module
1 parent 5ee2f63 commit 0b973ad

File tree

6 files changed

+243
-0
lines changed

6 files changed

+243
-0
lines changed

‎esp32/mpconfigport.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,7 @@
8787
#define MICROPY_PY_UCTYPES (1)
8888
#define MICROPY_PY_UHASHLIB (0)
8989
#define MICROPY_PY_UHASHLIB_SHA1 (0)
90+
#define MICROPY_PY_UTIMEQ (1)
9091
#define MICROPY_PY_UJSON (1)
9192
#define MICROPY_PY_URE (1)
9293
#define MICROPY_PY_MACHINE (1)

‎extmod/modutimeq.c

Lines changed: 232 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,232 @@
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 "spi.h"
31+
#include "py/objlist.h"
32+
#include "py/runtime.h"
33+
#include "py/runtime0.h"
34+
#include "py/smallint.h"
35+
36+
#if MICROPY_PY_UTIMEQ
37+
38+
#define MODULO MICROPY_PY_UTIME_TICKS_PERIOD
39+
40+
#define DEBUG 0
41+
42+
// the algorithm here is modelled on CPython's heapq.py
43+
44+
struct qentry {
45+
mp_uint_t time;
46+
mp_uint_t id;
47+
mp_obj_t callback;
48+
mp_obj_t args;
49+
};
50+
51+
typedef struct _mp_obj_utimeq_t {
52+
mp_obj_base_t base;
53+
mp_uint_t alloc;
54+
mp_uint_t len;
55+
struct qentry items[];
56+
} mp_obj_utimeq_t;
57+
58+
STATIC mp_uint_t utimeq_id;
59+
60+
STATIC mp_obj_utimeq_t *get_heap(mp_obj_t heap_in) {
61+
return MP_OBJ_TO_PTR(heap_in);
62+
}
63+
64+
STATIC bool time_less_than(struct qentry *item, struct qentry *parent) {
65+
mp_uint_t item_tm = item->time;
66+
mp_uint_t parent_tm = parent->time;
67+
mp_uint_t res = parent_tm - item_tm;
68+
if (res == 0) {
69+
// TODO: This actually should use the same "ring" logic
70+
// as for time, to avoid artifacts when id's overflow.
71+
return item->id < parent->id;
72+
}
73+
if ((mp_int_t)res < 0) {
74+
res += MODULO;
75+
}
76+
return res && res < (MODULO / 2);
77+
}
78+
79+
STATIC 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) {
80+
mp_arg_check_num(n_args, n_kw, 1, 1, false);
81+
mp_uint_t alloc = mp_obj_get_int(args[0]);
82+
mp_obj_utimeq_t *o = m_new_obj_var(mp_obj_utimeq_t, struct qentry, alloc);
83+
o->base.type = type;
84+
memset(o->items, 0, sizeof(*o->items) * alloc);
85+
o->alloc = alloc;
86+
o->len = 0;
87+
return MP_OBJ_FROM_PTR(o);
88+
}
89+
90+
STATIC void heap_siftdown(mp_obj_utimeq_t *heap, mp_uint_t start_pos, mp_uint_t pos) {
91+
struct qentry item = heap->items[pos];
92+
while (pos > start_pos) {
93+
mp_uint_t parent_pos = (pos - 1) >> 1;
94+
struct qentry *parent = &heap->items[parent_pos];
95+
bool lessthan = time_less_than(&item, parent);
96+
if (lessthan) {
97+
heap->items[pos] = *parent;
98+
pos = parent_pos;
99+
} else {
100+
break;
101+
}
102+
}
103+
heap->items[pos] = item;
104+
}
105+
106+
STATIC void heap_siftup(mp_obj_utimeq_t *heap, mp_uint_t pos) {
107+
mp_uint_t start_pos = pos;
108+
mp_uint_t end_pos = heap->len;
109+
struct qentry item = heap->items[pos];
110+
for (mp_uint_t child_pos = 2 * pos + 1; child_pos < end_pos; child_pos = 2 * pos + 1) {
111+
// choose right child if it's <= left child
112+
if (child_pos + 1 < end_pos) {
113+
bool lessthan = time_less_than(&heap->items[child_pos], &heap->items[child_pos + 1]);
114+
if (!lessthan) {
115+
child_pos += 1;
116+
}
117+
}
118+
// bubble up the smaller child
119+
heap->items[pos] = heap->items[child_pos];
120+
pos = child_pos;
121+
}
122+
heap->items[pos] = item;
123+
heap_siftdown(heap, start_pos, pos);
124+
}
125+
126+
STATIC mp_obj_t mod_utimeq_heappush(size_t n_args, const mp_obj_t *args) {
127+
(void)n_args;
128+
mp_obj_t heap_in = args[0];
129+
mp_obj_utimeq_t *heap = get_heap(heap_in);
130+
if (heap->len == heap->alloc) {
131+
mp_raise_msg(&mp_type_IndexError, "queue overflow");
132+
}
133+
mp_uint_t l = heap->len;
134+
heap->items[l].time = MP_OBJ_SMALL_INT 10000 _VALUE(args[1]);
135+
heap->items[l].id = utimeq_id++;
136+
heap->items[l].callback = args[2];
137+
heap->items[l].args = args[3];
138+
heap_siftdown(heap, 0, heap->len);
139+
heap->len++;
140+
return mp_const_none;
141+
}
142+
STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(mod_utimeq_heappush_obj, 4, 4, mod_utimeq_heappush);
143+
144+
STATIC mp_obj_t mod_utimeq_heappop(mp_obj_t heap_in, mp_obj_t list_ref) {
145+
mp_obj_utimeq_t *heap = get_heap(heap_in);
146+
if (heap->len == 0) {
147+
nlr_raise(mp_obj_new_exception_msg(&mp_type_IndexError, "empty heap"));
148+
}
149+
mp_obj_list_t *ret = MP_OBJ_TO_PTR(list_ref);
150+
if (!MP_OBJ_IS_TYPE(list_ref, &mp_type_list) || ret->len < 3) {
151+
mp_raise_TypeError(NULL);
152+
}
153+
154+
struct qentry *item = &heap->items[0];
155+
ret->items[0] = MP_OBJ_NEW_SMALL_INT(item->time);
156+
ret->items[1] = item->callback;
157+
ret->items[2] = item->args;
158+
heap->len -= 1;
159+
heap->items[0] = heap->items[heap->len];
160+
heap->items[heap->len].callback = MP_OBJ_NULL; // so we don't retain a pointer
161+
heap->items[heap->len].args = MP_OBJ_NULL;
162+
if (heap->len) {
163+
heap_siftup(heap, 0);
164+
}
165+
return mp_const_none;
166+
}
167+
STATIC MP_DEFINE_CONST_FUN_OBJ_2(mod_utimeq_heappop_obj, mod_utimeq_heappop);
168+
169+
STATIC mp_obj_t mod_utimeq_peektime(mp_obj_t heap_in) {
170+
mp_obj_utimeq_t *heap = get_heap(heap_in);
171+
if (heap->len == 0) {
172+
nlr_raise(mp_obj_new_exception_msg(&mp_type_IndexError, "empty heap"));
173+
}
174+
175+
struct qentry *item = &heap->items[0];
176+
return MP_OBJ_NEW_SMALL_INT(item->time);
177+
}
178+
STATIC MP_DEFINE_CONST_FUN_OBJ_1(mod_utimeq_peektime_obj, mod_utimeq_peektime);
179+
180+
#if DEBUG
181+
STATIC mp_obj_t mod_utimeq_dump(mp_obj_t heap_in) {
182+
mp_obj_utimeq_t *heap = get_heap(heap_in);
183+
for (int i = 0; i < heap->len; i++) {
184+
printf(UINT_FMT "\t%p\t%p\n", heap->items[i].time,
185+
MP_OBJ_TO_PTR(heap->items[i].callback), MP_OBJ_TO_PTR(heap->items[i].args));
186+
}
187+
return mp_const_none;
188+
}
189+
STATIC MP_DEFINE_CONST_FUN_OBJ_1(mod_utimeq_dump_obj, mod_utimeq_dump);
190+
#endif
191+
192+
STATIC mp_obj_t utimeq_unary_op(mp_unary_op_t op, mp_obj_t self_in) {
193+
mp_obj_utimeq_t *self = MP_OBJ_TO_PTR(self_in);
194+
switch (op) {
195+
case MP_UNARY_OP_BOOL: return mp_obj_new_bool(self->len != 0);
196+
case MP_UNARY_OP_LEN: return MP_OBJ_NEW_SMALL_INT(self->len);
197+
default: return MP_OBJ_NULL; // op not supported
198+
}
199+
}
200+
201+
STATIC const mp_rom_map_elem_t utimeq_locals_dict_table[] = {
202+
{ MP_ROM_QSTR(MP_QSTR_push), MP_ROM_PTR(&mod_utimeq_heappush_obj) },
203+
{ MP_ROM_QSTR(MP_QSTR_pop), MP_ROM_PTR(&mod_utimeq_heappop_obj) },
204+
{ MP_ROM_QSTR(MP_QSTR_peektime), MP_ROM_PTR(&mod_utimeq_peektime_obj) },
205+
#if DEBUG
206+
{ MP_ROM_QSTR(MP_QSTR_dump), MP_ROM_PTR(&mod_utimeq_dump_obj) },
207+
#endif
208+
};
209+
210+
STATIC MP_DEFINE_CONST_DICT(utimeq_locals_dict, utimeq_locals_dict_table);
211+
212+
STATIC const mp_obj_type_t utimeq_type = {
213+
{ &mp_type_type },
214+
.name = MP_QSTR_utimeq,
215+
.make_new = utimeq_make_new,
216+
.unary_op = utimeq_unary_op,
217+
.locals_dict = (void*)&utimeq_locals_dict,
218+
};
219+
220+
STATIC const mp_rom_map_elem_t mp_module_utimeq_globals_table[] = {
221+
{ MP_ROM_QSTR(MP_QSTR___name__), MP_ROM_QSTR(MP_QSTR_utimeq) },
222+
{ MP_ROM_QSTR(MP_QSTR_utimeq), MP_ROM_PTR(&utimeq_type) },
223+
};
224+
225+
STATIC MP_DEFINE_CONST_DICT(mp_module_utimeq_globals, mp_module_utimeq_globals_table);
226+
227+
const mp_obj_module_t mp_module_utimeq = {
228+
.base = { &mp_type_module },
229+
.globals = (mp_obj_dict_t*)&mp_module_utimeq_globals,
230+
};
231+
232+
#endif //MICROPY_PY_UTIMEQ

‎py/builtin.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@ extern const mp_obj_module_t mp_module_uhashlib;
109109
extern const mp_obj_module_t mp_module_ubinascii;
110110
extern const mp_obj_module_t mp_module_urandom;
111111
extern const mp_obj_module_t mp_module_ussl;
112+
extern const mp_obj_module_t mp_module_utimeq;
112113
extern const mp_obj_module_t mp_module_machine;
113114
extern const mp_obj_module_t mp_module_lwip;
114115
extern const mp_obj_module_t mp_module_websocket;

‎py/mpconfig.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -918,6 +918,11 @@ typedef double mp_float_t;
918918
#define MICROPY_PY_UHEAPQ (0)
919919
#endif
920920

921+
// Optimized heap queue for relative timestamps
922+
#ifndef MICROPY_PY_UTIMEQ
923+
#define MICROPY_PY_UTIMEQ (0)
924+
#endif
925+
921926
#ifndef MICROPY_PY_UHASHLIB
922927
#define MICROPY_PY_UHASHLIB (0)
923928
#endif

‎py/objmodule.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -189,6 +189,9 @@ STATIC const mp_rom_map_elem_t mp_builtin_module_table[] = {
189189
#if MICROPY_PY_UHEAPQ
190190
{ MP_ROM_QSTR(MP_QSTR_uheapq), MP_ROM_PTR(&mp_module_uheapq) },
191191
#endif
192+
#if MICROPY_PY_UTIMEQ
193+
{ MP_ROM_QSTR(MP_QSTR_utimeq), MP_ROM_PTR(&mp_module_utimeq) },
194+
#endif
192195
#if MICROPY_PY_UHASHLIB
193196
{ MP_ROM_QSTR(MP_QSTR_uhashlib), MP_ROM_PTR(&mp_module_uhashlib) },
194197
#endif

‎py/py.mk

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -208,6 +208,7 @@ PY_O_BASENAME = \
208208
../extmod/modure.o \
209209
../extmod/moduzlib.o \
210210
../extmod/moduheapq.o \
211+
../extmod/modutimeq.o \
211212
../extmod/moduhashlib.o \
212213
../extmod/modubinascii.o \
213214
../extmod/virtpin.o \

0 commit comments

Comments
 (0)
0