µOS++ IIIe Reference 7.0.0
The third edition of µOS++, a POSIX inspired open source framework, written in C++
Loading...
Searching...
No Matches
os-lists.cpp
Go to the documentation of this file.
1/*
2 * This file is part of the µOS++ distribution.
3 * (https://github.com/micro-os-plus)
4 * Copyright (c) 2016-2023 Liviu Ionescu. All rights reserved.
5 *
6 * Permission to use, copy, modify, and/or distribute this software
7 * for any purpose is hereby granted, under the terms of the MIT license.
8 *
9 * If a copy of the license was not distributed with this file, it can
10 * be obtained from https://opensource.org/licenses/mit/.
11 */
12
13#if defined(OS_USE_OS_APP_CONFIG_H)
14#include <cmsis-plus/os-app-config.h>
15#endif
16
17#include <cmsis-plus/rtos/os.h>
18
20
21// ----------------------------------------------------------------------------
22
23#if defined(__clang__)
24#pragma clang diagnostic ignored "-Wc++98-compat"
25#endif
26
27// ----------------------------------------------------------------------------
28
29namespace os
30{
31 namespace rtos
32 {
33 namespace internal
34 {
35 // ======================================================================
36
37 void
39 {
40 // Add thread intrusive node at the end of the list.
41 insert_after (thread.child_links_,
42 const_cast<utils::static_double_list_links*> (tail ()));
43 }
44
45 // ======================================================================
46
47 void
49 {
50 if (head_.prev () == nullptr)
51 {
52 // If this is the first time, initialise the list to empty.
53 clear ();
54 }
55
56 thread::priority_t prio = node.thread_->priority ();
57
58 waiting_thread_node* after =
59 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));
60
61 if (empty ())
62 {
63 // Insert at the end of the list.
64#if defined(OS_TRACE_RTOS_LISTS)
65 trace::printf ("ready %s() empty +%u\n", __func__, prio);
66#endif
67 }
68 else if (prio <= after->thread_->priority ())
69 {
70 // Insert at the end of the list.
71#if defined(OS_TRACE_RTOS_LISTS)
72 trace::printf ("ready %s() back %u +%u \n", __func__,
73 after->thread_->priority (), prio);
74#endif
75 }
76 else if (prio > head ()->thread_->priority ())
77 {
78#pragma GCC diagnostic push
79#if defined(__clang__)
80#elif defined(__GNUC__)
81#pragma GCC diagnostic ignored "-Wuseless-cast"
82#endif
83 // Insert at the beginning of the list.
84 after =
85 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (&head_));
86#pragma GCC diagnostic pop
87
88#if defined(OS_TRACE_RTOS_LISTS)
89 trace::printf ("ready %s() front +%u %u \n", __func__, prio,
90 head ()->thread_->priority ());
91#endif
92 }
93 else
94 {
95#pragma GCC diagnostic push
96#if defined(__clang__)
97#elif defined(__GNUC__)
98#pragma GCC diagnostic ignored "-Wuseless-cast"
99#endif
100 // Insert in the middle of the list.
101 // The loop is guaranteed to terminate, and not hit the head.
102 // The weight is relatively small, priority() is not heavy.
103 while (prio > after->thread_->priority ())
104 {
105 after =
106 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (after->prev ()));
107 }
108#pragma GCC diagnostic pop
109
110#if defined(OS_TRACE_RTOS_LISTS)
111 trace::printf ("ready %s() middle %u +%u \n", __func__,
112 after->thread_->priority (), prio);
113#endif
114 }
115
116 insert_after (node, after);
117
118 node.thread_->state_ = thread::state::ready;
119 }
120
125 thread*
127 {
128 assert (!empty ());
129
130 thread* th = head ()->thread_;
131
132#if defined(OS_TRACE_RTOS_LISTS)
133 trace::printf ("ready %s() %p %s\n", __func__, th, th->name ());
134#endif
135
136 const_cast<waiting_thread_node*> (head ())->unlink ();
137
138 assert (th != nullptr);
139
140 // Unlinking is immediately followed by a context switch,
141 // so in order to guarantee that the thread is marked as
142 // running, it is saver to do it here.
143
144 th->state_ = thread::state::running;
145 return th;
146 }
147
148 // ======================================================================
149
192 void
194 {
195 thread::priority_t prio = node.thread_->priority ();
196
197 waiting_thread_node* after =
198 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));
199
200 if (empty ())
201 {
202 // Insert at the end of the list.
203#if defined(OS_TRACE_RTOS_LISTS)
204 trace::printf ("wait %s() empty +%u\n", __func__, prio);
205#endif
206 }
207 else if (prio <= after->thread_->priority ())
208 {
209 // Insert at the end of the list.
210#if defined(OS_TRACE_RTOS_LISTS)
211 trace::printf ("wait %s() back %u +%u \n", __func__,
212 after->thread_->priority (), prio);
213#endif
214 }
215 else if (prio > head ()->thread_->priority ())
216 {
217#pragma GCC diagnostic push
218#if defined(__clang__)
219#elif defined(__GNUC__)
220#pragma GCC diagnostic ignored "-Wuseless-cast"
221#endif
222 // Insert at the beginning of the list.
223 after =
224 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (&head_));
225#pragma GCC diagnostic pop
226
227#if defined(OS_TRACE_RTOS_LISTS)
228 trace::printf ("wait %s() front +%u %u \n", __func__, prio,
229 head ()->thread_->priority ());
230#endif
231 }
232 else
233 {
234#pragma GCC diagnostic push
235#if defined(__clang__)
236#elif defined(__GNUC__)
237#pragma GCC diagnostic ignored "-Wuseless-cast"
238#endif
239 // Insert in the middle of the list.
240 // The loop is guaranteed to terminate, and not hit the head.
241 // The weight is relatively small, priority() is not heavy.
242 while (prio > after->thread_->priority ())
243 {
244 after =
245 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (after->prev ()));
246 }
247#pragma GCC diagnostic pop
248
249#if defined(OS_TRACE_RTOS_LISTS)
250 trace::printf ("wait %s() middle %u +%u \n", __func__,
251 after->thread_->priority (), prio);
252#endif
253 }
254
255 insert_after (node, after);
256 }
257
263 bool
265 {
266 thread* th;
267 {
268 // ----- Enter critical section -----------------------------------
270
271 // If the list is empty, silently return.
272 if (empty ())
273 {
274 return false;
275 }
276
277 // The top priority is to remove the entry from the list
278 // so that subsequent wakeups to address different threads.
279 th = head ()->thread_;
280 const_cast<waiting_thread_node*> (head ())->unlink ();
281 // ----- Exit critical section ------------------------------------
282 }
283 assert (th != nullptr);
284
285 thread::state_t state = th->state ();
286 if (state != thread::state::destroyed)
287 {
288 th->resume ();
289 }
290 else
291 {
292#if defined(OS_TRACE_RTOS_LISTS)
293 trace::printf ("%s() gone \n", __func__);
294#endif
295 }
296
297 return true;
298 }
299
300 void
302 {
303 while (resume_one ())
304 ;
305 }
306
307 // ======================================================================
308
310 timestamp (ts)
311 {
312#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
313 trace::printf ("%s() %p \n", __func__, this);
314#endif
315 }
316
318 {
319#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
320 trace::printf ("%s() %p \n", __func__, this);
321#endif
322 }
323
324 // ======================================================================
325
327 rtos::thread& th) :
329 { ts }, //
330 thread (th)
331 {
332#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
333 trace::printf ("%s() %p \n", __func__, this);
334#endif
335 }
336
338 {
339#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
340 trace::printf ("%s() %p \n", __func__, this);
341#endif
342 }
343
344 // Must be called in a critical section.
345 void
347 {
348 rtos::thread* th = &this->thread;
349 this->unlink ();
350
351 thread::state_t state = th->state ();
352 if (state != thread::state::destroyed)
353 {
354 th->resume ();
355 }
356 }
357
358 // ======================================================================
359
360#if !defined(OS_USE_RTOS_PORT_TIMER)
361
364 { ts }, //
365 tmr (tm)
366 {
367#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
368 trace::printf ("%s() %p \n", __func__, this);
369#endif
370 }
371
373 {
374#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
375 trace::printf ("%s() %p \n", __func__, this);
376#endif
377 }
378
383 void
385 {
386 this->unlink ();
387 tmr.internal_interrupt_service_routine ();
388 }
389
390#endif
391
392 // ======================================================================
393
408#pragma GCC diagnostic push
409#if defined(__clang__)
410#elif defined(__GNUC__)
411#pragma GCC diagnostic ignored "-Wnull-dereference"
412#endif
413 void
415 {
416 clock::timestamp_t timestamp = node.timestamp;
417
418 timeout_thread_node* after =
419 static_cast<timeout_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));
420
421 if (empty ())
422 {
423 // Insert at the end of the list.
424#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
425 trace::printf ("clock %s() empty +%u\n", __func__,
426 static_cast<uint32_t> (timestamp));
427#endif
428 }
429 else if (timestamp >= after->timestamp)
430 {
431 // Insert at the end of the list.
432#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
433 trace::printf ("clock %s() back %u +%u\n", __func__,
434 static_cast<uint32_t> (after->timestamp),
435 static_cast<uint32_t> (timestamp));
436#endif
437 }
438 else if (timestamp < head ()->timestamp)
439 {
440#pragma GCC diagnostic push
441#if defined(__clang__)
442#elif defined(__GNUC__)
443#pragma GCC diagnostic ignored "-Wuseless-cast"
444#endif
445 // Insert at the beginning of the list
446 // and update the new head.
447 after =
448 static_cast<timeout_thread_node*> (const_cast<utils::static_double_list_links *> (&head_));
449#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
450 trace::printf ("clock %s() front +%u %u\n", __func__,
451 static_cast<uint32_t> (timestamp),
452 static_cast<uint32_t> (head ()->timestamp));
453#endif
454#pragma GCC diagnostic pop
455 }
456 else
457 {
458 // Insert in the middle of the list.
459 // The loop is guaranteed to terminate.
460 while (timestamp < after->timestamp)
461 {
462#pragma GCC diagnostic push
463#if defined(__clang__)
464#elif defined(__GNUC__)
465#pragma GCC diagnostic ignored "-Wuseless-cast"
466#endif
467 after =
468 static_cast<timeout_thread_node*> (const_cast<utils::static_double_list_links *> (after->prev ()));
469 }
470#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
471 trace::printf ("clock %s() middle %u +%u\n", __func__,
472 static_cast<uint32_t> (after->timestamp),
473 static_cast<uint32_t> (timestamp));
474#endif
475#pragma GCC diagnostic pop
476 }
477
478 insert_after (node, after);
479 }
480#pragma GCC diagnostic pop
481
489 void
491 {
492 if (head_.next () == nullptr)
493 {
494 // This happens before the constructors are executed.
495 return;
496 }
497
498 // Multiple threads can wait for the same time stamp, so
499 // iterate until a node with future time stamp is identified.
500 for (;;)
501 {
502 // ----- Enter critical section -----------------------------------
504
505 if (empty ())
506 {
507 break;
508 }
509#pragma GCC diagnostic push
510#if defined(__clang__)
511#elif defined(__GNUC__)
512#pragma GCC diagnostic ignored "-Wnull-dereference"
513#endif
514 clock::timestamp_t head_ts = head ()->timestamp;
515#pragma GCC diagnostic pop
516 if (now >= head_ts)
517 {
518#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
519 trace::printf ("%s() %u \n", __func__,
520 static_cast<uint32_t> (sysclock.now ()));
521#endif
522 const_cast<timestamp_node*> (head ())->action ();
523 }
524 else
525 {
526 break;
527 }
528 // ----- Exit critical section ------------------------------------
529 }
530 }
531
532 // ======================================================================
533
534 void
536 {
537 if (head_.prev () == nullptr)
538 {
539 // If this is the first time, initialise the list to empty.
540 clear ();
541 }
542
543 waiting_thread_node* after =
544 static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));
545
546#if defined(OS_TRACE_RTOS_THREAD)
547 trace::printf ("terminated %s() %p %s\n", __func__, &node.thread_,
548 node.thread_->name ());
549#endif
550
551 node.thread_->state_ = thread::state::terminated;
552
553 insert_after (node, after);
554 }
555
556 // ------------------------------------------------------------------------
557 } /* namespace internal */
558 } /* namespace rtos */
559} /* namespace os */
560
561// ----------------------------------------------------------------------------
virtual timestamp_t now(void)
Tell the current time, possibly adjusted for epoch.
void check_timestamp(port::clock::timestamp_t now)
Check list time stamps.
Definition os-lists.cpp:490
volatile timestamp_node * head(void) const
Get list head.
Definition os-lists.h:978
void link(timestamp_node &node)
Add a new thread node to the list.
Definition os-lists.cpp:414
const char * name(void) const
Get object name.
Definition os-decls.h:759
thread * unlink_head(void)
Remove the top node from the list.
Definition os-lists.cpp:126
volatile waiting_thread_node * head(void) const
Get list head.
Definition os-lists.h:916
void link(waiting_thread_node &node)
Add a new thread node to the list.
Definition os-lists.cpp:48
void link(waiting_thread_node &node)
Add a new thread node to the list.
Definition os-lists.cpp:535
void link(thread &thread)
Add a new thread node to the list.
Definition os-lists.cpp:38
Double linked list node, with time stamp and thread.
Definition os-lists.h:223
timeout_thread_node(port::clock::timestamp_t ts, thread &th)
Construct a clock timeout node.
Definition os-lists.cpp:326
rtos::thread & thread
Reference to thread who initiated the timeout.
Definition os-lists.h:294
virtual ~timeout_thread_node() override
Destruct the node.
Definition os-lists.cpp:337
virtual void action(void) override
Action to perform when the time stamp is reached.
Definition os-lists.cpp:346
timer & tmr
Reference to waiting timer.
Definition os-lists.h:385
virtual void action(void) override
Action to perform when the time stamp is reached.
Definition os-lists.cpp:384
timer_node(port::clock::timestamp_t ts, timer &tm)
Construct a clock timer node.
Definition os-lists.cpp:362
virtual ~timer_node() override
Destruct the node.
Definition os-lists.cpp:372
Double linked list node, with time stamp.
Definition os-lists.h:130
port::clock::timestamp_t timestamp
Time stamp when the next action will be performed.
Definition os-lists.h:200
virtual ~timestamp_node()
Destruct the node.
Definition os-lists.cpp:317
timestamp_node(port::clock::timestamp_t ts)
Construct a node with a time stamp.
Definition os-lists.cpp:309
Double linked list node, with thread reference.
Definition os-lists.h:60
rtos::thread * thread_
Pointer to waiting thread.
Definition os-lists.h:108
void link(waiting_thread_node &node)
Add a new thread node to the list.
Definition os-lists.cpp:193
bool resume_one(void)
Wake-up one thread (the oldest with the highest priority)
Definition os-lists.cpp:264
volatile waiting_thread_node * head(void) const
Get list head.
Definition os-lists.h:938
void resume_all(void)
Wake-up all threads in the list.
Definition os-lists.cpp:301
Interrupts critical section RAII helper.
Definition os-sched.h:498
POSIX compliant thread, using the default RTOS allocator.
Definition os-thread.h:250
uint8_t state_t
Type of variables holding thread states.
Definition os-thread.h:356
result_t priority(priority_t prio)
Set the assigned scheduling priority.
void resume(void)
Resume the thread.
state_t state(void) const
Get thread scheduler state.
Definition os-thread.h:2349
User single-shot or periodic timer.
Definition os-timer.h:57
static_double_list_links head_
A list node used to point to head and tail.
Definition lists.h:482
void insert_after(static_double_list_links &node, static_double_list_links *after)
Insert a new node after existing node.
Definition lists.cpp:118
bool empty(void) const
Check if the list is empty.
Definition lists.h:1028
void clear(void)
Clear the list.
Definition lists.cpp:105
volatile static_double_list_links * tail(void) const
Get the list tail.
Definition lists.h:1041
int printf(const char *format,...)
Write a formatted string to the trace device.
Definition trace.cpp:60
int unlink(const char *name)
port::clock::timestamp_t timestamp_t
Type of variables holding clock time stamps.
Definition os-clocks.h:85
clock_systick sysclock
The system clock object instance.
uint8_t priority_t
Type of variables holding thread priorities.
Definition os-thread.h:271
System namespace.
Single file µOS++ RTOS definitions.
@ running
Has the CPU and runs.
Definition os-thread.h:385
@ destroyed
Terminated and resources (like stack) released.
Definition os-thread.h:397
@ terminated
No longer usable, but resources not yet released.
Definition os-thread.h:393
@ ready
Present in the READY list and competing for CPU.
Definition os-thread.h:381