«

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(current_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_pos) - 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 $

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

> last_match = sizeof(saved_pos) - 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 <> writes:

> 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_pos) - 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.

arnuld <> writes:

>> On Thu, 03 Apr 2008 19:14:49 +0530, arnuld wrote:
>
>> last_match = sizeof(saved_pos) - 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.

> 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.

> 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(current_line, pattern)) >= 0 )
{
printf("\n%d matches -- ", match_num);
if( match_num )
{
printf("Position %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]$

Richard Heathfield <> writes:

> Ben Bacarisse said:
>
>> Richard Heathfield <> writes:
>>
> <snip>
>>>
>>> What you meant to write was:
>>>
>>> last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;
>>>
>>> This fixes your problem.
>>
>> <snip> It 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.

arnuld <> writes:

>> On Thu, 03 Apr 2008 19:46:34 +0530, Ben Bacarisse wrote:
<snip>
>> 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:

The str_index function looks good to me but there is a bug in the input
routine. If made a few other comments...

> /* 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(current_line, pattern)) >= 0 )
> {
> printf("\n%d matches -- ", match_num);

It is more reliable to get into the habit of ending output with
newlines rather than starting it with then. In your case...

> if( match_num )
> {
> printf("Position %d is the last to match\n\n", matched_idx);
> }

.... when there is no match, the output is "left hanging". Output that
does not end with a newline is guaranteed to appear on all systems.

> }
> }
>
> 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;
> }

For simple testing, I prefer to read a whole line, storing only those
characters that fit but this way is fine. Except...

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

.... I think you have a bug here. The loop above can put max-1 chars
into the buffer (max being what it was originally, of course) but it
can end when c == '\n'. You then try to put the '\n' and the '\0' in
the one remaining space!

> 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;

No used.

> match_num = 0;

OK, maybe you do this for testing, but a utility function like this
should not use a file-scope (AKA "global") variable like match_num.
Of course, you code works if you just make match_num local to this
function.

> 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;
> }
> }

Looks good to me.

--
Ben.

Ben Bacarisse <> writes:
[...]
> ... when there is no match, the output is "left hanging". Output that
> does not end with a newline is guaranteed to appear on all systems.
[...]

You mean "is not guaranteed".

--
Keith Thompson (The_Other_Keith) <kst->
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

arnuld wrote:

> > 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.

Wow! Talk about your backhanded compliments.




Brian