PQRST 1.2.1
Priority Queue for Running Simple Tasks
pqrst.h
Go to the documentation of this file.
1// Priority Queue for Running Simple Tasks
2#ifndef PQRST_H_LOADED
3#define PQRST_H_LOADED 1
4 // for Doxygen
6
7#include <inttypes.h>
8
9// this lets macros be Doxygen-documented, below
10// (it's set to 1 in the Doxygen config)
11#define DOXYGEN_INCLUDE 0
12
13/*
14 * You may wish to configure the following three defines,
15 * by editing this file or by prepending settings for them.
16 */
17
18#if !defined(PQRST_SELF_QUEUE) || DOXYGEN_INCLUDE
26#define PQRST_SELF_QUEUE 0
27#endif
28
29#if !defined(PQRST_TASK_PRIORITIES) || DOXYGEN_INCLUDE
43#define PQRST_TASK_PRIORITIES 0
44#endif
45
46#if !defined(PQRST_TASK_IDENT) || DOXYGEN_INCLUDE
56#define PQRST_TASK_IDENT 0
57#endif
58
59#if !defined(PQRST_WITH_SLEEPER) || DOXYGEN_INCLUDE
66#define PQRST_WITH_SLEEPER 0
67#endif
68
69/* No configuration below */
70
71// forward class definition
72class TaskQueue;
73
84typedef uint32_t ms_t;
85
90#if !ARDUINO && !defined(MS_FMT)
91// this is used only in non-Arduino debugging code
92#define MS_FMT "%u"
93#endif
94
96#if ARDUINO
97#include <avr/pgmspace.h>
98#else
99#define PROGMEM
100#endif
101
102// Marker for a Task being queued/unqueued:
103// Task.next == PQRST_NEXT_UNQUEUED_ if the Task is _out_ of the queue.
104// See method is_enqueued_p().
105#define PQRST_NEXT_UNQUEUED_ reinterpret_cast<Task*>(1)
107
120const ms_t TIME_NEVER = (ms_t)0xffffffff;
121
140class Task {
141 friend class TaskQueue; // TaskQueue needs to see ready_time_ and next
142
143public:
148 static const PROGMEM char* const pqrst_version;
149
150private:
151 ms_t ready_time_;
152 Task* next_;
153
154#if PQRST_TASK_IDENT
155 const char* ident_;
156#endif
157
165 uint16_t flags_;
166
167#if PQRST_SELF_QUEUE
168 TaskQueue* queue_;
169#endif
170
171protected:
172 virtual void signal(int signal, ms_t t);
173 virtual void run_task(ms_t);
174
175public:
176#if PQRST_SELF_QUEUE
177 Task(TaskQueue*);
178#else
179 Task();
180#endif
181 virtual ~Task() {};
182
183 virtual void start(ms_t delay);
184 virtual void start(void);
185
186#if PQRST_SELF_QUEUE
192 TaskQueue* queue(void) const { return queue_; };
193#endif
194
215 virtual void run(ms_t t) = 0;
216
217 ms_t cancel(void);
218 ms_t uncancel(void);
219 void run_at(ms_t t, Task* T=nullptr);
220 void run_after(ms_t t, Task* T=nullptr);
221 void run_immediately(Task* T=nullptr);
222
223 bool before(const Task*) const;
224
225 bool set_task_slippy(bool);
226 bool get_task_slippy(void) const;
227
232 bool is_enqueued_p(void) const { return next_ != PQRST_NEXT_UNQUEUED_; };
233
234 ms_t ready_after(void) const;
235
236#if PQRST_TASK_PRIORITIES
237 void set_priority(unsigned char);
238 unsigned char get_priority(void) const;
239 void set_duration(ms_t);
240 ms_t get_duration(void) const;
241#endif
242
250 virtual bool user_task_p(void) const { return true; };
251
252#if PQRST_TASK_IDENT
261 void set_task_ident(const char* ident_string) { ident_ = ident_string; };
270 const char* get_task_ident(void) const { return ident_; };
271#endif
272};
273
281class MaintenanceTask : public Task {
282 friend class ModularTimeMinder;
283
284private:
285#if PQRST_SELF_QUEUE
286 MaintenanceTask(TaskQueue* tqp) : Task(tqp) {};
287#else
288 MaintenanceTask() : Task() {};
289#endif
290
291public:
297 bool user_task_p(void) const { return false; };
298};
299
303class LoopTask : public Task {
304private:
308 ms_t cadence_;
313 int n_;
314
315protected:
316 void run_task(ms_t);
317
318public:
319#if PQRST_SELF_QUEUE
320 LoopTask(TaskQueue*, ms_t cadence, int repeats=-1);
321#else
322 LoopTask(ms_t cadence, int repeats=-1);
323#endif
324
326 int set_repeats(int n);
327
333 ms_t get_cadence(void) const { return cadence_; };
340 int get_repeats(void) const { return n_; };
341
349 virtual void run(ms_t) = 0;
350};
351
360typedef void(*run_task_t)(ms_t t);
361
370class FunctionTask : public LoopTask {
371private:
372 run_task_t the_function_;
373
374public:
375#if PQRST_SELF_QUEUE
376 FunctionTask(TaskQueue*, run_task_t, ms_t cadence=0, int repeats=-1);
377#else
378 FunctionTask(run_task_t, ms_t cadence=0, int repeats=-1);
379#endif
380 void run(ms_t);
381};
382
389#if PQRST_TASK_IDENT
398typedef void (*traverse_queue_cb_t)(ms_t due, const char* ident, const Task* T);
399#else
407typedef void (*traverse_queue_cb_t)(ms_t due, const Task* T);
408#endif
409
411
412// The ms_t type (32-bit unsigned integer) will overflow at time
413// 0xffffffff (=4294967295), half of which is 0x7fffffff
414// (=2147483647). Call the times below 0x80000000 'lower-time' and
415// that time and above 'upper-time'. We want time to be regarded as
416// a ring, so that when the current time is a lower time, then all
417// upper-times are in the future, and when the current time is an
418// upper time, then all lower-times are in the future.
419//
420// Implement this in time comparisons (ie, within Task::before and
421// TaskQueue::pop) by XORing times with ModularTimeMinder.fix, which
422// we arrange to be zero during lower-time and 0x80000000 during
423// upper-time. In the former case, all lower times compare before all
424// upper times; and in the latter case, all upper times compare before
425// all lower times.
426
431class ModularTimeMinder : public MaintenanceTask {
432 friend class TaskQueue;
433
434private:
435 ms_t fix_;
436
437 // private constructor -- used only by friend class TaskQueue
438#if PQRST_SELF_QUEUE
440#else
442#endif
443 void run(ms_t t);
444};
445
447
448#if PQRST_WITH_SLEEPER
460class SleeperTask : public Task {
461public:
462#if PQRST_SELF_QUEUE
463 SleeperTask(TaskQueue* Q) : Task(Q) {};
464#else
465 SleeperTask(void) : Task() {};
466#endif
467
475 };
489 virtual Awakening wake_me(void) const = 0;
490};
491#endif
492
493
518private:
519 Task* head_;
520 ms_t reftime_;
521
522 Task* pop(ms_t);
523 void signal_to_task1(Task*, int);
524
525 ModularTimeMinder modtime_minder_;
526
527#if PQRST_WITH_SLEEPER
528 SleeperTask* sleeper_;
529#endif
530
531 Task* volatile interrupting_task_;
532
533#if PQRST_TEST_MODE
534 // The following method should only be used in the case
535 // PQRST_TEST_MODE. Making sure it's undefined, unless we're in an
536 // explicit test mode, means that it's almost impossible to have
537 // assertions inadvertently enabled in a firmware (as opposed to
538 // test) build (this is a good thing).
539 bool queue_is_valid_p(void) const;
540#endif
541
542
543public:
544 TaskQueue(void);
545 bool is_empty(void) const;
546 unsigned int size(bool inc_maintenance=false) const;
547 void traverse_queue(traverse_queue_cb_t, int max=-1);
548
549 void dump_queue_contents(void); // should only be used for debugging
550
551 void initialise(ms_t start_reftime=0);
552
553 bool run_ready(ms_t);
554 ms_t next_due_after(void) const;
555 void remove(Task*);
556 void remove_all_tasks(void);
557 void signal(int, ms_t);
558
559 void push_at(Task*, ms_t);
560 void push_after(Task*, ms_t);
561 void push_immediately(Task*);
563
564 int lateness(ms_t) const;
565
566#if PQRST_WITH_SLEEPER
579 void add_sleeper(SleeperTask* w) { sleeper_ = w; };
585 void clear_sleeper(void) { sleeper_ = nullptr; };
586#endif
587
588
589private:
599 ms_t modtime(ms_t t) const { return t ^ modtime_minder_.fix_; };
600
601 // Allow the Task::before function to use this method, and nothing else
602 friend bool Task::before(const Task* other) const;
603 friend ms_t Task::ready_after(void) const;
604};
605
606#if !PQRST_SELF_QUEUE
612extern TaskQueue Queue;
613#endif
614
615#undef TQP
616
617#endif /* PQRST_H_LOADED */
A task which runs a supplied function at a given time.
Definition: pqrst.h:370
FunctionTask(run_task_t, ms_t cadence=0, int repeats=-1)
Construct a task which will run the supplied function at a later time.
Definition: pqrst.cpp:1515
void run(ms_t)
Run a single iteration of the loop.
Definition: pqrst.cpp:1548
A Task which will automatically reschedule itself after it is run.
Definition: pqrst.h:303
int get_repeats(void) const
Returns the number of repeats still to do.
Definition: pqrst.h:340
void run_task(ms_t)
Run the task, additionally rescheduling it.
Definition: pqrst.cpp:1466
ms_t get_cadence(void) const
Return the interval between loop runs.
Definition: pqrst.h:333
ms_t set_cadence(ms_t)
Set the scheduling cadence.
Definition: pqrst.cpp:1422
virtual void run(ms_t)=0
Run a single iteration of the loop.
int set_repeats(int n)
Set the repeat-count of the loop.
Definition: pqrst.cpp:1438
LoopTask(ms_t cadence, int repeats=-1)
Construct a looping task.
Definition: pqrst.cpp:1406
There are a few ‘maintenance tasks’ on the queue, placed there by the queueing system.
Definition: pqrst.h:281
bool user_task_p(void) const
Indicates whether this is a user task or a maintenance task.
Definition: pqrst.h:297
friend class ModularTimeMinder
Definition: pqrst.h:282
A sleeper task is one which will run only when a given condition is true.
Definition: pqrst.h:460
virtual Awakening wake_me(void) const =0
Indicate whether the task is ready to be woken.
Awakening
An indication of how the task should be scheduled, when it is woken.
Definition: pqrst.h:472
@ WAKE
Wake and schedule due at the current time (like TaskQueue::push_after(0))
Definition: pqrst.h:473
@ KEEP_SLEEPING
Keep sleeping; do not awaken.
Definition: pqrst.h:472
@ WAKE_IMMEDIATELY
Wake and schedule immediately (like TaskQueue::push_immediately)
Definition: pqrst.h:474
SleeperTask(void)
Definition: pqrst.h:465
A Task represents a block of code to be executed at some point in the future.
Definition: pqrst.h:140
Task()
Construct a task.
Definition: pqrst.cpp:999
void set_task_ident(const char *ident_string)
Set the identification string for a task.
Definition: pqrst.h:261
unsigned char get_priority(void) const
Return the priority of the task.
Definition: pqrst.cpp:1305
void run_at(ms_t t, Task *T=nullptr)
Push a new task onto the queue, due at a given time.
Definition: pqrst.cpp:1086
static const PROGMEM char *const pqrst_version
Reports the PQRST version and compilation options.
Definition: pqrst.h:148
const char * get_task_ident(void) const
Retrieve the identification string.
Definition: pqrst.h:270
bool set_task_slippy(bool)
Set a task to be ‘slippy’.
Definition: pqrst.cpp:277
void run_after(ms_t t, Task *T=nullptr)
Push a new Task onto the queue, due some (non-negative) interval after the queue's current reference ...
Definition: pqrst.cpp:1111
ms_t get_duration(void) const
Return the task's expected duration.
Definition: pqrst.cpp:1338
bool before(const Task *) const
Impose an ordering on tasks.
Definition: pqrst.cpp:212
virtual bool user_task_p(void) const
True if this is a ‘user task’, as opposed to a maintenance task.
Definition: pqrst.h:250
bool is_enqueued_p(void) const
Return true if the task is currently scheduled on a queue.
Definition: pqrst.h:232
virtual ~Task()
Definition: pqrst.h:181
bool get_task_slippy(void) const
Determine whether a task is ‘slippy’.
Definition: pqrst.cpp:295
ms_t ready_after(void) const
Return the interval until the Task is next ready, relative to the queue reference time.
Definition: pqrst.cpp:712
ms_t cancel(void)
Cancel this task.
Definition: pqrst.cpp:1140
void set_priority(unsigned char)
Set the priority of the task.
Definition: pqrst.cpp:1288
ms_t uncancel(void)
Uncancel a task.
Definition: pqrst.cpp:1174
virtual void signal(int signal, ms_t t)
Receive a signal.
Definition: pqrst.cpp:1223
void run_immediately(Task *T=nullptr)
Push a task onto the queue, due immediately.
Definition: pqrst.cpp:1125
virtual void run_task(ms_t)
Run this task; this is the method which is actually called when a task is due to be run.
Definition: pqrst.cpp:1241
virtual void run(ms_t t)=0
Runs one step of the task.
virtual void start(void)
Start the task immediately.
Definition: pqrst.cpp:1062
void set_duration(ms_t)
Set the duration of the task.
Definition: pqrst.cpp:1322
A priority queue of Tasks.
Definition: pqrst.h:517
int lateness(ms_t) const
Return the interval between the given time and the queue's ‘reference time’.
Definition: pqrst.cpp:769
void push_immediately_interrupting(Task *)
Push the given task on the queue, in a way functionally equivalent to push_immediately,...
Definition: pqrst.cpp:526
void push_at(Task *, ms_t)
Push the given task onto the queue, due at time t.
Definition: pqrst.cpp:365
void push_immediately(Task *)
Push the given task on the queue, due immediately (in particular, at the current reference time).
Definition: pqrst.cpp:496
bool is_empty(void) const
Return true if the task queue is empty.
Definition: pqrst.cpp:301
void push_after(Task *, ms_t)
Push the given task onto the queue, due some (non-negative) interval after the current reference time...
Definition: pqrst.cpp:470
void add_sleeper(SleeperTask *w)
Add a sleeping task.
Definition: pqrst.h:579
void clear_sleeper(void)
Clear the sleeper task.
Definition: pqrst.h:585
void remove(Task *)
Remove from the queue an element which is == to the given Task.
Definition: pqrst.cpp:626
void traverse_queue(traverse_queue_cb_t, int max=-1)
Traverse the queue.
Definition: pqrst.cpp:829
ms_t next_due_after(void) const
Return the interval between the queue reference time and the due-time of the task at the head of the ...
Definition: pqrst.cpp:729
void dump_queue_contents(void)
Dump the queue.
Definition: pqrst.cpp:888
void initialise(ms_t start_reftime=0)
Initialise, or reinitialise, a TaskQueue.
Definition: pqrst.cpp:145
void remove_all_tasks(void)
Discard all of the tasks from the queue, without running them.
Definition: pqrst.cpp:907
TaskQueue(void)
Creates a new TaskQueue.
Definition: pqrst.cpp:107
unsigned int size(bool inc_maintenance=false) const
Return the number of user tasks currently in the queue.
Definition: pqrst.cpp:322
void signal(int, ms_t)
Pass the given integer on to each task in the queue.
Definition: pqrst.cpp:806
bool run_ready(ms_t)
If the head task in the queue is ready at the given time (ie, its due time is at or before that time)...
Definition: pqrst.cpp:670
void(* run_task_t)(ms_t t)
The type of the function which can be supplied to a FunctionTask.
Definition: pqrst.h:360
uint32_t ms_t
The Arduino supports a time type of unsigned long, which is a 4-byte unsigned integer on that platfor...
Definition: pqrst.h:84
const ms_t TIME_NEVER
TIME_NEVER is a time which will never happen.
Definition: pqrst.h:120
TaskQueue Queue
The global TaskQueue.
Definition: pqrst.cpp:1555
void(* traverse_queue_cb_t)(ms_t due, const char *ident, const Task *T)
The type of the callback for TaskQueue::traverse_queue.
Definition: pqrst.h:398