re-entrant function????????

[Lawrence Kirby]

Re: re-entrant function??????? ?

On Wed, 12 Jan 2005 02:42:29 +0000, Neil Kurzman wrote:
[color=blue]
>
>
> thesushant@redi ffmail.com wrote:
>[color=green]
>> hi,
>>
>> can anyone of C masters siting out there suggest any 1 example of
>> re-entrnt function just to show what is the significance of that
>> property and how we can exploit it ....
>>
>> sushant[/color]
>
> Look up the "tower of Honoi " The computer solution is very simple if
> recursion is used.
> recursive function are re-entrant.[/color]

Sometimes they are, but not always. Recursive functions call themselves
under very controlled circumstances. Reentrancy is a more general
principle than that.
[color=blue]
> Otherwise function used by multitasking, multithread, and interrupts
> may have to be re-entrant.
> since they may be paused in the middle and then call again.[/color]

Or maybe executed my multiple threads simultaneously.

Lawrence

[Guillaume]

Re: re-entrant function??????? ?

>>recursive function are re-entrant.[color=blue]
>
>
> Sometimes they are, but not always.[/color]

Huh? Give me one example of a recursive function that is not reentrant.
By definition, a recursive function will call itself at one point;
which makes it reentrant.
[color=blue]
> Recursive functions call themselves
> under very controlled circumstances.[/color]

Which doesn't make them any more non-reentrant. ;-)
[color=blue]
> Reentrancy is a more general
> principle than that.[/color]

That's right, of course! You named the multithreading case.
But there is more. A function can become recursive in a non-obvious
way (and that is one pitfall that some programmers will fall into
at one point or another): if it calls a function that calls another
function that... that ends up calling the first function.

In some programming languages, it could also be as simple as a
function calling itself in one of its arguments, such as:

array(array(1, 2), 3)

in some language that would construct a multi-dimensional array.

C does evaluate all of the arguments before calling the function, but
not all languages are like that.

[Xenos]

Re: re-entrant function??????? ?


"Guillaume" <"grsNOSPAM at NOTTHATmail dot com"> wrote in message
news:41e55fc5$0 $23340$7a628cd7 @news.club-internet.fr...[color=blue][color=green][color=darkred]
> >>recursive function are re-entrant.[/color]
> >
> >
> > Sometimes they are, but not always.[/color]
>
> Huh? Give me one example of a recursive function that is not reentrant.
> By definition, a recursive function will call itself at one point;
> which makes it reentrant.
>[/color]
void foo()
{
static int i = 10;

/* do wacky stuff here */

if (--i > 0)
foo();
}

this ugly function is recursive, but not reentrant.

[Chris Torek]

Re: re-entrant function??????? ?

In article <41e55fc5$0$233 40$7a628cd7@new s.club-internet.fr>
Guillaume <"grsNOSPAM at NOTTHATmail dot com"> wrote:[color=blue]
>Huh? Give me one example of a recursive function that is not reentrant.[/color]

It is easy to construct an artificial example, although this sort
of thing is much less likely to occur in real code.
[color=blue]
>By definition, a recursive function will call itself at one point;
>which makes it reentrant.[/color]

Not necessarily. Here is one example:

void pointless(int recurselevel, unsigned char c) {
static char *p;

if (recurselevel == 0)
p = malloc(UCHAR_MA X + 1);
if (c == 'Z') {
p[recurselevel] = '\0';
puts(p);
free(p);
} else {
p[recurselevel] = c;
pointless(recur selevel + 1, c + 1);
}
}
[color=blue][color=green]
>> Recursive functions call themselves
>> under very controlled circumstances.[/color][/color]
[color=blue]
>Which doesn't make them any more non-reentrant. ;-)[/color]

Unless, by accident or (as above) on purpose, they do something
"non-reentrant" at certain recursion levels.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Guillaume]

Re: re-entrant function??????? ?

> void foo()[color=blue]
> {
> static int i = 10;
>
> /* do wacky stuff here */
>
> if (--i > 0)
> foo();
> }
>
> this ugly function is recursive, but not reentrant.[/color]

It is reentrant, since it will reenter itself while still being inside
itself at a higher level. Whether it's harmful or not in this special
case is another story entirely. I don't see your point?

What is your definition of reentrancy?

[Alan Balmer]

Re: re-entrant function??????? ?

