gnulib: lib/memmem.c annotate

annotate lib/memmem.c @ 40231:9b3c79fdfe0b

strtod: fix clash with strtold Problem reported for RHEL 5 by Jesse Caldwell (Bug#34817). * lib/strtod.c (compute_minus_zero, minus_zero): Simplify by remving the macro / external variable, and having just a function. User changed. This avoids the need for an external variable that might clash.

author	Paul Eggert <eggert@cs.ucla.edu>
date	Mon, 11 Mar 2019 16:40:29 -0700
parents	b06060465f09
children

rev	line source
40057 b06060465f09 maint: Run 'make update-copyright' Paul Eggert <eggert@cs.ucla.edu> parents: 19484 diff changeset	1 /* Copyright (C) 1991-1994, 1996-1998, 2000, 2004, 2007-2019 Free Software
14079 97fc9a21a8fb maint: update almost all copyright ranges to include 2011 Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	2 Foundation, Inc.
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 This file is part of the GNU C Library.
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
5315 80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	5 This program is free software; you can redistribute it and/or modify
80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	6 it under the terms of the GNU General Public License as published by
80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	7 the Free Software Foundation; either version 2, or (at your option)
80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	8 any later version.
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
5315 80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	10 This program is distributed in the hope that it will be useful,
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
5315 80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	13 GNU General Public License for more details.
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
5315 80d6e1bdc9a2 Sync with glibc. Simon Josefsson <simon@josefsson.org> parents: 5310 diff changeset	15 You should have received a copy of the GNU General Public License along
19190 9759915b2aca all: prefer https: URLs Paul Eggert <eggert@cs.ucla.edu> parents: 18626 diff changeset	16 with this program; if not, see <https://www.gnu.org/licenses/>. */
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
9584 f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	18 /* This particular implementation was written by Eric Blake, 2008. */
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	19
8108 e22e004d89dd * lib/getsubopt.c [!_LIBC]: Include config.h and getsubopt.h. Paul Eggert <eggert@cs.ucla.edu> parents: 5848 diff changeset	20 #ifndef _LIBC
e22e004d89dd * lib/getsubopt.c [!_LIBC]: Include config.h and getsubopt.h. Paul Eggert <eggert@cs.ucla.edu> parents: 5848 diff changeset	21 # include <config.h>
e22e004d89dd * lib/getsubopt.c [!_LIBC]: Include config.h and getsubopt.h. Paul Eggert <eggert@cs.ucla.edu> parents: 5848 diff changeset	22 #endif
e22e004d89dd * lib/getsubopt.c [!_LIBC]: Include config.h and getsubopt.h. Paul Eggert <eggert@cs.ucla.edu> parents: 5848 diff changeset	23
9584 f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	24 /* Specification of memmem. */
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 #include <string.h>
9538 43d9769bf4d0 Fix memmem to avoid O(n^2) worst-case complexity. Eric Blake <ebb9@byu.net> parents: 8108 diff changeset	26
9601 fbf94c8a908a Share two-way algorithm. Eric Blake <ebb9@byu.net> parents: 9584 diff changeset	27 #define RETURN_TYPE void *
fbf94c8a908a Share two-way algorithm. Eric Blake <ebb9@byu.net> parents: 9584 diff changeset	28 #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
fbf94c8a908a Share two-way algorithm. Eric Blake <ebb9@byu.net> parents: 9584 diff changeset	29 #include "str-two-way.h"
9538 43d9769bf4d0 Fix memmem to avoid O(n^2) worst-case complexity. Eric Blake <ebb9@byu.net> parents: 8108 diff changeset	30
43d9769bf4d0 Fix memmem to avoid O(n^2) worst-case complexity. Eric Blake <ebb9@byu.net> parents: 8108 diff changeset	31 /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
43d9769bf4d0 Fix memmem to avoid O(n^2) worst-case complexity. Eric Blake <ebb9@byu.net> parents: 8108 diff changeset	32 if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
43d9769bf4d0 Fix memmem to avoid O(n^2) worst-case complexity. Eric Blake <ebb9@byu.net> parents: 8108 diff changeset	33 HAYSTACK. */
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 void *
9544 ae875e538d30 Use GNU style coding conventions. Bruno Haible <bruno@clisp.org> parents: 9543 diff changeset	35 memmem (const void *haystack_start, size_t haystack_len,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9601 diff changeset	36 const void *needle_start, size_t needle_len)
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 {
9566 dda8ef1c4bfd Treat untyped memory as an 'unsigned char' array. Bruno Haible <bruno@clisp.org> parents: 9558 diff changeset	38 /* Abstract memory is considered to be an array of 'unsigned char' values,
dda8ef1c4bfd Treat untyped memory as an 'unsigned char' array. Bruno Haible <bruno@clisp.org> parents: 9558 diff changeset	39 not an array of 'char' values. See ISO C 99 section 6.2.6.1. */
dda8ef1c4bfd Treat untyped memory as an 'unsigned char' array. Bruno Haible <bruno@clisp.org> parents: 9558 diff changeset	40 const unsigned char haystack = (const unsigned char ) haystack_start;
dda8ef1c4bfd Treat untyped memory as an 'unsigned char' array. Bruno Haible <bruno@clisp.org> parents: 9558 diff changeset	41 const unsigned char needle = (const unsigned char ) needle_start;
5310 26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	42
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 if (needle_len == 0)
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 /* The first occurrence of the empty string is deemed to occur at
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 the beginning of the string. */
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 return (void *) haystack;
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	47
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 /* Sanity check, otherwise the loop might search through the whole
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 memory. */
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 if (__builtin_expect (haystack_len < needle_len, 0))
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 return NULL;
26382eb5dbd2 New module 'memmem', from Simon Josefsson. Bruno Haible <bruno@clisp.org> parents: diff changeset	52
9584 f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	53 /* Use optimizations in memchr when possible, to reduce the search
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	54 size of haystack using a linear algorithm with a smaller
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	55 coefficient. However, avoid memchr for long needles, since we
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	56 can often achieve sublinear performance. */
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	57 if (needle_len < LONG_NEEDLE_THRESHOLD)
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	58 {
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	59 haystack = memchr (haystack, *needle, haystack_len);
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	60 if (!haystack \|\| __builtin_expect (needle_len == 1, 0))
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9601 diff changeset	61 return (void *) haystack;
9584 f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	62 haystack_len -= haystack - (const unsigned char *) haystack_start;
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	63 if (haystack_len < needle_len)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9601 diff changeset	64 return NULL;
9584 f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	65 return two_way_short_needle (haystack, haystack_len, needle, needle_len);
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	66 }
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	67 else
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	68 return two_way_long_needle (haystack, haystack_len, needle, needle_len);
f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	69 }
9538 43d9769bf4d0 Fix memmem to avoid O(n^2) worst-case complexity. Eric Blake <ebb9@byu.net> parents: 8108 diff changeset	70
9584 f490fd6e4955 Rewrite memmem to guarantee linear complexity without malloc. Eric Blake <ebb9@byu.net> parents: 9566 diff changeset	71 #undef LONG_NEEDLE_THRESHOLD

Mercurial > gnulib

annotate lib/memmem.c @ 40231:9b3c79fdfe0b