Inside Macintosh: Networking With Open Transport / Part 1 - Open Transport Essentials

Chapter 9 - Utilities

Using List Management Functions

The use of most of the utility functions introduced in this chapter and described in "Utilities Reference" is fairly straightforward. As mentioned in the previous section, using these utilities can often result in better performance. However, the group of functions used to manipulate linked lists merits additional comment. This section focuses on the use of these functions by way of a sample program, "ListMania," which is designed to illustrate the use of the Open Transport linked-list routines in a simple producer-consumer environment. The code includes two key routines, ProduceWidgets and ConsumeWidgets.

The ListMania program uses Open Transport LIFO list routines throughout. These routines are atomic with respect to interrupts and threads, and they are faster than the standard Mac OS equivalent functions (Enqueue and Dequeue). All code included in this sample program is running at system task time; however, all the list management in the critical portions of the code is perfectly safe to run at interrupt time. This program also demonstrates another advantage of using Open Transport list management functions: they make it easy for you to keep elements on multiple lists simultaneously. For example, in the ListMania program any given widget is always on the gAllWidgetList (linked through the fAllWidgets field) and on either the gPendingWidgetList or the gFreeWidgetList (linked through the fNext field).

Before looking at the program itself, we'll briefly discuss the data structures used by the program. The objects being produced and consumed are widgets, as defined by the Widget data type:

struct Widget {
   OTLink   fNext;
   OTLink   fAllWidgets;
   UInt32      fSequenceNumber;
   OTTimeStamp fCreationTime;
   OTTimeStamp fLastProducedTime;
};
typedef struct Widget Widget, *WidgetPtr;

The first two fields are link fields: The fNext field is used to link all the elements on either the pending or free widget list; the fAllWidgets field is used to link all the widgets in one long list, regardless of their status. The fSequenceNumber field is a unique monotonically increasing sequence number for each widget that is created. The fCreationTime field specifies the time when a widget is created, and the fLastProducedTime field specifies the time when a widget was last produced. The program also uses three LIFO lists: gAllWidgetList (which contains all widgets), gPendingWidgetList, and gFreeWidgetList.

Listing 9-1 shows the the global variable declarations for the ListMania program.

Listing 9-1 ListMania: global declarations

struct Widget {
   OTLink   fNext;
   OTLink   fAllWidgets;
   UInt32      fSequenceNumber;
   OTTimeStamp fCreationTime;
   OTTimeStamp fLastProducedTime;
};
typedef struct Widget Widget, *WidgetPtr;

static OTLIFO gAllWidgetList;
static OTLIFO gPendingWidgetList;
static OTLIFO gFreeWidgetList;

static UInt32 gLastWidgetSequenceNumber;

The function InitWidgetLists, shown in Listing 9-2 initializes all of the widget lists to empty.

Listing 9-2 The InitWidgetLists function

static void InitWidgetLists(void)
   /* Initializes all of the widget lists to empty.*/
{
   gAllWidgetList.fHead = nil;
   gPendingWidgetList.fHead = nil;
   gFreeWidgetList.fHead = nil;
   gLastWidgetSequenceNumber = 0;
}

The function shown in Listing 9-3creates a widget.

Listing 9-3 The CreateWidget function

static WidgetPtr CreateWidget(void)
{
   WidgetPtr result;
/* Allocate the memory for the widget. */
   result = OTAllocMem(sizeof(Widget));
   OTAssert("CreateWidget: Could not create widget", result != nil);
      
   OTMemzero(result, sizeof(Widget));
   result->fSequenceNumber = OTAtomicAdd32(1, (long *)
                              &gLastWidgetSequenceNumber);
   OTGetTimeStamp(&result->fCreationTime);
   
/* Add the widget to the list of all the widgets in the system.*/
   OTLIFOEnqueue(&gAllWidgetList, (OTLink *) &result->fAllWidgets);
   return (result);
}

The CreateWidget function allocates memory for a widget and then fills out the information fields for the widget structure: fSequenceNumber and fCreationTime. Note the use of the utility function OTAtomicAdd32 to increment the variable gLastWidgetSequenceNumber atomically. This guarantees that the sequence number is unique, even it this routine is re-entered. After creating the widget, the function adds it to the list of all the widgets in the system, gAllWidgetList, using the Open Transport list routine OTLIFOEnqueue , and then it returns a pointer to the newly created widget.

The ProduceWidgets function (shown in Listing 9-4) either calls CreateWidgets if there are no free widgets or obtains a free widget from the free widget list and then adds the widget to the pending widget list.

Listing 9-4 The ProduceWidgets function

