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.com, 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********@yahoo.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_Keith) 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********@yahoo.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*****@mindspring.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_Keith) 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.com, 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*****@mindspring.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*******@bulmalug.net
GnuPG ID: 0x3BAABDE1

[Keith Thompson]

Alberto Giménez <al****@teleline.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_Keith) 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.

[pete]

Tim Rentsch wrote:

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

My preferences for while loop vs. for loop, tends to go
according to aesthetics which I don't consider to be
related to style, in the sense that "good programming style"
means enhanced maintainability.

I think that for loops look funny when they have
empty expressions or statements.

I think your originally posted function definition
was only busy enough to fill up a while loop.
while( s[n] ) n++;

My preference for a loop to do something N times,
is a count down while loop.

void do_something_N_times(unsigned n)
{
while (n-- != 0) {
/* do something */
}
}

Always using a compound statement as a loop body,
*is* something that I consider to be a style issue.

--
pete

[Michael Wojcik]

Y'know, I'm a bit disappointed no one's proposed the elegant:

static size_t strlen_c(const char *s, size_t c){
return *s? strlen_c(s+1, c+1) : c;
}

size_t strlen(const char *s) {
return strlen_c(s, 0);
}

:-)

If your implementation optimizes tail recursion, this could even
produce reasonable code (for a normal C routine; usually for strlen
the implementor has other, better tricks available). Sometimes I
miss Scheme.

--
Michael Wojcik mi************@microfocus.com

I will shoue the world one of the grate Wonders of the world in 15
months if Now man mourders me in Dors or out Dors
-- "Lord" Timothy Dexter, _A Pickle for the Knowing Ones_

[Richard Tobin]

In article <d5********@news1.newsguy.com>,
Michael Wojcik <mw*****@newsguy.com> wrote:

Y'know, I'm a bit disappointed no one's proposed the elegant:

static size_t strlen_c(const char *s, size_t c){
return *s? strlen_c(s+1, c+1) : c;
}

size_t strlen(const char *s) {
return strlen_c(s, 0);
}

Because it's not elegant!

size_t strlen(const char *s)
{
return *s ? strlen(s+1) + 1 : 0;
}

would be elegant, but unfortunately not tail-recursive.

-- Richard

[Michael Wojcik]

In article <d5**********@pc-news.cogsci.ed.ac.uk>, ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:

In article <d5********@news1.newsguy.com>,
Michael Wojcik <mw*****@newsguy.com> wrote:

Y'know, I'm a bit disappointed no one's proposed the elegant:

static size_t strlen_c(const char *s, size_t c){
return *s? strlen_c(s+1, c+1) : c;
}

size_t strlen(const char *s) {
return strlen_c(s, 0);
}

Because it's not elegant!

size_t strlen(const char *s)
{
return *s ? strlen(s+1) + 1 : 0;
}

would be elegant, but unfortunately not tail-recursive.

"Would be elegant"? Please! It is or (as in your example) is not.
I would be phenomenally wealthy, but unfortunately I don't possess
absurd amounts of money.

On the other hand, my strlen_c is elegant, and strlen is an elegant
wrapper for it. In accordance with the property of distributive
elegance, that makes my entire proposal elegant.

(This is probably sufficiently silly now.)

On a more serious note, I think continuation-passing style is quite
elegant, when done right. What do you have against it?

--
Michael Wojcik mi************@microfocus.com

Recently, they appeared at the reopening of the Brookdale Library,
luring passersby with the opportunity to be anonymously silly.

[pete]

Michael Wojcik wrote:

In article <d5**********@pc-news.cogsci.ed.ac.uk>, ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:

In article <d5********@news1.newsguy.com>,
Michael Wojcik <mw*****@newsguy.com> wrote:

Y'know, I'm a bit disappointed no one's proposed the elegant:

static size_t strlen_c(const char *s, size_t c){
return *s? strlen_c(s+1, c+1) : c;
}

size_t strlen(const char *s) {
return strlen_c(s, 0);
}

Because it's not elegant!

size_t strlen(const char *s)
{
return *s ? strlen(s+1) + 1 : 0;
}

would be elegant, but unfortunately not tail-recursive.

"Would be elegant"? Please! It is or (as in your example) is not.
I would be phenomenally wealthy, but unfortunately I don't possess
absurd amounts of money.

On the other hand, my strlen_c is elegant, and strlen is an elegant
wrapper for it. In accordance with the property of distributive
elegance, that makes my entire proposal elegant.

(This is probably sufficiently silly now.)

On a more serious note, I think continuation-passing style is quite
elegant, when done right. What do you have against it?

It seems overly complicated.

size_t strlen(const char *s)
{
return *s ? strlen(s + 1) + 1 : 0;
}

--
pete

[pete]

pete wrote:

Michael Wojcik wrote:

In article <d5**********@pc-news.cogsci.ed.ac.uk>, > > ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:

size_t strlen(const char *s)
{
return *s ? strlen(s+1) + 1 : 0;
}

size_t strlen(const char *s)
{
return *s ? strlen(s + 1) + 1 : 0;
}

I wasn't paying attention.

--
pete

[Richard Tobin]

In article <d5*********@news1.newsguy.com>,
Michael Wojcik <mw*****@newsguy.com> wrote:

On a more serious note, I think continuation-passing style is quite
elegant, when done right. What do you have against it?

I think it's wonderful. In fact, I like compilers that translate all
my code into it.

-- Richard