Date: Fri, 26 Oct 2001 09:20:27 +0400 (MSD) From: "Andrew L. Neporada" <andr@dgap.mipt.ru> To: freebsd-hackers@freebsd.org Subject: memmem(3) -- new libc function proposal Message-ID: <20011026090237.V1864-200000@nas.dgap.mipt.ru>
next in thread | raw e-mail | index | archive | help
[-- Attachment #1 --]
memmem(3) is another one substring searching function. Unlike str(n)str
it could be used for binary strings search. memmem is compatible with GNU
libc memmem.
Please comment/review.
Andrew.
[-- Attachment #2 --]
diff -ruN src.orig/include/string.h src/include/string.h
--- src.orig/include/string.h Thu Oct 18 05:35:47 2001
+++ src/include/string.h Fri Oct 26 08:13:44 2001
@@ -81,6 +81,7 @@
int ffs __P((int));
char *index __P((const char *, int));
void *memccpy __P((void *, const void *, int, size_t));
+void *memmem __P((const void *, size_t, const void *, size_t));
char *rindex __P((const char *, int));
int strcasecmp __P((const char *, const char *));
char *strcasestr __P((const char *, const char *));
diff -ruN src.orig/lib/libc/string/Makefile.inc src/lib/libc/string/Makefile.inc
--- src.orig/lib/libc/string/Makefile.inc Wed Oct 10 06:17:35 2001
+++ src/lib/libc/string/Makefile.inc Thu Oct 25 22:29:40 2001
@@ -7,8 +7,8 @@
# machine-independent string sources
MISRCS+=bcmp.c bcopy.c bzero.c ffs.c index.c memccpy.c memchr.c memcmp.c \
- memcpy.c memmove.c memset.c rindex.c strcasecmp.c strcat.c strchr.c \
- strcmp.c strcoll.c strcpy.c strcspn.c strdup.c strerror.c \
+ memcpy.c memmem.c memmove.c memset.c rindex.c strcasecmp.c strcat.c \
+ strchr.c strcmp.c strcoll.c strcpy.c strcspn.c strdup.c strerror.c \
strlcat.c strlcpy.c strlen.c strmode.c strncat.c strncmp.c strncpy.c \
strcasestr.c strnstr.c \
strpbrk.c strrchr.c strsep.c strsignal.c strspn.c strstr.c strtok.c \
@@ -25,10 +25,10 @@
.if ${LIB} == "c"
MAN+= bcmp.3 bcopy.3 bstring.3 bzero.3 ffs.3 index.3 memccpy.3 memchr.3 \
- memcmp.3 memcpy.3 memmove.3 memset.3 rindex.3 strcasecmp.3 strcat.3 \
- strchr.3 strcmp.3 strcoll.3 strcpy.3 strcspn.3 strdup.3 strerror.3 \
- string.3 strlcpy.3 strlen.3 strmode.3 strpbrk.3 strrchr.3 strsep.3 \
- strspn.3 strstr.3 strtok.3 strxfrm.3 swab.3 wmemchr.3
+ memcmp.3 memcpy.3 memem.3 memmove.3 memset.3 rindex.3 strcasecmp.3 \
+ strcat.3 strchr.3 strcmp.3 strcoll.3 strcpy.3 strcspn.3 strdup.3 \
+ strerror.3 string.3 strlcpy.3 strlen.3 strmode.3 strpbrk.3 strrchr.3 \
+ strsep.3 strspn.3 strstr.3 strtok.3 strxfrm.3 swab.3 wmemchr.3
MLINKS+=strcasecmp.3 strncasecmp.3
MLINKS+=strcat.3 strncat.3
diff -ruN src.orig/lib/libc/string/bstring.3 src/lib/libc/string/bstring.3
--- src.orig/lib/libc/string/bstring.3 Mon Oct 1 20:09:00 2001
+++ src/lib/libc/string/bstring.3 Thu Oct 25 22:55:03 2001
@@ -45,6 +45,7 @@
.Nm memchr ,
.Nm memcmp ,
.Nm memcpy ,
+.Nm memmem ,
.Nm memmove ,
.Nm memset
.Nd byte string operations
@@ -67,6 +68,8 @@
.Ft void *
.Fn memcpy "void *dst" "const void *src" "size_t len"
.Ft void *
+.Fn memmem "const void *str" "size_t strlen" "const void *substr" "size_t sublen"
+.Ft void *
.Fn memmove "void *dst" "const void *src" "size_t len"
.Ft void *
.Fn memset "void *b" "int c" "size_t len"
@@ -86,6 +89,7 @@
.Xr memchr 3 ,
.Xr memcmp 3 ,
.Xr memcpy 3 ,
+.Xr memmem 3 ,
.Xr memmove 3 ,
.Xr memset 3
.Sh STANDARDS
diff -ruN src.orig/lib/libc/string/memmem.3 src/lib/libc/string/memmem.3
--- src.orig/lib/libc/string/memmem.3 Thu Jan 1 03:00:00 1970
+++ src/lib/libc/string/memmem.3 Fri Oct 26 07:21:02 2001
@@ -0,0 +1,84 @@
+.\" Copyright (c) 2001 Andrew L. Neporada <andr@dgap.mipt.ru>
+.\" Copyright (c) 1990, 1991, 1993
+.\" The Regents of the University of California. All rights reserved.
+.\"
+.\" This code is derived from software contributed to Berkeley by
+.\" Chris Torek and the American National Standards Committee X3,
+.\" on Information Processing Systems.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\" 3. All advertising materials mentioning features or use of this software
+.\" must display the following acknowledgement:
+.\" This product includes software developed by the University of
+.\" California, Berkeley and its contributors.
+.\" 4. Neither the name of the University nor the names of its contributors
+.\" may be used to endorse or promote products derived from this software
+.\" without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\" $FreeBSD$
+.\"
+.Dd October 26, 2001
+.Dt MEMMEM 3
+.Os
+.Sh NAME
+.Nm memmem
+.Nd locate a binary substring in a binary string
+.Sh LIBRARY
+.Lb libc
+.Sh SYNOPSIS
+.In string.h
+.Ft void *
+.Fn memmem "const void *str" "size_t strlen" "const void *substr" "size_t sublen"
+.Sh DESCRIPTION
+The
+.Fn memmem
+function
+locates the first occurrence of the binary string
+.Fa substr
+in the binary string
+.Fa str .
+Since the
+.Fn memmem
+function is a
+.Fx
+specific API, it should only be used when portability is not a concern.
+.Sh RETURN VALUES
+If
+.Fa sublen
+is zero,
+.Fa str
+is returned;
+if
+.Fa substr
+occurs nowhere in
+.Fa str ,
+NULL is returned;
+otherwise a pointer to the first byte of the first occurrence of
+.Fa substr
+is returned.
+.Sh SEE ALSO
+.Xr memchr 3 ,
+.Xr strcasestr 3 ,
+.Xr strchr 3 ,
+.Xr strnstr 3 ,
+.Xr strstr 3 ,
+.Xr strrchr 3
diff -ruN src.orig/lib/libc/string/memmem.c src/lib/libc/string/memmem.c
--- src.orig/lib/libc/string/memmem.c Thu Jan 1 03:00:00 1970
+++ src/lib/libc/string/memmem.c Fri Oct 26 08:27:56 2001
@@ -0,0 +1,82 @@
+/*-
+ * Copyright (c) 2001 Andrew L. Neporada <andr@dgap.mipt.ru>
+ * Copyright (c) 1990, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/types.h>
+#include <limits.h>
+#include <string.h>
+
+/*
+ * Find the first occurrence of byte string p in byte string s.
+ *
+ * This implementation uses simplified Boyer-Moore algorithm (only
+ * bad-character shift table is used).
+ * See:
+ * Boyer R.S., Moore J.S. 1977, "A fast string searching algorithm",
+ * Communications of ACM. 20:762-772.
+ */
+void *
+memmem(s, slen, p, plen)
+ register const void *s, *p;
+ size_t slen, plen;
+{
+ register const u_char *str, *substr;
+ register size_t i, max_shift, curr_shift;
+
+ size_t shift[UCHAR_MAX + 1];
+
+ if (!plen)
+ return ((void *)s);
+ if (plen > slen)
+ retunr (NULL);
+
+ str = (const u_char *)s;
+ substr = (const u_char *)p;
+
+ for (i = 0; i <= UCHAR_MAX; i++) shift[i] = plen + 1;
+ for (i = 0; i < plen; i++) shift[substr[i]] = plen - i;
+
+ i = 0;
+ max_shift = slen - plen;
+ while (i <= max_shift) {
+ if (*str == *substr && !memcmp(str + 1, substr + 1, plen - 1))
+ return ((void *)str);
+ curr_shift = shift[str[plen]];
+ str += curr_shift;
+ i += curr_shift;
+ }
+ return (NULL);
+}
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20011026090237.V1864-200000>