Share

STL Design Patterns II - Containers, Queues and Resource Management

We continue our discussion about STL design patterns. In this article we will discuss queuing and resource management patterns that can be implemented with ease using the STL queue and priority queue adaptors. A simple implementation of the following design patterns will be covered in this article:

Container Adaptors

We will be using the following container adaptors to implement our classes:

queue queue container adaptor supports the standard queue operations, viz. add to queue, remove from queue. STL allows you to specify the underlying container used for implementing the queue. By changing one line of code you could change from a linked list implementation to an array like double ended queue!
priority_queue Standard queue adds new arrivals at the tail of the queue. Priority queue however adds a new arrival according to its "priority". A higher priority entry is added before a lower priority entry in the queue. The "priority" for an entry is determined by invoking a user specified function.
stack Stack implements the standard LIFO (Last In First Out) operations. Just like the other container adaptors you can choose the underlying container to be a vector or a linked list.

Message Queue Pattern

Message Queues are a very important design pattern in embedded and real-time systems. Here we implement the Message Queue class as a very thin wrapper over the STL queue container adaptor.

Message Queue

#include <queue>     // STL header file for queue
#include <list>
using namespace std; // Specify that we are using the std namespace

class Message;

class Message_Queue
{
   typedef queue<Message *, list<Message *> > MsgQueType;

   MsgQueType m_msgQueue;
      
public:
   void Add(Message *pMsg)
   {
      // Insert the element at the end of the queue
      m_msgQueue.push(pMsg);
   }

   Message *Remove()
   {
      Message *pMsg = NULL;
      
      // Check if the message queue is not empty
      if (!m_msgQueue.empty())
      {
         // Queue is not empty so get a pointer to the
         // first message in the queue
         pMsg = m_msgQueue.front();
         
         // Now remove the pointer from the message queue
         m_msgQueue.pop();
      }
      return pMsg;
   }
   
   int GetLength() const
   {
      return m_msgQueue.size();
   }   
};

Priority Message Queue Pattern

The Message Queue class always adds the message to the end of the queue. In many applications, the messages need to be queued according to the priority sepcified at the time of addition i.e. when a high priority message arrives, it is enqueued before any previously present low priority messages.

We will be using the priority_queue container adaptor to implement the Priority Message Queue class.

Function Objects (Functors)

The implementation of the Priority Message Queue is quite similar to the Message Queue. The most important change here is the introduction of a struct called CompareMessages. This struct is a function object (functor), i.e. the sole purpose of this struct is to define a method for comparing the priorities of the two messages.

If you look closely you will see that the struct CompareMessages just overloads the "()" operator, i.e. the method to be invoked when CompareMessages struct is used along with the "()" operator. This provides an extremely efficient mechanism for passing function code as a parameter. This mechanism has the following advantages over passing a function pointer:

  • Function Objects are efficient, as they can even be inline. On the other hand, a function pointer will always have the overhead of a function call.
  • Function Objects provide a type safe implementation, there are no void pointers in this design.

Priority Message Queue

#include <queue>      // STL header file for queue
#include <list>
using namespace std;  // Specify that we are using the std namespace

class Message;

class Priority_Message_Queue
{
    struct Entry
    {
        Message *pMsg;
        int priority;
    };
   
    struct Compare_Messages
    {
        bool operator () (const Entry& left , const Entry& right)
        {
            return (left.priority < right.priority);
        }
    };  
 
   typedef priority_queue<Entry, vector<Entry>, Compare_Messages  > 
             Message_Queue_Type;

   Message_Queue_Type m_message_Queue;
      
public:

   void Add(Message *pMsg, int priority)
   {
      // Make an entry
      Entry entry;
      entry.pMsg = pMsg;
      entry.priority = priority;
      // Insert the element according to its priority
      m_message_Queue.push(entry);
   }
   
   Message *Remove()
   {
      Message *pMsg = NULL;
      
      // Check if the message queue is not empty
      if (!m_message_Queue.empty())
      {
         // Queue is not empty so get a pointer to the
         // first message in the queue
         pMsg = (m_message_Queue.top()).pMsg;
         
         // Now remove the pointer from the message queue
         m_message_Queue.pop();
      }
      return (pMsg);
   }
   
