On 11/20/2012 2:10 PM, Schaeferhaus wrote:
sorry, but i think there is no need for special prefix search functions in the judy arrays.
Look at my example previously posted:
for(pval = JudySLFirst(Jnew, curl, NULL); pval; pval = JudySLNext(Jnew, curl, NULL)) {
  if(memcmp(curl, prefix, prefixlen)) break;
}
Yes, that accomplishes a prefix search, and it's the same approach I'm using now.

However, it does unnecessary work.  For instance, if there are no matches for the prefix "abc", JudySLFirst() will continue looking for the next element even after it knows that there is nothing under the leaf for "abc" (or there no leaf for "abc" at all).  This happens whenever you reach the end of the loop.

If you're not doing a prefix search frequently, then the effect would be negligible.  It could add up in some algorithms, though.

For me the 2 major improvements to judy arrays are:
1  - Using Judy arrays for non null terminated strings (this is currently a big drawback).
Agreed.  Doug did say that this is in the works.
2  - Improving performance of the JudySLNext, JudySLPrev by using a cursor structure as parameter.
      The path of the Judy-three and the current string must be stored in this structure.
Agreed.


Tim