K&R2, exercise 4-2

[arnuld]

STATEMENT: Write the function strindex(s, t), which returns the position of the
rightmost occurence of t in s, or -1 if there is none.

PURPOSE: this program prints the index of the rightmost match on the line.
The match we have to find is a char array named pattern. We also print out
the number of matches we have found. We will take the input from
command-line.
PROBLEM: Segmentation Fault

The programe compiles fine but at run-time it segfaults :(
here is my solution which is a little modified version of the example
provided in the same section:

/* Exercise # 4.1 */

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

enum MAXSIZE { ARR_SIZE = 1000 };

int getline( char current_line[], int max );
int str_index( char current_line[], char search_for[] );

char pattern[] = "term";

int match_num;
int main( void )
{
char current_line[ARR_SIZE];
int matched_idx, idx;

idx = 0;
while( getline(current _line, ARR_SIZE) 0 )
{
if( (matched_idx = str_index(curre nt_line, pattern)) >= 0 )
{
printf("\n%d matches, \n%d is the last to match", match_num, matched_idx);
}
}

return 0;

}
/* takes a line as input and returns the length of the line */
int getline( char s[], int max )
{
int c, i;

for( i = 0; ( (c = getchar()) != EOF && (c != '\n') && (--max 0) ); ++i )
{
s[i] = c;
}

if( c == '\n' )
{
s[i++] = '\n';
}

s[i] = '\0';

return i;
}
/* search for a pattern in the line, will save every index position of
source string where the pattern starts to match. For string the index we
use an array of ints. we then return the last element of array which is the
index of the rightmost match. We also return the number of matches we have
found using an int match_num.
*/
int str_index( char s[], char p[] )
{
int i, j, k;
int idx, last_match;
int saved_pos[ARR_SIZE];
memset( saved_pos, '\0', sizeof( saved_pos ));

idx = 0;
match_num = 0;
for( i = 0; s[i] != '\0'; ++i )
{
for( k = 0, j = i; p[k] != '\0' ; ++k, ++j )
{
if( s[j] != p[k] )
{
break;
}
}

if( (k 0) && p[k] == '\0' )
{
saved_pos[idx] = i;
++match_num;
}
}

last_match = sizeof(saved_po s) - 2;
/* it checks whether we have any match or not. If we do not have any match
* then we have nothing in array */
if( saved_pos[0] )
{
return saved_pos[last_match];
}
else
{
return -1;
}
}
=========== OUTPUT =============
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra 4-1.c
/home/arnuld/programs/C $ ./a.out
terminal
and no one
and this
term
and Xterminal
segmentation fault
/home/arnuld/programs/C $

[arnuld]

On Thu, 03 Apr 2008 19:14:49 +0530, arnuld wrote:

last_match = sizeof(saved_po s) - 2;
/* it checks whether we have any match or not. If we do not have any
match
* then we have nothing in array */
if( saved_pos[0] )
{
return saved_pos[last_match];
}

that was the source of trouble. I changed it to this:
if( saved_pos[0] )
{
return saved_pos[match_num - 1];
}

and I got a new bug:
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 4-1.c
[arnuld@raj C]$ ./a.out
and no TERM
term
and term

1 matches,
4 is the last to match
how about this tErm
nope
the terminal is the xterm and urxvt term

3 matches,
0 is the last to match[arnuld@raj C]$
whats the problem now ?

[Richard Heathfield]

arnuld said:

<snip>

PROBLEM: Segmentation Fault

The programe compiles fine but at run-time it segfaults :(

<snip>

int str_index( char s[], char p[] )
{
int i, j, k;
int idx, last_match;
int saved_pos[ARR_SIZE];

<snip>

>
last_match = sizeof(saved_po s) - 2;

This doesn't do what you think. sizeof saved_pos gives the size, in bytes,
of the array. That's fine if ints are 1 byte in size, which they can be,
but it doesn't seem to be the case on your system.

What you meant to write was:

last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;

This fixes your problem.

And in case anyone's curious, the only use I made of gdb for finding this
bug was to get a backtrace, from which the problem was immediately
obvious.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Richard Heathfield]

arnuld said:

<snip>

> {
return saved_pos[last_match];
}

that was the source of trouble.

No, that was the symptom, not the cause. See my other reply.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[arnuld]

On Thu, 03 Apr 2008 19:22:29 +0530, Richard Heathfield wrote:

This doesn't do what you think. sizeof saved_pos gives the size, in
bytes, of the array. That's fine if ints are 1 byte in size, which they
can be, but it doesn't seem to be the case on your system.

your way/idea of telling the problem is very clear. I never expected that
from the author of a book like "C Unleashed". NO, I have not read the book
but heard about its toughness and harder ideas.

What you meant to write was:

last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;

This fixes your problem.

I got a new one:

[arnuld@raj C]$ ./a.out
term
term
Xterm

1 matches,
Position 1 is the last to match

[arnuld@raj C]$ ./a.out
this terminal

1 matches,
Position 1 is the last to match
[arnuld@raj C]$
look at the output. program is not reading the position 0 and always saying
that position 1 is th elast to match. I think I have modified the file a
little. you can check the whole source here:

http://pastebin.ca/969121

And in case anyone's curious, the only use I made of gdb for finding
this bug was to get a backtrace, from which the problem was immediately
obvious.

Oh... I never used gdb. I think I need to read the manual to start using
it.

[Ben Bacarisse]

Richard Heathfield <rj*@see.sig.in validwrites:

arnuld said:

<snip>

>PROBLEM: Segmentation Fault

The programe compiles fine but at run-time it segfaults :(

<snip>

>int str_index( char s[], char p[] )
{
int i, j, k;
int idx, last_match;
int saved_pos[ARR_SIZE];

<snip>

>>
last_match = sizeof(saved_po s) - 2;

This doesn't do what you think. sizeof saved_pos gives the size, in bytes,
of the array. That's fine if ints are 1 byte in size, which they can be,
but it doesn't seem to be the case on your system.

What you meant to write was:

last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;

This fixes your problem.

I am not sure if you are joking. It fixes the problem only for some
very limited meanings of either "fix" or "problem".

--
Ben.

[Ben Bacarisse]

arnuld <oo***@poonga.c omwrites:

>On Thu, 03 Apr 2008 19:14:49 +0530, arnuld wrote:

> last_match = sizeof(saved_po s) - 2;
/* it checks whether we have any match or not. If we do not have any
match
* then we have nothing in array */
if( saved_pos[0] )
{
return saved_pos[last_match];
}

that was the source of trouble. I changed it to this:
if( saved_pos[0] )
{
return saved_pos[match_num - 1];
}

and I got a new bug:

You have a few. I'll take only one that I can illustrate from the
fragment above: you can't tell if there is or is not a match by
testing saved_pos[0] because there match might be a first match at
position zero. Now, as it happens, you store all the match positions
in index 0 of this array because you don't increment idx (not shown)
so this bug only shows up when the first and last match are at
position zero.

I would suggest you don't try to store the matches. Try to find a way
that does not involve remembering them all, just to return the
right-most one.

--
Ben.

[Richard Heathfield]

Ben Bacarisse said:

Richard Heathfield <rj*@see.sig.in validwrites:

<snip>

>>
What you meant to write was:

last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;

This fixes your problem.

I am not sure if you are joking. It fixes the problem only for some
very limited meanings of either "fix" or "problem".

Well, okay, it fixes the segfault, anyway. The segfault was caused by his
violating the bounds of the saved_pos array a few lines further on,
because he was calculating the offset not in objects but in bytes. I'm not
claiming that my fix removes *all* the bugs from his program, but it
removes *this* bug.

If you don't find that this answer deals with your point, perhaps you could
explain further what you are getting at?

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[arnuld]

On Thu, 03 Apr 2008 19:46:34 +0530, Ben Bacarisse wrote:

You have a few. I'll take only one that I can illustrate from the
fragment above: you can't tell if there is or is not a match by testing
saved_pos[0] because there match might be a first match at position
zero. Now, as it happens, you store all the match positions in index 0
of this array because you don't increment idx (not shown) so this bug
only shows up when the first and last match are at position zero.

I would suggest you don't try to store the matches. Try to find a way
that does not involve remembering them all, just to return the
right-most one.

HEY.. thanks :) , how about this, works perfectly fine. Tell me if I have
any more bugs left:

/* Exercise # 4.1 */

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

enum MAXSIZE { ARR_SIZE = 1000 };

int getline( char current_line[], int max );
int str_index( char current_line[], char search_for[] );

char pattern[] = "term";

int match_num;
int main( void )
{
char current_line[ARR_SIZE];
int matched_idx, idx;

idx = 0;
while( getline(current _line, ARR_SIZE) 0 )
{
if( (matched_idx = str_index(curre nt_line, pattern)) >= 0 )
{
printf("\n%d matches -- ", match_num);
if( match_num )
{
printf("Positio n %d is the last to match\n\n", matched_idx);
}
}
}

return 0;

}
/* takes a line as input and returns the length of the line */
int getline( char s[], int max )
{
int c, i;

for( i = 0; ( (c = getchar()) != EOF && (c != '\n') && (--max 0) ); ++i )
{
s[i] = c;
}

if( c == '\n' )
{
s[i++] = '\n';
}

s[i] = '\0';

return i;
}
/* search for a pattern in the line, will save every index position of source
string where the pattern starts to match. For string the index we use an
array of ints. we then return the last element of array which is the
index of the rightmost match. We also return the number of matches we have
found using an int match_num.
*/
int str_index( char s[], char p[] )
{
int i, j, k;
int idx, match_pos;
idx = 0;
match_num = 0;
for( i = 0; s[i] != '\0'; ++i )
{
for( k = 0, j = i; p[k] != '\0' ; ++k, ++j )
{
if( s[j] != p[k] )
{
break;
}
}

if( (k 0) && p[k] == '\0' )
{
++match_num;
match_pos = i;
}
}

/* it checks whether we have any match or not. */
if( match_num )
{
return match_pos;
}
else
{
return -1;
}
}
========== OUTPUT ============
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra -ggdb 4-1.c
[arnuld@raj C]$ ./a.out
and this
and that
9843788327#&&$^ $^$^^$TER%%^
TERM
term

1 matches -- Position 0 is the last to match

term and term and term\0

3 matches -- Position 18 is the last to match

[arnuld@raj C]$

[Ben Bacarisse]

Richard Heathfield <rj*@see.sig.in validwrites:

Ben Bacarisse said:

>Richard Heathfield <rj*@see.sig.in validwrites:

<snip>

>>>
What you meant to write was:

last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;

This fixes your problem.

<snipIt fixes the problem only for some
very limited meanings of either "fix" or "problem".

Well, okay, it fixes the segfault, anyway.

Right. I thought that is maybe what you meant.

--
Ben.