1/* Searching in a string.
2   Copyright (C) 2005 Free Software Foundation, Inc.
3   Written by Bruno Haible <bruno@clisp.org>, 2005.
4
5   This program is free software; you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published by
7   the Free Software Foundation; either version 2, or (at your option)
8   any later version.
9
10   This program is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   GNU General Public License for more details.
14
15   You should have received a copy of the GNU General Public License
16   along with this program; if not, write to the Free Software Foundation,
17   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
18
19#ifdef HAVE_CONFIG_H
20# include <config.h>
21#endif
22
23/* Specification.  */
24#include "strstr.h"
25
26#include <stddef.h>  /* for NULL */
27
28#if HAVE_MBRTOWC
29# include "mbuiter.h"
30#endif
31
32/* Find the first occurrence of NEEDLE in HAYSTACK.  */
33char *
34strstr (const char *haystack, const char *needle)
35{
36  /* Be careful not to look at the entire extent of haystack or needle
37     until needed.  This is useful because of these two cases:
38       - haystack may be very long, and a match of needle found early,
39       - needle may be very long, and not even a short initial segment of
40         needle may be found in haystack.  */
41#if HAVE_MBRTOWC
42  if (MB_CUR_MAX > 1)
43    {
44      mbui_iterator_t iter_needle;
45
46      mbui_init (iter_needle, needle);
47      if (mbui_avail (iter_needle))
48	{
49	  mbui_iterator_t iter_haystack;
50
51	  mbui_init (iter_haystack, haystack);
52	  for (;; mbui_advance (iter_haystack))
53	    {
54	      if (!mbui_avail (iter_haystack))
55		/* No match.  */
56		return NULL;
57
58	      if (mb_equal (mbui_cur (iter_haystack), mbui_cur (iter_needle)))
59		/* The first character matches.  */
60		{
61		  mbui_iterator_t rhaystack;
62		  mbui_iterator_t rneedle;
63
64		  memcpy (&rhaystack, &iter_haystack, sizeof (mbui_iterator_t));
65		  mbui_advance (rhaystack);
66
67		  mbui_init (rneedle, needle);
68		  if (!mbui_avail (rneedle))
69		    abort ();
70		  mbui_advance (rneedle);
71
72		  for (;; mbui_advance (rhaystack), mbui_advance (rneedle))
73		    {
74		      if (!mbui_avail (rneedle))
75			/* Found a match.  */
76			return (char *) mbui_cur_ptr (iter_haystack);
77		      if (!mbui_avail (rhaystack))
78			/* No match.  */
79			return NULL;
80		      if (!mb_equal (mbui_cur (rhaystack), mbui_cur (rneedle)))
81			/* Nothing in this round.  */
82			break;
83		    }
84		}
85	    }
86	}
87      else
88	return (char *) haystack;
89    }
90  else
91#endif
92    {
93      if (*needle != '\0')
94	{
95	  /* Speed up the following searches of needle by caching its first
96	     character.  */
97	  char b = *needle++;
98
99	  for (;; haystack++)
100	    {
101	      if (*haystack == '\0')
102		/* No match.  */
103		return NULL;
104	      if (*haystack == b)
105		/* The first character matches.  */
106		{
107		  const char *rhaystack = haystack + 1;
108		  const char *rneedle = needle;
109
110		  for (;; rhaystack++, rneedle++)
111		    {
112		      if (*rneedle == '\0')
113			/* Found a match.  */
114			return (char *) haystack;
115		      if (*rhaystack == '\0')
116			/* No match.  */
117			return NULL;
118		      if (*rhaystack != *rneedle)
119			/* Nothing in this round.  */
120			break;
121		    }
122		}
123	    }
124	}
125      else
126	return (char *) haystack;
127    }
128}
129