PQRST  1.2
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
19 
26 #define PQRST_SELF_QUEUE 0
27 #endif
28 
29 #if !defined(PQRST_TASK_PRIORITIES) || DOXYGEN_INCLUDE
30 
43 #define PQRST_TASK_PRIORITIES 0
44 #endif
45 
46 #if !defined(PQRST_TASK_IDENT) || DOXYGEN_INCLUDE
47 
56 #define PQRST_TASK_IDENT 0
57 #endif
58 
59 #if !defined(PQRST_WITH_SLEEPER) || DOXYGEN_INCLUDE
60 
66 #define PQRST_WITH_SLEEPER 0
67 #endif
68 
69 /* No configuration below */
70 
71 // forward class definition
72 class TaskQueue;
73 
84 typedef 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)
106 
120 const ms_t TIME_NEVER = (ms_t)0xffffffff;
121 
140 class Task {
141  friend class TaskQueue; // TaskQueue needs to see ready_time_ and next
142 
143 public:
148  static const PROGMEM char* const pqrst_version;
149 
150 private:
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 
171 protected:
172  virtual void signal(int signal, ms_t t);
173  virtual void run_task(ms_t);
174 
175 public:
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
187 
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
253 
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 
281 class MaintenanceTask : public Task {
282  friend class ModularTimeMinder;
283 
284 private:
285 #if PQRST_SELF_QUEUE
286  MaintenanceTask(TaskQueue* tqp) : Task(tqp) {};
287 #else
288  MaintenanceTask() : Task() {};
289 #endif
290 
291 public:
297  bool user_task_p(void) const { return false; };
298 };
299 
303 class LoopTask : public Task {
304 private:
308  ms_t cadence_;
313  int n_;
314 
315 protected:
316  void run_task(ms_t);
317 
318 public:
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 
360 typedef void(*run_task_t)(ms_t t);
361 
370 class FunctionTask : public LoopTask {
371 private:
372  run_task_t the_function_;
373 
374 public:
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
390 
398 typedef void (*traverse_queue_cb_t)(ms_t due, const char* ident, const Task* T);
399 #else
400 
407 typedef 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 
431 class ModularTimeMinder : public MaintenanceTask {
432  friend class TaskQueue;
433 
434 private:
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
449 
460 class SleeperTask : public Task {
461 public:
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 
517 class TaskQueue {
518 private:
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 
543 public:
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
567 
579  void add_sleeper(SleeperTask* w) { sleeper_ = w; };
585  void clear_sleeper(void) { sleeper_ = nullptr; };
586 #endif
587 
588 
589 private:
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
607 
612 extern TaskQueue Queue;
613 #endif
614 
615 #undef TQP
616 
617 #endif /* PQRST_H_LOADED */
const ms_t TIME_NEVER
TIME_NEVER is a time which will never happen.
Definition: pqrst.h:120
void(* run_task_t)(ms_t t)
The type of the function which can be supplied to a FunctionTask.
Definition: pqrst.h:360
virtual Awakening wake_me(void) const =0
Indicate whether the task is ready to be woken.
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:460
Awakening
An indication of how the task should be scheduled, when it is woken.
Definition: pqrst.h:472
Task()
Construct a task.
Definition: pqrst.cpp:989
bool user_task_p(void) const
Indicates whether this is a user task or a maintenance task.
Definition: pqrst.h:297
int lateness(ms_t) const
Return the interval between the given time and the queue's ‘reference time’.
Definition: pqrst.cpp:759
ms_t ready_after(void) const
Return the interval until the Task is next ready, relative to the queue reference time.
Definition: pqrst.cpp:702
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:1505
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:370
ms_t get_cadence(void) const
Return the interval between loop runs.
Definition: pqrst.h:333
virtual void run(ms_t)=0
Run a single iteration of the loop.
TaskQueue Queue
The global TaskQueue.
Definition: pqrst.cpp:1545
void initialise(ms_t start_reftime=0)
Initialise, or reinitialise, a TaskQueue.
Definition: pqrst.cpp:135
SleeperTask(void)
Definition: pqrst.h:465
ms_t cancel(void)
Cancel this task.
Definition: pqrst.cpp:1130
void set_duration(ms_t)
Set the duration of the task.
Definition: pqrst.cpp:1312
TaskQueue(void)
Creates a new TaskQueue.
Definition: pqrst.cpp:97
unsigned char get_priority(void) const
Return the priority of the task.
Definition: pqrst.cpp:1295
LoopTask(ms_t cadence, int repeats=-1)
Construct a looping task.
Definition: pqrst.cpp:1396
There are a few ‘maintenance tasks’ on the queue, placed there by the queueing system.
Definition: pqrst.h:281
void traverse_queue(traverse_queue_cb_t, int max=-1)
Traverse the queue.
Definition: pqrst.cpp:819
static const PROGMEM char *const pqrst_version
Reports the PQRST version and compilation options.
Definition: pqrst.h:148
virtual bool user_task_p(void) const
True if this is a ‘user task’, as opposed to a maintenance task.
Definition: pqrst.h:250
A sleeper task is one which will run only when a given condition is true.
Definition: pqrst.h:460
void set_task_ident(const char *ident_string)
Set the identification string for a task.
Definition: pqrst.h:261
void run_at(ms_t t, Task *T=nullptr)
Push a new task onto the queue, due at a given time.
Definition: pqrst.cpp:1076
Wake and schedule immediately (like TaskQueue::push_immediately)
Definition: pqrst.h:474
bool before(const Task *) const
Impose an ordering on tasks.
Definition: pqrst.cpp:202
int get_repeats(void) const
Returns the number of repeats still to do.
Definition: pqrst.h:340
void run_immediately(Task *T=nullptr)
Push a task onto the queue, due immediately.
Definition: pqrst.cpp:1115
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:72
ms_t set_cadence(ms_t)
Set the scheduling cadence.
Definition: pqrst.cpp:1412
bool is_enqueued_p(void) const
Return true if the task is currently scheduled on a queue.
Definition: pqrst.h:232
A Task which will automatically reschedule itself after it is run.
Definition: pqrst.h:303
int set_repeats(int n)
Set the repeat-count of the loop.
Definition: pqrst.cpp:1428
const char * get_task_ident(void) const
Retrieve the identification string.
Definition: pqrst.h:270
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:660
void run(ms_t)
Run a single iteration of the loop.
Definition: pqrst.cpp:1538
friend class ModularTimeMinder
Definition: pqrst.h:282
void push_immediately(Task *)
Push the given task on the queue, due immediately (in particular, at the current reference time).
Definition: pqrst.cpp:486
void signal(int, ms_t)
Pass the given integer on to each task in the queue.
Definition: pqrst.cpp:796
virtual void start(void)
Start the task immediately.
Definition: pqrst.cpp:1052
void dump_queue_contents(void)
Dump the queue.
Definition: pqrst.cpp:878
unsigned int size(bool inc_maintenance=false) const
Return the number of user tasks currently in the queue.
Definition: pqrst.cpp:312
void remove(Task *)
Remove from the queue an element which is == to the given Task.
Definition: pqrst.cpp:616
bool get_task_slippy(void) const
Determine whether a task is ‘slippy’.
Definition: pqrst.cpp:285
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:1101
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:1231
void clear_sleeper(void)
Clear the sleeper task.
Definition: pqrst.h:585
bool is_empty(void) const
Return true if the task queue is empty.
Definition: pqrst.cpp:291
A Task represents a block of code to be executed at some point in the future.
Definition: pqrst.h:140
void set_priority(unsigned char)
Set the priority of the task.
Definition: pqrst.cpp:1278
Keep sleeping; do not awaken.
Definition: pqrst.h:472
ms_t get_duration(void) const
Return the task's expected duration.
Definition: pqrst.cpp:1328
virtual void signal(int signal, ms_t t)
Receive a signal.
Definition: pqrst.cpp:1213
Wake and schedule due at the current time (like TaskQueue::push_after(0))
Definition: pqrst.h:473
void run_task(ms_t)
Run the task, additionally rescheduling it.
Definition: pqrst.cpp:1456
bool set_task_slippy(bool)
Set a task to be ‘slippy’.
Definition: pqrst.cpp:267
ms_t uncancel(void)
Uncancel a task.
Definition: pqrst.cpp:1164
void push_immediately_interrupting(Task *)
Push the given task on the queue, in a way functionally equivalent to push_immediately,...
Definition: pqrst.cpp:516
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
virtual ~Task()
Definition: pqrst.h:181
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:719
void push_at(Task *, ms_t)
Push the given task onto the queue, due at time t.
Definition: pqrst.cpp:355
A priority queue of Tasks.
Definition: pqrst.h:517
void remove_all_tasks(void)
Discard all of the tasks from the queue, without running them.
Definition: pqrst.cpp:897
void add_sleeper(SleeperTask *w)
Add a sleeping task.
Definition: pqrst.h:579