Complex iterators in C

Question

note: this was originally asked on SO.

Part of my current project involves iterating over sequences that don't necessarily exist. For example, I have something similar to a relational database in memory, so say I have three arrays

typedef struct { size_t car_index, size_t part_index } car_part_t;

car_ * cars;
part_t * parts;
car_part * car_parts;

I want to be able to iterate over all the parts in a given car, for example. I specifically want the part and not the car_part. My current solution is

typedef struct {
    size_t car_index;
    size_t part_index;
    size_t m_car_part_index; // keeps progress
} car_part_iterator_t;

and to have two functions

car_part_iterator_t car_part_first(size_t car_index);

which returns an iterator set up such that it.part_index is the index of the part in parts, it.car_index is the car selected by the first parameter, and it.m_car_part_index is a 'private' variable used to track progress in the car_parts list.

I then have a similar function for getting the next one

bool car_part_next(car_part_iterator_t * it);

which moves to the next car part, and returns if the iterator is still valid. Finally for completeness I have

bool car_part_valid(car_part_iterator it);

to check if the current iterator is still valid. So it can be used in a for loop like

for (car_part_iterator_t it = car_part_first(car_index);
    car_part_valid(it); car_part_next(&it))
{
    // use it.part_index ...
}

To me, this sounds like a good solution that I came to after some trial and error. I also experimented with a function that returns an iterator before the first result, so the next` function would return the first result, for use in while loops.

Is this a good pattern? I assume a known one. Does it have a name? Are there pitfalls I'm not seeing?

---

notes:

On SO the generality of this was questioned (ie it can be made more general), but as it stands I'm not too bothered about that.

It was also pointed out that the valid function isn't strictly needed for the loop, but it allows for a more natural for loop, and is also sometimes useful outside of loops.

Answer 1

Is this a good pattern?

Yes, in general.

I can't see how it interacts with your data in detail, but it works well in lots of places, and is probably fine here too.

I assume a known one. Does it have a name?

It's just the iterator pattern. It may be more complex than a linked-list or array iterator, but it's not so obviously different to a tree iterator.

Are there pitfalls I'm not seeing?

Well, your current implementation seems to depend on global state. Generalizing this aspect is probably a good idea.

---

Lastly, when you said the sequence might not exist, I was expecting to see an iterator lazily generating the values. Since that isn't the case here, what do you actually mean?

Answer 2

Yes.. This is good pattern, but you can do something like this:

typedef struct {
   part_t *i, *end;
} car_part_iterator_t;

Then have functions

car_part_iterator_t car_part_iterator_first(size_t car_index);
void car_part_next(car_part_iterator* iter); // because I don't know why you need bool there
bool car_part_valid(car_part_iterator iter);

After that you can use it like this:

for(car_part_iterator_it it = car_part_iterator_first(index);
    car_part_valid(it); car_part_next(&it)) {
   doSomething(*(it.i));
}

And you can actually iterate like this if you want:

for(part_t *it = car_part_iterator_first(index); it != car_part_iterator_end(index); it++) {
   // do something..
}

Then you don't have to create another iterator struct, but still have to create to functions, though you can omit those functions if you want..

Edit: Because this website is not allowing me to comment, I have to embed my reply here. I think the *end in car_part_iterator_t struct is supposed to just check that. We set that *end to point to the part after current car's last part. In C, we can iterate over arrays like this:

int *array = calloc(sizeof(int), 10);
// we want to iterate over the first 5 elements
int *first = array;
int *end   = array + 5; // the element after the 5th element
for(int *it = first; it != end; it++)
    printf("Hello, %d\n", *it);
free(array);