How is strlen implemented?

[roy]

Hi,

I was wondering how strlen is implemented.
What if the input string doesn't have a null terminator, namely the
'\0'?
Thanks a lot
Roy

[CBFalconer]

Lawrence Kirby wrote:

On Thu, 28 Apr 2005 16:58:56 -0400, Joe Wright wrote:

.... snip ...

Show us a case where (p - s) can be out-of-bounds.

Instead think of a 16 bit system where size_t and ptrdiff_t are
16 bits wide. It would be permissible for a string to be up to
65534 characters plus the null character on that implementation
but anything above 32767 can cause problems for ptrdiff_t. 32768
is long for a string but not beyond the bounds of possibility.

size_t must be able to represent the size of any object (although
some debate is possible for calloc()). However C provides no
corresponding guarantee that ptrdiff_t can represent the
difference of any 2 pointers to elements of the same array.

Alright, you have finally convinced me. So this means that strlen
actually has to be a system function.

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

[Keith Thompson]

CBFalconer <cb********@yah oo.com> writes:

Lawrence Kirby wrote:

On Thu, 28 Apr 2005 16:58:56 -0400, Joe Wright wrote:

... snip ...

Show us a case where (p - s) can be out-of-bounds.

Instead think of a 16 bit system where size_t and ptrdiff_t are
16 bits wide. It would be permissible for a string to be up to
65534 characters plus the null character on that implementation
but anything above 32767 can cause problems for ptrdiff_t. 32768
is long for a string but not beyond the bounds of possibility.

size_t must be able to represent the size of any object (although
some debate is possible for calloc()). However C provides no
corresponding guarantee that ptrdiff_t can represent the
difference of any 2 pointers to elements of the same array.

Alright, you have finally convinced me. So this means that strlen
actually has to be a system function.

No, it just means that the (p - s) method isn't strictly portable.

size_t strlen(const char *s)
{
size_t result = 0;
const char *p = s;
while (*p++ != '\0') {
result ++;
}
return result;
}

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

Keith Thompson wrote:

CBFalconer <cb********@yah oo.com> writes:

Lawrence Kirby wrote:

On Thu, 28 Apr 2005 16:58:56 -0400, Joe Wright wrote:

... snip ...

Show us a case where (p - s) can be out-of-bounds.

Instead think of a 16 bit system where size_t and ptrdiff_t are
16 bits wide. It would be permissible for a string to be up to
65534 characters plus the null character on that implementation
but anything above 32767 can cause problems for ptrdiff_t. 32768
is long for a string but not beyond the bounds of possibility.

size_t must be able to represent the size of any object (although
some debate is possible for calloc()). However C provides no
corresponding guarantee that ptrdiff_t can represent the
difference of any 2 pointers to elements of the same array.

Alright, you have finally convinced me. So this means that strlen
actually has to be a system function.

No, it just means that the (p - s) method isn't strictly portable.

size_t strlen(const char *s)
{
size_t result = 0;
const char *p = s;
while (*p++ != '\0') {
result ++;
}
return result;
}

One should bear in mind that we all know where to find
real strlen when we need it, and that these posted strlen
defintions aren't meant to be competitive in terms of performance.

Writing standard library functions in C,
and merely getting it right, brings up various C topics.

Do you not like to increment the s parameter directly?
Some people don't like to change the values of parameters.
I prefer to change them whenever it's handy.

size_t strlen(const char *s)
{
size_t n;

for (n = 0; *s != '\0'; ++s) {
++n;
}
return n;
}

--
pete

[Keith Thompson]

pete <pf*****@mindsp ring.com> writes:

Keith Thompson wrote: [...]

size_t strlen(const char *s)
{
size_t result = 0;
const char *p = s;
while (*p++ != '\0') {
result ++;
}
return result;
}

One should bear in mind that we all know where to find
real strlen when we need it, and that these posted strlen
defintions aren't meant to be competitive in terms of performance.

Of course.
Writing standard library functions in C,
and merely getting it right, brings up various C topics.
Sure. The issue (or at least *an* issue) is why certain functions are
included in the C standard library. In many cases it's just arbitrary
historical precedent; a C library designed from scratch would probably
look very different from what we have now. Some functions are in the
C library because they can't be implemented portably (and library
implementers are not constrained to write portable code); the
offsetof() macro is a good example, as are most of the functions in
<stdio.h>. Other functions are in the standard library just because
they're convenient. Many of them *can* be implemented perfectly
portably, but it's nice that not every program has to provide its own
strlen() function -- and in some cases the implementer can provide a
non-portable version with improved performance.
Do you not like to increment the s parameter directly?
Some people don't like to change the values of parameters.
I prefer to change them whenever it's handy.

size_t strlen(const char *s)
{
size_t n;

for (n = 0; *s != '\0'; ++s) {
++n;
}
return n;
}

Yes, that's a good solution (probably a little better than mine).

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

pete wrote:

.... snip ...
One should bear in mind that we all know where to find real
strlen when we need it, and that these posted strlen defintions
aren't meant to be competitive in terms of performance.

