Volume Number: 14 (1998)
Issue Number: 1
Column Tag: Programming Techniques

The Mac OS, STL, & Iterators

by Duane Murphy, Bear River Associates, Inc.

Take advantage of the C++ Standard Library Algorithms with the Mac Toolbox

There are many parts of the Mac OS Toolbox that require you to search for what you need. Search for files with a certain type code. Search for a process with a particular creator code. Search for mounted volumes that are removable. The list of managers in the Mac OS that require searching goes on and on. So, we write search and loop routines to do the work.

Now wait a minute. Aren't there generic routines in the C++ Standard Template Library (STL) that can search and locate items with specific criteria? Those won't work; they only work on iterators and containers in STL, right? In fact, the STL is very flexible and extensible. In this article, you will learn how to take advantage of STL algorithms to search Mac OS Toolbox managers. Specifically, you will learn how to write a forward iterator that satisfies the criteria for STL algorithms in order to take advantage of them.

First, a word from our friendly C++ standards committee. There really isn't a Standard Template Library any more. All of the features and functions of the STL were rolled into the C++ Standard Library proper. However, history once called it the STL, and that name lives on. What we refer to in this article as the Standard Template Library is the generic algorithms, containers, and iterators that make up a large portion of the C++ Standard Library.

There are many articles and excellent books written about the Standard Template Library. We won't go into a great deal of detail here, but we will give enough background about generic algorithms, iterators, and function objects so that everyone should understand what follows. If you're experienced with using the STL for its valuable containers, like vectors, lists, and maps, you might want to skip to the next section.

STL is made up of 5 classifications of objects:

• Generic Algorithms
• Containers
• Iterators
• Function Objects
• Adapters

Generic algorithms operate on containers by using iterators. The generic algorithms can be specialized and extended by using function objects. Adapters can be used with iterators and containers to modify their behavior. We are interested in the algorithms and iterators. Because we need to specialize the algorithms, we will also use function objects.

Containers

Containers store objects. Containers own the objects that are stored in them. Containers also provide the iterators designed to iterate through the objects in the container. Container classes in the STL include vector, list, deque, set, and map. Each container has its particular feature set. These containers are invaluable for data storage in your application, but we won't be talking about them in this article.

Adapters

Adapters are used with iterators and containers. An iterator adapter can make a forward iterator into a reverse iterator, for example. A container adapter can turn a deque into a stack. Adapters are also very useful for your application data storage requirements, but again, we won't be needing them here.

Algorithms

These are the functions that we want to take advantage of. The most often used algorithms are for_each, find, and find_if. Sometimes you might use count or count_if. for_each will execute some function (using a function object) for each element specified by a pair of iterators.

Iterators

Iterators are the objects that connect algorithms to containers. Algorithms are always written in terms of iterators. An iterator is an abstraction of a C++ pointer. In fact, any algorithm can work with a C++ pointer as the iterator.

Function Objects

Finally, a function object, also known as a functor, gives the STL an object that can modify the behavior of an algorithm. For example, the for_each algorithm will apply a function object to an iterator. The find_if and count_if algorithms use a function object as a test, known as a predicate, for searching and counting using an iterator.

As explained above, iterators are the objects that allow algorithms to operate on the contents of a container. Algorithms don't have any direct knowledge of a container. The container is completely isolated inside the iterator. In the STL, iterators are usually provided by the container. Of course, the Mac OS doesn't know anything about the STL; so we have to build the iterators that would be provided by the Mac OS, as if it knew about the STL.

To build the iterators we must think in terms of the STL. In particular, iterators provide access to the elements of a container. We have to find the containers in the Mac OS and then figure out how to represent an iterator over that container. You can think of a container in the OS as anything that has a list or group of things that are the same type. In this article, we will use as examples: processes in the Process Manager, volumes in the file system, and files in a directory. We can think of the Process Manager as a container that has a list of processes running in the system. We can think of the file system as a container that has a list of volumes. We can think of a directory on a volume as a container of files.

There are many other examples of lists of objects in the Mac OS. Each of these can be thought of as a container. If you can access the objects in some order, then you can build an iterator to use with the algorithms in the STL. Thinking in the same terms as the STL will help you to better understand iterators.

Because iterators are the interface between containers and STL algorithms, the focus of this article is on STL iterators. In particular, we would like to take advantage of the algorithms in the STL to iterate over lists or groups of objects in the Mac OS. To do this, we must know the requirements of the iterators of the Standard Template Library.

Iterators in the STL come in five categories:

• Input Iterator
• Output Iterator
• Forward Iterator
• Bi-directional Iterator
• Random Access Iterator

Input and output iterators are used to iterate over streams. Forward iterators can only increment. Bi-directional iterators can increment and decrement, while random access iterators use the index operator to dereference any location. While there is no real inheritance in the iterator categories, you can see that each iterator category has increasing functionality.

The parts of the Mac OS Toolbox that we are interested in are usually candidates for forward iterators. The STL algorithms have a few requirements for the forward iterator.

