Open64 (mfef90, whirl2f, and IR tools)
TAG: version-openad; SVN changeset: 916
|
00001 static char USMID[] = "@(#)libc/gen/strnstrn.c 92.0 11/09/95 09:35:04"; 00002 00003 /* 00004 00005 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00006 00007 This program is free software; you can redistribute it and/or modify it 00008 under the terms of version 2.1 of the GNU Lesser General Public License 00009 as published by the Free Software Foundation. 00010 00011 This program is distributed in the hope that it would be useful, but 00012 WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00014 00015 Further, this software is distributed without any warranty that it is 00016 free of the rightful claim of any third person regarding infringement 00017 or the like. Any license provided herein, whether implied or 00018 otherwise, applies only to this software file. Patent licenses, if 00019 any, provided herein do not apply to combinations of this program with 00020 other software, or any other product whatsoever. 00021 00022 You should have received a copy of the GNU Lesser General Public 00023 License along with this program; if not, write the Free Software 00024 Foundation, Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307, 00025 USA. 00026 00027 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00028 Mountain View, CA 94043, or: 00029 00030 http://www.sgi.com 00031 00032 For further information regarding this notice, see: 00033 00034 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00035 00036 */ 00037 00038 #include <string.h> 00039 00040 #define MAXCHRS 256 /* Size of character set */ 00041 00042 /* 00043 * strnstrn Search for the first occurance of a substring 00044 * in another string. The length of the strings 00045 * are arguments and the strings are not necessarily 00046 * null-terminated. 00047 * 00048 * Algorithm: This routine uses the Boyer-Moore algorithm as 00049 * described in _Algorithms_ by Robert Sedgewick, 00050 * Addison-Wesley, 2d Ed., 1988. pp. 277-289. 00051 * 00052 * Performance: If M is the length of the substring and N is 00053 * the length of the string; this algorithm's worst case 00054 * is M+N character comparisons, and ``average-case'' is 00055 * N/M comparisons. The ``brute-force'' algorithm's 00056 * worst case is about N*M comparisons. 00057 */ 00058 00059 char * 00060 strnstrn(const char *string, size_t lenstr, const char *substr, size_t lensub) 00061 { 00062 register short i, j; 00063 unsigned short skip[MAXCHRS]; 00064 00065 if (lensub < 2) 00066 return( ((lensub == 1) ? 00067 (char *)memchr(string, (int) *substr, lenstr) : 00068 (char *)string) ); 00069 00070 /* Initialize skip array */ 00071 00072 for (i = 0; i < MAXCHRS; i++) /* Should vectorize */ 00073 skip[i] = lensub; 00074 00075 for (i = 0; i < lensub; i++) 00076 skip[(int)substr[i]] = lensub - 1 - i; 00077 00078 i = lensub - 1; 00079 j = lensub - 1; 00080 00081 do { 00082 00083 if (string[i] == substr[j]) { 00084 i = i - 1; 00085 j = j - 1; 00086 } 00087 else { 00088 if ((unsigned) (lensub - j) > skip[(int)string[i]]) 00089 i = i + lensub - j; 00090 else 00091 i = i + skip[(int)string[i]]; 00092 00093 j = lensub - 1; 00094 } 00095 00096 } while (j >= 0 && i < lenstr); 00097 00098 if (i >= (int) lenstr) 00099 return(NULL); 00100 else 00101 return( (char *) string + i + 1); 00102 }