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

> [book - Thu Dec 11 20:59:58 2008]:
> > [book - Thu Dec 11 06:36:54 2008]:
> > 
> > Attached patch adds a generic iterator interface for
> > implementing iteration macros.
> > 
> > [...]
> >
> > Now while the 4 goals listed above should be satisfied by
> > this framework, there are some disadvantages to this
> > particular implementation of the system:
> > 
> > [...]
> I would add to the list of disadvantages that using the
> 'return' statment in a generic_iterate macro prevents the
> iterator from being freed. This is a pretty big deal-
> breaker in my opinion. :(
> I do have an idea on how to fix 3 of the 4 disadvantages
> though, so I will try a second version soon. :)

Alright here is an improved version of the iterator
interface that satisfies the four goals in my first post,
and solves three (ok 2.5 ;)) of the four mentioned

The main change is to use a variation of c++ "placement
new" and dynamically allocated stack space for derived
iterator types. The memory is allocated using a c99
variable length array whose size is determined by a
special 'sizeof' function for each derived iterator. This
memory is then passed to a "constructor"-like function
which initializes it according to the derived type, and
returns a pointer to the iterator base class.

So in terms of the previously given example, the foo.h
header becomes:

#include "iterator.h"
struct foo_iter;
size_t foo_iter_sizeof(void);
struct iterator *foo_iter_init(struct foo_iter *it, const struct foo 

#define foo_thing_iterate(pfoo, pthing)\
generic_iterate(struct foo_iter, struct thing *, pthing, 
foo_iter_sizeof, foo_iter_init, pfoo)
#define foo_thing_iterate_end generic_iterate_end

And in foo.c we would have:

struct foo_iter {
  struct iterator vtable;
  ... /* Implementation specific data. */
size_t foo_iter_sizeof(void) { return sizeof(struct foo_iter); }
struct iterator *foo_iter_init(struct foo_iter *it, const struct foo 
  ... /* Setup vtable and private data. */
  return ITERATOR(it);

The iteration macro use remains the same, but now there
is no use of malloc/free and it is safe to exit the loop
via 'return' (as well as nesting the macro as before).

I say "2.5" above since the body of the generic_iterate
is still rather ugly, making use of a lot of token
concatention (to make local variable names unique) and
the c99 macro vararg syntax (to allow zero or more extra
arguments to the init function).

In fact the macro vararg uses the gcc extension that eats
the leading comma if there are no args given for '...'.
Since this is not strict c99, if this is a problem I can
just make at least one argument mandatory.

Otherwise the standard c99 macro varargs and the variable
length array features are checked for in m4/c99.m4 so I take
it that these are safe to use.

I'll post an updated version of the hash iterators (40597)
making use of this patch so that you can see this interface
in action.

 utility/Makefile.am |    1 +
 utility/iterator.h  |   88 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 89 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..738d019
--- /dev/null
+++ b/utility/iterator.h
@@ -0,0 +1,88 @@
+ 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 *(*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) {
+  it->next(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->get(it);
+  Returns TRUE if the iterator points to an item in the sequence.
+static inline bool iterator_valid(const struct iterator *it) {
+  return it->valid(it);
+  Iteration macro for iterators derived from the 'iterator' base class.
+  Usually you would define a specific iteration macro for each derived
+  iterator type. The meaning of the arguments is as follows:
+  TYPE_it - The type of the derived iterator. E.g. 'struct foo_iter'.
+  TYPE_a - The real type of the items in the list. The variable with name
+           'NAME_a' will be cast to this.
+  NAME_a - The name of the variable that will be assigned the current item
+           in each iteration. It will be declared for you within the scope
+           of the iteration loop.
+  FUNC_size - A function that returns the total size in bytes of a
+              'TYPE_it'.
+  FUNC_init - A "construtor" for 'TYPE_it' objects. It returns a pointer to
+              a 'struct iterator' and takes as its first argument a pointer
+              to memory large enough to hold a 'TYPE_it' (this amount must
+              match the result of FUNC_size()). NB: This function must not
+              return NULL; it must return a valid iterator pointing to the
+              first element in the sequence, or an invalid iterator.
+  ... - Zero or more extra arguments that 'FUNC_init' expects.
+#define generic_iterate(TYPE_it, TYPE_a, NAME_a, FUNC_size, FUNC_init, ...)\
+do {\
+  char MY_mem_##NAME_a[FUNC_size()];\
+  struct iterator *MY_it_##NAME_a;\
+  TYPE_a NAME_a;\
+  MY_it_##NAME_a = FUNC_init((TYPE_it *) MY_mem_##NAME_a , ## __VA_ARGS__);\
+  for (; iterator_valid(MY_it_##NAME_a); iterator_next(MY_it_##NAME_a)) {\
+    NAME_a = (TYPE_a) iterator_get(MY_it_##NAME_a);\
+#define generic_iterate_end\
+  }\
+} while (FALSE)
+#endif /* FC__ITERATOR_H */
Freeciv-dev mailing list

Reply via email to