ao2_iterator Struct Reference

When we need to walk through a container, we use ao2_iterator to keep track of the current position. More...

#include <astobj2.h>

Collaboration diagram for ao2_iterator:

Data Fields
int	bucket
struct ao2_container *	c
unsigned int	c_version
int	flags
void *	obj
unsigned int	version

Detailed Description

When we need to walk through a container, we use ao2_iterator to keep track of the current position.

Because the navigation is typically done without holding the lock on the container across the loop, objects can be inserted or deleted or moved while we work. As a consequence, there is no guarantee that the we manage to touch all the elements on the list, or it is possible that we touch the same object multiple times. However, within the current hash table container, the following is true:

It is not possible to miss an object in the container while iterating unless it gets added after the iteration begins and is added to a bucket that is before the one the current object is in. In this case, even if you locked the container around the entire iteration loop, you still would not see this object, because it would still be waiting on the container lock so that it can be added.
It would be extremely rare to see an object twice. The only way this can happen is if an object got unlinked from the container and added again during the same iteration. Furthermore, when the object gets added back, it has to be in the current or later bucket for it to be seen again.

An iterator must be first initialized with ao2_iterator_init(), then we can use o = ao2_iterator_next() to move from one element to the next. Remember that the object returned by ao2_iterator_next() has its refcount incremented, and the reference must be explicitly released when done with it.

Example:

  struct ao2_container *c = ... // the container we want to iterate on
  struct ao2_iterator i;
  struct my_obj *o;

  i = ao2_iterator_init(c, flags);

  while ( (o = ao2_iterator_next(&i)) ) {
     ... do something on o ...
     ao2_ref(o, -1);
  }

The Astobj2 iterator

Note:: You are not supposed to know the internals of an iterator! We would like the iterator to be opaque, unfortunately its size needs to be known if we want to store it around without too much trouble. Anyways... The iterator has a pointer to the container, and a flags field specifying various things e.g. whether the container should be locked or not while navigating on it. The iterator "points" to the current object, which is identified by three values:

a bucket number;
the object_id, which is also the container version number when the object was inserted. This identifies the object univoquely, however reaching the desired object requires scanning a list.
a pointer, and a container version when we saved the pointer. If the container has not changed its version number, then we can safely follow the pointer to reach the object in constant time.

Details are in the implementation of ao2_iterator_next() A freshly-initialized iterator has bucket=0, version = 0.

Definition at line 999 of file astobj2.h.