Procedure for eliminating static variables?

[Mr. Ed]

This should be easy, but I can't immediately see what the answer is...

I have some code which needs to be re-entrant. It also needs to create
a unique identifier. The obvious way to create a unique ID is to
maintain a static counter, and to increment it each time it's needed.
Any ideas on how to do this in a re-entrant way?

I don't call this code (it's Yacc output), so I can't suppy anything
on the stack.

Cheers

Ed

 

[Giorgos Keramidas]

This should be easy, but I can't immediately see what the answer is...

I have some code which needs to be re-entrant. It also needs to create
a unique identifier. The obvious way to create a unique ID is to
maintain a static counter, and to increment it each time it's needed.
Any ideas on how to do this in a re-entrant way?

This is OT here.

It's also a bad method for generating unique IDs. Just as food for
thought, what happens when your program restarts? Do the "unique" IDs
roll back to an already used value?

 

[Victor Bazarov]

This is OT here.

Where? And why?

[..]

 

[Mr. Ed]

This is OT here.

It's C, so it seems to me to be ideal for c.l.c.

It's also a bad method for generating unique IDs.

It's the simplest possible way to 'uniquify' multiple instances of an
object.

Just as food for
thought, what happens when your program restarts? Do the "unique" IDs
roll back to an already used value?

Yes. They only need to be unique for a program run.

Ed

 

[Eric Sosman]

It's C, so it seems to me to be ideal for c.l.c.




It's the simplest possible way to 'uniquify' multiple instances of an
object.




Yes. They only need to be unique for a program run.

If you mean "re-entrant" in the strictest sense, C can't
help you. C's notion of simultaneous execution covers only
the very limited case of signal handlers, and the scope of
things you can do inside an asynchronously-invoked signal
handler is quite narrow. For example, it's not safe to call
malloc() to obtain memory in which to store the new unique
identifier.

If you mean "re-entrant" as "thread-safe," C itself has
no support for threads. Various platforms add their own thread
support to what C provides, and comp.programming.threads is a
good place to discuss what's available. <ot> Stick a mutex
around the increment-and-read of the static variable, and you'll
probably be all set. </ot>

If you mean "re-entrant" as "safe for recursive use," all
is well without any further effort on your part: just use the
static variable and be happy.

 

[tedu]

This should be easy, but I can't immediately see what the answer is...

I have some code which needs to be re-entrant. It also needs to create
a unique identifier. The obvious way to create a unique ID is to
maintain a static counter, and to increment it each time it's needed.
Any ideas on how to do this in a re-entrant way?

Assuming you're not using threads and just need to support recursive
calls,
why wouldn't this work?

int get_unique_id() { static int id; return ++id }

 

[Anonymous 7843]

This should be easy, but I can't immediately see what the answer is...

I have some code which needs to be re-entrant. It also needs to create
a unique identifier. The obvious way to create a unique ID is to
maintain a static counter, and to increment it each time it's needed.
Any ideas on how to do this in a re-entrant way?

I don't call this code (it's Yacc output), so I can't suppy anything
on the stack.

Yacc output is normally not re-entrant; you may have larger
problems than you realize.

If you are using a threading library, then there is probably
a mutex function available. If you are *not* using a threading
library then all forms of C re-entrancy would be compatible
with a single non-recursive function that increments a static
variable.

In another message you indicated that the uniqueness is only
needed during the lifetime of the program. An alternative way
of achieving this is to use the addresses of the objects as the
"unique" thing.

 

[John Bode]

It's C, so it seems to me to be ideal for c.l.c.

If it's a question about the C language itself, then it's ideal for
c.l.c. If it's a question of "how do I do X in C," it may or may not
be topical depending on X. For example, "how do I mask out a value in
a bit string" is topical for clc. "How do I clear the screen" is not.


The solution to your problem is some sort of semaphore or mutex to
serialize access to a critical resource. Since C does not provide any
language-level support for this, it is beyond the scope of the C
language itself, and hence this newsgroup. Google on "mutex" and your
particular platform, e.g., "mutex windows", and you should get
something useful.

[snip rest]

 

[Giorgos Keramidas]

Where? And why?

I realized I failed to specify "where". I meant in comp.lang.c, because
there is no explicit notion of "reentrancy" in the standard.

 

[Victor Bazarov]

I realized I failed to specify "where". I meant in comp.lang.c, because
there is no explicit notion of "reentrancy" in the standard.

I am not sure what you consider "explicit". The C standard does say that
library functions are not reentrant, for example. From that I can only
conclude that the concept of "reentrancy" is considered _external_ to the
C Standard (and to C++ Standard AFAICT).

V

 

[Mr. Ed]

Wow - I hadn't realised that my use of a forbidden word would stir up
such a hornet's nest. Perhaps I could rephrase the problem in an
acceptable manner. Assume that I have a routine that does this:

int get_unique_id() { static int id; return ++id }

