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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Jason Short wrote:
> <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.

This patch uses a const parameter.

-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, const 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, const 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, const 
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))