1/* Test of searching in a string. 2 Copyright (C) 2007 Free Software Foundation, Inc. 3 4 This program is free software: you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; either version 3 of the License, or 7 (at your option) any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 16 17/* Written by Bruno Haible <bruno@clisp.org>, 2007. */ 18 19#include <config.h> 20 21#include "c-strstr.h" 22 23#include <stdio.h> 24#include <stdlib.h> 25#include <string.h> 26 27#define ASSERT(expr) \ 28 do \ 29 { \ 30 if (!(expr)) \ 31 { \ 32 fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \ 33 abort (); \ 34 } \ 35 } \ 36 while (0) 37 38int 39main () 40{ 41 { 42 const char input[] = "foo"; 43 const char *result = c_strstr (input, ""); 44 ASSERT (result == input); 45 } 46 47 { 48 const char input[] = "foo"; 49 const char *result = c_strstr (input, "o"); 50 ASSERT (result == input + 1); 51 } 52 53 { 54 const char input[] = "ABC ABCDAB ABCDABCDABDE"; 55 const char *result = c_strstr (input, "ABCDABD"); 56 ASSERT (result == input + 15); 57 } 58 59 { 60 const char input[] = "ABC ABCDAB ABCDABCDABDE"; 61 const char *result = c_strstr (input, "ABCDABE"); 62 ASSERT (result == NULL); 63 } 64 65 /* Check that a very long haystack is handled quickly if the needle is 66 short and occurs near the beginning. */ 67 { 68 size_t repeat = 10000; 69 size_t m = 1000000; 70 char *needle = 71 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" 72 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; 73 char *haystack = (char *) malloc (m + 1); 74 if (haystack != NULL) 75 { 76 memset (haystack, 'A', m); 77 haystack[0] = 'B'; 78 haystack[m] = '\0'; 79 80 for (; repeat > 0; repeat--) 81 { 82 ASSERT (c_strstr (haystack, needle) == haystack + 1); 83 } 84 85 free (haystack); 86 } 87 } 88 89 /* Check that a very long needle is discarded quickly if the haystack is 90 short. */ 91 { 92 size_t repeat = 10000; 93 size_t m = 1000000; 94 char *haystack = 95 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" 96 "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB"; 97 char *needle = (char *) malloc (m + 1); 98 if (needle != NULL) 99 { 100 memset (needle, 'A', m); 101 needle[m] = '\0'; 102 103 for (; repeat > 0; repeat--) 104 { 105 ASSERT (c_strstr (haystack, needle) == NULL); 106 } 107 108 free (needle); 109 } 110 } 111 112 /* Check that the asymptotic worst-case complexity is not quadratic. */ 113 { 114 size_t m = 1000000; 115 char *haystack = (char *) malloc (2 * m + 2); 116 char *needle = (char *) malloc (m + 2); 117 if (haystack != NULL && needle != NULL) 118 { 119 const char *result; 120 121 memset (haystack, 'A', 2 * m); 122 haystack[2 * m] = 'B'; 123 haystack[2 * m + 1] = '\0'; 124 125 memset (needle, 'A', m); 126 needle[m] = 'B'; 127 needle[m + 1] = '\0'; 128 129 result = c_strstr (haystack, needle); 130 ASSERT (result == haystack + m); 131 } 132 if (needle != NULL) 133 free (needle); 134 if (haystack != NULL) 135 free (haystack); 136 } 137 138 return 0; 139} 140