static void ProduceWidgets(UInt32 howMany)
{
   UInt32    i;
   OTLink   *freeLink;
   WidgetPtr thisWidget;
   
   for (i = 0; i < howMany; i++) {
      freeLink = OTLIFODequeue(&gFreeWidgetList);
      if ( freeLink != nil ) {
         thisWidget = OTGetLinkObject(freeLink, Widget, fNext);
      } else {
         thisWidget = CreateWidget();
      }
      OTGetTimeStamp(&thisWidget->fLastProducedTime);
      
      OTLIFOEnqueue(&gPendingWidgetList, (OTLink *)
                                 &thisWidget->fNext);
   }
}

The for loop used in the function ProduceWidgets takes a free element from the front of the free widget list using the OTLIFODequeue function . If the function returns nil, there is no free element and a new widget needs to be created by calling the CreateWidget function . If the free widget list does contain a free element, the OTGetLinkObject macro is used to derive the widget from freeLink. After this, the widget is no longer on the free widget list and we can now produce the widget by calling the utility function OTGetTimeStamp to set the fLastProducedTime field. Once the widget is produced, it is added to the list of pending widgets using the OTLIFOEnqueue function.

The function ConsumeWidgets, shown in Listing 9-5 first calls the OTLIFOStealList function to remove all of the widgets on the pending list and then calls the OTReverseList function so that the widgets can be consumed in the same order they were produced. While there are still widgets left on the pending list, the function then calls the PrintWidget function, shown in Listing 9-6, and then adds the most recently consumed widget to the free list by calling the OTLIFOEnque function.

Listing 9-5 The ConsumeWidgets function

static void ConsumeWidgets(void)
{
   OTLink *listToConsume;
   WidgetPtr thisWidget;

/* Remove widgets from pending list; put them in list to consume */
   listToConsume = OTLIFOStealList(&gPendingWidgetList);
   listToConsume = OTReverseList(listToConsume);
   
   while ( listToConsume != nil ) {
/* Given the link element, derive the actual widget object.*/
      thisWidget = OTGetLinkObject(listToConsume, Widget, fNext);
      
/* Consume the widget by printing to stdout */
      PrintWidget(thisWidget);
      printf("\n");
      
/* Get next list element... */
      listToConsume = listToConsume->fNext;
      /* add the most recently consumed widget to free list */
      OTLIFOEnqueue(&gFreeWidgetList, (OTLink *) &thisWidget->fNext);
   }
}

It's important to note the order of the two operations used to consume (print) the widget and to add the most recently consumed widget to the free list. This is because the field thisWidget->fNext occupies the same memory location as the field listToConsume->fNext, so we can't change thisWidget->fNext by enqueuing it until we have extracted the linkage information from it.

Listing 9-6 The PrintWidget function

static void PrintWidget(WidgetPtr thisWidget)
{
   printf("  %03d, Created @ %08x%08x, Produced @ %08x%08x",
      thisWidget->fSequenceNumber,
      thisWidget->fCreationTime.hi, 
      thisWidget->fCreationTime.lo,
      thisWidget->fLastProducedTime.hi,
      thisWidget->fLastProducedTime.lo
      );
}

The DumpAllWidgetLists function, shown in Listing 9-7 dumps all of the widgets on all of the lists. Because the widgets are linked in different ways on the three lists, the DumpAllWidgetLists function must call an additional function, DumpWidgetList, to dump the widgets that are linked using the fNext field--that is, the widgets in the pending and free lists.

Listing 9-7 The DumpAllWidgetLists

static void DumpAllWidgetLists(void)
{
   OTLink   *link;
   WidgetPtr thisWidget;

   printf("gPendingWidgetList\n");
   DumpWidgetList(&gPendingWidgetList);

   printf("gFreeWidgetList\n");
   DumpWidgetList(&gFreeWidgetList);

   printf("gAllWidgetList\n");
   link = gAllWidgetList.fHead;
   while ( link != nil ) {
      thisWidget = OTGetLinkObject(link, Widget, fAllWidgets);
      PrintWidget(thisWidget);
      printf("\n");
      link = link->fNext;
   }
}

The DumpWidgetList function is shown in Listing 9-8.

Listing 9-8 The DumpWidgetList function

static void DumpWidgetList(OTLIFO *list)
   /* Dump a widget list that is linked using the fNext field. */
   /* This is appropriate for the pending and free lists of widgets. */
{
   OTLink *link;
   WidgetPtr thisWidget;
   
   link = list->fHead;
   while ( link != nil ) {
      thisWidget = OTGetLinkObject(link, Widget, fNext);
      PrintWidget(thisWidget);
      printf("\n");
      link = link->fNext;
   }
}