What's the best way to create an associative array in C?

[Angus Comber]

Hello

I want to create a lookup table where I can store string keys:

For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP address
(sort of the key).

Angus Comber
(e-mail address removed)

 

[Sidney Cadot]

Hello

I want to create a lookup table where I can store string keys:

For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP address
(sort of the key).

C does not provide support for associative arrays out of the box. You
will have to implement this kind of thing from lower-level things using
an appropriate algorithm.

If you don't insist on rolling-your-own, take a look at libjudy
(http://sourceforge.net/projects/judy/).

Note that your calling the value associated with the IP address "sort of
the key" is a bit confusing; in normal parlor, the thing being used as
index (in your case, the IP address) is referred to as the "key".

Best regards,

Sidney

 

[Arthur J. O'Dwyer]

[What's the best way to create an associative array in C?]

In future posts, please don't start writing your message until
you move the cursor to the message body. The first line of your
post seems to have ended up in the subject line. [I know that it
must have been intended to go in the message body, because it
contains important information relevant to your question.]

I want to create a lookup table where I can store string keys:
For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP
address (sort of the key).

It all depends on what you want to do with the entries. Only
providing this much information, you will almost certainly be deluged
with smartass answers along the lines of

const char *arr[3][2] =
{
{ "192.168.0.1", "Purple" },
{ "192.168.0.2", "Blue" },
{ "192.168.0.3", "Red" },
};

So, do you want a full associative-array implementation, like
something that could be used to implement Perl? Try a hash table.
Do you just want to store a few addresses and values, like 20 or
30? Maybe a simple array would be better. Since you know that
all your keys are 32-bit numbers, maybe you should consider a trie
with four levels:

enum Color { Red, Purple, Blue };

struct trienode
{
struct trienode *child[256];
enum Color value;
};

There are many, many ways to store data in C (as in any other
language). If you're interested in the merits of various data
structures, ask again in comp.programming. But if you come out and
tell us *what* you want to do, and *why* you want to do it [the
*why* is very important], then I'm sure someone can suggest a good
way to do it in C.

-Arthur

 

[Jack Klein]

Hello

I want to create a lookup table where I can store string keys:

For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP address
(sort of the key).

Angus Comber
(e-mail address removed)

The nice thing about IP addresses is that they are guaranteed to fit
into an unsigned long on every conforming C implementation.

It depends on use, but if there are a lot of these you could save
storage by converting the IP addresses into unsigned longs.

If all possible values are available at program start-up, define a
structure type with two members, an unsigned long (the IP address),
and the other member being whatever you need, such as pointer to
character string. Populate an array of them, qsort() it, and then you
can bsearch() it when you need to look up values, an extremely
efficient search technique.

If need to be able to add, delete, and change items all the time,
various other data structures might be more appropriate than a simple
array. Ask in comp.programming for help in selecting the best
structure.

 

[Sidney Cadot]

The nice thing about IP addresses is that they are guaranteed to fit
into an unsigned long on every conforming C implementation.

That is only true for IPv4 addresses. It would perhaps not be a very
good idea to make use of this fact in new software.

Best regards,

Sidney

 

[Paul Hsieh]

I want to create a lookup table where I can store string keys:

For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP address
(sort of the key).

Ordinarily, this is the wrong newsgroup for this kind of a question.
C is too low-level of a language to do this in a simple or natural
way, and discussions of algorithms is not the focus of this group.
Only topics like casting malloc, are really covered here.

Anyhow, the solution is to build a hash-table with a target on the end
of each map. So the idea is that you would store a (ip,attribute)
tuple but use only the first tuple for the key. I'm going to assume
that what you've got here is really just a string -> string mapping.
So each tuple would be roughly:

struct aaStr2StrTuple {
struct aaStr2StrTuple * next;
unsigned int keyHash32;
char * key, * result;
};

#define HASH_KEY_SZ (65536)

struct aaStr2StrTuple * hashTable[HASH_KEY_SZ];

Then the core API would include:

int setEntryInHashTable (struct aaStr2StrTuple * h,
const char * key,
const char * result);
char * getEntryInHashTable (struct aaStr2StrTuple * h,
const char * key);

The idea would be that you would copy, then canonicallize the "key"
string. Then you would compute some kind of 48-bit hash (using a
CRC-48 or something), from which you could extract a 16-bit hash
index, and additional 32-bit verification bits (so that you can by
virtue of index seperation an one fast int comparison, perform
essentially a fairly strong 48-bit hash test, before having to drop
down to a strcmp.) Then copy the result string, and you should be
able to find/insert into the hash table fairly easily. To wipe an
entry you can so something like calling setEntryInHashTable with
result set to NULL. If you don't find an entry, then
getEntryInHashTable should return NULL.

You can do more complicated things like having a variable sized hash
index, but then you have to generate two hashes, or have redundant
bits or something like that (or suffer worse collision issues.)
Whatever -- these are just hash design issues, which you can research
from any good data structures text.

 

[Grumble]

Only topics like casting malloc, are really covered here.

<g>

The bitterness is almost palpable.

 

[Thomas Matthews]

Hello

I want to create a lookup table where I can store string keys:

For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP address
(sort of the key).

Angus Comber
(e-mail address removed)

Other people have suggested a hash table.
Another idea is a binary tree, based on the key field.
You could take it up a notch and use a B-Tree, in which
each node is a page (or array) of nodes, to reduce down
the fetching times.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Jack Klein]

That is only true for IPv4 addresses. It would perhaps not be a very
good idea to make use of this fact in new software.

Best regards,

Sidney

IPv6 has been just around the corner how long now? I'm not holding my
breath for it, or for the replacement for SMTP that will make spamming
impossible.

 

[Angus Comber]

You mentioned bsearch() ? What is that?

Angus

The nice thing about IP addresses is that they are guaranteed to fit
into an unsigned long on every conforming C implementation.

It depends on use, but if there are a lot of these you could save
storage by converting the IP addresses into unsigned longs.

If all possible values are available at program start-up, define a
structure type with two members, an unsigned long (the IP address),
and the other member being whatever you need, such as pointer to
character string. Populate an array of them, qsort() it, and then you
can bsearch() it when you need to look up values, an extremely
efficient search technique.

If need to be able to add, delete, and change items all the time,
various other data structures might be more appropriate than a simple
array. Ask in comp.programming for help in selecting the best
structure.

 

[Peter Shaggy Haywood]

Groovy hepcat Angus Comber was jivin' on Mon, 2 Feb 2004 23:07:15
-0000 in comp.lang.c.
What's the best way to create an associative array in C?'s a cool
scene! Dig it!

I want to create a lookup table where I can store string keys:
For example:

192.168.0.1 -> Purple
192.168.0.2 -> Blue
192.168.0.3 -> Red

The first field are IP addresses - but basically a text string. The
colour - eg Purple, Blue or Red is the value associated with the IP address
(sort of the key).

And your C question is...?
(P. S.: I hate all those posts that just say something like "And
your C question is...?" However, sometimes I find that they are rather
approriate.)

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?

 

[Grumble]

You mentioned bsearch() ? What is that?

http://www.freebsd.org/cgi/man.cgi?query=bsearch

 

[Mark McIntyre]

You mentioned bsearch() ? What is that?

a Standard Library function.