general purpose iterator pattern

Name

gg_iter, GG_ITER_PREPARE, GG_ITER_FOREACH, GG_ITER_DONE : general purpose iterator pattern

Synopsis

#include <ggi/gg.h>

struct gg_iter;

typedef int  (ggfunc_iter_next)(struct gg_iter *);
typedef void (ggfunc_iter_done)(struct gg_iter *);

struct gg_iter {
      ggfunc_iter_next    *next;
      ggfunc_iter_done    *done;

};

#define ITER_DONE  0
#define ITER_YIELD 1

#define GG_AS_ITER(i) ((struct gg_iter *)i)
#define GG_ITER_PREPARE(i, n, d) do {              \
      GG_AS_ITER(i)->next = (ggfunc_iter_next*)n;  \
      GG_AS_ITER(i)->done = (ggfunc_iter_done*)d;  \
} while(0)
#define GG_ITER_FOREACH(i) while(GG_AS_ITER(i)->next(GG_AS_ITER(i)))
#define GG_ITER_DONE(i) if(GG_AS_ITER(i)->done) GG_AS_ITER(i)->done(GG_AS_ITER(i))

Description

There are situations when a library programmer would like to allow the user to iterate over objects exposed by its API. The problem is that the iteration process itself may be complicated or it may require access to an internal data structure that the programmer does not really want to expose to the user. Furthermore, he might want to avoid adding bloat to the public APIs with yet another abstraction around objects to browse them safely. To handle those cases, this part of LibGG propose a simple, elegant (well, that is just a matter of taste) and general-purpose iterator pattern. It does not add symbols to libgg. It is more a macro-assisted general "way-of-doing-it" than a real API, just like the GG_LIST thing.

The idea is to allow the user to loop very naturally through iterator results as it would do with a regular loop, without having to provide callbacks. People who loves continuation-passing style will hate them, but it makes things way simpler in C.

Writing an iterator

To provide an iterator, the following things are needed:

  1. A structure extending gg_iter. This structure holds both the interator configuration, placeholder for results proposed at each step in the iteration and the internal state of an iterator.
  2. A ggfunc_iter_next function that implements the iterator logic. This function is usually static. From the current state, this function must decide wether the iteration is over or not. In the former case, it simply returns 'ITER_DONE'. In the latter case, it must:

    • adapt the result fields of the iterator with the values to be used as result of this step.
    • adapt the internal state of the iterator
    • return ITER_YIELD to give the result back to the user.
  3. Optionally, a ggfunc_iter_done callback that is responsible for cleaning the iterator internal state when the iteration loops is ended, either by exhaustion or explicitely aborted by the user. This function is necessary when the iteration process involves creating resources internally, like memory allocation. This function is also internal.
  4. One or more initialization function(s) for the iterator. This are part of the public API. This function will initialize the iterator internal state and call 'GG_ITER_PREPARE' to install the correct callbacks.

This example shows how to write a simple counter iterator. It is very trivial but it is a good illustration:

struct range_iter {
      struct gg_iter iter;
      int current;      /* result used by the user */
      int _stop;        /* internal configuration */
      int _step;        /* internal configuration */

};

static int _range_next(struct my_iter * i) {
      i->current += i->_step;
      if(i->current < i->_stop) {
              return ITER_YIELD;
      }
      return ITER_DONE;
}

/* a simple counter 0, 1, 2, ... n-1 */
void init_counter(struct range_iter *i, int n) {
      init_range(i, 0, n);
}

/* a simple sequence { a, a+1, ... b-1 } */
void init_range(struct range_iter *i, int a, int b) {
     init_range_step(i, a, b, 1);
}

/* same, but with a specific increment.
   assume start >= stop and step > 0 */
void init_range_step(struct range_iter *i, int start, int stop, int step) {
      GG_ITER_PREPARE(i, _range_next, NULL);
      i->current = start - step;
      i->_stop   = stop;
      i->_step   = step;
}

For a more complex iterator with recurvise states, see the implementation behind ggConfigIterTarget(3).

Using an iterator

When simple using an iterator, the programmer does not really need to know the interator internals. From his point of view, the library will provide two things:

  1. A specific iterator structure, that extends the gg_iter structure and adds all relevant fields for both iterator configuration and results.
  2. A function to set up such iterators.

A third item would be, hopefully, proper documentation for them.

The following example shows how to use the range iterator defined above:

struct range_iter range;

init_counter(&range, 10);
GG_ITER_FOREACH(&range) {
    printf("%i\n", range.current);
}
GG_ITER_DONE(&range);

It is very important to call GG_ITER_DONE to clean up the iterator when iteration is stopped, even if the loop ends by iterator exhaustion. Iteration can be aborted during the loop process, provided that GG_ITER_DONE is properly called after.

Also, extra care should be taken about who owns the results. This is an iterator-specific question, but usually the yielded values belong to the iterator implementation. That means they must not be changed, and they must be copied to be used after the iteration is over. Of course, they are also invalidated between iteration steps. This issue is very important when itertors yields strings, for example.

See also