Where to get a unique id for a newly allocated datastructure member

[A. Farber]

Hello,

I'm programming a web game on OpenBSD, but am
also trying to keep in runnable on Linux and Cygwin.

I have a list of tables at which a player/kibitzer can
sit down or create a new empty one if (s)he wants.

I keep tables in a doubly-linked list using the nice TAILQ_* macros:
http://www.openbsd.org/cgi-bin/man.cgi?query=queue
and later I'd like to switch to red-black hashes - the RB_* macros in:
http://www.openbsd.org/cgi-bin/man.cgi?query=tree
(for Linux and Cygwin I just copy OpenBSD's tree.h and queue.h).

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered:

1) Using epoch seconds - is not nice, race condition
2) Using a random number - not nice, same as above
3) Using a sequential number - I'd have to cycle through
my whole doubly linked list of tables to verify it is unique
4) Using the id of the creating player - can't do that,
because I don't want to drop all other players/kibitzers
off the table if that 1st player wants to stand up
(and maybe move to another table)
5) Using the address of the newly created table struct -
seems to be ok, but requires a long long type...

Does anybody please have some other idea?

Thank you
Alex

 

[Chris Dollin]

Hello,

I'm programming a web game on OpenBSD, but am
also trying to keep in runnable on Linux and Cygwin.

I have a list of tables at which a player/kibitzer can
sit down or create a new empty one if (s)he wants.

I keep tables in a doubly-linked list using the nice TAILQ_* macros:
http://www.openbsd.org/cgi-bin/man.cgi?query=queue
and later I'd like to switch to red-black hashes - the RB_* macros in:
http://www.openbsd.org/cgi-bin/man.cgi?query=tree
(for Linux and Cygwin I just copy OpenBSD's tree.h and queue.h).

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered:

I don't see that this is a C question at all. (That your code
is, presumably, C isn't enough.) Wouldn't comp.programming be
better?

 

[A. Farber]

Hello Chris,

I don't see that this is a C question at all. (That your code
is, presumably, C isn't enough.) Wouldn't comp.programming be
better?

I was considering other newsgroups too: comp.unix.programming
(maybe there is some OS trick to get a unique id), comp.algorithms
(but they wouldn't know C macros and would suggest me to switch
my prog. language to some academic BS and so one), etc...

As I didn't want to crosspost, I've decided that comp.lang.c would
be the best place to fish for the trick that I'm looking for.
So I don't agree with you that my question is not appropriate here:

I need a C trick/macro/function/usual pattern for a unique id.

Regards
Alex

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

Hello,

I'm programming a web game on OpenBSD, but am
also trying to keep in runnable on Linux and Cygwin.

I have a list of tables at which a player/kibitzer can
sit down or create a new empty one if (s)he wants.

I keep tables in a doubly-linked list using the nice TAILQ_* macros:
http://www.openbsd.org/cgi-bin/man.cgi?query=queue
and later I'd like to switch to red-black hashes - the RB_* macros in:
http://www.openbsd.org/cgi-bin/man.cgi?query=tree
(for Linux and Cygwin I just copy OpenBSD's tree.h and queue.h).

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered: ....
3) Using a sequential number - I'd have to cycle through
my whole doubly linked list of tables to verify it is unique

Why ?
If you have one id whcih you increment it each time you need one - it is
unique (atleast until it wraps around).

(problems arise if it needs to be unique among multiple
systems. If it needs to be unique between sessions, you store the
current id and read it back upon the next start/session)

 

[Chris Dollin]

Hello Chris,



I was considering other newsgroups too: comp.unix.programming
(maybe there is some OS trick to get a unique id),

(If there were, it would be off-topic here.)

comp.algorithms (but they wouldn't know C macros

Why does that matter? (And why would you want to use /macros/ for
this?)

and would suggest me to switch my prog. language to some academic BS

Really? Well, if that happened, you could just ignore that bit and
take whatever algorithm thingy they offered.

and so one), etc...

As I didn't want to crosspost, I've decided that comp.lang.c would
be the best place to fish for the trick that I'm looking for.
So I don't agree with you that my question is not appropriate here:

I need a C trick/macro/function/usual pattern for a unique id.

comp.programming would be better. There's /nothing/ C-specific about
your question. Expressing the computation, once you know what it is,
/that/ could be a C question.

 

[Richard Heathfield]

A. Farber said:

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered:

1) Using epoch seconds - is not nice, race condition

