Features

A Simple, Easy AutoQueue Class

R. Scott Guthrie

Scott Guthrie has been programming in C for over ten years. He received a B.S. in Computer Science from California Polytechnic State University, San Luis Obispo in 1976. Scott resides in Colorado Springs, Colorado, and works in Network Systems Engineering for MCI Telecommunications, Consumer Markets Division. Scott can be reached on the Internet as r._scott_guthrie@mcimail.com or by phone at (719) 535-3236.

Introduction

On a recent project, I needed to have separate applications exchange messages. Since several such messages could be simultaneously in transit and received in no particular order, I needed a simple way to keep track of incoming messages for later processing by the application. The most obvious method was to place the outstanding message requests in a queue.

Although queues seem like a great way to simplify data handling, and many candidate implementations appear in articles and books, these implementations always seem to miss the mark exhibiting either a lack or a gross excess of needed capabilities. At the risk of reinventing the wheel (or queue in this case), I've designed my own queue class. I've tried to strike a balance between versatility and practicality by first creating a list of my requirements. This article presents the resulting design.

Design Requirements

My design requirements fall under two general categories. The first category is data handling, the second is encapsulation. As far as data handling is concerned, the queue must be capable of storing the message content, information about where each message originated, and each message's current status. The queue must also be capable of the following:

Encapsulation

I also want to take advantage of data and functionality encapsulation. Since it looks like I am reinventing the queue after all, I want to be able to reuse the implementation so I surely won't have to do this again!

I've considered the standard AddNodeToList and DeleteNodeFromList type interface and thought "what if I put the linking code in the constructor and the delinking code in the destructor?" Just the creation of the instance can add an entry to the list, and the removal can be as simple as deleting an instance. The only interface left to define will deal just with data access methods. My next thought is that if I create a base class to implement the queuing behavior, I can inherit this class and only deal with the data issues in the derived class. A base class like this could surely be reusable.

The AutoQueue Class

Listing 1 and Listing 2 show AUTOQ.HPP and AUTOQ.CPP, the respective declaration and implementation for the AutoQueue class. The AutoQueue class has two constructors, a destructor, and four methods to support queue traversal.

The first constructor creates a stand-alone node not associated with a queue. This type of node could be useful for holding data that is not yet part of a list. If the data later needs to be added to a queue, the node can be moved or copied to the queue.

The second constructor creates a data instance linked to a specified queue. This constructor links new nodes at the top of the queue, but that doesn't mean AutoQueues are limited to a LIFO or FIFO operations. An AutoQueue can be searched (traversed) and nodes can be removed from any position.

The destructor extracts a linked node from the queue. If the node is not associated with a queue, the destructor merely deletes it.

Member function IsLinked determines if a node is linked to a queue, returning an integer one if linked, zero if not. The other three methods are useful for queue traversal. GetFirstNode returns the address of the first (last added) instance in the queue, GetNextNode returns the address of the next, and GetPreviousNode returns the previous node's address. These last two functions return zero when there is no next/previous node.

Each class contains three private data items, accessible only through the methods already described. Since these are Get-type methods, the private members are effectively read-only, which helps maintain the integrity of the queue. The user does not require access or knowledge of these values to maintain or traverse the queue.

Deriving from AutoQueue

As a base class, AutoQueue provides queuing behavior to all derived classes. Classes derived from AutoQueue need only define the data elements of the queue and the methods necessary to access them.

As an example, the AutoQueueMessage class in AQMSG.HPP and AQMSG.CPP (Listing 3 and Listing 4) shows how to add an integer and string value to an AutoQueue instance.

As with AutoQueue, the AutoQueueMessage class has two constructors. The "non-queuing" constructor includes parameters for setting the data values, while the queuing constructor for linked nodes includes these parameters but adds another parameter to pass the address of the list the node is to join.

// Non-Queuing Constructor:
// Initialize Data Values.
AutoQueueMessage(int Number, string& Text);

// Queuing Constructor:
// Specify Destination Queue and
// Initialize Data Values.
AutoQueueMessage(AutoQueueMessage** QHead,
              int Number, string& Text);
The AutoQueueMessage destructor does nothing since de-linking is handled by the AutoQueue base class.

AutoQueueMessage has two specialized copy constructors. One creates stand-alone nodes and the other creates linked nodes. Both constructors accept either stand-alone or linked nodes as source parameters:

// Non Queuing Copy Constructor:
// Copies 'Source' data to a new Stand Alone Node.
AutoQueueMessage(const AutoQueueMessage* Source);

// Queuing Copy Constructor:
// Copies 'Source' data to a new Queued Node.
AutoQueueMessage(AutoQueueMessage** QHead,
              const AutoQueueNessage* Source);
Member function FindByNumber demonstrates how a queue might be searched. This method searches the queue for a match of the private Number_ value, returning the address of the last added instance meeting the match criteria. If no instance in the list passes the test, the method returns a zero.

//Find node that matches TargetValue and return a pointer to it.
AutoQueueMessage* FindByNumber(const int TargetValue);
I've included member function List here for the sake of example. List traverses the list from the beginning (regardless of the instance location from which it was called), and sends the queue data to cout. Including a method such as this may prove useful during development and testing.

void List(); // Output entire queue contents via cout.
I've disabled the default copy constructor and assignment operator for the AutoQueueMessage class, by declaring them as class private and not including a body for their methods. Some rigorous compilers and utility programs such as PC Lint by Gimpel Software will issue a warning about this, which you can safely ignore.

Using AutoQueueMessage

AQTEST. CPP (Listing 5) is a sample test program showing the use of the AutoQueueMessage class. It demonstrates the following:

Please refer to the listings for the specifics. Listing 6 shows the output from AQTEST.

You should take a few precautions when using the AutoQueueMessage (or any AutoQueue-derived) class:

1) Initialize the queue pointers to zero. The AutoQueue constructor expects a queue pointer that either points to an instance or is null. AutoQueue interprets the queue pointer value as the address of the first entry in the node. (Who knows what will be in a non-initialized pointer.)

2) Before executing a method, make sure the queue is not empty. The access methods are members of the instances and are executed as follows:

Queue->Method(); // Execute 'Method()' from an instance.
If Queue contains a null because no instances are linked to it, the call will fail with disastrous results. Always check access to a method, as in:

if(Queue)              // If there is an instance,
    Queue->Method();   // Method() can be invoked.
3) Maintain pointers to all stand-alone instances (created with new) so they can later be deleted. This advice seems obvious but it's easy to forget because pointers to the queued instances do not need to be explicitly maintained by the user. The queue linking provided by the AutoQueue base class keeps the instance pointer within its structure allowing the user to create an instance as follows:

(void) new AutoQueueMessage(&List1, 6, (string)"Hello World!");
In this case the return value is cast to void to eliminate compiler warning messages.

Conclusion

The AutoQueue class not only provides an easily reusable queue management facility, but also helps to demonstrate a level of encapsulation that can be easily and efficiently achieved.

Some of my associates and I have already found a number of applications for the AutoQueue class and I hope you can benefit from it as well.