Back to the WFC main page


$Revision: 23 $


This class a simple, thread-safe but high-performance queue. It allows one thread to add to the queue while another thread can get from the queue without blocking. Normally, getting something from a queue blocks anyone from adding to that queue. This is a performance bottleneck. CQueue was designed for speed.

CQueue automatically grows the queue when needed. It is a first-in, first-out queue. In other words, the order in which things were added to the queue is the order in which they will be retrieved from the queue.


CQueue( DWORD initial_queue_size = 1024 )
Constructs the object. You can specify an initial size for the queue. The larger the queue the fewer the growth periods (which can be expensive).


BOOL Add( DWORD new_item )
BOOL Add( void * item )
This is how you add something to the queue. The queue will automatically grow to accomodate new items.
void Dump( CDumpContext& dump_context ) const
Present only in debug builds. Dumps interesting information about CQueue to the dump_context provided.
void Empty( void )
Empties the queue. There will be no entries in the queue when you call this method.
BOOL Get( DWORD& item )
BOOL Get( void * & item )
This is how you get something from the queue. It will return TRUE if a value was successfully retrieved from the queue. It will return FALSE when there is nothing in the queue to pull.
DWORD GetLength( void ) const
Returns the number of items in the queue. Warning! This method will prevent anything from being added or gotten from the queue. It must prevent queue operations for the time it takes to compute the number of elements in the queue. In other words, calling this method is a performance hit.
DWORD GetMaximumLength( void ) const
Returns the maximum size of the current queue. This is not the maximum number of things the queue can hold. It is the maximum number of items the queue can hold before it enters a growth period. Currently, when the queue fills, its size doubles.


It is boring to use CQueue on a single-CPU machine. The chances of entering a deadlock are pretty much nil. However, CQueue really shines on multiple-CPU boxes. To test this, I created a simple toy program that creates two threads. One constantly adds to the test queue while the other thread constantly gets from the test queue. Using a single locking mechanism on a two-CPU machine, I was able to get this performance from the queue code in a 30 second test:
Number of Adds1,517,100 (50,570 operations per second)
Number of Gets1,200,136 (40,004 operations per second)
Number of Items Left In Queue 316,974
Queue Grew To Maximum Size524,288
Average CPU Usage58%
Using the double-locking technique, I got these numbers:
Number of Adds11,675,987 (389,199 operations per second)
Number of Gets11,675,537 (389,184 operations per second)
Number of Items Left In Queue 462
Maximum Size1024
Average CPU Usage100%
As you can see, the double-locking mechanism is the best. CQueue


void test_CQueue( void )
   WFCTRACEINIT( TEXT( "test_CQueue()" ) );

   CQueue queue( 4 );

   queue.Add( 1 );
   queue.Add( 2 );
   queue.Add( 3 );

   WFCTRACE( TEXT( "Next addition should cause growth" ) );

   queue.Add( 4 );
   queue.Add( 5 );

   DWORD item = 0;

   while( queue.Get( item ) != FALSE )
      WFCTRACEVAL( TEXT( "Got ", item ) );

   queue.Add( 6 );
   queue.Add( 7 );
   queue.Add( 8 );

   queue.Get( item );

   queue.Add( 9 );
   queue.Add( 10 );

   while( queue.Get( item ) != FALSE )
      WFCTRACEVAL( TEXT( "Got ", item ) );

Copyright, 2000, Samuel R. Blackburn
$Workfile: CQueue.cpp $
$Modtime: 1/17/00 9:10a $