PQRST  1.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 /*
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 
88 // Marker for a Task being queued/unqueued:
89 // Task.next == PQRST_NEXT_UNQUEUED_ if the Task is _out_ of the queue.
90 // See method is_enqueued_p().
91 #define PQRST_NEXT_UNQUEUED_ reinterpret_cast<Task*>(1)
92 
106 const ms_t TIME_NEVER = (ms_t)0xffffffff;
107 
126 class Task {
127  friend class TaskQueue; // TaskQueue needs to see ready_time_ and next
128 
129 public:
134  static const PROGMEM char* const pqrst_version;
135 
136 private:
137  ms_t ready_time_;
138  Task* next;
139 
140 #if PQRST_TASK_IDENT
141  const char* ident_;
142 #endif
143 
151  uint16_t flags;
152 
153 #if PQRST_SELF_QUEUE
154  TaskQueue* queue_;
155 #endif
156 
157 protected:
158  virtual void signal(int signal, ms_t t);
159  virtual void run_task(ms_t);
160 
161 public:
162 #if PQRST_SELF_QUEUE
163  Task(TaskQueue*);
164 #else
165  Task();
166 #endif
167  virtual ~Task() {};
168 
169  virtual void start(ms_t delay);
170  virtual void start(void);
171 
172 #if PQRST_SELF_QUEUE
173 
178  TaskQueue* queue(void) const { return queue_; };
179 #endif
180 
201  virtual void run(ms_t t) = 0;
202 
203  ms_t cancel(void);
204  ms_t uncancel(void);
205  void run_at(ms_t t, Task* T=nullptr);
206  void run_after(ms_t t, Task* T=nullptr);
207  void run_immediately(Task* T=nullptr);
208 
209  bool before(const Task*) const;
210 
211  bool set_task_slippy(bool);
212  bool get_task_slippy(void) const;
213 
218  bool is_enqueued_p(void) const { return next != PQRST_NEXT_UNQUEUED_; };
219 
220  ms_t ready_after(void) const;
221 
222 #if PQRST_TASK_PRIORITIES
223  void set_priority(unsigned char);
224  unsigned char get_priority(void) const;
225  void set_duration(ms_t);
226  ms_t get_duration(void) const;
227 #endif
228 
236  virtual bool user_task_p(void) const { return true; };
237 
238 #if PQRST_TASK_IDENT
239 
247  void set_task_ident(const char* ident_string) { ident_ = ident_string; };
256  const char* get_task_ident(void) const { return ident_; };
257 #endif
258 };
259 
267 class MaintenanceTask : public Task {
268  friend class ModularTimeMinder;
269 
270 private:
271 #if PQRST_SELF_QUEUE
272  MaintenanceTask(TaskQueue* tqp) : Task(tqp) {};
273 #else
274  MaintenanceTask() : Task() {};
275 #endif
276 
277 public:
283  bool user_task_p(void) const { return false; };
284 };
285 
289 class LoopTask : public Task {
290 private:
294  ms_t cadence;
299  int n;
300 
301 protected:
302  void run_task(ms_t);
303 
304 public:
305 #if PQRST_SELF_QUEUE
306  LoopTask(TaskQueue*, ms_t cadence, int repeats=-1);
307 #else
308  LoopTask(ms_t cadence, int repeats=-1);
309 #endif
310 
311  ms_t set_cadence(ms_t);
312  int set_repeats(int n);
313 
319  ms_t get_cadence(void) const { return cadence; };
326  int get_repeats(void) const { return n; };
327 
335  virtual void run(ms_t) = 0;
336 };
337 
346 typedef void(*run_task_t)(ms_t t);
347 
356 class FunctionTask : public LoopTask {
357 private:
358  run_task_t the_function;
359 
360 public:
361 #if PQRST_SELF_QUEUE
362  FunctionTask(TaskQueue*, run_task_t, ms_t cadence=0, int repeats=-1);
363 #else
364  FunctionTask(run_task_t, ms_t cadence=0, int repeats=-1);
365 #endif
366  void run(ms_t);
367 };
368 
375 #if PQRST_TASK_IDENT
376 
384 typedef void (*traverse_queue_cb_t)(ms_t due, const char* ident, const Task* T);
385 #else
386 
393 typedef void (*traverse_queue_cb_t)(ms_t due, const Task* T);
394 #endif
395 
397 
398 // The ms_t type (32-bit unsigned integer) will overflow at time
399 // 0xffffffff (=4294967295), half of which is 0x7fffffff
400 // (=2147483647). Call the times below 0x80000000 'lower-time' and
401 // that time and above 'upper-time'. We want time to be regarded as
402 // a ring, so that when the current time is a lower time, then all
403 // upper-times are in the future, and when the current time is an
404 // upper time, then all lower-times are in the future.
405 //
406 // Implement this in time comparisons (ie, within Task::before and
407 // TaskQueue::pop) by XORing times with ModularTimeMinder.fix, which
408 // we arrange to be zero during lower-time and 0x80000000 during
409 // upper-time. In the former case, all lower times compare before all
410 // upper times; and in the latter case, all upper times compare before
411 // all lower times.
412 
417 class ModularTimeMinder : public MaintenanceTask {
418  friend class TaskQueue;
419 
420 private:
421  ms_t fix;
422 
423  // private constructor -- used only by friend class TaskQueue
424 #if PQRST_SELF_QUEUE
425  ModularTimeMinder(TaskQueue*);
426 #else
427  ModularTimeMinder();
428 #endif
429  void run(ms_t t);
430 };
431 
433 
434 
458 class TaskQueue {
459 private:
460  Task* head;
461  ms_t reftime;
462 
463  Task* pop(ms_t);
464  void signal_to_task1(Task*, int);
465 
466  ModularTimeMinder modtime_minder;
467 
468 #if PQRST_TEST_MODE
469  // The following method should only be used in the case
470  // PQRST_TEST_MODE. Making sure it's undefined, unless we're in an
471  // explicit test mode, means that it's almost impossible to have
472  // assertions inadvertently enabled in a firmware (as opposed to
473  // test) build (this is a good thing).
474  bool queue_is_valid_p(void) const;
475 #endif
476 
477 
478 public:
479  TaskQueue(void);
480  bool is_empty(void) const;
481  unsigned int size(bool inc_maintenance=false) const;
482  void traverse_queue(traverse_queue_cb_t, int max=-1);
483 
484  void dump_queue_contents(void); // should only be used for debugging
485 
486  void initialise(ms_t start_reftime=0);
487 
488  bool run_ready(ms_t);
489  ms_t next_due_after(void) const;
490  void remove(Task*);
491  void remove_all_tasks(void);
492  void signal(int, ms_t);
493 
494  void push_at(Task*, ms_t);
495  void push_after(Task*, ms_t);
496  void push_immediately(Task*);
497 
498  int lateness(ms_t) const;
499 
500 private:
510  ms_t modtime(ms_t t) const { return t ^ modtime_minder.fix; };
511 
512  // Allow the Task::before function to use this method, and nothing else
513  friend bool Task::before(const Task* other) const;
514  friend ms_t Task::ready_after(void) const;
515 };
516 
517 #if !PQRST_SELF_QUEUE
518 
523 extern TaskQueue Queue;
524 #endif
525 
526 #undef TQP
527 
528 #endif /* PQRST_H_LOADED */
const ms_t TIME_NEVER
TIME_NEVER is a time which will never happen.
Definition: pqrst.h:106
void(* run_task_t)(ms_t t)
The type of the function which can be supplied to a FunctionTask.
Definition: pqrst.h:346
Task()
Construct a task.
Definition: pqrst.cpp:882
bool user_task_p(void) const
Indicates whether this is a user task or a maintenance task.
Definition: pqrst.h:283
ms_t ready_after(void) const
Return the interval until the Task is next ready, relative to the queue reference time...
Definition: pqrst.cpp:595
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:356
ms_t get_cadence(void) const
Return the interval between loop runs.
Definition: pqrst.h:319
TaskQueue Queue
The global TaskQueue.
Definition: pqrst.cpp:1439
ms_t cancel(void)
Cancel this task.
Definition: pqrst.cpp:1027
void set_duration(ms_t)
Set the duration of the task.
Definition: pqrst.cpp:1206
unsigned char get_priority(void) const
Return the priority of the task.
Definition: pqrst.cpp:1189
There are a few ‘maintenance tasks’ on the queue, placed there by the queueing system.
Definition: pqrst.h:267
static const PROGMEM char *const pqrst_version
Reports the PQRST version and compilation options.
Definition: pqrst.h:134
virtual bool user_task_p(void) const
True if this is a ‘user task’, as opposed to a maintenance task.
Definition: pqrst.h:236
void set_task_ident(const char *ident_string)
Set the identification string for a task.
Definition: pqrst.h:247
void run_at(ms_t t, Task *T=nullptr)
Push a new task onto the queue, due at a given time.
Definition: pqrst.cpp:976
bool before(const Task *) const
Impose an ordering on tasks.
Definition: pqrst.cpp:182
int get_repeats(void) const
Returns the number of repeats still to do.
Definition: pqrst.h:326
void run_immediately(Task *T=nullptr)
Push a task onto the queue, due immediately.
Definition: pqrst.cpp:1012
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:218
A Task which will automatically reschedule itself after it is run.
Definition: pqrst.h:289
const char * get_task_ident(void) const
Retrieve the identification string.
Definition: pqrst.h:256
virtual void start(void)
Start the task immediately.
Definition: pqrst.cpp:952
bool get_task_slippy(void) const
Determine whether a task is ‘slippy’.
Definition: pqrst.cpp:265
void run_after(ms_t t, Task *T=nullptr)
Push a new Task onto the queue, due some (non-negative) interval after the queue&#39;s current reference ...
Definition: pqrst.cpp:998
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:1129
A Task represents a block of code to be executed at some point in the future.
Definition: pqrst.h:126
void set_priority(unsigned char)
Set the priority of the task.
Definition: pqrst.cpp:1172
ms_t get_duration(void) const
Return the task&#39;s expected duration.
Definition: pqrst.cpp:1222
virtual void signal(int signal, ms_t t)
Receive a signal.
Definition: pqrst.cpp:1111
bool set_task_slippy(bool)
Set a task to be ‘slippy’.
Definition: pqrst.cpp:247
ms_t uncancel(void)
Uncancel a task.
Definition: pqrst.cpp:1062
friend class TaskQueue
Definition: pqrst.h:127
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:384
virtual ~Task()
Definition: pqrst.h:167
A priority queue of Tasks.
Definition: pqrst.h:458