Very large array?

[cbdeja]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's
the best way of representing the in-use state of all label values
without having to waste memory on a vast array? (Perhaps just using
memory for those values which are in-use.)

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

 

[cbdeja]

Apologies. Please ignore the root message in this thread.

I intended to post to the C++ group, but selected C by mistake.

 

[Eric Sosman]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

Why?

There are at least 2^64 distinct `unsigned long long'
values (that's 18,446,744,073,709,551,616 distict values,
for those keeping score at home). If you consume them at
a rate of one GHz -- one billion transactions per second --
it will take more than five hundred eighty-four years to
exhaust the supply. Even then, you'll only be in trouble
if some transactions are still running after all that time.
(Studies of human/computer interaction suggest that most
users find response times greater than half a millennium
to be annoying.)

The bug reports will not begin to arrive until sometime
after the year 2590. If you're still around to address them,
be sure to check with your uncle Methuselah before hurrying
to issue a patch.

 

[Chad]

I looked up long in the book "The C Programming Language", second
edition by Kernighan and Richtie. How come on page 36 they say:

"In addition; there are a number of qualifiers that can be applied to
these basic data types. short and long apply to integers".

But on page 211, section A8.2, they put both long and short as a
type-specifier, not a type-qualifier.

The sentence on page 36 seems to imply that long is being used as a
type-qualifer and not a type-specifier. When using long in conjunction
with long or int, does makes it a type-qualifier, but not a
type-specifier?

Chad

 

[Eric Sosman]

Chad wrote On 03/16/06 09:37,:

I looked up long in the book "The C Programming Language", second
edition by Kernighan and Richtie. How come on page 36 they say:

"In addition; there are a number of qualifiers that can be applied to
these basic data types. short and long apply to integers".

But on page 211, section A8.2, they put both long and short as a
type-specifier, not a type-qualifier.

The sentence on page 36 seems to imply that long is being used as a
type-qualifer and not a type-specifier. When using long in conjunction
with long or int, does makes it a type-qualifier, but not a
type-specifier?

K&R's book ("K&R II") describes the C language of the
original 1989 ANSI Standard ("C89," or "C90" for the date
of its adoption by ISO), and in that version of the language
there is no `long long'. In 1999 a new version of the
Standard ("C99") was adopted by ISO and ANSI, and this version
adds the `long long' type (and some others) to the C89
repertoire. This type has at least sixty-four bits, hence
about 1.9e19 distinct values.

Also, some pre-1999 compilers accept `long long' as an
extension to the C89 language. Most, it seems, use it to
designate a 64-bit integer.

K&R have not yet produced a third edition of their book
to match the C99 Standard, and it is widely believed (with or
without justification) that they probably don't intend to.