PQRST  1.0
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 /*
10  * You may wish to configure the following three defines,
11  * by editing this file or by prepending settings for them.
12  */
13 
14 #ifndef PQRST_SELF_QUEUE
15 
22 #define PQRST_SELF_QUEUE 0
23 #endif
24 
25 #ifndef PQRST_TASK_PRIORITIES
26 
39 #define PQRST_TASK_PRIORITIES 0
40 #endif
41 
42 #ifndef PQRST_TASK_IDENT
43 
52 #define PQRST_TASK_IDENT 0
53 #endif
54 
55 /* No configuration below */
56 
57 // forward class definition
58 class TaskQueue;
59 
70 typedef uint32_t ms_t;
71 
76 #if !ARDUINO && !defined(MS_FMT)
77 // this is used only in non-Arduino debugging code
78 #define MS_FMT "%u"
79 #endif
80 
82 #if ARDUINO
83 #include <avr/pgmspace.h>
84 #else
85 #define PROGMEM
86 #endif
87 
98 #ifndef TIME_NEVER
99 #define TIME_NEVER ((ms_t)0xffffffff)
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)
106 
125 class Task {
126  friend class TaskQueue; // TaskQueue needs to see ready_time_ and next
127 
128 public:
133  static const PROGMEM char* const pqrst_version;
134 
135 private:
136  ms_t ready_time_;
137  Task* next;
138 
139 #if PQRST_TASK_IDENT
140  const char* ident;
141 #endif
142 
150  uint16_t flags;
151 
152 #if PQRST_SELF_QUEUE
153  TaskQueue* queue_;
154 #endif
155 
156 protected:
157  virtual void signal(int signal, ms_t t);
158  virtual void run_task(ms_t);
159 
160 public:
161 #if PQRST_SELF_QUEUE
162  Task(TaskQueue*);
163 #else
164  Task();
165 #endif
166  virtual ~Task() {};
167 
168  virtual void start(ms_t delay);
169  virtual void start(void);
170 
171 #if PQRST_SELF_QUEUE
172 
177  TaskQueue* queue(void) const { return queue_; };
178 #endif
179 
200  virtual void run(ms_t t) = 0;
201 
202  ms_t cancel(void);
203  ms_t uncancel(void);
204  void run_at(ms_t t, Task* T=nullptr);
205  void run_after(ms_t t, Task* T=nullptr);
206  void run_immediately(Task* T=nullptr);
207 
208  bool before(const Task*) const;
209 
210  bool set_task_slippy(bool);
211  bool get_task_slippy(void) const;
212 
217  bool is_enqueued_p(void) const { return next != PQRST_NEXT_UNQUEUED_; };
218 
226  ms_t ready_time(void) const { return ready_time_; };
227 
228 #if PQRST_TASK_PRIORITIES
229  void set_priority(unsigned char);
230  unsigned char get_priority(void) const;
231  void set_duration(ms_t);
232  ms_t get_duration(void) const;
233 #endif
234 
242  virtual bool user_task_p(void) const { return true; };
243 
244 #if PQRST_TASK_IDENT
245 
253  void set_task_ident(const char* ident_string) { ident = ident_string; };
262  const char* get_task_ident(void) const { return ident; };
263 #endif
264 };
265 
273 class MaintenanceTask : public Task {
274  friend class ModularTimeMinder;
275 
276 private:
277 #if PQRST_SELF_QUEUE
278  MaintenanceTask(TaskQueue* tqp) : Task(tqp) {};
279 #else
280  MaintenanceTask() : Task() {};
281 #endif
282 
283 public:
289  bool user_task_p(void) const { return false; };
290 };
291 
295 class LoopTask : public Task {
296 private:
300  ms_t cadence;
305  int n;
306 
307 protected:
308  void run_task(ms_t);
309 
310 public:
311 #if PQRST_SELF_QUEUE
312  LoopTask(TaskQueue*, ms_t cadence, int repeats=-1);
313 #else
314  LoopTask(ms_t cadence, int repeats=-1);
315 #endif
316 
317  ms_t set_cadence(ms_t);
318  int set_repeats(int n);
319 
325  ms_t get_cadence(void) const { return cadence; };
332  int get_repeats(void) const { return n; };
333 
341  virtual void run(ms_t) = 0;
342 };
343 
352 typedef void(*run_task_t)(ms_t t);
353 
362 class FunctionTask : public LoopTask {
363 private:
364  run_task_t the_function;
365 
366 public:
367 #if PQRST_SELF_QUEUE
368  FunctionTask(TaskQueue*, run_task_t, ms_t cadence=0, int repeats=-1);
369 #else
370  FunctionTask(run_task_t, ms_t cadence=0, int repeats=-1);
371 #endif
372  void run(ms_t);
373 };
374 
381 #if PQRST_TASK_IDENT
382 
390 typedef void (*traverse_queue_cb_t)(ms_t due, const char* ident, const Task* T);
391 #else
392 
399 typedef void (*traverse_queue_cb_t)(ms_t due, const Task* T);
400 #endif
401 
403 
404 // The ms_t type (32-bit unsigned integer) will overflow at time
405 // 0xffffffff (=4294967295), half of which is 0x7fffffff
406 // (=2147483647). Call the times below 0x80000000 'lower-time' and
407 // that time and above 'upper-time'. We want time to be regarded as
408 // a ring, so that when the current time is a lower time, then all
409 // upper-times are in the future, and when the current time is an
410 // upper time, then all lower-times are in the future.
411 //
412 // Implement this in time comparisons (ie, within Task::before and
413 // TaskQueue::pop) by XORing times with ModularTimeMinder.fix, which
414 // we arrange to be zero during lower-time and 0x80000000 during
415 // upper-time. In the former case, all lower times compare before all
416 // upper times; and in the latter case, all upper times compare before
417 // all lower times.
418 
423 class ModularTimeMinder : public MaintenanceTask {
424  friend class TaskQueue;
425 
426 private:
427  ms_t fix;
428 
429  // private constructor -- used only by friend class TaskQueue
430 #if PQRST_SELF_QUEUE
431  ModularTimeMinder(TaskQueue*);
432 #else
433  ModularTimeMinder();
434 #endif
435  void run(ms_t t);
436 };
437 
439 
440 
464 class TaskQueue {
465 private:
466  Task* head;
467  ms_t reftime;
468 
469  Task* pop(ms_t);
470  void signal_to_task1(Task*, int);
471 
472  ModularTimeMinder modtime_minder;
473 
474 #if PQRST_TEST_MODE
475  // The following method should only be used in the case
476  // PQRST_TEST_MODE. Making sure it's undefined, unless we're in an
477  // explicit test mode, means that it's almost impossible to have
478  // assertions inadvertently enabled in a firmware (as opposed to
479  // test) build (this is a good thing).
480  bool queue_is_valid_p(void) const;
481 #endif
482 
483 
484 public:
485  TaskQueue(void);
486  bool is_empty(void) const;
487  unsigned int size(bool inc_maintenance=false) const;
488  void traverse_queue(traverse_queue_cb_t, int max=-1);
489 
490  void dump_queue_contents(void); // should only be used for debugging
491  void initialise(void); // ditto
492 
493  bool run_ready(ms_t);
494  ms_t next_due_after(void) const;
495  void remove(Task*);
496  void remove_all_tasks(void);
497  void signal(int, ms_t);
498 
499  void push_at(Task*, ms_t);
500  void push_after(Task*, ms_t);
501  void push_immediately(Task*);
502 
503  int lateness(ms_t) const;
504 
505 private:
515  ms_t modtime(ms_t t) const { return t ^ modtime_minder.fix; };
516 
517  // Allow the Task::before function to use this method, and nothing else
518  friend bool Task::before(const Task* other) const;
519 };
520 
521 #if !PQRST_SELF_QUEUE
522 
527 extern TaskQueue Queue;
528 #endif
529 
530 #undef TQP
531 
532 #endif /* PQRST_H_LOADED */
void(* run_task_t)(ms_t t)
The type of the function which can be supplied to a FunctionTask.
Definition: pqrst.h:352
ms_t ready_time(void) const
Return the time when the tast is next ready.
Definition: pqrst.h:226
Task()
Construct a task.
Definition: pqrst.cpp:835
bool user_task_p(void) const
Indicates whether this is a user task or a maintenance task.
Definition: pqrst.h:289
virtual void run(ms_t t)=0
Runs one step of the task.
A task which runs a supplied function at a given time.
Definition: pqrst.h:362
ms_t get_cadence(void) const
Return the interval between loop runs.
Definition: pqrst.h:325
TaskQueue Queue
The global TaskQueue.
Definition: pqrst.cpp:1382
ms_t cancel(void)
Cancel this task.
Definition: pqrst.cpp:970
void set_duration(ms_t)
Set the duration of the task.
Definition: pqrst.cpp:1149
unsigned char get_priority(void) const
Return the priority of the task.
Definition: pqrst.cpp:1132
There are a few ‘maintenance tasks’ on the queue, placed there by the queueing system.
Definition: pqrst.h:273
static const PROGMEM char *const pqrst_version
Reports the PQRST version and compilation options.
Definition: pqrst.h:133
virtual bool user_task_p(void) const
True if this is a ‘user task’, as opposed to a maintenance task.
Definition: pqrst.h:242
void set_task_ident(const char *ident_string)
Set the identification string for a task.
Definition: pqrst.h:253
void run_at(ms_t t, Task *T=nullptr)
Push a new task onto the queue, due at a given time.
Definition: pqrst.cpp:922
bool before(const Task *) const
Impose an ordering on tasks.
Definition: pqrst.cpp:171
int get_repeats(void) const
Returns the number of repeats still to do.
Definition: pqrst.h:332
void run_immediately(Task *T=nullptr)
Push a task onto the queue, due immediately.
Definition: pqrst.cpp:955
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:58
bool is_enqueued_p(void) const
Return true if the task is currently scheduled on a queue.
Definition: pqrst.h:217
A Task which will automatically reschedule itself after it is run.
Definition: pqrst.h:295
const char * get_task_ident(void) const
Retrieve the identification string.
Definition: pqrst.h:262
virtual void start(void)
Start the task immediately.
Definition: pqrst.cpp:905
bool get_task_slippy(void) const
Determine whether a task is ‘slippy’.
Definition: pqrst.cpp:255
void run_after(ms_t t, Task *T=nullptr)
Push a new Task onto the queue, due some (positive) interval after the queue&#39;s current reference time...
Definition: pqrst.cpp:941
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:1072
A Task represents a block of code to be executed at some point in the future.
Definition: pqrst.h:125
void set_priority(unsigned char)
Set the priority of the task.
Definition: pqrst.cpp:1115
ms_t get_duration(void) const
Return the task&#39;s expected duration.
Definition: pqrst.cpp:1165
virtual void signal(int signal, ms_t t)
Receive a signal.
Definition: pqrst.cpp:1054
bool set_task_slippy(bool)
Set a task to be ‘slippy’.
Definition: pqrst.cpp:237
ms_t uncancel(void)
Uncancel a task.
Definition: pqrst.cpp:1005
friend class TaskQueue
Definition: pqrst.h:126
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:390
virtual ~Task()
Definition: pqrst.h:166
A priority queue of Tasks.
Definition: pqrst.h:464