Cyclic List Traversal

Here is a cyclic list traversal macro, which is alleged to meet the following requirements:

  1. If the pointer is initially NULL, it scans the full list, starting at the beginning.
  2. If the pointer initially references a list element, it scans starting with the next element, and wraps around the end of the list if needed to finally visit the node initially specified.
  3. If the list is empty, the loop acts as an extended no-op.
  4. An additional pointer argument is permitted if needed in order to remember the beginning of the list.
  5. If the list exits normally, the value of the pointer(s) need not be well defined.
  6. The list can be assumed to be constant.

Here is one solution that meets these requirements: 

  1 #define list_next_element(p, h, t, m) \
  2        (p)->next != h \
  3            ? list_entry((p)->next, t, m) \
  4            : list_entry((h)->next, t, m)
  5 #define list_for_each_entry_proceed(t, tt, h, m) \
  6   for ((t) = (t) == NULL \
  7            ? list_next_element((h), (h), typeof(*(t)), m) \
  8            : list_next_element(&(t)->m, (h), typeof(*(t)), m), \
  9        (tt) = NULL; \
 10        (t) != (tt) && (h)->next != (h); \
 11        (tt) = ((tt) == NULL ? (t) : (tt)), \
 12        (t) = list_next_element(&(t)->m, (h), typeof(*t), m))

The list_next_element() helper macro is on lines 1-4. It differs from the Linux kernel's list_next_entry() in that it skips the header. Of course, given an empty list, it will yield a pointer to the mythical element containing the header, and the caller must deal with this possibility.

The list_for_each_entry_proceed() macro is shown on lines 5-12. It is a big “for” statement, with each part described by a paragraph below.

First, the initialization part on lines 6-9. If t is initially NULL, then line 7 points it to the first entry in the list, otherwise line 8 points it to the successor of the entry referenced by the initial value of t. Note that if the list is empty, the new value of t will reference the mythical entry containing the header. In either case, line 9 sets the value of tt to NULL.

The check part on line 10 is straightforward: we stop if we have arrived at the first entry processed or if the list is empty.

The increment part on lines 11 and 12 is more subtle. Line 11 sets tt to t, but only if tt is NULL. This captures the first entry, which is used to check for loop termination. Line 12 uses list_next_element() to advance to the next list entry, excluding the mythical entry enclosing the header. Note that empty lists do not get this far due to the check on Line 10.

Creating a version that is safe for RCU readers is left as an exercise for the reader. ;–)