On 11/19/2012 3:09 PM, Doug Baskins wrote:

Sorry for delayed reply.  I have been getting ready for travel.  I am currently
in an Airport on my way to Thailand (from Colorado, USA).
Absolutely, not a problem.  Have a safe trip.
> 2.) Doug, have you thought about making a search function that will give 
> up as soon as it determines that there are no matches beginning with 
> Index?  What do you think about including it in one of the upcoming 
> versions?

I think it is very do-able.  The data structure lends itself to that kind of 
That's what I thought.  From my basic knowledge of the structure, it seems that a prefix-search is simply a First where you quit early if it turns out you would have to go up a level.  So that might be a simple matter of leaving out some code that the normal JudySLFirst() requires.

By the way, I misspoke in my first email.  I said that I was using JudySLNext() followed by an strncmp(), but I should have said JudySLFirst().  It's along these lines:
inline PPvoid_t JudySLPrefix (Pcvoid_t PArray, uint8_t *Index, PJError_t PJError) const {
        PPvoid_t PStoredValue;
        size_t Prefix_Len=strlen((char*)Index);
        char Prefix_Cpy[Prefix_Len+1] = {0};
        strcpy (Prefix_Cpy, (char*)Index);
        return (PStoredValue=JudySLFirst (PArray, Index, PJError))!=NULL ? (!strncmp((char*)Index, Prefix_Cpy, Prefix_Len) ? PStoredValue : NULL) : NULL;

Suggest an API and I will consider it.
It occurs to me that a prefix version of both JudySLFirst() and JudySLNext() would be desirable, for looping through all elements that share the prefix.  However, it's less clear that a JudySLNextPrefix() would perform well in a loop--wouldn't you have to repeat a lookup for the prefix leaf each time you call it?

Suggested API
If you're just making JudySLFirstPrefix(), the API could be identical to JudySLFirst().  Seed Index with the prefix, and then it will be populated with a key value during the call.

If you're also making JudySLNextPrefix(), in order to use it in a loop it would require both the standard Index and a separate const parameter for the prefix.  So why not make the parameter list identical in both functions?  Namely:
PPvoid_t JudySLFirstPrefix(Pcvoid_t PArray, const uint8_t * Prefix, uint8_t * Index, PJError_t PJError);
PPvoid_t JudySLNextPrefix(Pcvoid_t PArray, const uint8_t * Prefix, uint8_t * Index, PJError_t PJError);
Example code
A loop for all the elements that have the prefix would be the following.  (As always, Index must be big enough for the largest key on the tree.)
for (Word_t *PStoredValue=JudySLFirstPrefix(PArray, Prefix, Index, PJError); PStoredValue!=NULL; PStoredValue=JudySLNextPrefix(PArray, Prefix, Index, PJError)) {
    //do something with PStoredValue and Index
Also, depending on how you implement JudySLFirstPrefix(), someone might be able to get away with calling it like so:
PStoredValue = JudySLFirstPrefix (PArray, Index, Index, PJError);
That would be useful when we don't need the Prefix buffer after calling JudySLFirstPrefix().  Why create a separate Prefix buffer if we don't need it?  On the other hand, this is a bit sneaky and misunderstandable, and it doesn't get you very much, so it might be best not to support it.

(see below, there is a
paper that suggest Judy is a weak performer in this area).

Thanks for your interest


PS.  My intuition is it may not improve performance, because of caching of the
data.  But, there are people that say "I am out of touch" with modern computers.
They have implemented a "bulk" JudyLNext() and got big improvements.  I have
not had a chance to verify.
Are you talking about the Judy1SetArray() and JudyLInsArray() functions that Alan Silverstein wrote?  Those aren't applicable to JudySL, right?
There was a paper presented recently that compared
Judy performance with several other methods.  I will look it up, if your interested.
Improving Judy*Next is on my "to do" list.
I would be interested in that paper, yes.  Thank you.

Tim Margheim
Neuric Technologies, LLC