Velocity Reviews > K&R2, exercise 4-2

K&R2, exercise 4-2

arnuld
Guest
Posts: n/a

 04-03-2008
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 \$

arnuld
Guest
Posts: n/a

 04-03-2008
> 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
nope
the terminal is the xterm and urxvt term

3 matches,
0 is the last to match[arnuld@raj C]\$

whats the problem now ?

Ben Bacarisse
Guest
Posts: n/a

 04-03-2008
Richard Heathfield <(E-Mail Removed)> 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;
>

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
Guest
Posts: n/a

 04-03-2008
arnuld <(E-Mail Removed)> 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.

arnuld
Guest
Posts: n/a

 04-03-2008
> 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;
>

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.

arnuld
Guest
Posts: n/a

 04-03-2008
> 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.

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]\$

Ben Bacarisse
Guest
Posts: n/a

 04-03-2008
Richard Heathfield <(E-Mail Removed)> writes:

> Ben Bacarisse said:
>
>> Richard Heathfield <(E-Mail Removed)> writes:
>>

> <snip>
>>>
>>> What you meant to write was:
>>>
>>> last_match = sizeof saved_pos / sizeof saved_pos[0] - 2;
>>>

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

Ben Bacarisse
Guest
Posts: n/a

 04-03-2008
arnuld <(E-Mail Removed)> 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.

>
> any more bugs left:

The str_index function looks good to me but there is a bug in the input

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

Keith Thompson
Guest
Posts: n/a

 04-03-2008
Ben Bacarisse <(E-Mail Removed)> 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) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Default User
Guest
Posts: n/a

 04-03-2008
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.

Brian