Advice, references to implementation of a map or similar data structs

[void * clvrmnky()]

Greetings,

I'm in the process of refactoring some code, and have determined that I
need a map (or some other dictionary structure) to maintain a small list
of key-value pairs. This is follow-on work from parallel development
done in Java, so I'm working to a spec based on exposed methods.

I've cooked up some prototypes based on linked-lists or tuples, but I
have the feeling I'm missing something.

What online refs do folks here use to see working examples and
discussions of data structures in C? My Google-fu is failing me -- I'm
getting plenty of definitions of maps, and considerations on
implementation, but I'd like a concrete example to compare with my
(rather naive) attempts.

I only have to implemented add(key, value), fetch(key) and getallkeys()
functions for this use, and the map itself will only have a handful of
entries, and we never need to remove them. Both the keys and the values
are wchars (though I'm not against making them void *).

I have no problem just implementing a fix-sized tuple (yes, I know...)
as this is all that is required of the design. Of course, the reason
I'm updating this code is because the original design assumed we've
never need more than a handful of items in a struct...

It may need to be said that this data and the functions to access it are
essentially private to this component. I don't need a general-purpose
library for the entire product (which is mostly in Java, anyway -- hence
my ignorance of implementation).

Thanks.

 

[John F]

Greetings,

I'm in the process of refactoring some code, and have determined that I
need a map (or some other dictionary structure) to maintain a small list
of key-value pairs. This is follow-on work from parallel development done
in Java, so I'm working to a spec based on exposed methods.

I've cooked up some prototypes based on linked-lists or tuples, but I have
the feeling I'm missing something.

What online refs do folks here use to see working examples and discussions
of data structures in C? My Google-fu is failing me -- I'm getting plenty
of definitions of maps, and considerations on implementation, but I'd like
a concrete example to compare with my (rather naive) attempts.

I only have to implemented add(key, value), fetch(key) and getallkeys()
functions for this use, and the map itself will only have a handful of
entries, and we never need to remove them. Both the keys and the values
are wchars (though I'm not against making them void *).

I have no problem just implementing a fix-sized tuple (yes, I know...) as
this is all that is required of the design. Of course, the reason I'm
updating this code is because the original design assumed we've never need
more than a handful of items in a struct...

It may need to be said that this data and the functions to access it are
essentially private to this component. I don't need a general-purpose
library for the entire product (which is mostly in Java, anyway -- hence
my ignorance of implementation).

Thanks.

This makes use of one:
http://ndevilla.free.fr/iniparser/

John

 

[Chris Torek]

I'm in the process of refactoring some code, and have determined that I
need a map (or some other dictionary structure) to maintain a small list
of key-value pairs. This is follow-on work from parallel development
done in Java, so I'm working to a spec based on exposed methods. ...

What online refs do folks here use to see working examples and
discussions of data structures in C? My Google-fu is failing me -- I'm
getting plenty of definitions of maps, and considerations on
implementation, but I'd like a concrete example to compare with my
(rather naive) attempts.

This is perhaps dangerously off-topic (will the Topic Cops haul my
posting off to net.jail? ), but I will say this: you will have
much better luck finding sample C implementations if you refer to
this "map" concept using its much older name, "hash table".

(Of course, <key,value> tuples -- more general than mere pairs --
lie at the heart of databases as well. But you want "hash tables".)

 

[Len Philpot]

Chris Torek said the following on 3/3/2006 1:04 AM:

[snip]

This is perhaps dangerously off-topic (will the Topic Cops haul my
posting off to net.jail? ), but I will say this: you will have

I suspect if anyone here has earned a 'Get Out of Jail Free' card, your
standing is good order.

 

[CBFalconer]

This is perhaps dangerously off-topic (will the Topic Cops haul
my posting off to net.jail? ), but I will say this: you will
have much better luck finding sample C implementations if you
refer to this "map" concept using its much older name, "hash
table".

(Of course, <key,value> tuples -- more general than mere pairs
-- lie at the heart of databases as well. But you want
"hash tables".)

In which case I will also risk being hauled directly off to gaol
without passing go or collecting 200 dollars and tell the OP that
he can probably handle everything he wants with my hashlib package,
written in portable standard C, available at:

<http://cbfalconer.home.att.net/download/hashlib.zip>

He can also look at an application using it, i.e. id2id-20,
available at the same place. This does some interesting things
with the relationships.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>