1. Default Constructor. A default constructor can usually be used to mark the end point of the iteration. We will see examples of this in our iterators. Additional constructors can also be defined.
2. Copy Constructor. Iterators are meant to be lightweight. They are, after all, an abstraction of a pointer. Iterators are almost always passed by value; therefore, a copy constructor is needed.
3. Comparison Operator. STL algorithms operate over a range of a container. A begin and end iterator are provided to the algorithm. The comparison operator of the iterator is used to determine when the range has been completed.
4. Assignment Operator. For the same reason we need a copy constructor, we need an assignment operator. Iterators are lightweight, passed by value, and are easily assigned to one another.
5. Dereference Operator. This is how the algorithm gets access to the container. The algorithm will use the dereference operator of the iterator to get the value of the container identified by the iterator.
6. Pre-increment Operator. This is the fundamental iteration function. The algorithm will iterate over the container by calling the pre-increment and post-increment operators.
7. Post-increment Operator. Algorithms use both the pre-increment and post-increment operators. The iterator must provide both.

The iterator stationery provided with this articles project files (on the MacTech ftp site) gives you a head start in creating your own iterators. Most of the functionality of the iterator is provided. You must provide some basic nuts and bolts to customize it for your use, but most of the boiler plate code is here.

The stationery is divided into three sections: the class definition, the inline functions, and the non-inline functions. The class definition will sometimes be changed; you may want to include additional constructors or additional routines to access information about the iterator. Here is the class definition from the stationery:

class ForwardIterator
   :   public   forward_iterator <Type, ptrdiff_t>
{
   public:
         // Default constructor.
         // Required by STL. 
         // Can be used as a mark for the ending point of iteration.
      ForwardIterator();

      // Insert other constructors here

         // Copy constructor
         // Required by STL.
      ForwardIterator(
         const ForwardIterator &   inOriginal );

         // Comparision operator.
         // Required by STL.
      bool
      operator==(
         const ForwardIterator &   inRHS) const;

         // A negative comparision operator is also
         // required by STL. But utility.h includes a template
         // function that implements != in terms of ==.

         // Assignment operator
         // Required by STL.
      ForwardIterator &
      operator=(
         const ForwardIterator &   inRHS);

         // Dereference operator
         // Required by STL.
      const Type &
      operator*() const;

         // Indirection operator (Optional)
         // If type is a struct or an object then include this
      const Type *
      operator->() const;

         // preincrement operator
         // Required by STL.
      ForwardIterator &
      operator++();

         // postincrement operator
         // Required by STL. Always in terms of preincrement.
      ForwardIterator
      operator++(int);   // The presence of the (int) indicates
                              // postincrement instead of preincrement.
      
   protected:
      Type   fType;
};

Many of the functions provided by the stationery do not have to be changed, while others must have the code filled in. These functions provided by the stationery usually do not need to be changed:

inline const Type &
ForwardIterator::operator*() const
{
   return fType;
}

inline const Type *
ForwardIterator::operator->() const
{
   return &fType;
}

inline ForwardIterator
ForwardIterator::operator++(int)
{
   // The post-increment operator is always implemented
   // in terms of the pre-increment operator.
   ForwardIterator temp = *this;
   ++(*this);
   return temp;
}

The other functions are discussed in rest of the article. These functions often need additional code supplied to complete them.

To use the stationery you must do a search and replace on three strings:

1. Replace "ForwardIterator" with the name of your iterator.
2. Replace "fType" with the name of the basic storage element of the container you are iterating. This is the name of a data member of the iterator.
3. Replace "Type" with the type of the basic storage element of the container that you are iterating. The iterator will represent a pointer to this type.

Preparing to Write an Iterator

Before writing an iterator, there are a few things about the iterator that we'll need to know:

1. How does it iterate?
That is, what container or list is being iterated over and how do we get the next element from the container? This will help us to determine the implementation of the pre-increment operator.

2. What is the type of the iterator?
Identify the type that will be returned by the dereference operator. This is the fundamental type of the iterator; the iterator represents a pointer to this type.

3. How do we compare iterators?
Does the system or container supply some way of identifying equality? Equality in the sense of an iterator can get a little muddy. It is supposed to signify that the two iterators refer to the same element in the same container.

4. How do we recognize the end of the iteration?
This is a special case of comparing iterators. Algorithms operate on two iterators; one representing the beginning and one representing the end of the iteration. Algorithms assume that iterators can go one past the end. The end is identified by another iterator. Our iterator must have a way not only to compare to other iterators, but also to recognize that the end of the container has been reached, and iteration has occurred.

Let's look at an example to see what all this means.

Let's create an iterator that will iterate over the currently running processes. We can think of this as being an iterator for the list of processes maintained by the Process Manager. The Process Manager gives us an easy way to do this using GetNextProcess. In this example, we will create an iterator using GetNextProcess and we will use a function object to locate a specific process with a signature.