   size_t Get_Length() const
   {
      return m_message_Queue.size();
   }   
};

Resource Allocator Pattern

A simple Resource Allocator can be implemented by using the queue and the stack container adaptors. The container adaptors are used to maintain the free list of resources.

The Resource Allocator supports the following interfaces:

  • Construction: When the Resource Allocator is constructed, it is a given a list of free resources. These resources are added to the free resource queue.
  • Allocate: When a resource is requested, it is removed from the free resource queue and the pointer to the resource is passed to the caller.
  • Free: When a resource is freed, it is added back to the free queue.
  • GetFreeResourceCount: Returns the total number of free resources currently available.

Coldest First

In coldest first resource allocation, the resource not allocated for maximum time is allocated first. To implement this first in first out, FIFO type of allocation, the resource allocating entity keeps the free resources in a queue. A resource allocation request is serviced by removing a resource from the head of the queue. A freed resource is returned to the free list by adding it to the tail of the queue.

The following code defines a simple "coldest first" resource allocator:

Resource Allocator (Coldest First)

#include <queue>      // STL header file for queue
#include <list>
using namespace std;  // Specify that we are using the std namespace

class Resource;

class Cold_Resource_Allocator
{
   typedef queue<Resource *, list<Resource *> > Free_Queue_Type;

   Free_Queue_Type m_free_Resource_Queue;
      
public:
   
   Cold_Resource_Allocator(int resource_Count, 
                             Resource *resource_Array[])
   {
      for (int i = 0; i < resource_Count; i++)
      {
         m_free_Resource_Queue.push(resource_Array[i]);
      }
   }
 
   Resource * Allocate()
   {
      Resource *pResource = NULL;
      
      // Check if any free resources are available.
      if (!m_free_Resource_Queue.empty())
      {
         // Queue is not empty so get a pointer to the
         // first resource in the queue
         pResource = m_free_Resource_Queue.front();
         
         // Now remove the pointer from the free resource queue
         m_free_Resource_Queue.pop();
      }
      return pResource;
   }
   
   void Free(Resource *pResource)
   {
      // Insert the resource at the end of the free queue
      m_free_Resource_Queue.push(pResource);
   }
      
   size_t GetFreeResourceCount()
   {
      return m_free_Resource_Queue.size();
   }   
};

Hottest First

In hottest first resource allocation, the resource last released is allocated on next resource request. To implement this last in first out, LIFO type of allocation, the list of free resources is maintained as a stack. An allocation request is serviced by popping a free resource from the stack. When a resource is freed, it is pushed on the free resource list.

The "coldest first" resource allocator can be changed to "hottest first" resource allocator by simply replacing the queue with a stack. The following code illustrates the code for hottest first resource allocator:

Resource Allocator (Hottest First)

#include <stack>     // STL header file for stack
#include <deque>
using namespace std; // Specify that we are using the std namespace

class Resource;

class Hot_Resource_Allocator
{

   typedef stack <Resource *, deque <Resource *> > 
             Free_Stack_Type;

   Free_Stack_Type m_free_Resource_Stack;
      
public:
   
   Hot_Resource_Allocator(int resource_Count, 
                            Resource *resource_Array[])
   {
      for (int i = 0; i < resource_Count; i++)
      {
         m_free_Resource_Stack.push(resource_Array[i]);
      }
   }

   Resource * Allocate()
   {
      Resource *pResource = NULL;
      
      // Check if any free resources are available.
      if (!m_free_Resource_Stack.empty())
      {
         // Queue is not empty so get a pointer to the
         // first resource in the stack
         pResource = m_free_Resource_Stack.top();
         
         // Now remove the pointer from the free resource stack
         m_free_Resource_Stack.pop();
      }
      return pResource;
   }
   
   void Free(Resource *pResource)
   {
      // Insert the resource at the end of the free stack
      m_free_Resource_Stack.push(pResource);
   }
      
   size_t GetFreeResourceCount()
   {
      return m_free_Resource_Stack.size();
   }   
};