Freeze::map.lower_bound

[sylvain]

Hi,

As I read in other post, or as I saw when looking at some part of the code, Freeze is very tightly coupled with Berkeley db. I am not familiar at all with Berkeley db, but looking at the documentation it seems that "search" possibilities are limited.

I suppose that this is the reason why Freeze::map doesn't implement the lower_bound and upper_bound that are part of the STL standard for maps.

It seems however, that it is possible to store data in berkeley db using some kind of Btree. So, my question is: are you planning to implement Freeze::map.lower_bound for a future release, or is it not possible?

If not, do you have a hint on how I could implement this kind of features in a way that it smoothly interact with Freeze?

The reason is of course to implement some simple "wildcards" searches, for example if a STL map contains some key/value pairs like : {"A","001"},{"Ba","002"},{"Bb","003"},{"C","004 "}, then lower_bound("B") will return an iterator on {"Ba","002"} and lower_bound("C") will return an iterator on {"C","004"} so by looping from the first iterator to the second (but not including it) I can extract record with keys beggining with "B".

I would very happy if I could do the same with Freeze::map...

Thanks in advance.

[bernard]

Hi Sylvain,

Although a Freeze Map uses for storage a Btree Berkeley DB database, currently it is not "really" sorted. The Freeze:: DBMap template has no sorting argument, so the sorting on disk is the default: keys are marshalled using the Ice encoding (see the Ice Protocal chapter in the Ice book) , and Berkeley DB sorts the resulting binary strings.

If you'd like to improve these Maps to make them sortable, you'll need to add a template parameter to specify the key sorting, and somehow pass it down to Berkeley DB. See http://www.sleepycat.com/docs/api_cx..._compare.html.
and DB_SET_RANGE in http://www.sleepycat.com/docs/api_cxx/dbc_get.html.
(In the next Ice release, the Freeze DBMap will be implemented using Berkeley DB/C++).

Maybe you could also consider to use Berkeley DB directly?

Cheers,
Bernard

[sylvain]

I just add a method lower_bound in DBMap that is exactly similar to find except that it calls a _db->getCursorAtKeyRange(k) method (instead of your _db->getCursorAtKey(k)).

I added a getCursorAtKeyRange in DBI.cpp that is exactly similar to the getCursorAtKeyRange, except that is calls the Berkeley db c_get method with the argument DB_SET_RANGE instead of DB_SET for the flag argument (and of course I had to modife also DB.ice)

As key in a db managed through freeze (in XML) always begin with the same <Key> tag, the default lexicographical ordering of the key of the freeze map is not altered. Thus, the method lower_bound discribed above works exactly as expected (I just made a few however) and this is perfeclty fine for my application.

Thanks a lot.

[marc]

I guess this works fine for strings as keys, and structs with only strings as keys, but it might not work for other key types.

But since strings are the most common type of keys, perhaps we should add this for maps with strings or structs with strings as keys.