Let's answer our iterator questions.

1. How does it iterate?
The Process Manager provides GetNextProcess, which we can use to iterate over the list of processes.

2. What is the type of the iterator?
The Process Manager represents processes using a ProcessSerialNumber. The iterator will represent a pointer to a ProcessSerialNumber.

3. How do we compare iterators?
There is only one container concerned with processes, and that is the list of processes maintained by the Process Manager. Therefore, if the ProcessSerialNumbers are the same, the iterators are the same. ProcessSerialNumbers are compared using the SameProcess function provided by the Process Manager.

4. How do we recognize the end of the iteration?
GetNextProcess will return kNoProcess as the ProcessSerialNumber when the iteration is complete. GetNextProcess also wants the iteration to begin at kNoProcess. Therefore, this is a circular iterator; the beginning and the end are the same.

We start by opening the ForwardIterator.h stationery. Replace "ForwardIterator" with "BR_LProcessIterator," the name of our class. Replace "fType" with "fPSN." fPSN will hold the process serial number of the process we are currently referring to. Finally, replace "Type" with "ProcessSerialNumber," the type of fPSN as well as the type returned by a few of the functions.

Before we review the functions and fill in the code, there are a few constants that are useful:

const ProcessSerialNumber kBR_NoProcess
            = { 0, kNoProcess };
const ProcessSerialNumber kBR_SystemProcess
            = { 0, kSystemProcess };
const ProcessSerialNumber kBR_CurrentProcess
            = { 0, kCurrentProcess };

This iterator is pretty straightforward and is almost a direct interface to the Toolbox. Therefore, we are going to implement this using all inline functions. To complete the iterator we will replace the strings in the ForwardIterator.cp stationery file and copy those functions into BR_LProcessIterator.h.

The first function to look at is the constructor. Instead of a strict default constructor, we will provide a constructor with a default parameter. This way, we can iterate over all of the processes or begin iterating at some known process.

inline
BR_LProcessIterator::BR_LProcessIterator(
   const ProcessSerialNumber &   inPSN )
   :   fPSN( inPSN )
{
}

All we need to do is initialize fPSN.

Next is the comparison operator. We will build the comparison operator in two steps. First, we can map SameProcess into a global comparison operator for ProcessSerialNumbers.

inline bool
operator==(
   const ProcessSerialNumber &   inLHS,
   const ProcessSerialNumber &   inRHS)
{
   Boolean   sameProcess = false;
   
   ::SameProcess( &inLHS, &inRHS, &sameProcess );
   
   return sameProcess;
}

This lets us write the iterator comparison operator

inline bool
BR_LProcessIterator::operator==(
   const BR_LProcessIterator &   inRHS) const
{
   return ( *(*this) == *inRHS );
}

We have to dereference this twice because this is a pointer to an iterator and the iterator is a pointer to a ProcessSerialNumber which means that this is a pointer to a pointer to a ProcessSerialNumber. Dereferencing this twice gives us a ProcessSerialNumber which can then be compared using the global comparison operator.

The dereference operator, indirection operator, and post-increment operator are all provided by the stationery.

The last three functions we need to complete the process iterator come from the ForwardIterator.cp stationery. Open the stationery and make the same replacements as we did in the ForwardIterator.h file: replace "ForwardIterator" with "BR_LProcessIterator," "fType" with "fPSN," and "Type" with "ProcessSerialNumber."

The stationery helps us to fill in the interface to the iterator functions, but we need to fill in the implementation.

The first function is the copy constructor. Just like the default constructor, we initialize fPSN.

inline
BR_LProcessIterator::BR_LProcessIterator(
   const BR_LProcessIterator &   inOriginal )
   :   fPSN ( inOriginal.fPSN )
{
}

The assignment operator is provided by the stationery. The pre-increment operator gets us to the next ProcessSerialNumber. We use the Process Manager function GetNextProcess.

inline
BR_LProcessIterator &
BR_LProcessIterator::operator++()
{
   ::GetNextProcess( &fPSN );
   return *this;
}

These functions are all reasonably small, so we can copy them from the .cp file into the .h file. We only need to place the inline keyword in front of each function definition.

Use This Iterator In a Sentence

How can we use this iterator to locate a specific process? Suppose we want to locate the process serial number of the Finder to send it an AppleEvent. The algorithm we want to use is find_if. The find_if algorithm takes two iterators, and a function object and returns an iterator. This is how we would like to use it:

const BR_LProcessIterator   theEndProcess;
BR_LProcessIterator            theProcess;

theProcess = find_if(
                     ++theProcess,
                     theEndProcess,
                     MyFunctor() );   // What is MyFunctor()???
if ( theEndProcess == theProcess )
{
   // The Finder is not running
}
else
{
   // The Finder is running
   // theProcess is the Finder Process
}

