<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40596 >

Attached patch adds a generic iterator interface for
implementing iteration macros. This framework serves
the following purposes:

1. Hide specific container and iterator implementation
   details from other code modules, in particular
   remove the need for the iteration macros defined in
   header files to have access to container internals.
2. Preserve constness of containers when iterating over
   them, i.e. the container is not modified when using
   an iteration macro.
3. Reduce code duplication in iteration macros, i.e.
   have specific iteration macros only change what needs
   to be changed rather than rewriting the whole loop
   structure each time.
4. Ensure that iteration over a sequence of N values
   has O(N) time complexity.

The interface is used as follows. Suppose we wish to add
iteration macros for the opaque type 'foo'. In foo's
header file we add:

#include "iterator.h"
struct iterator *foo_get_iter(const struct foo *pfoo);
#define foo_thing_iterate(pfoo, pthing)\
  generic_iterate(foo_get_iter(pfoo), struct thing *, pthing)
#define foo_thing_iterate_end generic_iterate_end

Then in foo's code module we define a derived iterator
type, say 'foo_thing_iterator', which provides implementations
for the 4 iterator interface functions next, free, get and
valid. The body of foo_get_iter() creates the derived
iterator (setting up its "vtable", i.e. function pointers)
and returns it as a "base class" iterator pointer.

Now we can iterate over foo's things like:

#include "foo.h"
... /* Make a foo, add some things. */
foo_thing_iterate(pfoo, pthing) {
  ... /* Use pthing */
} foo_thing_iterate_end;

Now while the 4 goals listed above should be satisfied by
this framework, there are some disadvantages to this
particular implementation of the system:
1. Iterators are allocated on the heap and free'd after the
   iteration loop, which is possibly slower than if they
   were just variables allocated on the stack.
2. The "virtual" functions incur at least an extra pointer
   dereference when ever they are used. Since there are
   usually 3 virtual calls per loop iteration, this could
   be a significant running time overhead.
3. The actual generic_iterate macro body is pretty hairy,
   using token concatenation and a for-loop syntax hack
   to allow nesting of itself and to ensure iterators are
   always free'd.

So I'm not sure whether this is really necessary, or whether
it is overkill for the purposes of the code base. Anyway I
will let it sit a bit for your examination and try out some
uses of it in subsequent patches.

 utility/Makefile.am |    1 +
 utility/iterator.h  |   92 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 93 insertions(+), 0 deletions(-)

diff --git a/utility/Makefile.am b/utility/Makefile.am
index 106d87f..5dbbe12 100644
--- a/utility/Makefile.am
+++ b/utility/Makefile.am
@@ -23,6 +23,7 @@ libcivutility_a_SOURCES = \
 		inputfile.h	\
 		ioz.c		\
 		ioz.h		\
+		iterator.h	\
 		log.c		\
 		log.h		\
 		netintf.c	\
diff --git a/utility/iterator.h b/utility/iterator.h
new file mode 100644
index 0000000..c701f4e
--- /dev/null
+++ b/utility/iterator.h
@@ -0,0 +1,92 @@
+ Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   GNU General Public License for more details.
+#ifndef FC__ITERATOR_H
+#define FC__ITERATOR_H
+  Iterator base class. "Derived" iterators must have this struct as
+  their first member (as a "vtable") and provide implementations of
+  the "pure virtual" member functions. See the function comment headers
+  below for the expected behaviour of these functions.
+struct iterator {
+  void (*next)(struct iterator *it);
+  void (*free)(struct iterator *it);
+  void *(*get)(const struct iterator *it);
+  bool (*valid)(const struct iterator *it);
+#define ITERATOR(p) ((struct iterator *)(p))
+  Advances the iterator to point to the next item in the sequence.
+static inline void iterator_next(struct iterator *it) {
+  if (it) {
+    it->next(it);
+  }
+  Frees any data allocated by the iterator.
+static inline void iterator_free(struct iterator *it) {
+  if (it) {
+    it->free(it);
+  }
+  Returns the item currently pointed to by the iterator. Note that the
+  iterator could point to an item whose value is NULL; to actually test
+  whether the iterator is still valid (e.g. has not gone past the
+  end of the sequence), use iterator_valid().
+static inline void *iterator_get(const struct iterator *it) {
+  return it ? it->get(it) : NULL;
+  Returns TRUE if the iterator points to an item in the sequence.
+static inline bool iterator_valid(const struct iterator *it) {
+  return it ? it->valid(it) : FALSE;
+  Iteration macro for iterators derived from the 'iterator' base class.
+  Usually you would define a specific iteration macro for each derived
+  iterator type; 'EXPR_new_iter' is the expression that will be evalua-
+  ted once to create the iterator (usually a call to an iterator_new()-
+  like function). It is safe to nest calls to this macro (as long as
+  you use a different 'NAME_item' for each level).
+  NB: It is assumed that newly created iterators point to the first
+  item in the sequence, or are invalid.
+#define generic_iterate(EXPR_new_iter, TYPE_item, NAME_item)\
+do {\
+  struct iterator *MY_iter##NAME_item = (EXPR_new_iter);\
+  TYPE_item NAME_item;\
+  int MY_i##NAME_item = 1;\
+  for (; MY_i##NAME_item--; iterator_free(MY_iter##NAME_item)) {\
+    for (; iterator_valid(MY_iter##NAME_item);\
+         iterator_next(MY_iter##NAME_item)) {\
+      NAME_item = iterator_get(MY_iter##NAME_item);\
+#define generic_iterate_end\
+    }\
+  }\
+} while (FALSE)
+#endif /* FC__ITERATOR_H */
Freeciv-dev mailing list

Reply via email to