os::rtos::internal::waiting_threads_list Class Reference

Priority ordered list of threads. More...

#include <os-lists.h>

Inheritance diagram for os::rtos::internal::waiting_threads_list:

Public Types
Types and constants
using	iterator = utils::double_list_iterator< thread, waiting_thread_node, &waiting_thread_node::thread_ >
	Iterator over the list threads.

Public Member Functions
Constructors & Destructor
	waiting_threads_list ()
	Construct a list of waiting threads.
	~waiting_threads_list ()
	Destruct the list.
Public Member Functions
void	link (waiting_thread_node &node)
	Add a new thread node to the list.
volatile waiting_thread_node *	head (void) const
	Get list head.
bool	resume_one (void)
	Wake-up one thread (the oldest with the highest priority)
void	resume_all (void)
	Wake-up all threads in the list.
iterator	begin () const
	Iterator begin.
iterator	end () const
	Iterator begin.
Public Member Functions
bool	uninitialized (void) const
	Check if the list is uninitialised.
void	clear (void)
	Clear the list.
bool	empty (void) const
	Check if the list is empty.
volatile static_double_list_links *	tail (void) const
	Get the list tail.

Protected Member Functions
Private Member Functions
void	insert_after (static_double_list_links &node, static_double_list_links *after)
	Insert a new node after existing node.

Protected Attributes
Private Member Variables
static_double_list_links	head_
	A list node used to point to head and tail.

Detailed Description

There are at least two strategies:

• keep the list ordered by priorities and have the top node easily accessible the head
• preserve the insertion order and perform a full list traversal to determine the top node.

The first strategy requires a partial list traverse with each insert, to find the place to insert the node, but makes retrieving the top priority node trivial, by a single access to the list head.

The second strategy might minimise the overall processing time, but always requires a full list traversal to determine the top priority node.

On the other hand, typical waiting lists contain only one element, and in this case there is no distinction. Mutex objects occasionally might have two entries (and rarely more). Condition variables might also have several waiting threads, the number is usually small. In these cases, the distinction between the two strategies is also minimal.

In the rare cases when the waiting list is large, the first strategy favours top node retrieval, possibly improving the response time, and is thus preferred.

Definition at line 542 of file os-lists.h.

Member Typedef Documentation

iterator

using os::rtos::internal::waiting_threads_list::iterator = utils::double_list_iterator<thread, waiting_thread_node, &waiting_thread_node::thread_>

Definition at line 553 of file os-lists.h.

Constructor & Destructor Documentation

waiting_threads_list()

os::rtos::internal::waiting_threads_list::waiting_threads_list ( )

inline

The initial list status is empty.

Definition at line 916 of file os-lists.h.

      {
      }

~waiting_threads_list()

os::rtos::internal::waiting_threads_list::~waiting_threads_list ( )

inline

Definition at line 920 of file os-lists.h.

      {
      }

Member Function Documentation

begin()

waiting_threads_list::iterator os::rtos::internal::waiting_threads_list::begin ( ) const

inline

Returns

An iterator positioned at the first element.

Definition at line 937 of file os-lists.h.

      {
        return iterator{
          static_cast<waiting_threads_list::iterator::iterator_pointer> (
              head_.next ())
        };
      }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::next().

clear()

void os::utils::static_double_list::clear ( void  )

inherited

Parameters

None.

Returns

Nothing.

Initialise the mandatory node with links to itself.

Definition at line 108 of file lists.cpp.

    {
#pragma GCC diagnostic push
#if defined(__clang__)
#elif defined(__GNUC__)
#pragma GCC diagnostic ignored "-Wuseless-cast"
#endif
      head_.next (const_cast<static_double_list_links*> (&head_));
      head_.prev (const_cast<static_double_list_links*> (&head_));
#pragma GCC diagnostic pop
    }

References os::utils::static_double_list::head_, os::utils::static_double_list_links::next(), and os::utils::static_double_list_links::prev().

