Code for associative arrays ?

[Andre Majorel]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

 

[santosh]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

What about SQLite?

<http://www.sqlite.org/>

 

[Marc Boyer]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

I assume the code distributed on the CD with "C Unleashed" should
satisfy you. I have read the book, but not used the code.

You could also have a look on a small code I have developped.
http://irt.enseeiht.fr/boyer/Tools.html

Marc Boyer

 

[Andre Majorel]

The data is a bunch of (key, value) pairs. [...] I'm looking
for some code to do that. Hash table, B-tree, whatever as
long as it's :

What about SQLite?

Clarification : the data is in core, not on disk.

 

[Ian Collins]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

Use C++?

 

[Keith Thompson]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,

[...]

I assume the code distributed on the CD with "C Unleashed" should
satisfy you. I have read the book, but not used the code.

What are the license terms for that code?

You could also have a look on a small code I have developped.
http://irt.enseeiht.fr/boyer/Tools.html

Same question (I didn't see a license on the web page, but I didn't
look very hard).

 

[Dann Corbit]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,

[...]

I assume the code distributed on the CD with "C Unleashed" should
satisfy you. I have read the book, but not used the code.

What are the license terms for that code?

The license is not identical for all of the code. I used a Berkeley style
license for chapter 13.

Each product on the CD does come with its own license agreement. Many of
them are GPL.

Same question (I didn't see a license on the web page, but I didn't
look very hard).

Not too sure about that one.

 

[Marc Boyer]

Same question (I didn't see a license on the web page, but I didn't
look very hard).

I did not chose any for the moment.
Which one would you like ?

Marc Boyer

 

[Keith Thompson]

I did not chose any for the moment.
Which one would you like ?

I have no opinion; others might.

 

[Dann Corbit]

I have no opinion; others might.

My opinion is that the author should choose the kind of license they want.

My favorite license type is Berkeley style, but others like GPL or LGPL or
Apache or whatever.

 

[Richard Harter]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

You might like my implementation of unordered radix trees.
A descriptive article is at:
http://home.tiac.net/~cri/2007/urtree.html

There are two different implementations on line. I suggest
you use the urtree implementation which has three source
files, one C file and two include files.

http://home.tiac.net/~cri_a/source_code/urtree/urtree.c
http://home.tiac.net/~cri_a/source_code/urtree/urtree_private.h
http://home.tiac.net/~cri_a/source_code/urtree/urtree_public.h

The license is BSD style.

Create/update/delete is O(log N). There is no get all KV pairs
but there is a routine to print out a formatted version of the
tree. Modifying the tree print to deliver all KV pairs would be
trivial.

HTH


Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die

 

[CBFalconer]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

You can do it easily in O(1) time, i.e. constant time per
entry/deletion etc. Coded in standard C, and licensed under GPL.
See hashlib.zip, at:

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

 

[Dann Corbit]

You can do it easily in O(1) time, i.e. constant time per
entry/deletion etc. Coded in standard C, and licensed under GPL.
See hashlib.zip, at:

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

Clearly his requirement a) leaves your GPL code out.

 

[Andre Majorel]

You might like my implementation of unordered radix trees.
A descriptive article is at:
http://home.tiac.net/~cri/2007/urtree.html

There are two different implementations on line. I suggest
you use the urtree implementation which has three source
files, one C file and two include files.

http://home.tiac.net/~cri_a/source_code/urtree/urtree.c
http://home.tiac.net/~cri_a/source_code/urtree/urtree_private.h
http://home.tiac.net/~cri_a/source_code/urtree/urtree_public.h

Thanks. One thing I don't understand about the implementation
above is why does urtree_delete() need both a key and a value ?

 

[CBFalconer]

Clearly his requirement a) leaves your GPL code out.

That's his problem. However, since I own hashlib, he can always
try it out and if it does his job he can contact me for a suitable
license, with suitable payments. Or he can make his software
open-source.

 

[Richard Harter]

Thanks. One thing I don't understand about the implementation
above is why does urtree_delete() need both a key and a value ?

To be honest, I don't think it does. IIRC having both the key
and the value was intended as a safety check.



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die

 

[Richard]

That's his problem. However, since I own hashlib, he can always
try it out and if it does his job he can contact me for a suitable
license, with suitable payments. Or he can make his software
open-source.

I seem to recall you being very vociferous on the subject of Jacob Navia
possibly making money from his compiler. Strange how it's ok for you.

 

[Kenny McCormack]

That's his problem. However, since I own hashlib, he can always
try it out and if it does his job he can contact me for a suitable
license, with suitable payments. Or he can make his software
open-source.

I seem to recall you being very vociferous on the subject of Jacob Navia
possibly making money from his compiler. Strange how it's ok for you.[/QUOTE]

Funny that, innit?

 

[CBFalconer]

I seem to recall you being very vociferous on the subject of Jacob
Navia possibly making money from his compiler. Strange how it's ok
for you.

Not strange at all. My software is available under GPL. If you
want a different license, you have the option to pay. And I didn't
criticize Jacob making money.

 

[Malcolm McLean]

The data is a bunch of (key, value) pairs. The key is a
NUL-terminated string, the value is a struct. I need to :
a) create/update any element by key in log(N) time or less,
b) get all (key, value) pairs, not necessarily in order.

I'm looking for some code to do that. Hash table, B-tree,
whatever as long as it's :
a) available under the terms of a very liberal licence as it
will be used in closed-source software,
b) compact (one .c, one .h and no dependencies on any kind of
config.h),
c) mature ; if I had the time to debug it, I would roll my
own.

Any recommendations ? Thanks in advance.

You might find what you are looking for on my website. It's a free chapter
of "Basic Algorithms".
It can meet a and b. c is a bit more dicey. Thoguh the code isn't exactly
bugged - it will produce a working associative array - there are things that
could be done better. We had a long thread on it a month ago.