Before we figure out what MyFunctor() is, we should comment on the pre-increment of theProcess in the call to find_if. Recall that this is a circular iterator. The iterator begins by pointing to no process (kBR_NoProcess). If this iterator is incremented, then we will start at the first process. find_if expects that the iterator is pointing to the beginning of the sequence. Therefore, we need to move the pointer to the first process by incrementing it first.

In STL terms, MyFunctor() is a unary predicate. A predicate returns bool true or false. The unary part means that the predicate will receive a single argument. The argument to a function object is always the dereferenced value of the iterator. Function objects do not operate on iterators directly. Function objects operate on whatever the iterator points to.

We could write a function that specifically compares the signature for the ProcessSerialNumber to the signature for the Finder or we could write a more general comparison function and use the function object adapter, bind2nd to locate any specific signature.

The function object adapter bind2nd is used to convert a binary operation into a unary operation. The first argument is passed through from the algorithm being used. The second value that is passed to the binary operator is given to the bind2nd object when it is constructed. Here is the function object that is used with bind2nd:

struct ProcessHasSignature
   : binary_function< ProcessSerialNumber, OSType, bool >
{
   bool
   operator()(
      const ProcessSerialNumber &   inPSN,
      const OSType &                     inSignature ) const
   {
      ProcessInfoRec info;

         // initialize the fields of the process info
      info.processInfoLength   = sizeof( info );
      info.processName            = 0;   // not needed
      info.processAppSpec         = 0;   // not needed

      OSErr err = ::GetProcessInformation( &inPSN, &info );
      bool processHasSignature = false;
      if ( noErr == err )
      {
         processHasSignature =
            ( inSignature == info.processSignature );
      }
      return processHasSignature;
   }
};

Notice that the function object is a struct. All that means is that everything is public. Next, notice that the only item in the struct is a function that implements the function call operator, operator(). The function will get the process information for the ProcessSerialNumber and compare the processSignature field to the process signature inSignature.

Here is how this function object is used with bind2nd

      const OSType                kFinderType = 'MACS';
      const BR_LProcessIterator   theEndProcess;
      BR_LProcessIterator         theProcess;

      theProcess = find_if( 
                           ++theProcess, 
                           theEndProcess,
                           bind2nd( 
                           ProcessHasSignature(), kFinderType ) );
      if ( theEndProcess == theProcess )
      {
         // The Finder is not running
      }
      else
      {
         // The Finder is running
         // theProcess is the Finder Process
      }

bind2nd will pass the process serial number given to it by the find_if algorithm and the constant kFinderType to the operator() function of the ProcessHasSignature object. The ProcessHasSignature() statement may throw you at first. This is not a function call. This is a constructor that takes no parameters.

Listing 1 shows the example program that first uses a process iterator to print a list of the current running processes. Then the Finder process is searched for using find_if and then SimpleText is searched for using find_if.

Listing 1: ProcessIterator.cp

#include <string>
#include <iostream>

#include <TextUtils.h>

#include "BR_LProcessIterator.h"

void
main()
{
   cout << "Currently running files:" << endl;

   {
      BR_LProcessIterator iterator;
      BR_LProcessIterator end;
      while ( ++iterator != end )
      {
         Str32 processName;
         FSSpec processSpec;
         ProcessInfoRec info;
         
               // initialize the fields of the process info
         info.processInfoLength   = sizeof( info );
         info.processName            = processName;
         info.processAppSpec         = &processSpec;

         OSErr err = ::GetProcessInformation( iterator, &info );
         if ( noErr == err )
         {
            char *cstrProcessName = p2cstr( processName );
            cout << cstrProcessName << endl;
         }
         else
         {
            cout << "An error occured/n";
         }
      }
   }

   cout << endl << "Locate the Finder..." << endl;

   {
      const OSType kFinderType = 'MACS';
      const BR_LProcessIterator theEndProcess;
      BR_LProcessIterator theProcess;

      theProcess 
         = find_if( ++theProcess, theEndProcess,
               bind2nd( ProcessHasSignature(), kFinderType ) );
      if ( theEndProcess == theProcess )
      {
         cout << "The Finder is NOT running." << endl;
      }
      else
      {
         cout << "The Finder is running." << endl;
      }
   }
   
   cout << endl << "Locate SimpleText..." << endl;

   {
      const BR_LProcessIterator theEndProcess;
      BR_LProcessIterator theProcess;

      theProcess
         = find_if( ++theProcess, theEndProcess,
               bind2nd( ProcessHasSignature(), sigSimpleText ) );
      if ( theEndProcess == theProcess )
      {
         cout << "SimpleText is NOT running." << endl;
      }
      else
      {
         cout << "SimpleText is running." << endl;
      }
   }
}

Another list that can be iterated in the Mac OS is the list of volumes maintained by the file system. You can think of the list of volumes as a container that can be iterated. You can iterate through the list of volumes, for example, to find removable volumes or simply to provide a list of available volumes.

The first step is to answer our questions about how to implement the iterator.

1. How are we iterating?
Volumes can be iterated by using PBHGetVInfo. The iteration is achieved by making successive calls to PBHGetVInfo while incrementing the ioVolIndex field.