On Wed, 12 Jan 2005 22:10:50 +0100, Guillaume <"grsNOSPAM at
NOTTHATmail dot com"> wrote:
[color=blue][color=green]
>> void foo()
>> {
>> static int i = 10;
>>
>> /* do wacky stuff here */
>>
>> if (--i > 0)
>> foo();
>> }
>>
>> this ugly function is recursive, but not reentrant.[/color]
>
>It is reentrant, since it will reenter itself while still being inside
>itself at a higher level.[/color]
Sounds like a definition of recursive, not reentrant.
[color=blue]
> Whether it's harmful or not in this special
>case is another story entirely. I don't see your point?
>[/color]
By that definition, all functions are reentrant, since they can be
called twice.
[color=blue]
>What is your definition of reentrancy?[/color]

http://en.wikipedia.org/wiki/Reentrant

--
Al Balmer
Balmer Consulting
removebalmercon sultingthis@att .net

[Xenos]

Re: re-entrant function??????? ?


"Guillaume" <"grsNOSPAM at NOTTHATmail dot com"> wrote in message
news:41e59259$0 $23332$7a628cd7 @news.club-internet.fr...[color=blue][color=green]
> > void foo()
> > {
> > static int i = 10;
> >
> > /* do wacky stuff here */
> >
> > if (--i > 0)
> > foo();
> > }
> >
> > this ugly function is recursive, but not reentrant.[/color]
>
> It is reentrant, since it will reenter itself while still being inside
> itself at a higher level. Whether it's harmful or not in this special
> case is another story entirely. I don't see your point?
>
> What is your definition of reentrancy?[/color]
Just because the function calls itself does not make it reentrant. If it
were, it could be called by multiple threads, interrupts or whatever without
them affecting any other invocation. That is not the same as recursion.

[Keith Thompson]

Re: re-entrant function??????? ?

Guillaume <"grsNOSPAM at NOTTHATmail dot com"> writes:[color=blue][color=green][color=darkred]
>>>recursive function are re-entrant.[/color]
>> Sometimes they are, but not always.[/color]
>
> Huh? Give me one example of a recursive function that is not reentrant.
> By definition, a recursive function will call itself at one point;
> which makes it reentrant.[/color]

Here's a contrived example:

#include <stdio.h>

static int recursive_but_n ot_reentrant(in t n)
{
static int count = 0;
if (n <= 0) {
return count;
}
else {
count ++;
return recursive_but_n ot_reentrant(n - 1);
}
}

int main(void)
{
printf("recursi ve_but_not_reen trant(10) = %d\n",
recursive_but_n ot_reentrant(10 ));
printf("recursi ve_but_not_reen trant(10) = %d\n",
recursive_but_n ot_reentrant(10 ));
return 0;
}

Output:

recursive_but_n ot_reentrant(10 ) = 10
recursive_but_n ot_reentrant(10 ) = 20

--
Keith Thompson (The_Other_Keit h) kst-u@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.

[Keith Thompson]

Re: re-entrant function??????? ?

Alan Balmer <albalmer@att.n et> writes:[color=blue]
> On Wed, 12 Jan 2005 22:10:50 +0100, Guillaume <"grsNOSPAM at
> NOTTHATmail dot com"> wrote:[/color]
[...][color=blue][color=green]
>>What is your definition of reentrancy?[/color]
> http://en.wikipedia.org/wiki/Reentrant[/color]

<http://wombat.doc.ic.a c.uk/foldoc/foldoc.cgi?quer y=reentrant&act ion=Search>
is also a good definition (and probably more relevant to the current
discussion).

--
Keith Thompson (The_Other_Keit h) kst-u@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.

[Richard Tobin]

Re: re-entrant function??????? ?

In article <41e59259$0$233 32$7a628cd7@new s.club-internet.fr>,
Guillaume <"grsNOSPAM at NOTTHATmail dot com"> wrote:
[color=blue]
>It is reentrant, since it will reenter itself while still being inside
>itself at a higher level.[/color]

Usage varies, but re-entrant is commonly used to refer to code that
can safely be re-entered at any time (subject perhaps to locks). A
function that re-enters itself from certain fixed points (ie a recursive
function) may not be safely callable from another thread, and so may
not be re-entrant by this definition.

There doesn't even need another thread to be involved. Consider
a function sort() that works recursively, by calling itself on parts
of the array of items to sort. Such a function might not be designed
to work if the user-supplied comparison function itself calls sort(),
in which case it would not be re-entrant.

-- Richard

[Guillaume]

Re: re-entrant function??????? ?

> Usage varies, but re-entrant is commonly used to refer to code that[color=blue]
> can safely be re-entered at any time (subject perhaps to locks). A
> function that re-enters itself from certain fixed points (ie a recursive
> function) may not be safely callable from another thread, and so may
> not be re-entrant by this definition.[/color]

