Software developer blog

Postponable iterator

When I started this blog I had no idea how hard it will be to post useful things without revealing too much about the "top secret" projects we are involved in. 🙂 This time though I've been allowed to release an entire class that turned out to be useful in an application we were developing a while back. The piece of software below was created with a financial support by Uratim Ltd. and can be used under the terms of the GPL license. YAY for free software.

Postponable Iterator source

The iterator pattern is one of the most frequently occurring patterns used in software design. Even before one learns about design patterns inevitably implements an iterator without actually realizing. The problem I came across not so long ago was that I had an iterator that was returning  jobs from job packets that would have to be processed but there were a number of constrains I had to keep in mind:

  • For each job there is a resource assigned for the job. It can only be executed using the resource assigned to it.
  • As long as possible certain resources should not be accessed too frequently. (But they can be accessed more frequently when it is necessary.)
  • Packages are processed semi asynchronously: all jobs in one package are returned at once, but there may be more that one pending package. The maximal number of packages under simultaneous processing is a parameter.
  • When there are too many jobs waiting for a single resource than access times should be gradually decreased to avoid too long waiting times for jobs.

The concept was to create a decorator object that takes a standard iterator, and implements all of the resource management related issues. Since I didn't find any similar patterns on the Internet (if you do please let me know) I took the liberty to call it the "Postponable iterator". The interface is described below:

  • The constructor takes a traditional iterator as a parameter, the maximal number of active packages, a default frequency, and initalizes the class with these values.
  • The next function (just as expected) returns an item:
    • If there is an item previously postponed that can now be retried, than return that one
    • If there aren't too many opened packages than return a new item from the iterator
    • If there are too many opened packages, than try to return a job for the resource that would accept a new job next.
    • If non of the above holds, than the iteration can be stoped.
  • The postpone function takes the last item that was returned by the postponable iterator and puts it back into a que identified by a string.
  • All other public functions (except for getStat) in the class provide an interface for setting the que frequency, and checking if processing of a certain package is finished.

Another version could decide about postponing items before ever returning them with the next function, but I wanted to decouple the implementation of that decision from the postponable iterator. It was a bit more complex since different resources had to be accessed under different policies, resulting in a large variety of preferred frequencies even for a single resource.

I also considered a version where frequency handling functions, and the postpone function are protected, and a pure virtual function is called to decide if the item should be postponed before returning it with the next function, but we may want to make our algorithm parallel, and in that case the decision of postponing an item should be made by an object commonly used by the threads, but each would have a separate postponable iterator.

@ //