2. What is the iterator type?
We will represent a volume with an HParamBlockRec. Actually, we could use the volumeParam variation of the HParamBlockRec, but HParamBlockRec is close enough. The iterator will be a pointer to an HParamBlockRec.

3. How do we compare iterators?
Every mounted volume has a different volume reference number. Therefore, iterators can be compared by comparing the volume reference number in the ioVRefNum field. Just like the process iterator, there is only one container; the list of volumes stored in the file system.

4. How do you compare to the end?
This is where we have to get creative. We can initialize the iterator by setting ioVRefNum to 0. A 0 value for ioVRefNum is really a logical value representing the system volume, but should not occur during our iteration. If we use the default constructor as the end marker, then we need to similarly represent the end of the iteration. Therefore, in the pre-increment operator, we will set the ioVRefNum field to 0 when there is an error. The error indication will also prevent us from incrementing an iterator that has already been completed. Of course, the code is easier than the explanation.

We begin by creating the volume iterator in the same way we created the process iterator. Open the ForwardIterator.h stationery file. Replace "ForwardIterator" with "BR_LVolumeIterator." This will be the name of our iterator class. Next, replace "fType" with "fPB." This is the field that holds the current iterated value. We don't have a real container so we provide storage for the current item. Finally, replace "Type" with "HParamBlockRec."

Before we get started adding some real code, we are going to add a couple of helpful items to this iterator. First, we are iterating over volumes. Two useful things we need to know about volumes are the volume reference number and the volume name. So we will add two accessors to this iterator.

   // The volume reference number
SInt16
VolumeRefNum() const;

   // The volume name (this is an internal pointer reference
   // it will change on the next iteration).
StringPtr
VolumeName() const;

And, due to the way PBHGetVInfo works, we need to provide a string to store the volume name. So we add

Str32 fVolumeName;

to the protected section of the class.

Now we can begin filling in the blanks. The default constructor initializes the volume name and the parameter block with appropriate values. This iterator is also circular like the process iterator. We indicate the beginning and end of the iteration with the same value. This is indicated in the constructor by setting the ioVRefNum field to 0.

inline
BR_LVolumeIterator::BR_LVolumeIterator()
{
   fVolumeName[0] = 0;

   fPB.volumeParam.ioCompletion      = 0;
   fPB.volumeParam.ioResult         = noErr;
   fPB.volumeParam.ioNamePtr         = fVolumeName;
   fPB.volumeParam.ioVRefNum         = 0;
   fPB.volumeParam.ioVolIndex      = 0;
}

The comparison operator cannot compare parameter blocks, so we will compare ioVRefNum fields. The code for the VolumeRefNum and VolumeName accessors are also inlined in the header file.

inline bool
BR_LVolumeIterator::operator==(
   const BR_LVolumeIterator &   inRHS) const
{
   return ( 
      inRHS.fPB.volumeParam.ioVRefNum 
         == fPB.volumeParam.ioVRefNum );
}

inline SInt16
BR_LVolumeIterator::VolumeRefNum() const
{
   return fPB.volumeParam.ioVRefNum;
}

inline ConstStr255Param
BR_LVolumeIterator::VolumeName() const
{
   return fVolumeName;
}

The BR_LVolumeIterator.cp file rounds out the implementation by including the copy constructor, assignment operator, and the pre-increment operator. The copy constructor copies the parameter block and the volume name fields. Also, the volume name pointer in the parameter block must be reset to the correct volume name.

BR_LVolumeIterator::BR_LVolumeIterator(
   const BR_LVolumeIterator &   inOriginal )
   :   fPB( inOriginal.fPB )
{
   PLstrcpy( fVolumeName, inOriginal.fVolumeName );
   fPB.volumeParam.ioNamePtr = fVolumeName;
}

The assignment operator looks pretty much the same as the copy constructor. First, an in place copy is checked before copying the fields.

BR_LVolumeIterator &
BR_LVolumeIterator::operator=(
   const BR_LVolumeIterator &   inRHS )
{
   if ( this != &inRHS )
   {
      fPB = inRHS.fPB;
      fPB.volumeParam.ioNamePtr = fVolumeName;
      PLstrcpy( fVolumeName, inRHS.fVolumeName );
   }
   return *this;
}

The pre-increment operator is the key to the iterator. First, check if there was an error. We don't want to iterate past the end and an error indicates the end. Increment the ioVolIndex field and call PBGetVInfoSync. If there was an error, reset the ioVRefNum field to 0 so that this iterator will compare equal to a default iterator.

BR_LVolumeIterator &
BR_LVolumeIterator::operator++()
{
   if ( noErr == fPB.volumeParam.ioResult )
   {
      ++fPB.volumeParam.ioVolIndex;
      PBHGetVInfoSync( &fPB );
      if ( noErr != fPB.volumeParam.ioResult )
      {
         fPB.volumeParam.ioVRefNum = 0;
      }
   }
   return *this;
}

