Evaluation of C program

[morphex@gmail.com]

Hi,

I'm a python programmer that's started to play a bit with C as I'll
probably have to make C extensions eventually.. I made this little
program that I'd like to get feedback on, it's basically a find
substring and return pointer to it function and tests for it..

Could this be done better/differently? Is anything fundamentally
wrong?

---

#include <stdio.h>

char *find_substring (char *substring, char *string) {
int index_string, index_substring ;
for (index_string = 0; string[index_string] != 0; index_string++) {
index_substring = 0;
do {
if (substring[index_substring] == 0)
goto success;
if (string[index_string + index_substring] !=
substring[index_substring])
goto next;
} while (++index_substr ing);
success:
return &string[index_string];
next: ;
}
return 0;
}

int main() {
if(find_substri ng("test", "this is a test"))
printf("Found test in string!\n");

return 0;
}

---

Thanks,

Morten

[Walter Roberson]

Re: Evaluation of C program

In article <1140113852.635 717.152500@g43g 2000cwa.googleg roups.com>,
<morphex@gmail. com> wrote:[color=blue]
>I'm a python programmer that's started to play a bit with C as I'll
>probably have to make C extensions eventually.. I made this little
>program that I'd like to get feedback on, it's basically a find
>substring and return pointer to it function and tests for it..[/color]
[color=blue]
>Could this be done better/differently? Is anything fundamentally
>wrong?[/color]
[color=blue]
>#include <stdio.h>[/color]