Agreed - that's a bad idea.

2) Using a random number - not nice, same as above

Not agreed. Construct a random (or at least pseudorandom) bit string using
as a seed the information you already have from your client. XOR it with an
arbitrary random bit string using some other seed (such as your real-time
clock, if you have access to it), both strings having the same length.

If you use enough bits, you can reduce the probability of a collision to a
far lower value than the probability that your brain will suddenly melt and
pour out through your nostrils. At that point, if you do not see the point
in concerning yourself with the latter possibility, then there is no
rational reason to be concerned about the former.

 

[Henryk]

What about GUIDs?

see http://en.wikipedia.org/wiki/Globally_Unique_Identifier

Maybe your operating system provides a function to create such an id.
For Windows check CoCreateGuid with google...

Cheers

Henryk

 

[A. Farber]

Construct a random (or at least pseudorandom) bit string using
as a seed the information you already have from your client. XOR it with an
arbitrary random bit string using some other seed (such as your real-time
clock, if you have access to it), both strings having the same length.

Thanks, but what is the XORing meant for?

If you use enough bits, you can reduce the probability of a collision to a
far lower value than the probability that your brain will suddenly melt and
pour out through your nostrils. At that point, if you do not see the point
in concerning yourself with the latter possibility, then there is no
rational reason to be concerned about the former.

Regards
Alex

 

[A. Farber]

Hi,

comp.programming would be better. There's /nothing/ C-specific about
your question. Expressing the computation, once you know what it is,
/that/ could be a C question.

no, I still disagree. Maybe you know the book "Code Reading:
The Open Source Perspective" http://www.spinellis.gr/codereading/

At first glance it is about algrithms. But in fact it is a book
about getting better C reading (and programming) skills by
learning a list of very common C patterns.

And same is here: I don't care about algorithms in other
languages. I was looking for another C lego block to add
to my C toolbox. That's why I've asked my question here

Regards
Alex

 

[Richard Heathfield]

A. Farber said:

Thanks, but what is the XORing meant for?

Because my first thought was to do an MD5 hash on the information supplied
to you by the client, e.g. "Joe Surfer" + "9 yrs" + "USA" - and then I
realised that this wasn't necessarily unique, and would need
disambiguating, and I solved that problem by salting the information with
random bits. But of course if you have random bits, you don't need the
original bits.

So it was just sloppy thinking, really.

The important point is that you only need, say, 256 bits of entropy to
render the probability of a collision vanishingly low - many orders of
magnitude lower than the chance of you winning the lottery jackpot. So
don't discard the random option. But a naive "id = rand()" is indeed asking
for trouble.

 

[Chris Dollin]

no, I still disagree. Maybe you know the book "Code Reading:
The Open Source Perspective" http://www.spinellis.gr/codereading/

I don't, I'm afraid.

At first glance it is about algrithms. But in fact it is a book
about getting better C reading (and programming) skills by
learning a list of very common C patterns.

And same is here: I don't care about algorithms in other
languages. I was looking for another C lego block to add
to my C toolbox. That's why I've asked my question here

Then you're asking two separate questions: what's a good way to
generate a unique id; what's a good way to express that in C.
(Followup: how to perturb the algorithm to make it fit C
better. Were that to arise, then there might be some interesting
topicality issues.) The former isn't a C question, but it is
the question you asked.

I'd be interested in hearing what specific-to-C properties you might
be expecting from a unique-id generator.

I don't know why Richard H. thinks it's topical, but after all,
different reasonable people can have different opinions ...

 

[Richard Heathfield]

Chris Dollin said:

I'd be interested in hearing what specific-to-C properties you might
be expecting from a unique-id generator.

I don't know why Richard H. thinks it's topical, but after all,
different reasonable people can have different opinions ...

Actually, I have a confession to make...

 

[Random832]

A. Farber said:


Agreed - that's a bad idea.


Not agreed. Construct a random (or at least pseudorandom) bit string using
as a seed the information you already have from your client. XOR it with an
arbitrary random bit string using some other seed (such as your real-time
clock, if you have access to it), both strings having the same length.