Ok with that, I think we weren't using the same definition. Now this is
clearer.

By that definition, non-reentrant recursive functions are often
ill-written (making too much assumptions about how they are going to
run), but that could lead to another debate.

[Chris Croughton]

Re: re-entrant function??????? ?

On Thu, 13 Jan 2005 02:13:07 +0100, Guillaume
<> wrote:
[color=blue][color=green]
>> Usage varies, but re-entrant is commonly used to refer to code that
>> can safely be re-entered at any time (subject perhaps to locks). A
>> function that re-enters itself from certain fixed points (ie a recursive
>> function) may not be safely callable from another thread, and so may
>> not be re-entrant by this definition.[/color]
>
> Ok with that, I think we weren't using the same definition. Now this is
> clearer.[/color]

The implied word is 'safely', any function by your definition is
re-entrant but only some are safely re-entrant (have predictable
and defined behaviour even if they are called before they complete). In
the standard library, for instance, strtok and qsort are two which are
not safely re-entrant (strtok is even worse, it can't be called safely
even if it has completed execution, it's a terrible function). The
strerror function isn't safely re-entrant because it uses a static
buffer to store the returned string.
[color=blue]
> By that definition, non-reentrant recursive functions are often
> ill-written (making too much assumptions about how they are going to
> run), but that could lead to another debate.[/color]

If they aren't designed and documented as such, it can lead to errors.
However, there are a number of situations where that functionality is
desired. A number of top-down recursive parsers, for instance, use
global data because the overhead in complexity of passing the
environment around is not worth it.

Chris C

[Lawrence Kirby]

Re: re-entrant function??????? ?

On Tue, 11 Jan 2005 17:27:00 -0800, E. Robert Tisdale wrote:

....
[color=blue]
> The ANSI/ISO standards do *not* guarantee
> that the first example above will be reentrant.[/color]

It does to the extent that signal handlers create reentrancy issues and
code that follows the rules still has to work when executed in a signal
handler.
[color=blue]
> Implementations are allowed to copy local variables into static storage
> where they may be corrupted by other threads but, to my knowledge, there
> are no viable ANSI/ISO compliant implementations which do so. So the
> first example is, in *fact*, thread safe.[/color]

The possibility of recursion/mutual recursion also limits the compiler's
freedom in doing this. The fact is though that standard C doesn't support
miltithreading. It only makes sense to talk about reentrancy issues for
multithreading in the context of a particular multithreading environment.
For example there is nothing to stop a threading environment making all
normal C static objects per thread objects and limiting normal C
pointers to objects created in that thread. This makes everything
thread safe including strtok() with just some issues for shared external
resources like files. Such a threading implementation would presumably
provide a different mechanism for shared objects. Processes (in the Unix
sense) do that, but it could also be done in an environment where threads
share the same address space. This may not happen much in practice but
shows why thread safety in a standard C context is a meaningless
discussion, it is all down to the details of the multithreading
environment.

Lawrence

[Guillaume]

Re: re-entrant function??????? ?

Chris Croughton wrote:[color=blue]
> the standard library, for instance, strtok and qsort are two which are
> not safely re-entrant (strtok is even worse, it can't be called safely[/color]

Thanks for pointing that out! I did know about strtok, but I didn't know
qsort was not safely reentrant... (I guess on some particular
implementation, it can be.)

That means if we need to sort stuff in a multithreading application,
qsort is usually not an option? Bummers!
[color=blue]
> desired. A number of top-down recursive parsers, for instance, use
> global data because the overhead in complexity of passing the
> environment around is not worth it.[/color]

That's true, although I've written parsers before that did pass the
whole "parsing environment" as a pointer to a dynamically-allocated
structure. The overhead is not that bad.

[Lawrence Kirby]

Re: re-entrant function??????? ?

On Thu, 13 Jan 2005 17:35:05 +0100, Guillaume wrote:
[color=blue]
> Chris Croughton wrote:[color=green]
>> the standard library, for instance, strtok and qsort are two which are
>> not safely re-entrant (strtok is even worse, it can't be called safely[/color]
>
> Thanks for pointing that out! I did know about strtok, but I didn't know
> qsort was not safely reentrant... (I guess on some particular
> implementation, it can be.)
>
> That means if we need to sort stuff in a multithreading application,
> qsort is usually not an option? Bummers![/color]

No, it means you have to look to the guarantees provided by the
multithreading environment to see if it is. That is true for nearly all of
the standard C library functions, if not all of them.

Lawrence