river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Patricia Shanahan <p...@acm.org>
Subject Re: datastructure classes
Date Fri, 17 Dec 2010 23:48:37 GMT
On 12/17/2010 10:22 AM, Gregg Wonderly wrote:
> On 12/16/2010 9:35 PM, Patricia Shanahan wrote:
>> I would love to be able to base it on a ConcurrentMap, but I don't see
>> how it
>> would work.
>> As far as I can tell, there is no clean split between key and non-key
>> among the
>> entry's public fields. A template can specify values for any subset of
>> the
>> fields, and different templates used in reading from the same space
>> may choose
>> different sets of fields.
>> Any ideas how to work around that?
> One of the things I did in Griddle was to create a CHM for each key
> field name. I then put every entry into the appropriate map based on it
> having a key value pair with a name.
> Matching is then a matter of querying each map with the provided key's
> value, and only if the same entry exists in all tables does a match
> begin processing.

Yes, I see what you mean. I've used similar techniques with 
java.util.HashMap to deal with multiple entries for the same key.

It raises a question about Outrigger functionality. As currently 
implemented, it is FIFO. For example, a single Entry read gets the 
oldest Entry in the space that matches the template.

The net.jini.space.JavaSpace interface does not require FIFO behavior. 
It says things like "Read any matching entry from the space, blocking 
until one exists."

In  a CHM-based implementation keeping the FIFO behavior might involve a 
sort taking O(k log k) time, where k is the number of elements that match.

Or k may be the number of entries in the smallest contents for any match 
field. One possible sequence is find the matching entries for the most 
restrictive field, sort them in time order, and search the sorted result 
for the first Entry that meets the rest of the template rules.

Any thoughts on this.


View raw message