That covers it. The example in Listing 2 shows a simple loop walking through the volumes and printing out their names. Similar code could search for a characteristic of a volume. After that, we use a unary function object or predicate that tests if a volume is locked and to print a list of locked volumes. This example uses a combination of a while loop and the find_if algorithm. This is a common technique for locating multiple items in an iteration that satisfy certain criteria.

Listing 2: VolumeIterator.cp

#include <string>
#include <iostream>
#include "BR_LVolumeIterator.h"
void
main()
{
   cout << "Mounted Volumes" << endl;

   {
      BR_LVolumeIterator            iterator;
      const BR_LVolumeIterator   end;
      while ( ++iterator != end )
      {
         string str( (char *)&( iterator.VolumeName()[1] ),
                     iterator.VolumeName()[0] );
         cout << str << endl;
      }
   }
      // A unary function or predicate for testing if a volume is locked.
      // if a volume is locked.
   struct VolumeIsLocked
      : unary_function< HParamBlockRec, bool >
   {
      bool
      operator()(
         const HParamBlockRec & pb ) const
      {
         bool volumeIsLocked = false;
         if ( ( pb.volumeParam.ioVAtrb & 0x0080 ) != 0 )
         {
               // Hardware lock (like a CD)
            volumeIsLocked = true;
         }
         else if ( ( pb.volumeParam.ioVAtrb & 0x8000 ) != 0 )
         {
               // Software lock
            volumeIsLocked = true;
         }
         return volumeIsLocked;
      }
   };
   cout << endl << "The following volumes are locked" << endl;
   {
      BR_LVolumeIterator            iterator;
      const BR_LVolumeIterator   end;
      bool done = false;
      while ( !done )
      {
         iterator 
            = find_if( ++iterator, end, VolumeIsLocked() );
         done = ( iterator == end );
         if ( !done )
         {
            string str(   (char *)&(iterator.VolumeName()[1]),
                        iterator.VolumeName()[0] );
            cout << str << endl;
         }
      }
   }
}

The last example iterator is a file iterator. This iterator will iterate over all of the files in a given folder. We must answer a few questions about the iterator before we get started.

1. How are we iterating?
We can iterate over files in a folder by using PBGetCatInfo.

2. What is the iterator type?
PBGetCatInfo uses a CInfoPBRec to iterate over the files. However, FSSpecs are easier to use in other Toolbox calls. A CIinfoPBRec will be used internally, but an FSSpec will be used externally.

3. How do we compare iterators?
Iterators are equal if their ioVRefNum, ioDirID, and ioFDirIndex fields are the same. That is, if they are referring to the same volume, the same directory, and the same indexed file. The volume and directory represent the container, while the file represents the element in the container.

4. How do we recognize the end?
The ioFDirIndex field is initialized to 0 and incremented through the files. When an error such as iterating past the last file occurs, the ioFDirIndex field is reset to 0. A special case in the comparison operator is to check for the ioFDirIndex fields both being equal to 0.

We begin constructing the iterator the same way. The name of the iterator is BR_LFileIterator. The name of the iteration field is fSpec and its type is FSSpec. Three Replace-All's and we are most of the way there.

First, add a couple of constructors that are pretty useful:

   // Construct from an FSSpec
   // Note the use of explicit. This constructor is not a type converter.
explicit
BR_LFileIterator(
   const FSSpec &   inFolderSpec);
   // Construct from vRefNum and DirID
BR_LFileIterator(
   short   inFolderVRefNum,
   long      inFolderDirID);

The underlying implementation uses a CInfoPBRec and we might want to use it in other places so:

   // Get access to the CInfoPBRec. 
const CInfoPBRec &
GetCInfoPBRec( void ) const;
Finally, add the parameter block:

CInfoPBRec   fPB;

Next, fill in the inline functions in the header file. The default constructor turns out to be a bit too much to be efficient inline, so it should be moved into BR_LFileIterator.cp after we create it from the stationery file. Likewise, the other constructors will also be implemented in BR_LFileIterator.cp.

The only function to fill in here is the comparison operator; the other functions work just fine from the stationery file. The comparison operator looks like:

inline bool
BR_LFileIterator::operator==(
   const BR_LFileIterator &   inRHS) const
{
   // If both indexes are 0 then these are equal. The only time
   // an index is zero is at the beginning or the end of an iteration.
   bool equal = 
         ( inRHS.fPB.hFileInfo.ioFDirIndex      == 0 ) 
       && ( fPB.hFileInfo.ioFDirIndex         == 0 );
   if ( !equal )
   {
      // Otherwise all three of index, directory, and vRefNum 
      // must be equal.
      equal =
         ( inRHS.fPB.hFileInfo.ioFDirIndex 
            ==    fPB.hFileInfo.ioFDirIndex )
      &&   ( inRHS.fPB.hFileInfo.ioDirID
            == fPB.hFileInfo.ioDirID )
      &&   ( inRHS.fPB.hFileInfo.ioVRefNum
            == fPB.hFileInfo.ioVRefNum );
   }
   return ( equal );
}