Now, also assume that for ideological reasons, I don't like to use
static variables. If you like, you can also imagine that I am
executing in an environment in which the keyword 'static' ensures that
this code won't work; it doesn't matter whether this is actually the
case, or why it won't work if this does happen to be the case.

Problem: is there a way to reformulate 'get_unique_id' so that:

1) 'id' is not in static storage; it should be on the stack somewhere

2) 'id' retains a memory of its value between function calls

3) The interface to 'get_unique_id' is unchanged

At first sight, this doesn't seem to be possible. The only obvious
solution is for the caller to save the current 'id' on their own
stack, and for 'get_unique_id' to increment it, but this isn't
possible because of constraint (3).

Any ideas?

Cheers

Ed

 

[Victor Bazarov]

Wow - I hadn't realised that my use of a forbidden word would stir up
such a hornet's nest. Perhaps I could rephrase the problem in an
acceptable manner. Assume that I have a routine that does this:




Now, also assume that for ideological reasons, I don't like to use
static variables. If you like, you can also imagine that I am
executing in an environment in which the keyword 'static' ensures that
this code won't work; it doesn't matter whether this is actually the
case, or why it won't work if this does happen to be the case.

Problem: is there a way to reformulate 'get_unique_id' so that:

1) 'id' is not in static storage; it should be on the stack somewhere

If it's on the stack, the only way to get to it would be to have its
address passed to this function. The "somewhere" makes it impossible
to do otherwise. However, that would go against the requirement 3 (the
interface is unchanged).

2) 'id' retains a memory of its value between function calls

That requires its location to be outside of any memory area that can
inadvertently be affected by functions being called or returning to
their caller. That essentially puts it _outside_ the stack. Now your
two requirements (1 and 2) are conflicting.

3) The interface to 'get_unique_id' is unchanged

At first sight, this doesn't seem to be possible. The only obvious
solution is for the caller to save the current 'id' on their own
stack, and for 'get_unique_id' to increment it, but this isn't
possible because of constraint (3).

Any ideas?

Nope.

You could have a bit more sophisticated mechanism if you needed counting
within each thread, but that falls outside the scope of the language since
it would require to obtain a thread id or some other thread-specific value
which you could use to store/retrieve the counter values in/from some kind
of a hash table (which itself will need to be static+dynamic).

V

P.S. I left the cross-posting to conjure the help of the colleagues from
the c.l.c group (which I don't visit any more). If that's contrary to the
rules, I apologize.

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

Now, also assume that for ideological reasons, I don't like to use
static variables. If you like, you can also imagine that I am
executing in an environment in which the keyword 'static' ensures that
this code won't work; it doesn't matter whether this is actually the (...)
Any ideas?

The better idea may be to not imagine nonsenses and tell what the real
problem is. And if it is off-topic, to ask in other place.

 

[Gordon Burditt]

Wow - I hadn't realised that my use of a forbidden word would stir up

such a hornet's nest. Perhaps I could rephrase the problem in an
acceptable manner. Assume that I have a routine that does this:

One method that works for getting rid of static variables is to
make a struct containing all these variables. Call this a "context".
Pass a pointer to the context to all the functions that use them.
You may need a function to initialize a context. And if your
function requires that there be *ONLY ONE* context, you have to
arrange to pass it around.

Now, also assume that for ideological reasons, I don't like to use
static variables. If you like, you can also imagine that I am
executing in an environment in which the keyword 'static' ensures that
this code won't work;

It is more reasonable to assume that you are working in an environment
in which use of the keyword 'static' ensures that you will be fired.

it doesn't matter whether this is actually the
case, or why it won't work if this does happen to be the case.

Problem: is there a way to reformulate 'get_unique_id' so that:

1) 'id' is not in static storage; it should be on the stack somewhere

2) 'id' retains a memory of its value between function calls

3) The interface to 'get_unique_id' is unchanged

Is using a global variable containing a pointer to 'id' (which is
an auto variable in main() or something, and therefore "on the stack
somewhere" in many implementations) acceptable? In most cases, if
you hate static, global variables are even worse.

My "context" approach is ruled out by (3).

At first sight, this doesn't seem to be possible. The only obvious
solution is for the caller to save the current 'id' on their own
stack, and for 'get_unique_id' to increment it, but this isn't
possible because of constraint (3).

Gordon L. Burditt

 

[Eric Sosman]

Wow - I hadn't realised that my use of a forbidden word would stir up
such a hornet's nest. Perhaps I could rephrase the problem in an
acceptable manner. Assume that I have a routine that does this:




Now, also assume that for ideological reasons, I don't like to use
static variables. If you like, you can also imagine that I am
executing in an environment in which the keyword 'static' ensures that
this code won't work; it doesn't matter whether this is actually the
case, or why it won't work if this does happen to be the case.

Problem: is there a way to reformulate 'get_unique_id' so that:

1) 'id' is not in static storage; it should be on the stack somewhere

2) 'id' retains a memory of its value between function calls