Your entire find_substring( ) function could be replaced with a
single call to strstr();
[color=blue]
>char *find_substring (char *substring, char *string) {
> int index_string, index_substring ;
> for (index_string = 0; string[index_string] != 0; index_string++) {[/color]

strings can be longer than an 'int' can hold. Check out size_t
[color=blue]
> index_substring = 0;
> do {
> if (substring[index_substring] == 0)
> goto success;[/color]

goto should rarely be used. Consider using "break" here.
[color=blue]
> if (string[index_string + index_substring] !=
>substring[index_substring])
> goto next;[/color]

goto should rarely be used. Consider using "continue" here.
[color=blue]
> } while (++index_substr ing);[/color]

The only way that ++index_substri ng could be false in that test is
if the int representation overflowed. This suggests that you are using
the wrong control structure; consider using a for().
[color=blue]
> success:
> return &string[index_string];
> next: ;
> }
> return 0;[/color]

Returning 0 is not wrong here, but it would be more readable
if you were to use NULL instead of 0.
[color=blue]
>}[/color]
[color=blue]
>
>int main() {[/color]

int main(void) {
[color=blue]
> if(find_substri ng("test", "this is a test"))
> printf("Found test in string!\n");[/color]

If you do not find the substring, then you print nothing, and
won't know what happened.[color=blue]
>
> return 0;[/color]

Returning 0 indicates success, but it could be argued that if you
do not find the substring then your program has failed and so
returning EXIT_FAILURE (from <stdlib.h>) would be more appropriate
in that instance.
[color=blue]
>}[/color]

[color=blue]
>Could this be done better/differently?[/color]

Suppose you don't find a match the first iteration through
because the 10th character in the trial substring does not match
the 10th character in the input string. You then loop back
and start testing from the substring again from the second
character of the input string -- ignoring all the information
you could have gleened by paying attention to what was in
offsets 1 thru 9 that you have already looked at.

Suppose for example that what you found at the 10th character at the
input string was an 'X', and there are no occurances of 'X' in the
trial substring. A moment's reflection would show you that in
such an instance you would be able to skip testing for the
substring as starting from 1 thru 9, since that 'X' will still be
there at offset 9 blocking any possible match.

What this tells you is that there are algorithms which can be
much faster than your search algorithm. Indeed, there is an entire
literature on search algorithms. Some are probably mentioned in the C
FAQ or by googling for "string search algorithms".
--
If you lie to the compiler, it will get its revenge. -- Henry Spencer

[Morten W. Petersen]

Re: Evaluation of C program

>> #include <stdio.h>[color=blue]
>
> Your entire find_substring( ) function could be replaced with a
> single call to strstr();[/color]

Yep. This was an exercise so I didn't look, but good to know.
[color=blue][color=green]
>> char *find_substring (char *substring, char *string) {
>> int index_string, index_substring ;
>> for (index_string = 0; string[index_string] != 0; index_string++) {[/color]
>
> strings can be longer than an 'int' can hold. Check out size_t[/color]

Good point.
[color=blue][color=green]
>> index_substring = 0;
>> do {
>> if (substring[index_substring] == 0)
>> goto success;[/color]
>
> goto should rarely be used. Consider using "break" here.
>[color=green]
>> if (string[index_string + index_substring] !=
>> substring[index_substring])
>> goto next;[/color]
>
> goto should rarely be used. Consider using "continue" here.[/color]

I don't see the harm in using goto.. it does the job. :-)
[color=blue][color=green]
>> } while (++index_substr ing);[/color]
>
> The only way that ++index_substri ng could be false in that test is
> if the int representation overflowed. This suggests that you are using
> the wrong control structure; consider using a for().[/color]

Well, it will always goto using one of the two statements above it, so
it works. But it should be a long, yes.
[color=blue][color=green]
>> success:
>> return &string[index_string];
>> next: ;
>> }
>> return 0;[/color]
>
> Returning 0 is not wrong here, but it would be more readable
> if you were to use NULL instead of 0.[/color]

Yep.
[color=blue][color=green]
>> }[/color]
>[color=green]
>> int main() {[/color]
>
> int main(void) {
>[color=green]
>> if(find_substri ng("test", "this is a test"))
>> printf("Found test in string!\n");[/color]
>
> If you do not find the substring, then you print nothing, and
> won't know what happened.[/color]

Yeah..
[color=blue][color=green]
>> return 0;[/color]
>
> Returning 0 indicates success, but it could be argued that if you
> do not find the substring then your program has failed and so
> returning EXIT_FAILURE (from <stdlib.h>) would be more appropriate
> in that instance.
>[color=green]
>> }[/color]
>
>[color=green]
>> Could this be done better/differently?[/color]
>
> Suppose you don't find a match the first iteration through
> because the 10th character in the trial substring does not match
> the 10th character in the input string. You then loop back
> and start testing from the substring again from the second
> character of the input string -- ignoring all the information
> you could have gleened by paying attention to what was in
> offsets 1 thru 9 that you have already looked at.
>
> Suppose for example that what you found at the 10th character at the
> input string was an 'X', and there are no occurances of 'X' in the
> trial substring. A moment's reflection would show you that in
> such an instance you would be able to skip testing for the
> substring as starting from 1 thru 9, since that 'X' will still be
> there at offset 9 blocking any possible match.
>
> What this tells you is that there are algorithms which can be
> much faster than your search algorithm. Indeed, there is an entire
> literature on search algorithms. Some are probably mentioned in the C
> FAQ or by googling for "string search algorithms".[/color]

OK. This was a bit beyond what I was looking to figure out, but good to
know I guess.

Thanks. :)

-Morten

[Fred Kleinschmidt]

Re: Evaluation of C program


"Walter Roberson" <roberson@ibd.n rc-cnrc.gc.ca> wrote in message
news:dt2hs2$hbg $1@canopus.cc.u manitoba.ca...[color=blue]
> In article <1140113852.635 717.152500@g43g 2000cwa.googleg roups.com>,
> <morphex@gmail. com> wrote:[color=green]
>>I'm a python programmer that's started to play a bit with C as I'll
>>probably have to make C extensions eventually.. I made this little
>>program that I'd like to get feedback on, it's basically a find
>>substring and return pointer to it function and tests for it..[/color]
>[color=green]
>>Could this be done better/differently? Is anything fundamentally
>>wrong?[/color]
>[color=green]
>>#include <stdio.h>[/color]
>
> Your entire find_substring( ) function could be replaced with a
> single call to strstr();
>[color=green]
>>char *find_substring (char *substring, char *string) {
>> int index_string, index_substring ;
>> for (index_string = 0; string[index_string] != 0; index_string++) {[/color]
>
> strings can be longer than an 'int' can hold. Check out size_t
>[color=green]
>> index_substring = 0;
>> do {
>> if (substring[index_substring] == 0)
>> goto success;[/color]
>
> goto should rarely be used. Consider using "break" here.
>[color=green]
>> if (string[index_string + index_substring] !=
>>substring[index_substring])
>> goto next;[/color]
>
> goto should rarely be used. Consider using "continue" here.
>[color=green]
>> } while (++index_substr ing);[/color]
>
> The only way that ++index_substri ng could be false in that test is
> if the int representation overflowed. This suggests that you are using
> the wrong control structure; consider using a for().
>[color=green]
>> success:
>> return &string[index_string];
>> next: ;
>> }
>> return 0;[/color]
>
> Returning 0 is not wrong here, but it would be more readable
> if you were to use NULL instead of 0.
>[color=green]
>>}[/color]
>[color=green]
>>
>>int main() {[/color]
>
> int main(void) {
>[color=green]
>> if(find_substri ng("test", "this is a test"))
>> printf("Found test in string!\n");[/color]
>
> If you do not find the substring, then you print nothing, and
> won't know what happened.[color=green]
>>
>> return 0;[/color]
>
> Returning 0 indicates success, but it could be argued that if you
> do not find the substring then your program has failed and so
> returning EXIT_FAILURE (from <stdlib.h>) would be more appropriate
> in that instance.
>[color=green]
>>}[/color]
>
>[color=green]
>>Could this be done better/differently?[/color]
>
> Suppose you don't find a match the first iteration through
> because the 10th character in the trial substring does not match
> the 10th character in the input string. You then loop back
> and start testing from the substring again from the second
> character of the input string -- ignoring all the information
> you could have gleened by paying attention to what was in
> offsets 1 thru 9 that you have already looked at.
>
> Suppose for example that what you found at the 10th character at the
> input string was an 'X', and there are no occurances of 'X' in the
> trial substring. A moment's reflection would show you that in
> such an instance you would be able to skip testing for the
> substring as starting from 1 thru 9, since that 'X' will still be
> there at offset 9 blocking any possible match.
>[/color]
Not True!

Suppose string = "XXXXXXXXXX Y"
and substring = "XXXXXXXXXY "

They do not match beginning from index 0, since 'X' != 'Y'
But you cannot skip to index 9, since they DO match statring at index 1.
[color=blue]
> What this tells you is that there are algorithms which can be
> much faster than your search algorithm. Indeed, there is an entire
> literature on search algorithms. Some are probably mentioned in the C
> FAQ or by googling for "string search algorithms".
> --
> If you lie to the compiler, it will get its revenge. -- Henry Spencer[/color]

--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Software Reuse Project

[Walter Roberson]

Re: Evaluation of C program

In article <Iusu1t.79n@new s.boeing.com>,
Fred Kleinschmidt <fred.l.kleinms chmidt@boeing.c om> wrote:
[color=blue]
>"Walter Roberson" <roberson@ibd.n rc-cnrc.gc.ca> wrote in message
>news:dt2hs2$hb g$1@canopus.cc. umanitoba.ca...[/color]
[color=blue][color=green]
>> Suppose for example that what you found at the 10th character at the
>> input string was an 'X', and there are no occurances of 'X' in the
>> trial substring. A moment's reflection would show you that in
>> such an instance you would be able to skip testing for the
>> substring as starting from 1 thru 9, since that 'X' will still be
>> there at offset 9 blocking any possible match.[/color][/color]
[color=blue]
> Not True![/color]
[color=blue]
>Suppose string = "XXXXXXXXXX Y"
>and substring = "XXXXXXXXXY "[/color]
[color=blue]
>They do not match beginning from index 0, since 'X' != 'Y'
>But you cannot skip to index 9, since they DO match statring at index 1.[/color]

But that violates the proposition "and there are no occurances
of 'X' in the trial substring".
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

[August Karlstrom]

Re: Evaluation of C program

morphex@gmail.c om wrote:[color=blue]
> I'm a python programmer that's started to play a bit with C as I'll
> probably have to make C extensions eventually.. I made this little
> program that I'd like to get feedback on, it's basically a find
> substring and return pointer to it function and tests for it..
>
> Could this be done better/differently? Is anything fundamentally
> wrong?
>
> ---
>
> #include <stdio.h>
>
> char *find_substring (char *substring, char *string) {
> int index_string, index_substring ;
> for (index_string = 0; string[index_string] != 0; index_string++) {
> index_substring = 0;
> do {
> if (substring[index_substring] == 0)
> goto success;
> if (string[index_string + index_substring] !=
> substring[index_substring])
> goto next;
> } while (++index_substr ing);
> success:
> return &string[index_string];
> next: ;
> }
> return 0;
> }
>
> int main() {
> if(find_substri ng("test", "this is a test"))
> printf("Found test in string!\n");
>
> return 0;
> }[/color]

Here is how I would do it.


--- Source Text ---

#include <stdio.h>
#include <string.h>


/* Returns the starting index of pattern in s or -1 if not found. */

int position(const char *pattern, const char *s)
{
int j, k, plen, slen, res;

plen = strlen(pattern) ;
slen = strlen(s);
res = -1;
j = 0;
while ((res < 0) && (j + plen < slen)) {
k = 0;
while ((k < plen) && (pattern[k] == s[j + k])) { k++; }
if (k == plen) { res = j; }
j++;
}
return res;
}


int main(void)
{
char s[] = "Hello there!";
char pattern[] = "there";
int pos;

pos = position(patter n, s);
if (pos < 0) {
printf("\"%s\" does not contain \"%s\".\n", s, pattern);
} else {
printf("\"%s\" contains \"%s\" starting at index %d.\n",
s, pattern, pos);
}
return 0;
}

--- End Of Source Text ---


August

--
I am the "ILOVEGNU" signature virus. Just copy me to your
signature. This email was infected under the terms of the GNU
General Public License.

[Morten W. Petersen]

Re: Evaluation of C program

> Here is how I would do it.[color=blue]
>
>
> --- Source Text ---
>
> #include <stdio.h>
> #include <string.h>
>
>
> /* Returns the starting index of pattern in s or -1 if not found. */
>
> int position(const char *pattern, const char *s)
> {
> int j, k, plen, slen, res;
>
> plen = strlen(pattern) ;
> slen = strlen(s);
> res = -1;
> j = 0;
> while ((res < 0) && (j + plen < slen)) {
> k = 0;
> while ((k < plen) && (pattern[k] == s[j + k])) { k++; }
> if (k == plen) { res = j; }
> j++;
> }
> return res;
> }[/color]

This was a nice example. Thanks for posting it. :-)

-Morten

[micans@gmail.com]

Re: Evaluation of C program

Walter Roberson wrote:[color=blue]
> In article <1140113852.635 717.152500@g43g 2000cwa.googleg roups.com>,
> <morphex@gmail. com> wrote:[color=green]
> >I'm a python programmer that's started to play a bit with C as I'll
> >probably have to make C extensions eventually.. I made this little
> >program that I'd like to get feedback on, it's basically a find
> >substring and return pointer to it function and tests for it..[/color]
>[color=green]
> >Could this be done better/differently? Is anything fundamentally
> >wrong?[/color][/color]
[color=blue]
> Suppose you don't find a match the first iteration through
> because the 10th character in the trial substring does not match
> the 10th character in the input string. You then loop back
> and start testing from the substring again from the second
> character of the input string -- ignoring all the information
> you could have gleened by paying attention to what was in
> offsets 1 thru 9 that you have already looked at.
>
> Suppose for example that what you found at the 10th character at the
> input string was an 'X', and there are no occurances of 'X' in the
> trial substring. A moment's reflection would show you that in
> such an instance you would be able to skip testing for the
> substring as starting from 1 thru 9, since that 'X' will still be
> there at offset 9 blocking any possible match.
>
> What this tells you is that there are algorithms which can be
> much faster than your search algorithm. Indeed, there is an entire
> literature on search algorithms. Some are probably mentioned in the C
> FAQ or by googling for "string search algorithms".[/color]

Boyer Horspool Moore comes to mind. I implemented it with
a circular buffer; it's fast.

Stijn

[CBFalconer]

Re: Evaluation of C program

micans@gmail.co m wrote:[color=blue]
> Walter Roberson wrote:[color=green]
>> <morphex@gmail. com> wrote:[/color]
>[color=green][color=darkred]
>>> I'm a python programmer that's started to play a bit with C as
>>> I'll probably have to make C extensions eventually.. I made
>>> this little program that I'd like to get feedback on, it's
>>> basically a find substring and return pointer to it function
>>> and tests for it..[/color]
>>[color=darkred]
>>> Could this be done better/differently? Is anything fundamentally
>>> wrong?[/color][/color]
>[color=green]
>> Suppose you don't find a match the first iteration through
>> because the 10th character in the trial substring does not match
>> the 10th character in the input string. You then loop back
>> and start testing from the substring again from the second
>> character of the input string -- ignoring all the information
>> you could have gleened by paying attention to what was in
>> offsets 1 thru 9 that you have already looked at.
>>
>> Suppose for example that what you found at the 10th character at the
>> input string was an 'X', and there are no occurances of 'X' in the
>> trial substring. A moment's reflection would show you that in
>> such an instance you would be able to skip testing for the
>> substring as starting from 1 thru 9, since that 'X' will still be
>> there at offset 9 blocking any possible match.
>>
>> What this tells you is that there are algorithms which can be
>> much faster than your search algorithm. Indeed, there is an entire
>> literature on search algorithms. Some are probably mentioned in the C
>> FAQ or by googling for "string search algorithms".[/color]
>
> Boyer Horspool Moore comes to mind. I implemented it with
> a circular buffer; it's fast.[/color]

Knuth-Morris-Pratt has the distinct advantage of allowing operation
on streams and totally avoiding any need for look ahead or look
back. The following is from a post I made here almost two years
ago, and illustrates the use of KMP on a file stream.

/*
Leor Zolman wrote:[color=blue]
> On 25 Feb 2004 07:34:40 -0800, joan@ljungh.se (spike) wrote:
>[color=green]
>> Im trying to write a program that should read through a binary
>> file searching for the character sequence "\name\"
>>
>> Then it should read the characters following the "\name\"
>> sequence until a NULL character is encountered.
>>
>> But when my program runs it gets a SIGSEGV (Segmentation
>> vioalation) signal.
>>
>> Whats wrong? And is there a better way than mine to solve
>>this task (most likely)[/color]
>
> I think so. Here's a version I just threw together:[/color]
*/

/* And heres another throw -- binfsrch.c by CBF */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

/* The difference between a binary and a text file, on read,
is the conversion of end-of-line delimiters. What those
delimiters are does not affect the action. In some cases
the presence of 0x1a EOF markers (MsDos) does.

This is a version of Knuth-Morris-Pratt algorithm. The
point of using this is to avoid any backtracking in file
reading, and thus avoiding any use of buffer arrays.
*/

size_t chrcount; /* debuggery, count of input chars, zeroed */

/* --------------------- */

/* Almost straight out of Sedgewick */
/* The next array indicates what index in id should next be
compared to the current char. Once the (lgh - 1)th char
has been successfully compared, the id has been found.
The array is formed by comparing id to itself. */
void initnext(int *next, const char *id, int lgh)
{
int i, j;

assert(lgh > 0);
next[0] = -1; i = 0; j = -1;
while (i < lgh) {
while ((j >= 0) && (id[i] != id[j])) j = next[j];
i++; j++;
next[i] = j;
}
#if (0)
for (i = 0; i < lgh; i++)
printf("id[%d] = '%c' next[%d] = %d\n",
i, id[i], i, next[i]);
#endif
} /* initnext */

/* --------------------- */

/* reads f without rewinding until either EOF or *marker
has been found. Returns EOF if not found. At exit the
last matching char has been read, and no further. */
int kmpffind(const char *marker, int lgh, int *next, FILE *f)
{
int j; /* char position in marker to check */
int ch; /* current char */

assert(lgh > 0);
j = 0;
while ((j < lgh) && (EOF != (ch = getc(f)))) {
chrcount++;
while ((j >= 0) && (ch != marker[j])) j = next[j];
j++;
}
return ch;
} /* kmpffind */

/* --------------------- */

/* Find marker in f, display following printing chars
up to some non printing character or EOF */
int binfsrch(const char *marker, FILE *f)
{
int *next;
int lgh;
int ch;
int items; /* count of markers found */

lgh = strlen(marker);
if (!(next = malloc(lgh * sizeof *next))) {
puts("No memory");
exit(EXIT_FAILU RE);
}
else {
initnext(next, marker, lgh);
items = 0;
while (EOF != kmpffind(marker , lgh, next, f)) {
/* found, take appropriate action */
items++;
printf("%d %s : \"", items, marker);
while (isprint(ch = getc(f))) {
chrcount++;
putchar(ch);
}
puts("\"");
if (EOF == ch) break;
else chrcount++;
}
free(next);
return items;
}
} /* binfsrch */

/* --------------------- */

int main(int argc, char **argv)
{
FILE *f;

f = stdin;
if (3 == argc) {
if (!(f = fopen(argv[2], "rb"))) {
printf("Can't open %s\n", argv[2]);
exit(EXIT_FAILU RE);
}
argc--;
}
if (2 != argc) {
puts("Usage: binfsrch name [binaryfile]");
puts(" (file defaults to stdin text mode)");
}
else if (binfsrch(argv[1], f)) {
printf("\"%s\" : found\n", argv[1]);
}
else printf("\"%s\" : not found\n", argv[1]);
printf("%lu chars\n", (unsigned long)chrcount);
return 0;
} /* main binfsrch */

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>