This is a little complicated, but not overly so. First, check for the index values being 0. The only time the index values are zero is before the beginning or after the end of the iteration. We treat these points the same, so if both indexes are zero, then the iterators are equal.

Otherwise, we compare the index, directory ID, and the volume reference numbers all for equality. If they are all equal then the iterators are also equal.

Next, create BR_LFileIterator.cp. Begin by opening the ForwardIterator.cp stationery file. Make the same replacements here as we did in the header file: "ForwardIterator" is "BR_LForwardIterator," "fType" is "fSpec," and "Type" is "FSSpec."

The first three functions are constructors. They each just set default values for fields or copy the relevant fields from the source. The default constructor initializes the relevant fields to zeros.

BR_LFileIterator::BR_LFileIterator()
{
   fSpec.vRefNum   = 0;
   fSpec.parID      = 0;
   fSpec.name[0]    = 0;

   fPB.hFileInfo.ioCompletion   = 0;
   fPB.hFileInfo.ioResult         = noErr;
   fPB.hFileInfo.ioNamePtr         = fSpec.name;
   fPB.hFileInfo.ioVRefNum         = 0;
   fPB.hFileInfo.ioFDirIndex      = 0;
   fPB.hFileInfo.ioDirID          = 0;   
}

The copy constructor copies the structures wholesale, and then fixes the ioNamePtr field in the parameter block to point to the correct FSSpec.

BR_LFileIterator::BR_LFileIterator(
   const BR_LFileIterator &   inOriginal )
   : fSpec( inOriginal.fSpec ),
      fPB( inOriginal.fPB )
{
   // Fix the ioNamePtr field in the parameter block.
   fPB.hFileInfo.ioNamePtr = fSpec.name;
}

The constructor from a volume reference number and directory ID just use the values to initialize the FSSpec and parameter block fields.

BR_LFileIterator::BR_LFileIterator(
   short   inFolderVRefNum,
   long   inFolderDirID)
{
   fSpec.vRefNum   = inFolderVRefNum;
   fSpec.parID      = inFolderDirID;
   fSpec.name[0]   = 0;

   fPB.hFileInfo.ioCompletion   = 0;
   fPB.hFileInfo.ioResult         = noErr;
   fPB.hFileInfo.ioNamePtr         = fSpec.name;
   fPB.hFileInfo.ioVRefNum         = fSpec.vRefNum;
   fPB.hFileInfo.ioFDirIndex      = 0;
   fPB.hFileInfo.ioDirID          = fSpec.parID;
}

Constructing from an FSSpec is a little more complicated. If the FSSpec is for a folder, then we need its directory ID. If the FSSpec is to a file, then we needs its parent directory ID. First, initialize the parameter block and FSSpec fields. Then call PBGetCatInfoSync. Checking the ioFlAttrib field tells us whether the result is a directory or a file. We can then initialize the parID field of the FSSpec with the correct field value.

BR_LFileIterator::BR_LFileIterator(
   const FSSpec &   inFolderSpec)
{
   // Copy the fsSpec into our FSSpec. 
   fSpec.vRefNum   = inFolderSpec.vRefNum;
   fSpec.parID      = inFolderSpec.parID;
   PLstrcpy( fSpec.name, inFolderSpec.name );
   // Initialize the fields of the parameter block
   fPB.hFileInfo.ioCompletion   = 0;
   fPB.hFileInfo.ioNamePtr         = fSpec.name;
   fPB.hFileInfo.ioVRefNum         = fSpec.vRefNum;
   fPB.hFileInfo.ioFDirIndex      = 0;
   fPB.hFileInfo.ioDirID          = fSpec.parID;
   // Get the info for the FSSpec.
   //
   // If the FSSpec was a folder then the ioDrDirID field is
   // the directory ID of that folder and this will iterate files
   // in that directory.
   //
   // If the FSSpec was to a file, then the ioFlParID field 
   // is the directory ID of the parent directory and this will
   // iterate files in that directory.
   //
   // Maintain the directory id in the parID field of the FSSpec.
   // PBGetCatInfo will over write the value, so it must be restored
   // before each call. See operator++().
   OSErr err = ::PBGetCatInfoSync( &fPB );
   bool isDirectory 
            = ( fPB.hFileInfo.ioFlAttrib & ioDirMask ) != 0;
   fSpec.parID = isDirectory ?
               fPB.dirInfo.ioDrDirID : fPB.hFileInfo.ioFlParID;
}

The assignment operator is straightforward. Instead of copying the structures wholesale, we'll only copy the fields we need. We must remember to set the ioNamePtr field appropriately.