Referenced by os::utils::double_list::double_list(), os::rtos::internal::ready_threads_list::link(), and os::rtos::internal::terminated_threads_list::link().

empty()

bool os::utils::static_double_list::empty ( void  ) const

inlineinherited

Parameters

None.

Return values

true	The list has no nodes.
false	The list has at least one node.

Definition at line 1001 of file lists.h.

    {
      // If it points to itself, it is empty.
      return (head_.next () == &head_) || (head_.next () == nullptr);
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::next().

Referenced by os::utils::double_list::~double_list(), os::rtos::internal::clock_timestamps_list::check_timestamp(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), link(), resume_one(), and os::rtos::internal::ready_threads_list::unlink_head().

end()

waiting_threads_list::iterator os::rtos::internal::waiting_threads_list::end ( ) const

inline

Returns

An iterator positioned after the last element.

Definition at line 946 of file os-lists.h.

      {
        return iterator{
          static_cast<waiting_threads_list::iterator::iterator_pointer> (
              const_cast<utils::static_double_list_links*> (&head_))
        };
      }

References os::utils::static_double_list::head_.

head()

volatile waiting_thread_node * os::rtos::internal::waiting_threads_list::head ( void  ) const

inline

Parameters

None.

Returns

Casted pointer to head node.

Definition at line 925 of file os-lists.h.

      {
        return static_cast<volatile waiting_thread_node*> (
            double_list::head ());
      }

Referenced by link(), and resume_one().

insert_after()

void os::utils::static_double_list::insert_after ( static_double_list_links &  node, static_double_list_links *  after  )

protectedinherited

Parameters

node	Reference to node to insert.
after	Reference to existing node.

Returns

Nothing.

Definition at line 121 of file lists.cpp.

    {
#if defined(OS_TRACE_UTILS_LISTS)
      trace::printf ("%s() n=%p after %p\n", __func__, &node, after);
#endif
 
      // Unlinked nodes must have both pointers null.
      // If not, most probably the node was already linked.
      // Or the memory is corrupted.
      assert (node.prev () == nullptr);
      assert (node.next () == nullptr);
 
      // The `after` node must be linked. Only the `next` pointer is
      // tested, since only it is used.
      assert (after->next () != nullptr);
 
      // Make the new node point to its neighbours.
      node.prev (after);
      node.next (after->next ());
 
      // Make the neighbours point to the node. The order is important.
      after->next ()->prev (&node);
      after->next (&node);
    }

References os::utils::static_double_list_links::next(), os::utils::static_double_list_links::prev(), and os::trace::printf().

Referenced by os::rtos::internal::thread_children_list::link(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), link(), and os::rtos::internal::terminated_threads_list::link().

link()

void os::rtos::internal::waiting_threads_list::link

(

waiting_thread_node &

node

)

Parameters

[in]

node

Reference to a list node.

Returns

Nothing.

Based on priority, the node is inserted

• at the end of the list,
• at the beginning of the list,
• in the middle of the list, which requires a partial list traversal (done from the end).

To satisfy the circular double linked list requirements, an empty list still contains the head node with references to itself.

Definition at line 194 of file os-lists.cpp.

      {
        thread::priority_t prio = node.thread_->priority ();
 
        waiting_thread_node* after = static_cast<waiting_thread_node*> (
            const_cast<utils::static_double_list_links*> (tail ()));
 
        if (empty ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() empty +%u\n", __func__, prio);
#endif
          }
        else if (prio <= after->thread_->priority ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() back %u +%u \n", __func__,
                           after->thread_->priority (), prio);
#endif
          }
        else if (prio > head ()->thread_->priority ())
          {
#pragma GCC diagnostic push
#if defined(__clang__)
#elif defined(__GNUC__)
#pragma GCC diagnostic ignored "-Wuseless-cast"
#endif
            // Insert at the beginning of the list.
            after = static_cast<waiting_thread_node*> (
                const_cast<utils::static_double_list_links*> (&head_));
#pragma GCC diagnostic pop
 
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() front +%u %u \n", __func__, prio,
                           head ()->thread_->priority ());
#endif
          }
        else
          {
#pragma GCC diagnostic push
#if defined(__clang__)
#elif defined(__GNUC__)
#pragma GCC diagnostic ignored "-Wuseless-cast"
#endif
            // Insert in the middle of the list.
            // The loop is guaranteed to terminate, and not hit the head.
            // The weight is relatively small, priority() is not heavy.
            while (prio > after->thread_->priority ())
              {
                after = static_cast<waiting_thread_node*> (
                    const_cast<utils::static_double_list_links*> (
                        after->prev ()));
              }
#pragma GCC diagnostic pop
 
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() middle %u +%u \n", __func__,
                           after->thread_->priority (), prio);
