Add memelem and memrelem

Signed-off-by: Mattias Andrée <maandree@kth.se>

8 files changed, 361 insertions, 0 deletions

diff --git a/Makefile b/Makefile
index cb3628a..9071f61 100644
--- a/Makefile
+++ b/Makefile
@@ -60,9 +60,11 @@ OBJ =\
 	envreallocn.o\
 	isutf8.o\
 	memdup.o\
+	memelem.o\
 	memends.o\
 	memmem.o\
 	memrchr.o\
+	memrelem.o\
 	memrmem.o\
 	memstarts.o\
 	minimise_number_string.o\
diff --git a/libsimple/mem.h b/libsimple/mem.h
index cf5a866..bd20a49 100644
--- a/libsimple/mem.h
+++ b/libsimple/mem.h
@@ -95,6 +95,44 @@ void *libsimple_memrmem(const void *, size_t, const void *, size_t);
 #endif
 
 
+/**
+ * Finds the first element in an array
+ * 
+ * @param   haystack   The array of bytes to search
+ * @param   nhaystack  The length of `haystack`, divided by `needle`
+ * @param   needle     The substring to search for
+ * @param   nneedle    The length of `needle`
+ * @return             `haystack` with a minimal offset such that,
+ *                     `!memcmp(r, needle, nneedle)` where `r` is the
+ *                     returned pointer and such that `(r - haystack) % nneedle == 0`,
+ *                     `NULL` if no such offset exists
+ */
+_LIBSIMPLE_GCC_ONLY(__attribute__((__pure__, __warn_unused_result__)))
+void *libsimple_memelem(const void *, size_t, const void *, size_t);
+#ifndef memelem
+# define memelem libsimple_memelem
+#endif
+
+
+/**
+ * Finds the last element in an array
+ * 
+ * @param   haystack   The array of bytes to search
+ * @param   nhaystack  The length of `haystack`, divided by `needle`
+ * @param   needle     The substring to search for
+ * @param   nneedle    The length of `needle`
+ * @return             `haystack` with a maximal offset such that,
+ *                     `!memcmp(r, needle, nneedle)` where `r` is the
+ *                     returned pointer and such that `(r - haystack) % nneedle == 0`,
+ *                     `NULL` if no such offset exists
+ */
+_LIBSIMPLE_GCC_ONLY(__attribute__((__pure__, __warn_unused_result__)))
+void *libsimple_memrelem(const void *, size_t, const void *, size_t);
+#ifndef memrelem
+# define memrelem libsimple_memrelem
+#endif
+
+
 _LIBSIMPLE_GCC_ONLY(__attribute__((__pure__, __warn_unused_result__)))
 int libsimple_memstarts(const void *, size_t, const void *, size_t);
 #ifndef memstarts
diff --git a/man/libsimple_memelem.3 b/man/libsimple_memelem.3
new file mode 100644
index 0000000..be182c3
--- /dev/null
+++ b/man/libsimple_memelem.3
@@ -0,0 +1,82 @@
+.TH LIBSIMPLE_MEMELEM 3 2018-10-20 libsimple
+.SH NAME
+libsimple_memelem \- find byte string in memory
+.SH SYNOPSIS
+.nf
+#include <libsimple.h>
+
+void *libsimple_memelem(const void *haystack, size_t nhaystack, const void *needle, size_t nneedle);
+
+#ifndef memelem
+# define memelem libsimple_memelem
+#endif
+.fi
+
+Link with
+.IR \-lsimple .
+.SH DESCRIPTION
+The
+.BR libsimple_memelem ()
+function scans the memory segment
+.IR haystack ,
+with the size
+.IR nhaystack*nneedle ,
+for the first occurence of the byte string
+.I needle
+with the size
+.IR nneedle ,
+and with an offset equivalent to zero modulo
+.IR nneedle .
+.SH RETURN VALUE
+The
+.BR libsimple_memelem ()
+function returns the pointer
+.I s
+with a minimal offset such that
+.IR !memcmp(r,needle,nneedle) ,
+where
+.I r
+is the returned pointer, and such that
+the offset is equivalent to zero modulo
+.IR nneedle .
+If no such offset exists,
+.B NULL
+is returned.
+.SH ERRORS
+The
+.BR libsimple_memelem ()
+function cannot fail.
+.SH ATTRIBUTES
+For an explanation of the terms used in this section, see
+.BR attributes (7).
+.TS
+allbox;
+lb lb lb
+l l l.
+Interface	Attribute	Value
+T{
+.BR libsimple_memelem ()
+T}	Thread safety	MT-Safe
+T{
+.BR libsimple_memelem ()
+T}	Async-signal safety	AS-Safe
+T{
+.BR libsimple_memelem ()
+T}	Async-cancel safety	AC-Safe
+.TE
+.SH EXAMPLES
+None.
+.SH APPLICATION USAGE
+None.
+.SH RATIONALE
+None.
+.SH FUTURE DIRECTIONS
+None.
+.SH NOTES
+None.
+.SH BUGS
+None.
+.SH SEE ALSO
+.BR libsimple_memrelem (3),
+.BR libsimple_memmem (3),
+.BR memchr (3)
diff --git a/man/libsimple_memmem.3 b/man/libsimple_memmem.3
index f084de9..6701b46 100644
--- a/man/libsimple_memmem.3
+++ b/man/libsimple_memmem.3
@@ -74,4 +74,5 @@ None.
 None.
 .SH SEE ALSO
 .BR libsimple_memrmem (3),
