EventHelix.com: CASE Tools; Real-time and Embedded System Design; Object Oriented Design
  Home  |  EventStudio System Designer 4.0  |  VisualEther Protocol Analyzer 1.0  |  Real-time Mantra  |  Contact Us
Home > Real-time Mantra > Design Patterns > STL Design Patterns II

STL Design Patterns II

 Click here to open Message Queue Documentation in a new window Message Queue Documentation
 Click here to open Priority Message Queue Documentation in a new window Priority Message Documentation
 Click here to open Coldest First Resource Allocator Documentation in a new window Coldest First Resource Allocator Documentation
 Click here to open Hottest First Resource Allocator Documentation in a new window Hottest First Resource Allocator Documentation
Click here to download STL Design Patterns II Source Code STL Design Patterns II Source Code

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 
00009 #include <queue>     // STL header file for queue
00010 #include <list>
00011 using namespace std; // Specify that we are using the std namespace
00012 
00013 class Message;
00014 
00027 
00028 class Message_Queue
00029 {
00032    typedef queue<Message *, list<Message *> > MsgQueType;
00033 
00035    MsgQueType m_msgQueue;
00036       
00037 public:
00044    void Add(Message *pMsg)
00045    {
00046       // Insert the element at the end of the queue
00047       m_msgQueue.push(pMsg);
00048    }
00049
00060    Message *Remove()
00061    {
00062       Message *pMsg = NULL;
00063       
00064       // Check if the message queue is not empty
00065       if (!m_msgQueue.empty())
00066       {
00067          // Queue is not empty so get a pointer to the
00068          // first message in the queue
00069          pMsg = m_msgQueue.front();
00070          
00071          // Now remove the pointer from the message queue
00072          m_msgQueue.pop();
00073       }
00074       return pMsg;
00075    }
00076    
00080    int GetLength() const
00081    {
00082       return m_msgQueue.size();
00083    }   
00084 };

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 
00008 #include <queue>      // STL header file for queue
00009 #include <list>
00010 using namespace std;  // Specify that we are using the std namespace
00011 
00012 class Message;
00013 
00024 class Priority_Message_Queue
00025 {
00028     struct Entry
00029     {
00031         Message *pMsg;
00034         int priority;
00035     };
00036    
00051     struct Compare_Messages
00052     {
00055         bool operator () (const Entry& left , const Entry& right)
00056         {
00057             return (left.priority < right.priority);
00058         }
00059     };  
00060  
00065    typedef priority_queue<Entry, vector<Entry>, Compare_Messages  > 
                   Message_Queue_Type;
00066 
00068    Message_Queue_Type m_message_Queue;
00069       
00070 public:
00071 
00084    void Add(Message *pMsg, int priority)
00085    {
00086       // Make an entry
00087       Entry entry;
00088       entry.pMsg = pMsg;
00089       entry.priority = priority;
00090       // Insert the element according to its priority
00091       m_message_Queue.push(entry);
00092    }
00093    
00104    Message *Remove()
00105    {
00106       Message *pMsg = NULL;
00107       
00108       // Check if the message queue is not empty
00109       if (!m_message_Queue.empty())
00110       {
00111          // Queue is not empty so get a pointer to the
00112          // first message in the queue
00113          pMsg = (m_message_Queue.top()).pMsg;
00114          
00115          // Now remove the pointer from the message queue
00116          m_message_Queue.pop();
00117       }
00118       return (pMsg);
00119    }
00120    
00123    size_t Get_Length() const
00124    {
00125       return m_message_Queue.size();
00126    }   
00127 };

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) 
00008 #include <queue>      // STL header file for queue
00009 #include <list>
00010 using namespace std;  // Specify that we are using the std namespace
00011 
00012 class Resource;
00013 
00021 class Cold_Resource_Allocator
00022 {
00029    typedef queue<Resource *, list<Resource *> > Free_Queue_Type;
00030 
00032    Free_Queue_Type m_free_Resource_Queue;
00033       
00034 public:
00035    
00041    Cold_Resource_Allocator(int resource_Count, 
                                   Resource *resource_Array[])
00042    {
00043       for (int i = 0; i < resource_Count; i++)
00044       {
00045          m_free_Resource_Queue.push(resource_Array[i]);
00046       }
00047    }
00048  
00053    Resource * Allocate()
00054    {
00055       Resource *pResource = NULL;
00056       
00057       // Check if any free resources are available.
00058       if (!m_free_Resource_Queue.empty())
00059       {
00060          // Queue is not empty so get a pointer to the
00061          // first resource in the queue
00062          pResource = m_free_Resource_Queue.front();
00063          
00064          // Now remove the pointer from the free resource queue
00065          m_free_Resource_Queue.pop();
00066       }
00067       return pResource;
00068    }
00069    
00074    void Free(Resource *pResource)
00075    {
00076       // Insert the resource at the end of the free queue
00077       m_free_Resource_Queue.push(pResource);
00078    }
00079       
00082    size_t GetFreeResourceCount()
00083    {
00084       return m_free_Resource_Queue.size();
00085    }   
00086 };

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) 
00008 #include <stack>     // STL header file for stack
00009 #include <deque>
00010 using namespace std; // Specify that we are using the std namespace
00011 
00012 class Resource;
00013 
00021 class Hot_Resource_Allocator
00022 {
00028 
00029    typedef stack <Resource *, deque <Resource *> > 
                   Free_Stack_Type;
00030 
00032    Free_Stack_Type m_free_Resource_Stack;
00033       
00034 public:
00035    
00041    Hot_Resource_Allocator(int resource_Count, 
                                  Resource *resource_Array[])
00042    {
00043       for (int i = 0; i < resource_Count; i++)
00044       {
00045          m_free_Resource_Stack.push(resource_Array[i]);
00046       }
00047    }
00048 
00053    Resource * Allocate()
00054    {
00055       Resource *pResource = NULL;
00056       
00057       // Check if any free resources are available.
00058       if (!m_free_Resource_Stack.empty())
00059       {
00060          // Queue is not empty so get a pointer to the
00061          // first resource in the stack
00062          pResource = m_free_Resource_Stack.top();
00063          
00064          // Now remove the pointer from the free resource stack
00065          m_free_Resource_Stack.pop();
00066       }
00067       return pResource;
00068    }
00069    
00074    void Free(Resource *pResource)
00075    {
00076       // Insert the resource at the end of the free stack
00077       m_free_Resource_Stack.push(pResource);
00078    }
00079       
00082    size_t GetFreeResourceCount()
00083    {
00084       return m_free_Resource_Stack.size();
00085    }   
00086 };

 

Explore More ...
Click here to open Message Queue Documentation in a new window Message Queue Documentation
 Click here to open Priority Message Queue Documentation in a new window Priority Message Documentation
 Click here to open Coldest First Resource Allocator Documentation in a new window Coldest First Resource Allocator Documentation
 Click here to open Hottest First Resource Allocator Documentation in a new window Hottest First Resource Allocator Documentation
Click here to download STL Design Patterns II Source Code STL Design Patterns II Source Code
  Home  |  EventStudio System Designer 4.0  |  VisualEther Protocol Analyzer 1.0  |  Real-time Mantra  |  Contact Us
Copyright © 2000-2008 EventHelix.com Inc. All Rights Reserved.