BR_LFileIterator &
BR_LFileIterator::operator=(
   const BR_LFileIterator &   inRHS )
{
   if ( this != &inRHS )
   {
      // Copy the FSSpec
      fSpec.vRefNum   = inRHS.fSpec.vRefNum;
      fSpec.parID      = inRHS.fSpec.parID;
      ::PLstrcpy( fSpec.name, inRHS.fSpec.name );
      // Copy the parameter block. We only care about 6 fields.
      fPB.hFileInfo.ioCompletion = 0;
      fPB.hFileInfo.ioResult
         = inRHS.fPB.hFileInfo.ioResult;
      fPB.hFileInfo.ioNamePtr
         = fSpec.name;
      fPB.hFileInfo.ioVRefNum   
         = inRHS.fPB.hFileInfo.ioVRefNum;
      fPB.hFileInfo.ioFDirIndex   
         = inRHS.fPB.hFileInfo.ioFDirIndex;
      fPB.hFileInfo.ioDirID 
         = inRHS.fPB.hFileInfo.ioDirID;
   }
   return *this;
}

Finally, the real iteration part of the iterator, the pre-increment operator:

BR_LFileIterator &
BR_LFileIterator::operator++()
{
      // Only increment if there is no error.
   if ( noErr == fPB.hFileInfo.ioResult )
   {
      ++fPB.hFileInfo.ioFDirIndex;      // increment the index
      fPB.hFileInfo.ioDirID = fSpec.parID;   // use the correct dir ID
      OSErr err = ::PBGetCatInfoSync( &fPB );
      if ( noErr != err )
      {
            // Reset the index to indicate that we are done.
         fPB.hFileInfo.ioFDirIndex = 0;
      }
   }   
   return *this;
}

First, make sure that there has not been an error. Then we increment the index. We also need to copy the directory ID field. This field is an IO field for PBGetCatInfoSync so we must reset it before each call. Next, call PBGetCatInfoSync. If an error occurs, we reset the index to zero to indicate that we are done.

That completes our file iterator. This iterator can iterate over any folder returning all of the files and folders in that folder. Shown in Listing 3 is an example program that uses a simple while loop to iterate over all of the files in the System Folder.

After that, we use a function object called FSSpecIsType to locate all of the 'INIT' files in the extension folder. This example also uses a combination of a while loop and the find_if algorithm as we did in the volume iterator example. This is a common technique for locating multiple items in an iteration that satisfy certain criteria. If we needed the list of 'INIT' files to be persistent, we could use remove_copy_if and a vector of FSSpecs.

Listing 3: FileIterator.cp

#include <Folders.h>
#include "BR_LFileIterator.h"
void
main()
{
   short   vRefNum   = 0;
   long      dirID      = 0;
   FindFolder(
      kOnSystemDisk, kSystemFolderType, kDontCreateFolder, 
      &vRefNum, &dirID );
   BR_LFileIterator   end;   // just a default marker
   BR_LFileIterator   iterator( vRefNum, dirID );
   cout << "List the files in the system folder\n";
   while ( ++iterator != end )
   {
      string str( 
         (char *)&(iterator->name[1]), iterator->name[0] );
      cout << str << endl;
   }
   cout << "List the INITs in the extension folder\n";
      // Define a binary function that tests 
      // the file type of an FSSpec.
   struct FSSpecIsType
      : binary_function< FSSpec, OSType, bool >
   {
      bool
      operator()(
         const FSSpec &   inSpec,
         const OSType &   inType ) const
      {
         bool isType = false;
         FInfo fInfo;
         OSErr err = FSpGetFInfo( &inSpec, &fInfo );
         if ( noErr == err )
         {
            isType = ( inType == fInfo.fdType );
         }
         return isType;
      }
   };
   FindFolder(
      kOnSystemDisk, kExtensionFolderType, kDontCreateFolder, 
      &vRefNum, &dirID );
   FSSpec extensionFolder;
   FSMakeFSSpec( vRefNum, dirID, 0, &extensionFolder );
   BR_LFileIterator extIterator( extensionFolder );
   bool done = false;
   while ( !done )
   {
      extIterator = find_if( ++extIterator, end,
         bind2nd( FSSpecIsType(), 'INIT' ) );
      done = ( extIterator == end );
      if ( !done )
      {
         string str(
            (char *)&(extIterator->name[1]),
                   extIterator->name[0] );
         cout << str << endl;
      }
   }
}

We hope that you have learned how you can take advantage of the Standard Template Library to easily find information and iterate over items in the Mac OS. There are many other iterators that can be created. Some ideas are to iterate over items in an AppleEvent list, extend the file iterator to iterate over folder hierarchies, or iterate over the items in a resource list such as a string list ('STR#') resource. We are sure you will come across many other examples of iterators in your programming. The stationery files and the techniques described here should help you to construct iterators for your applications.

Duane Murphy, dmurphy@bearriver.com is a Senior Consultant for Bear River Associates, Inc. He has been programming for over 10 years; the last 7 years on the Macintosh. Duane has a special appreciation for C++. When he is not sitting in front of his computer, he can be found playing with his two daughters, unless they're sitting in front of the computer.