Callback Enumeration APIs & the Input Iterator Concept (original) (raw)
Matthew uses collaborative context switching when adapting callback enumeration APIs to an STL Iterator Concept.
February 04:
When adapting callback enumeration APIs to an STL Iterator concept, you usually have no choice but to enumerate the entire sequence results into a temporary storage container, then iterate through that container. However a novel approach, which enumerates only those items as are requested by operator ++(), advance(), or similar, is to use collaborative context switching. This approach works by conducting the callback enumeration in one context and the decision making (that is, completion or abandonment of the range iteration) in the context in which the client code is executing.
In this article, I demonstrate this approach using a technique based on the Win32 Fiber API. This technique provides an example container and associated iterator class along with a client code program to show how the technique can be implemented. The source code at http://www.cuj.com/code/ presents an example use of predicates and functionals applied to the adapted sequence, thereby demonstrating the utility of STL compliance.
Enumeration Models
The are many types of enumeration models, including Get-First/Get-Next (for instance, opendir()/readdir()), Get-Nth (RegEnumValue()), and Reset/Get-Next (such as COM's IEnumXXXX), to mention a few. All have trade-offs in terms of convenience, flexibility, and efficiency. An efficient but inflexible model is the callback enumeration model (or callback model).
The callback model is made up of an enumeration function and a callback function type. It is used by passing a function matching the callback function type and (usually) some search information to the enumeration function, which then conducts its internal enumeration (by whatever manner dictated by implementation and/or efficiency requirements) and, for each enumerated item, calls back the given callback function. In many implementations, the callback function is able to indicate (via the return value or by adjusting flag references) that the enumeration should either continue or be cancelled, thereby letting the caller control the extent of the enumeration. Also, it is common for the enumeration function to take an additional user-data parameter that is passed through to each invocation of the callback function, so that the caller may pass some context information (for example, a buffer in which to write information obtained from each individual enumerated element).
Callback enumeration APIs are easy to use and can be efficient. Here's a typical use, which simply prints all the local peer hosts to stdout:
bool CALLCONV ip_list_proc(char const *address, void *user_data) { FILE *stm = reinterpret_cast<FILE*>(user_data); fprintf(stm, "%s\n", address); return true; } int main(...) { enum_peer_hosts(ip_list_proc, IPPEERHOSTF_LOCAL, stdout); }
Adapting to STL Iterators
Since the callback model works by returning results to the caller until told to do otherwise (in contrast with other models where each result is explicitly requested by the caller), it is not a straightforward matter to adapt it to the STL concept of iterators. There are usually two options to handle this. The first option (Listing 1) is to enumerate throughout the full range, storing items in a container that is passed via the user-data parameter. The implementation is simple, but can be inefficient because it requires the full sequence to be enumerated and stored. When the sequence is large, this can be a waste of time and space and the code using the container may only interrogate the first few elements in the sequence. Also, by taking a snapshot of the iteration sequence, it is possible to present an out-of-date set to the caller by the time the full enumeration is completed. On the other hand, this technique can, depending on the container type, support Forward, Bidirectional, and Random-access Iterator concepts (see Generic Programming and the STL: Using and Extending the C++ Standard Template Library, by Matthew Austern, Addison-Wesley, 1998).
The second option is to enumerate only as far as the current iterator position in the sequence, and hold enumeration state in a custom wrapper container class that exposes the container concept semantics. Each time its increment operator is called, the whole callback enumeration operation is restarted and run until 1 past the current position, or until no more elements are available. This solution can also be inefficient when the sequence is large and (in contrast to the first option) most or all of the sequence will be iterated. Furthermore, if the underlying sequence can change between enumeration function calls, then it is possible for the container to behave erroneously and miss the (now deleted) current position value, arriving at end() prematurely (see the sidebar entitled "Input Iterators").
Using Fibers
A novel solution to the problem was presented by John Robbins in his article "A COM Symbol Engine Aids Debugging" (MSDN Magazine, August 2000), which described a technique for adapting a callback enumeration API to a COM enumeration model. This technique is based on collaborative (nonpreemptive) context switching. The approach I present here similarly uses the Win32 Fibers API (see the accompanying sidebar "Win32 Fibers").
The implementation is straightforward; see the child_window_ sequence class in Listing 2. The container's begin() method creates an enumeration context structure (shared between the fibers) that relates the fibers and the current iteration point, then passes it as user data to the CreateFiber() call to create the worker fiber. After this, the implementation of begin() and the iterator's operator ++() are identical. They call SwitchToFiber() to pass control to the worker, and test for the end-of-sequence marker (enumeration HWND is NULL) to delete the enumeration context structure once control returns.
The bulk of the work is carried out in the static WorkerProc() and EnumChildProc() methods of the container. WorkerProc() — the worker fiber procedure — calls the Win32 function EnumChildWindows(), after which it sets the end-of-sequence marker and returns to the main fiber. Inside EnumChildWindows(), the child windows are enumerated and passed back to EnumChildProc(). It is this function that updates the enumeration context structure and switches control to the main fiber (returning either inside the begin() or operator ++() methods), for each enumerated child window.
In this way, the execution switches between the worker and main fibers, resulting in precise input iterator semantics. When EnumChildWindows() completes its iteration, it returns control to the main fiber one last time. The iterator at that point contains the end-of-sequence marker (as does that returned by end()), resulting in correct semantics for the != operator.
In effect, fibers can be used to assist in the unified expression of a variety of enumeration models in the concepts and techniques of the STL.
The Problem with Win32's Fibers
All this sounds great, and it is — up to a point. Unfortunately, there is a drawback. I was implementing a version of this technique for the WinSTL project (http://winstl.org/) and discovered that, unfortunately, there is no way to close all the fibers without closing the thread (that is, there is no CloseThreadFiber() function). In other words, you cannot "de-fiber-ize" the thread. It is possible (at least on Windows 2000) to ignore a previous initialization and call ConvertThreadToFiber() again, but the previously allocated fiber-management block remains allocated. Although the MSDN Knowledgebase article Q185231 implies that you can simply call LocalFree() on this block, this is sailing far too close to the wind for me to recommend.
Neither is it possible to call GetFiberData() to determine whether fiber support has been initialized, as this raises an access violation if it has not (and I don't like the hack of catching that exception as the indicator), rather than returning NULL. Even if it were, the problems of interposing one fiber subsystem on another would be inhibitive.
The hitch is: What if some other part of the process is already using fibers, or starts to use them during/after the initialization of your use of them? The simple (and unappealing) answer is that it crashes. If two fiber subsystems run concurrently (within the scope defined by ConvertThreadToFiber() and the exit from the calling thread), then the second one to be initialized destroys the execution contexts of the first. If they run consecutively, then there is a memory leak (although it is only experience, as opposed to explicit documentation on the subject, that lends this understanding).
In the child_window_sequence implementation, this problem is partially ameliorated by having the main fiber context (obtained from calling ConvertThreadToFiber()) in a static method, which enables multiple instances of this class to be used. However, this is still vulnerable to failure if any other code in the thread makes use of the Fiber API for its own purposes. Indeed, as implemented in the form shown here, the class would fail if instances were used in two or more threads.
Listing 3, an example client program for the class, demonstrates use of the child_window_sequence class in an STL-compliant fashion. It uses a conversion shim to extract the window text from the window handle (see my article "Generalized String Manipulation: Access Shims and Type Tunnelling," CUJ, August 2003). The program works perfectly in translating the callback model to the sequential one, but only because it respects the fragilities described. (It's worth noting that another reason this approach is not widely used is that it based on the Win32 Fibers API, and fibers are not available on Windows 95/98/Me.)
Summary
This article has demonstrated a novel approach to the adaptation of callback enumeration APIs to the STL Input Iterator concept. Although the inadequacies of the Win32 Fiber API prevent production use at this time, there is no in-principal reason why this technique could not be rendered robust and efficient given the availability of suitable cooperative multitasking infrastructure.
Matthew Wilson is a software development consultant for Synesis Software and author of the STLSoft libraries and the upcoming Imperfect C++ (Addison-Wesley, 2004). He can be contacted via [email protected], or at http://stlsoft.org/.