[Freeciv-Dev] (PR#14362) new genlist/speclist function to search

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

This patch adds a new function genlist_search.  It's an inefficient O(n) 
operation (as all list ops are) that returns a bool indicating whether 
the given element is in the list.

Without changing other files it is impossible to use bool in genlist.h. 
  genlist.h cannot include shared.h (for bool) because shared.h includes 
speclist.h which includes genlist.h.  My solution is to move the bool 
and attribute stuff from shared.h into support.h, making that a 
lower-level file and reversing the dependency there.

-jason

Index: utility/genlist.c
===================================================================
--- utility/genlist.c   (revision 11149)
+++ utility/genlist.c   (working copy)
@@ -227,7 +227,24 @@
   return plink;
 }
 
+/************************************************************************
+  Return TRUE iff this element is in the list.
 
+  This is an O(n) operation.  Hence, "search".
+************************************************************************/
+bool genlist_search(struct genlist *pgenlist, void *data)
+{
+  struct genlist_link *plink;
+
+  for (plink = pgenlist->head_link; plink; plink = plink->next) {
+    if (plink->dataptr == data) {
+      return TRUE;
+    }
+  }
+
+  return FALSE;
+}
+
 /************************************************************************
  Sort the elements of a genlist.
  
Index: utility/genlist.h
===================================================================
--- utility/genlist.h   (revision 11149)
+++ utility/genlist.h   (working copy)
@@ -49,6 +49,8 @@
   See also the speclist module.
 ***********************************************************************/
 
+#include "support.h" /* bool */
+
 /* A single element of a genlist, storing the pointer to user
    data, and pointers to the next and previous elements:
 */
@@ -77,6 +79,8 @@
 void genlist_prepend(struct genlist *pgenlist, void *data);
 void genlist_unlink(struct genlist *pgenlist, void *punlink);
 
+bool genlist_search(struct genlist *pgenlist, void *data);
+
 void genlist_sort(struct genlist *pgenlist,
                  int (*compar)(const void *, const void *));
 
Index: utility/support.h
===================================================================
--- utility/support.h   (revision 11149)
+++ utility/support.h   (working copy)
@@ -27,8 +27,49 @@
 #include <sys/types.h>
 #endif
 
-#include "shared.h"            /* bool type and fc__attribute */
+#ifdef TRUE
+#undef TRUE
+#endif
 
+#ifdef FALSE
+#undef FALSE
+#endif
+
+#define TRUE true
+#define FALSE false
+
+#if __BEOS__
+#include <posix/be_prim.h>
+#define __bool_true_false_are_defined 1
+#else
+#ifdef HAVE_STDBOOL_H
+#include <stdbool.h>
+#else /* Implement <stdbool.h> ourselves */
+#undef bool
+#undef true
+#undef false
+#undef __bool_true_false_are_defined
+#define bool fc_bool
+#define true  1
+#define false 0
+#define __bool_true_false_are_defined 1
+typedef unsigned int fc_bool;
+#endif /* ! HAVE_STDBOOL_H */
+#endif /* ! __BEOS__ */
+
+/* Want to use GCC's __attribute__ keyword to check variadic
+ * parameters to printf-like functions, without upsetting other
+ * compilers: put any required defines magic here.
+ * If other compilers have something equivalent, could also
+ * work that out here.   Should this use configure stuff somehow?
+ * --dwp
+ */
+#if defined(__GNUC__)
+#define fc__attribute(x)  __attribute__(x)
+#else
+#define fc__attribute(x)
+#endif
+
 int mystrcasecmp(const char *str0, const char *str1);
 int mystrncasecmp(const char *str0, const char *str1, size_t n);
 
Index: utility/speclist.h
===================================================================
--- utility/speclist.h  (revision 11149)
+++ utility/speclist.h  (working copy)
@@ -37,6 +37,7 @@
       void foo_list_append(struct foo_list *This, foo_t *pfoo);
       void foo_list_unlink(struct foo_list *This, foo_t *pfoo);
       void foo_list_unlink_all(struct foo_list *This);
+      bool foo_list_search(struct foo_list *this, foo_t *pfoo);
       void foo_list_sort(struct foo_list *This, 
          int (*compar)(const void *, const void *));
 
@@ -121,6 +122,11 @@
   free(tthis);
 }
 
+static inline bool SPECLIST_FOO(_list_search) (SPECLIST_LIST *tthis, 
SPECLIST_TYPE *pfoo)
+{
+  return genlist_search(tthis->list, pfoo);
+}
+
 static inline void SPECLIST_FOO(_list_sort) (SPECLIST_LIST * tthis, int 
(*compar) (const void *, const void *))
 {
   genlist_sort(tthis->list, compar);
Index: utility/shared.h
===================================================================
--- utility/shared.h    (revision 11149)
+++ utility/shared.h    (working copy)
@@ -17,44 +17,14 @@
 #include <string.h>            /* memset */
 #include <time.h>              /* time_t */
 
+#include "support.h" /* bool, fc__attribute */
+
 #ifdef HAVE_CONFIG_H
 #ifndef FC_CONFIG_H            /* this should be defined in config.h */
 #error Files including fcintl.h should also include config.h directly
 #endif
 #endif
 
-#if __BEOS__
-#include <posix/be_prim.h>
-#define __bool_true_false_are_defined 1
-#else
-#ifdef HAVE_STDBOOL_H
-#include <stdbool.h>
-#else /* Implement <stdbool.h> ourselves */
-#undef bool
-#undef true
-#undef false
-#undef __bool_true_false_are_defined
-#define bool fc_bool
-#define true  1
-#define false 0
-#define __bool_true_false_are_defined 1
-typedef unsigned int fc_bool;
-#endif /* ! HAVE_STDBOOL_H */
-#endif /* ! __BEOS__ */
-
-/* Want to use GCC's __attribute__ keyword to check variadic
- * parameters to printf-like functions, without upsetting other
- * compilers: put any required defines magic here.
- * If other compilers have something equivalent, could also
- * work that out here.   Should this use configure stuff somehow?
- * --dwp
- */
-#if defined(__GNUC__)
-#define fc__attribute(x)  __attribute__(x)
-#else
-#define fc__attribute(x)
-#endif
-
 #define MAX_LEN_ADDR     256   /* see also MAXHOSTNAMELEN and RFC 1123 2.1 */
 #define MAX_LEN_PATH 4095
 
@@ -62,17 +32,6 @@
    another unreachable condition. */
 #define FC_INFINITY            (1000 * 1000 * 1000)
 
-#ifdef TRUE
-#undef TRUE
-#endif
-
-#ifdef FALSE
-#undef FALSE
-#endif
-
-#define TRUE true
-#define FALSE false
-
 #ifndef MAX
 #define MAX(x,y) (((x)>(y))?(x):(y))
 #define MIN(x,y) (((x)<(y))?(x):(y))