MVM_VECTOR_CONTAINS.patch

From b0cf91cf7bc32fc20f73f4abc463d952c86983a3 Mon Sep 17 00:00:00 2001
From: Bart Wiegmans <[email protected]>
Date: Fri, 17 May 2019 12:45:13 +0200
Subject: [PATCH] [Vector] Implement MVM_VECTOR_CONTAINS with memmem

This should be more flexible (arbitrary sized items) and hopefully
faster because memmem is fairly optimized. And allows the use as an
expression.
---
 build/Makefile.in     |  1 +
 src/core/vector.h     | 18 ++++++------------
 src/platform/memmem.c | 23 +++++++++++++++++++++++
 src/platform/memmem.h | 24 +-----------------------
 src/spesh/pea.c       |  5 ++---
 src/strings/ops.c     |  2 +-
 6 files changed, 34 insertions(+), 39 deletions(-)
 create mode 100644 src/platform/memmem.c

diff --git a/build/Makefile.in b/build/Makefile.in
index e0223083a..6782add8c 100644
--- a/build/Makefile.in
+++ b/build/Makefile.in
@@ -236,6 +236,7 @@ OBJECTS2 = src/6model/reprs/MVMDLLSym@obj@ \
           src/instrument/line_coverage@obj@ \
           src/platform/sys@obj@ \
           src/platform/random@obj@ \
+          src/platform/memmem@obj@ \
           src/platform/memmem32@obj@ \
           src/moar@obj@ \
           @platform@ \
diff --git a/src/core/vector.h b/src/core/vector.h
index d46615b42..8fb19f131 100644
--- a/src/core/vector.h
+++ b/src/core/vector.h
@@ -22,8 +22,9 @@
         x ## _alloc = 0; \
     } while (0)
 
-#define MVM_VECTOR_SIZE(x) \
-    (sizeof(*x) * (x ## _alloc))
+
+#define MVM_VECTOR_ELEM_SIZE(x) (sizeof(*x))
+#define MVM_VECTOR_SIZE(x) (MVM_VECTOR_ELEM_SIZE(x) * (x ## _alloc))
 
 #define MVM_VECTOR_TOP(x) \
     ((x) + (x ## _num))
@@ -62,7 +63,6 @@
 #define MVM_VECTOR_POP(x) \
     (x)[--(x ## _num)]
 
-
 #define MVM_VECTOR_APPEND(x, ar, len) do { \
         size_t _l = (len); \
         MVM_VECTOR_ENSURE_SPACE(x, _l); \
@@ -84,12 +84,6 @@
         a ## _num = b ## _num; \
     } while (0)
 
-#define MVM_VECTOR_CONTAINS(x, elem, result) do { \
-        MVMint32 i; \
-        result = 0; \
-        for (i = 0; i < x ## _num; i++) \
-            if (x[i] == elem) { \
-                result = 1; \
-                break; \
-            } \
-    } while (0)
+#define MVM_VECTOR_SEARCH(h, n) (MVM_memmem(h, MVM_VECTOR_SIZE(h), n, MVM_VECTOR_ELEM_SIZE(h)))
+
+#define MVM_VECTOR_CONTAINS(h, n) (MVM_VECTOR_SEARCH(h, n) != NULL)
diff --git a/src/platform/memmem.c b/src/platform/memmem.c
new file mode 100644
index 000000000..b03e24606
--- /dev/null
+++ b/src/platform/memmem.c
@@ -0,0 +1,23 @@
+/* On Linux we use glibc's memmem which uses the Knuth-Morris-Pratt algorithm.
+ * We use FreeBSD's libc memmem on Windows and MacOS, which uses
+ * Crochemore-Perrin two-way string matching.
+ * Reasoning:
+ * Windows, does not include any native memmem
+ * MacOS has a memmem but is slower and originates from FreeBSD dated to 2005
+ * Solaris doesn't seem to have memmem                                        */
+
+#if defined(_WIN32) || defined(__APPLE__) || defined(__Darwin__) || defined(__sun)
+#include "../3rdparty/freebsd/memmem.c"
+#else
+/* On systems that use glibc, you must define _GNU_SOURCE before including string.h
+ * to get access to memmem. */
+#define _GNU_SOURCE
+#include <string.h>
+#endif
+
+void * MVM_memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen) {
+    return memmem(haystack, haystacklen, needle, needlelen);
+}
+
+/* Extended info:
+ * In glibc, the Knuth-Morris-Pratt algorithm was added as of git tag glibc-2.8-44-g0caca71ac9 */
diff --git a/src/platform/memmem.h b/src/platform/memmem.h
index b03e24606..8c40f6724 100644
--- a/src/platform/memmem.h
+++ b/src/platform/memmem.h
@@ -1,23 +1 @@
-/* On Linux we use glibc's memmem which uses the Knuth-Morris-Pratt algorithm.
- * We use FreeBSD's libc memmem on Windows and MacOS, which uses
- * Crochemore-Perrin two-way string matching.
- * Reasoning:
- * Windows, does not include any native memmem
- * MacOS has a memmem but is slower and originates from FreeBSD dated to 2005
- * Solaris doesn't seem to have memmem                                        */
-
-#if defined(_WIN32) || defined(__APPLE__) || defined(__Darwin__) || defined(__sun)
-#include "../3rdparty/freebsd/memmem.c"
-#else
-/* On systems that use glibc, you must define _GNU_SOURCE before including string.h
- * to get access to memmem. */
-#define _GNU_SOURCE
-#include <string.h>
-#endif
-
-void * MVM_memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen) {
-    return memmem(haystack, haystacklen, needle, needlelen);
-}
-
-/* Extended info:
- * In glibc, the Knuth-Morris-Pratt algorithm was added as of git tag glibc-2.8-44-g0caca71ac9 */
+void * MVM_memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen);
diff --git a/src/spesh/pea.c b/src/spesh/pea.c
index 2e0557eff..b1dc313cb 100644
--- a/src/spesh/pea.c
+++ b/src/spesh/pea.c
@@ -1,4 +1,5 @@
 #include "moar.h"
+#include "platform/memmem.h"
 
 /* Debug logging of EA. */
 #define PEA_LOG 0
@@ -1197,9 +1198,7 @@ static void setup_bb_state(MVMThreadContext *tc, GraphState *gs, MVMSpeshBB *new
                     num_materialized++;
                     for (k = 0; k < MVM_VECTOR_ELEMS(a_state->materializations); k++) {
                         Transformation *t = a_state->materializations[k];
-                        MVMint32 already_seen;
-                        MVM_VECTOR_CONTAINS(distinct_materializations, t, already_seen);
-                        if (!already_seen)
+                        if (!MVM_VECTOR_CONTAINS(distinct_materializations, t))
                             MVM_VECTOR_PUSH(distinct_materializations, t);
                     }
                 }
diff --git a/src/strings/ops.c b/src/strings/ops.c
index 14caf69a4..20c63d3e9 100644
--- a/src/strings/ops.c
+++ b/src/strings/ops.c
@@ -1,6 +1,6 @@
+#include "moar.h"
 #include "platform/memmem.h"
 #include "platform/memmem32.h"
-#include "moar.h"
 #define MVM_DEBUG_STRANDS 0
 #define MVM_string_KMP_max_pattern_length 8192
 /* Max value possible for MVMuint32 MVMStringBody.num_graphs */
-- 
2.20.1