Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /* Byte-wise substring search, using the Two-Way algorithm.
  2.  * Copyright (C) 2008 Eric Blake
  3.  * Permission to use, copy, modify, and distribute this software
  4.  * is freely granted, provided that this notice is preserved.
  5.  */
  6.  
  7. /*
  8. FUNCTION
  9.         <<memmem>>---find memory segment
  10.  
  11. INDEX
  12.         memmem
  13.  
  14. ANSI_SYNOPSIS
  15.         #include <string.h>
  16.         char *memmem(const void *<[s1]>, size_t <[l1]>, const void *<[s2]>,
  17.                      size_t <[l2]>);
  18.  
  19. DESCRIPTION
  20.  
  21.         Locates the first occurrence in the memory region pointed to
  22.         by <[s1]> with length <[l1]> of the sequence of bytes pointed
  23.         to by <[s2]> of length <[l2]>.  If you already know the
  24.         lengths of your haystack and needle, <<memmem>> can be much
  25.         faster than <<strstr>>.
  26.  
  27. RETURNS
  28.         Returns a pointer to the located segment, or a null pointer if
  29.         <[s2]> is not found. If <[l2]> is 0, <[s1]> is returned.
  30.  
  31. PORTABILITY
  32. <<memmem>> is a newlib extension.
  33.  
  34. <<memmem>> requires no supporting OS subroutines.
  35.  
  36. QUICKREF
  37.         memmem pure
  38. */
  39.  
  40. #include <string.h>
  41.  
  42. #if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
  43. # define RETURN_TYPE void *
  44. # define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
  45. # include "str-two-way.h"
  46. #endif
  47.  
  48. void *
  49. _DEFUN (memmem, (haystack_start, haystack_len, needle_start, needle_len),
  50.         const void *haystack_start _AND
  51.         size_t haystack_len _AND
  52.         const void *needle_start _AND
  53.         size_t needle_len)
  54. {
  55.   /* Abstract memory is considered to be an array of 'unsigned char' values,
  56.      not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
  57.   const unsigned char *haystack = (const unsigned char *) haystack_start;
  58.   const unsigned char *needle = (const unsigned char *) needle_start;
  59.  
  60.   if (needle_len == 0)
  61.     /* The first occurrence of the empty string is deemed to occur at
  62.        the beginning of the string.  */
  63.     return (void *) haystack;
  64.  
  65. #if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
  66.  
  67.   /* Less code size, but quadratic performance in the worst case.  */
  68.   while (needle_len <= haystack_len)
  69.     {
  70.       if (!memcmp (haystack, needle, needle_len))
  71.         return (void *) haystack;
  72.       haystack++;
  73.       haystack_len--;
  74.     }
  75.   return NULL;
  76.  
  77. #else /* compilation for speed */
  78.  
  79.   /* Larger code size, but guaranteed linear performance.  */
  80.  
  81.   /* Sanity check, otherwise the loop might search through the whole
  82.      memory.  */
  83.   if (haystack_len < needle_len)
  84.     return NULL;
  85.  
  86.   /* Use optimizations in memchr when possible, to reduce the search
  87.      size of haystack using a linear algorithm with a smaller
  88.      coefficient.  However, avoid memchr for long needles, since we
  89.      can often achieve sublinear performance.  */
  90.   if (needle_len < LONG_NEEDLE_THRESHOLD)
  91.     {
  92.       haystack = memchr (haystack, *needle, haystack_len);
  93.       if (!haystack || needle_len == 1)
  94.         return (void *) haystack;
  95.       haystack_len -= haystack - (const unsigned char *) haystack_start;
  96.       if (haystack_len < needle_len)
  97.         return NULL;
  98.       return two_way_short_needle (haystack, haystack_len, needle, needle_len);
  99.     }
  100.   return two_way_long_needle (haystack, haystack_len, needle, needle_len);
  101. #endif /* compilation for speed */
  102. }
  103.