Writing standard library functions in C,
and merely getting it right, brings up various C topics.

Do you not like to increment the s parameter directly?
Some people don't like to change the values of parameters.
I prefer to change them whenever it's handy.

size_t strlen(const char *s)
{
size_t n;

for (n = 0; *s != '\0'; ++s) {
++n;
}
return n;
}

Even so, I think I would prefer to write:

inline size_t strlen(const char *s)
{
size_t n;

for (n = 0; *s++;) ++n;
return n;
}

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

[Tim Rentsch]

pete <pf*****@mindsp ring.com> writes:

Keith Thompson wrote:

[how might strlen be implemented portably...]

size_t strlen(const char *s)
{
size_t result = 0;
const char *p = s;
while (*p++ != '\0') {
result ++;
}
return result;
}

One should bear in mind that we all know where to find
real strlen when we need it, and that these posted strlen
defintions aren't meant to be competitive in terms of performance.

Writing standard library functions in C,
and merely getting it right, brings up various C topics.

Do you not like to increment the s parameter directly?
Some people don't like to change the values of parameters.
I prefer to change them whenever it's handy.

size_t strlen(const char *s)
{
size_t n;

for (n = 0; *s != '\0'; ++s) {
++n;
}
return n;
}

Normally I prefer parameters to retain their original values and
introduce new variables instead. I'm willing to break the rule
but in the absence of a compelling reason I usually don't.

In this case though it doesn't have to come up. Sometimes the
most straightforward code is best:

size_t
strlen( const char *s ){
size_t n=0;

while( s[n] ) n++;
return n;
}

This implementation ran faster in my tests than any of the
pointer versions posted.

[Flash Gordon]

Tim Rentsch wrote:

<snip - portable code to implement strlen>

In this case though it doesn't have to come up. Sometimes the
most straightforward code is best:

size_t
strlen( const char *s ){
size_t n=0;

while( s[n] ) n++;
return n;
}

This implementation ran faster in my tests than any of the
pointer versions posted.

Personally I would probably do the following, since there is
initialisation, condition and increment. Purely as a matter of taste,
not correctness.

size_t strlen( const char *s )
{
size_t n;
for (n=0; s[n]; n++)
continue;
return n;
}

--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Alberto Giménez]

El Sat, 30 Apr 2005 17:03:47 +0100, Flash Gordon escribió:

size_t strlen( const char *s )
{
size_t n;
for (n=0; s[n]; n++)
continue;
return n;
}

I wonder if that 'continue' is required. Wouldn't a simple null
statement ';' do the work?

for (n=0; s[n]; n++)
; /* continue */
Greetings.
--
Luis Alberto Giménez
JabberID: Si*******@bulma lug.net
GnuPG ID: 0x3BAABDE1

[Keith Thompson]

Alberto Giménez <al****@telelin e.es> writes:

El Sat, 30 Apr 2005 17:03:47 +0100, Flash Gordon escribió:

size_t strlen( const char *s )
{
size_t n;
for (n=0; s[n]; n++)
continue;
return n;
}

I wonder if that 'continue' is required. Wouldn't a simple null
statement ';' do the work?

for (n=0; s[n]; n++)
; /* continue */

Yes, in this context, an empty statement ";" is exactly equivalent to
"continue;" . The "continue" statement is just more explicit; a lone
";" is easy to miss.

I note that you felt it necessary to add a comment; as long as you're
doing that, why not use the "continue" keyword?

I would probably have written it as:

for (n=0; s[n]; n++) {
;
}

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Tim Rentsch]

Flash Gordon <sp**@flash-gordon.me.uk> writes:

Tim Rentsch wrote:

<snip - portable code to implement strlen>

In this case though it doesn't have to come up. Sometimes the
most straightforward code is best:

size_t
strlen( const char *s ){
size_t n=0;

while( s[n] ) n++;
return n;
}

This implementation ran faster in my tests than any of the
pointer versions posted.

Personally I would probably do the following, since there is
initialisation, condition and increment. Purely as a matter of taste,
not correctness.

size_t strlen( const char *s )
{
size_t n;
for (n=0; s[n]; n++)
continue;
return n;
}

Normally I expect 'for' statements are used when iterating over known
quantities; also they usually "do" something with each element
iterated over. Of course these conditions needn't be true but most
often they are. So the for loop here seems a little off.

On the other hand, 'while' statements are often used to establish
postconditions. The code

n = 0;
while( s[n] ) n++;

clearly establishes the postcondition

s[n] == 0 && s[k] != 0 for 0 <= k < n

which is more or less the definition for 'n' being the length of the
string 's'. (Initializing 'n' on its declaration is just a convenient
shortening of an initializing expression.)

Certainly you're right that operationally the two functions are
equivalent. It just seems to be a little more mental effort to be
sure that the 'for' code is doing the right thing - it's less clear
or less obvious or perhaps both. For these reasons I tend to favor
the 'while' form here.