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

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

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)

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)