memmem.c

Go to the documentation of this file.
00001 /* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007,2008 Free Software
00002    Foundation, Inc.
00003    This file is part of the GNU C Library.
00004 
00005    This program is free software; you can redistribute it and/or modify
00006    it under the terms of the GNU Lesser General Public License as published by
00007    the Free Software Foundation; either version 2.1, or (at your option)
00008    any later version.
00009 
00010    This program is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013    GNU Lesser General Public License for more details.
00014 
00015    You should have received a copy of the GNU Lesser General Public License along
00016    with this program; if not, write to the Free Software Foundation,
00017    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
00018 
00019 /* This particular implementation was written by Eric Blake, 2008.  */
00020 
00021 /* Specification of memmem.  */
00022 #include "gnutls_global.h"
00023 #include <string.h>
00024 
00025 #if !HAVE_MEMMEM
00026 
00027 #ifndef _LIBC
00028 # define __builtin_expect(expr, val)   (expr)
00029 #endif
00030 
00031 #define RETURN_TYPE void *
00032 #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
00033 #include "str-two-way.h"
00034 
00035 /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
00036    if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
00037    HAYSTACK.  */
00038 void *
00039 memmem (const void *haystack_start, size_t haystack_len,
00040         const void *needle_start, size_t needle_len)
00041 {
00042   /* Abstract memory is considered to be an array of 'unsigned char' values,
00043      not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
00044   const unsigned char *haystack = (const unsigned char *) haystack_start;
00045   const unsigned char *needle = (const unsigned char *) needle_start;
00046 
00047   if (needle_len == 0)
00048     /* The first occurrence of the empty string is deemed to occur at
00049        the beginning of the string.  */
00050     return (void *) haystack;
00051 
00052   /* Sanity check, otherwise the loop might search through the whole
00053      memory.  */
00054   if (__builtin_expect (haystack_len < needle_len, 0))
00055     return NULL;
00056 
00057   /* Use optimizations in memchr when possible, to reduce the search
00058      size of haystack using a linear algorithm with a smaller
00059      coefficient.  However, avoid memchr for long needles, since we
00060      can often achieve sublinear performance.  */
00061   if (needle_len < LONG_NEEDLE_THRESHOLD)
00062     {
00063       haystack = memchr (haystack, *needle, haystack_len);
00064       if (!haystack || __builtin_expect (needle_len == 1, 0))
00065         return (void *) haystack;
00066       haystack_len -= haystack - (const unsigned char *) haystack_start;
00067       if (haystack_len < needle_len)
00068         return NULL;
00069       return two_way_short_needle (haystack, haystack_len, needle,
00070                                    needle_len);
00071     }
00072   else
00073     return two_way_long_needle (haystack, haystack_len, needle, needle_len);
00074 }
00075 
00076 #undef LONG_NEEDLE_THRESHOLD
00077 
00078 #endif /* !HAVE_MEMMEM */

Generated on Tue May 19 23:21:08 2009 for GNU libmicrohttpd by  doxygen 1.5.8