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

Discussion in 'C Programming' started by Angus Comber, Feb 2, 2004.

  1. Angus Comber

    Angus Comber Guest

    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
     
    Angus Comber, Feb 2, 2004
    #1
    1. Advertising

  2. Angus Comber

    Sidney Cadot Guest

    Angus Comber wrote:

    > 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
     
    Sidney Cadot, Feb 2, 2004
    #2
    1. Advertising

  3. On Mon, 2 Feb 2004, Angus Comber wrote:
    >
    > [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
     
    Arthur J. O'Dwyer, Feb 3, 2004
    #3
  4. Angus Comber

    Jack Klein Guest

    On Mon, 2 Feb 2004 23:07:15 -0000, "Angus Comber"
    <> wrote in comp.lang.c:

    > 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
    >


    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.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Feb 3, 2004
    #4
  5. Angus Comber

    Sidney Cadot Guest

    Jack Klein wrote:

    > 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
     
    Sidney Cadot, Feb 3, 2004
    #5
  6. Angus Comber

    Paul Hsieh Guest

    "Angus Comber" <> wrote:
    > 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.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    Paul Hsieh, Feb 3, 2004
    #6
  7. Angus Comber

    Grumble Guest

    Paul Hsieh wrote:

    > Only topics like casting malloc, are really covered here.


    <g>

    The bitterness is almost palpable.
     
    Grumble, Feb 3, 2004
    #7
  8. Angus Comber wrote:

    > 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
    >
    >
    >
    >


    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
     
    Thomas Matthews, Feb 3, 2004
    #8
  9. Angus Comber

    Jack Klein Guest

    On Tue, 03 Feb 2004 08:18:16 +0100, Sidney Cadot <>
    wrote in comp.lang.c:

    > Jack Klein wrote:
    >
    > > 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


    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.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Feb 4, 2004
    #9
  10. Angus Comber

    Angus Comber Guest

    You mentioned bsearch() ? What is that?

    Angus

    "Jack Klein" <> wrote in message
    news:...
    > On Mon, 2 Feb 2004 23:07:15 -0000, "Angus Comber"
    > <> wrote in comp.lang.c:
    >
    > > 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
    > >

    >
    > 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.
    >
    > --
    > Jack Klein
    > Home: http://JK-Technology.Com
    > FAQs for
    > comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    > comp.lang.c++ http://www.parashift.com/c -faq-lite/
    > alt.comp.lang.learn.c-c++
    > http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Angus Comber, Feb 4, 2004
    #10
  11. 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"?
     
    Peter Shaggy Haywood, Feb 5, 2004
    #11
  12. Angus Comber

    Grumble Guest

    Grumble, Feb 5, 2004
    #12
  13. On Wed, 4 Feb 2004 22:49:07 -0000, in comp.lang.c , "Angus Comber"
    <> wrote:

    >You mentioned bsearch() ? What is that?


    a Standard Library function.


    --
    Mark McIntyre
    CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
    CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


    ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
    http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
    ---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
     
    Mark McIntyre, Feb 8, 2004
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. desktop
    Replies:
    5
    Views:
    388
    James Kanze
    Jun 26, 2007
  2. Yvon Thoraval
    Replies:
    5
    Views:
    210
    Jason Creighton
    Sep 17, 2003
  3. mark4asp
    Replies:
    5
    Views:
    95
    mark4asp
    Sep 28, 2004
  4. VK
    Replies:
    47
    Views:
    552
    Thomas 'PointedEars' Lahn
    Jul 13, 2005
  5. VK
    Replies:
    36
    Views:
    655
    Martin Honnen
    Aug 3, 2005
Loading...

Share This Page