If you use enough bits, you can reduce the probability of a collision to a
far lower value than the probability that your brain will suddenly melt and
pour out through your nostrils.

Wouldn't it be better to use the timestamp _and_ a random number? After
all, the probability is much lower for a short period of time [namely,
the time period during which some computers somewhere will have their
clock set to that time, not to mention that the probable _number_ of
computers that have a time set to that timestamp or will at any point
in the future quickly vanishes to a very small number] and the
possibility is closed once the number of such computers reaches zero,
whereas if you only use randomness, or if you negate the determinicity
of the timestamp by XORing it with randomness, the possibility of
a collision remains open forever.

I also suspect it would take a VERY large number of bits to literally
reduce the probability to that of anyone's brain suddenly melting
(though, once there, reducing it further to that of any _particular_
person's brain doing so will only take 35 or so more bits).

Adding the MAC address, too, will substantially reduce the number of
computers you have to worry about generating the same value, though it
has the disadvantage of making the generated value traceable to your
computer.

 

[Laurent Deniau]

Hello,

I'm programming a web game on OpenBSD, but am
also trying to keep in runnable on Linux and Cygwin.

I have a list of tables at which a player/kibitzer can
sit down or create a new empty one if (s)he wants.

I keep tables in a doubly-linked list using the nice TAILQ_* macros:
http://www.openbsd.org/cgi-bin/man.cgi?query=queue
and later I'd like to switch to red-black hashes - the RB_* macros in:
http://www.openbsd.org/cgi-bin/man.cgi?query=tree
(for Linux and Cygwin I just copy OpenBSD's tree.h and queue.h).

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered:

1) Using epoch seconds - is not nice, race condition

very bad.

2) Using a random number - not nice, same as above

This is probably the best solution. Use a group generator to generate
pseudo random numbers.

3) Using a sequential number - I'd have to cycle through
my whole doubly linked list of tables to verify it is unique

Why? 2) is better if you don't want a monotonic sequence, but otherwise
3) is ok.

In both case, unicity can be garantee by number size. If you use a
64bits number and if your C code generate a new number at 5Ghz, it will
still take about 117 years before you get a collision.

4) Using the id of the creating player - can't do that,
because I don't want to drop all other players/kibitzers
off the table if that 1st player wants to stand up
(and maybe move to another table)
5) Using the address of the newly created table struct -
seems to be ok, but requires a long long type...

This is also a good solution, specially if you want small id which can
be recycled when not used.

a+, ld.

 

[Keith Thompson]

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered:

1) Using epoch seconds - is not nice, race condition
2) Using a random number - not nice, same as above
3) Using a sequential number - I'd have to cycle through
my whole doubly linked list of tables to verify it is unique
4) Using the id of the creating player - can't do that,
because I don't want to drop all other players/kibitzers
off the table if that 1st player wants to stand up
(and maybe move to another table)
5) Using the address of the newly created table struct -
seems to be ok, but requires a long long type...

[...]

Unique in what context? If it only needs to be unique within one
execution of your program, a single integer variable, incremented for
each table allocation, will work just fine. If it needs to be unique
across multiple sequential executions of the program, store the
counter in a file between runs (writing the counter each time it
changes will protect you from program crashes).

Straying slightly from topicality ...

If it needs to be unique across concurrent executions of the same
program, possibly on different machines, it becomes more complicated.
Either you need a central source of uniqueness (which could become a
bottleneck), or you combine a unique identifier for this execution of
the program with something that's unique within the execution of the
program, or you rely on random numbers (use a good generator; rand()
typically isn't) and settle for a vanishingly small probability of a
collision. Methods for doing this are likely to require
system-specific extensions.

 

[goose]

A. Farber wrote:

MY PROBLEM is to get a unique id for a newly allocated
table structure. Here are the options I've considered:

static size_t last_uid = 0;

size_t get_uid (void)
{
return ++last_uid;
}

Write the unique ID to a file before exiting and read it
back in when starting the program.

If you need more unique identifiers than is possible with
size_t, then consider using an array of size_t of the size
you require and returning the array as a uid.
e.g.
static size_t last_uid[2];

Incrementing that number is left as an exercise to the reader

goose,

<snipped>