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 000..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
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ 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