+.BR libsimple_memelem (3),
 .BR memchr (3)
diff --git a/man/libsimple_memrelem.3 b/man/libsimple_memrelem.3
new file mode 100644
index 0000000..77f5293
--- /dev/null
+++ b/man/libsimple_memrelem.3
@@ -0,0 +1,82 @@
+.TH LIBSIMPLE_MEMRELEM 3 2018-10-20 libsimple
+.SH NAME
+libsimple_memrelem \- find byte string in memory
+.SH SYNOPSIS
+.nf
+#include <libsimple.h>
+
+void *libsimple_memrelem(const void *haystack, size_t nhaystack, const void *needle, size_t nneedle);
+
+#ifndef memrelem
+# define memrelem libsimple_memrelem
+#endif
+.fi
+
+Link with
+.IR \-lsimple .
+.SH DESCRIPTION
+The
+.BR libsimple_memrelem ()
+function scans the memory segment
+.IR haystack ,
+with the size
+.IR nhaystack*nneedle ,
+for the last occurence of the byte string
+.I needle
+with the size
+.IR nneedle ,
+and with an offset equivalent to zero modulo
+.IR nneedle .
+.SH RETURN VALUE
+The
+.BR libsimple_memrelem ()
+function returns the pointer
+.I s
+with a maximal offset such that
+.IR !memcmp(r,needle,nneedle) ,
+where
+.I r
+is the returned pointer, and such that
+the offset is equivalent to zero modulo
+.IR nneedle .
+If no such offset exists,
+.B NULL
+is returned.
+.SH ERRORS
+The
+.BR libsimple_memrelem ()
+function cannot fail.
+.SH ATTRIBUTES
+For an explanation of the terms used in this section, see
+.BR attributes (7).
+.TS
+allbox;
+lb lb lb
+l l l.
+Interface	Attribute	Value
+T{
+.BR libsimple_memrelem ()
+T}	Thread safety	MT-Safe
+T{
+.BR libsimple_memrelem ()
+T}	Async-signal safety	AS-Safe
+T{
+.BR libsimple_memrelem ()
+T}	Async-cancel safety	AC-Safe
+.TE
+.SH EXAMPLES
+None.
+.SH APPLICATION USAGE
+None.
+.SH RATIONALE
+None.
+.SH FUTURE DIRECTIONS
+None.
+.SH NOTES
+None.
+.SH BUGS
+None.
+.SH SEE ALSO
+.BR libsimple_memelem (3),
+.BR libsimple_memrmem (3),
+.BR libsimple_memrchr (3)
diff --git a/man/libsimple_memrmem.3 b/man/libsimple_memrmem.3
index 71bf251..c9daf17 100644
--- a/man/libsimple_memrmem.3
+++ b/man/libsimple_memrmem.3
@@ -74,4 +74,5 @@ None.
 None.
 .SH SEE ALSO
 .BR libsimple_memmem (3),
+.BR libsimple_memrelem (3),
 .BR libsimple_memrchr (3)