#endif
          }
 
        insert_after (node, after);
      }

References os::utils::static_double_list::empty(), head(), os::utils::static_double_list::head_, os::utils::static_double_list::insert_after(), os::utils::static_double_list_links::prev(), os::trace::printf(), os::rtos::thread::priority(), os::utils::static_double_list::tail(), and os::rtos::internal::waiting_thread_node::thread_.

resume_all()

void os::rtos::internal::waiting_threads_list::resume_all

(

void

)

Parameters

None.

Returns

Nothing.

Definition at line 303 of file os-lists.cpp.

      {
        while (resume_one ())
          ;
      }

References resume_one().

resume_one()

bool os::rtos::internal::waiting_threads_list::resume_one

(

void

)

Parameters

None.

Return values

true	The list may have further entries.
false	The list is empty.

Atomically get the top thread from the list, remove the node and wake-up the thread.

Definition at line 266 of file os-lists.cpp.

      {
        thread* th;
        {
          // ----- Enter critical section -------------------------------------
          interrupts::critical_section ics;
 
          // If the list is empty, silently return.
          if (empty ())
            {
              return false;
            }
 
          // The top priority is to remove the entry from the list
          // so that subsequent wakeups to address different threads.
          th = head ()->thread_;
          const_cast<waiting_thread_node*> (head ())->unlink ();
          // ----- Exit critical section --------------------------------------
        }
        assert (th != nullptr);
 
        thread::state_t state = th->state ();
        if (state != thread::state::destroyed)
          {
            th->resume ();
          }
        else
          {
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("%s() gone \n", __func__);
#endif
          }
 
        return true;
      }

References os::rtos::thread::state::destroyed, os::utils::static_double_list::empty(), head(), os::trace::printf(), os::rtos::thread::resume(), os::rtos::thread::state(), os::rtos::internal::waiting_thread_node::thread_, and unlink().

Referenced by resume_all().

tail()

volatile static_double_list_links * os::utils::static_double_list::tail ( void  ) const

inlineinherited

Parameters

None.

Returns

Pointer to tail node.

Definition at line 1014 of file lists.h.

    {
      return (head_.prev ());
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::prev().

Referenced by os::rtos::internal::thread_children_list::link(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), link(), and os::rtos::internal::terminated_threads_list::link().

uninitialized()

bool os::utils::static_double_list::uninitialized ( void  ) const

inlineinherited

Parameters

None.

Return values

true	The list was not initialised.
false	The list was initialised.

Definition at line 994 of file lists.h.

    {
      // If it points to nowhere, it is not yet initialised.
      return (head_.prev () == nullptr);
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::prev().

Member Data Documentation

head_

static_double_list_links os::utils::static_double_list::head_

protectedinherited

To simplify processing, the list always has a node.

Definition at line 473 of file lists.h.

Referenced by begin(), os::rtos::internal::clock_timestamps_list::check_timestamp(), os::utils::static_double_list::clear(), os::utils::static_double_list::empty(), end(), os::utils::static_double_list::head(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), link(), os::rtos::internal::terminated_threads_list::link(), os::utils::static_double_list::tail(), and os::utils::static_double_list::uninitialized().

---

The documentation for this class was generated from the following files:

• os-lists.h
• os-lists.cpp