3) The interface to 'get_unique_id' is unchanged

At first sight, this doesn't seem to be possible. The only obvious
solution is for the caller to save the current 'id' on their own
stack, and for 'get_unique_id' to increment it, but this isn't
possible because of constraint (3).

Any ideas?

How about an idea for an impossibility proof? Would that
make you happier? Here's a sketch:

Because the function is forbidden to use static variables
(by which I assume you mean "objects with static storage
duration, whether or not the `static' keyword is used"), it
can only access its own arguments and its own `auto' and
`register' variables. By constraint (3) there are no arguments,
and the other two possibilities do not meet the requirements
of constraint (2).

Dynamically-allocated storage won't help, because to make
use of its persistence (until freed) you'd need to communicate
a pointer value from one function invocation to another. The
argument above shows that no suitable channel exists -- and
besides: we know you're looking for re-entrancy, and malloc()
is not re-entrant. Nor, for that matter, are time() and clock()
and getc() and getenv() and any other Standard C library functions
you might use to query the state of the universe. No, not even
rand() is available.

You could form a pointer to an `auto' variable and try to
deduce something about the state of the stack. However, the C
Standard doesn't guarantee that `auto' variables reside on "the"
stack, nor even on "a" stack (although it's common implementation
practice). Besides, the only thing you can do with a pointer to
an `auto' variable is use it to refer to that variable, and do
a little simple arithmetic on the pointer -- the moment you start
trying to probe outside the `auto' variable itself, you're in the
land of undefined behavior. You certainly cannot use a pointer
to an `auto' variable to somehow locate a variable that belongs
to some caller somewhere.

So: Are you going to look for other approaches (several
have been suggested, but you're being so coy about your intent
that it's hard to choose between them), or are you going to
keep on trying to pound nails with a hacksaw?

 

[Anonymous 7843]

Problem: is there a way to reformulate 'get_unique_id' so that:

1) 'id' is not in static storage; it should be on the stack somewhere

2) 'id' retains a memory of its value between function calls

3) The interface to 'get_unique_id' is unchanged

Any ideas?

On many architectures the stack exists as plain old memory. You could
create a function that scans for a pre-arranged pattern of bytes lower
on the stack. When it finds the pattern, it looks immediately above
that for the counter. Not exactly efficent, or conforming, or
anything. Merely possible.

 

[Richard Tobin]

I have some code which needs to be re-entrant. It also needs to create
a unique identifier.

Standard C does not support re-entrancy except in a very limited way
using signals. It does however provide an integer type sig_atomic_t
which can be accessed atomically. This is sufficient to implement a
locking mechanism using for example Peterson's algorithm.

At the expense of some memory, you could malloc a small object and use
its address as a unique identifier, assuming your standard C library
supports re-entrancy.

-- Richard

 

[Richard Tobin]

Standard C does not support re-entrancy except in a very limited way
using signals. It does however provide an integer type sig_atomic_t
which can be accessed atomically. This is sufficient to implement a
locking mechanism using for example Peterson's algorithm.

Oops, this doesn't work for your case, because Peterson's algorithm
needs a shared variable for each process that might want to acquire
the lock. I'm not sure whether all similar algorithms have this
requirement.

-- Richard

 

[Jonathan Mcdougall]

Wow - I hadn't realised that my use of a forbidden word would stir up
such a hornet's nest. Perhaps I could rephrase the problem in an
acceptable manner. Assume that I have a routine that does this:


Now, also assume that for ideological reasons, I don't like to use
static variables. If you like, you can also imagine that I am
executing in an environment in which the keyword 'static' ensures that
this code won't work; it doesn't matter whether this is actually the
case, or why it won't work if this does happen to be the case.

Problem: is there a way to reformulate 'get_unique_id' so that:

1) 'id' is not in static storage; it should be on the stack somewhere

2) 'id' retains a memory of its value between function calls

These two points are contradictory. You cannot change the lifetime of
automatic objects, so that rules out local objects.

3) The interface to 'get_unique_id' is unchanged

But you can change the implementation, can you?

I don't have much experience with threads, so I can be completly wrong
here. But here's a suggestion.

What about a global variable? If the function is responsible for
synchronizing access, it should be possible, no? Or a Singleton which
does not use a static instance (not "Meyer's singleton")?

But if no one proposed this solution, it is probably because it's
wrong. If it is, I'd like to know why.


Jonathan

 

[Mr. Ed]

What about a global variable? If the function is responsible for
synchronizing access, it should be possible, no? Or a Singleton which
does not use a static instance (not "Meyer's singleton")?

But if no one proposed this solution, it is probably because it's
wrong. If it is, I'd like to know why.

This basically just moves the problem. A global variable is fine, if
you're willing to take the hit of synchronising access to it from
multiple threads (the variable needs to be incremented, or changed in
some way, so access to it must be protected). I was hoping to find
some way of avoiding this overhead, but it doesn't seem to be
possible.

Thanks

Ed