diff --git a/memelem.c b/memelem.c
new file mode 100644
index 0000000..2561456
--- /dev/null
+++ b/memelem.c
@@ -0,0 +1,73 @@
+/* See LICENSE file for copyright and license details. */
+#include "libsimple.h"
+#ifndef TEST
+
+
+void *
+libsimple_memelem(const void *hay_, size_t hayn, const void *sub_, size_t subn)
+{
+	if (!subn)
+		return (void *)hay_;
+
+	switch (subn) {
+	case 1:
+		return memchr(hay_, hayn, *(char *)sub_);
+	case 2:
+		{
+			uint16_t *hay = (void *)hay_;
+			uint16_t sub = *(uint16_t *)sub_;
+			for (; hayn--; hay++)
+				if (*hay == sub)
+					return hay;
+			break;
+		}
+	case 4:
+		{
+			uint32_t *hay = (void *)hay_;
+			uint32_t sub = *(uint32_t *)sub_;
+			for (; hayn--; hay++)
+				if (*hay == sub)
+					return hay;
+			break;
+		}
+	case 8:
+		{
+			uint64_t *hay = (void *)hay_;
+			uint64_t sub = *(uint64_t *)sub_;
+			for (; hayn--; hay++)
+				if (*hay == sub)
+					return hay;
+			break;
+		}
+	default:
+		{
+			char *hay = (void *)hay_;
+			const char *sub = sub_;
+			for (; hayn--; hay += subn)
+				if (!memcmp(hay, sub, subn))
+					return hay;
+			break;
+
+		}
+	}
+
+	return NULL;
+}
+
+
+#else
+#include "test.h"
+
+int
+main(void)
+{
+	assert(!strcmpnul(libsimple_memelem("12345634", 4, "", 0), "12345634"));
+	assert(!strcmpnul(libsimple_memelem("12345634", 4, "34", 2), "345634"));
+	assert(!libsimple_memelem("12345634", 4, "xx", 2));
+	assert(!libsimple_memelem("13456342", 4, "34", 2));
+	assert(!libsimple_memelem("12345634", 0, "34", 2));
+	assert(!strcmpnul(libsimple_memelem("12345634", 0, "34", 0), "12345634"));
+	return 0;
+}
+
+#endif
diff --git a/memrelem.c b/memrelem.c
new file mode 100644
index 0000000..cc11d9e
--- /dev/null
+++ b/memrelem.c
@@ -0,0 +1,82 @@
+/* See LICENSE file for copyright and license details. */
+#include "libsimple.h"
+#ifndef TEST
+
+
+void *
+libsimple_memrelem(const void *hay_, size_t hayn, const void *sub_, size_t subn)
+{
+	if (!subn)
+		return (void *)hay_;
+
+	switch (subn) {
+	case 1:
+		{
+			uint8_t *hay = (void *)hay_;
+			uint8_t sub = *(uint8_t *)sub_;
+			for (hay += hayn; hayn--;)
+				if (*--hay == sub)
+					return hay;
+			break;
+		}
+	case 2:
+		{
+			uint16_t *hay = (void *)hay_;
+			uint16_t sub = *(uint16_t *)sub_;
+			for (hay += hayn; hayn--;)
+				if (*--hay == sub)
+					return hay;
+			break;
+		}
+	case 4:
+		{
+			uint32_t *hay = (void *)hay_;
+			uint32_t sub = *(uint32_t *)sub_;
+			for (hay += hayn; hayn--;)
+				if (*--hay == sub)
+					return hay;
+			break;
+		}
+	case 8:
+		{
+			uint64_t *hay = (void *)hay_;
+			uint64_t sub = *(uint64_t *)sub_;
+			for (hay += hayn; hayn--;)
+				if (*--hay == sub)
+					return hay;
+			break;
+		}
+	default:
+		{
+			char *hay = (void *)hay_;
+			const char *sub = sub_;
+			for (hay += hayn * subn; hayn--;) {
+				hay -= subn;
+				if (!memcmp(hay, sub, subn))
+					return hay;
+			}
+			break;
+
+		}
+	}
+
+	return NULL;
+}
+
+
+#else
+#include "test.h"
+
+int
+main(void)
+{
+	assert(!strcmpnul(libsimple_memrelem("12345634", 4, "", 0), "12345634"));
+	assert(!strcmpnul(libsimple_memrelem("12345634", 4, "34", 2), "34"));
+	assert(!libsimple_memrelem("12345634", 4, "xx", 2));
+	assert(!libsimple_memrelem("13456342", 4, "34", 2));
+	assert(!libsimple_memrelem("12345634", 0, "34", 2));
+	assert(!strcmpnul(libsimple_memrelem("12345634", 0, "34", 0), "12345634"));
+	return 0;
+}
+
+#endif