range lookup using Judy;

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

I need to perform range lookup on a set which has 256 entries.
There are millions of such independent 256 entries sets.
currently I'm having linked list for each such set where each
node contains begin and end of the range. Each entry in the
set is disjoint. Now I need to do a lookup of a range and
find out all the entries that overlaps with the input range and
also insert the regions which do not exist.
e.g, set = {(0, 8), (16, 24)}
     lookup of (0, 32) should return entry index 0, 16 and
     set = {(0, 8), (8, 8), (16, 24), (24, 8)}
I 'm thinking of evaluating JudyArray for this purpose. Is it possible
to use JudyArray to solve this problem faster than a linked list or a range 
tree? which
Judy variation will be most suited? And how? Thanks for the suggestions.

________________________________
From: Justin Foutts <jmf...@ya...>
To: judy <jud...@li...>
Sent: Tue, February 8, 2011 1:51:08 PM
Subject: Re: Future

Towards a lightweight C++ wrapper, here is basic some code I just wrote to 
efficiently mimic an STL style container.  

Note:
- I have issues with including Judy.h in every file in my project, so I hide the 
Judy calls in a .cpp file.
- I assume using namespace std (or using namespace EASTL in my case)

If the style of tricks and hacks is approved of then I will gladly submit a 
complete version.

Thanks,
Justin

struct judysmap_impl {
    void *impl;

    ~judysmap_impl();
    judysmap_impl() : impl(0) {}

     void remove(const char *);
     void set(const char *, void *val);
     void **set(const char *);
     void **get(const char *);

    struct iterator {
        judysmap_impl *impl;
        char *k;
        void **v;

        static const int keymax = 1024;
        char buf[keymax];
        bool done;

        iterator(judysmap_impl *impl) : impl(impl), k(0), v(0), done(0) { 
buf[0]=0; }
        iterator(const iterator &r) : impl(r.impl), k(r.k), v(r.v), done(r.done) 
{ strncpy(buf, r.buf, sizeof(buf)); }

        bool operator!=(const iterator &r) { return done != r.done || (!done && 
strcmp(buf, r.buf)); }
        void operator++(int) { impl->next(this); }
    };

     void begin(iterator *) const;
     void next(iterator *) const;
     void _fill(iterator *, void *) const;
};

template <class X, class Y> struct judysmap {
    judysmap_impl impl;
    judysmap() { if (sizeof(Y) > sizeof(void*)) fatal("invalid value size %d > 
%d", sizeof(Y), sizeof(void*)); }

    typedef judysmap<X, Y> this_type;
    typedef Y              value_type;

    struct charptr { /* emulate std::string */
        const char *v;
        charptr() : v(0) {}
        const char *data() const { return v; }
        const char *c_str() const { return v; }
        int size() const { return strlen(v); }
        int length() const { return strlen(v); }
        bool empty() const { return !v || !*v; }
        const char& operator[](size_t pos) { return v[pos]; }
        string substr(size_t pos=0, size_t n=string::npos) const { return 
string(v, pos, n); } /* assumes using namespace std */
    };

    struct const_iterator {
        judysmap_impl::iterator impl;
        charptr first;
        value_type second;

        const_iterator(const this_type *parent) : 
impl((judysmap_impl*)&parent->impl) { first.v=impl.buf; }
        const_iterator(const const_iterator &r) : impl(r.impl), first(r.first), 
second(r.second) { first.v=impl.buf; }
        const const_iterator& operator*() const { return *this; }
        bool operator!=(const const_iterator &r) { return impl != r.impl; }
        void operator++() { impl++; assignSecond(); }
        void operator++(int) { impl++; assignSecond(); }
        void assignSecond() { if (!impl.done) second = *(value_type *)impl.v; }
    };

    const_iterator begin() const { const_iterator iter(this); 
impl.begin(&iter.impl); iter.assignSecond(); return iter; }
    const_iterator end() const { const_iterator iter(this); iter.impl.done=1; 
return iter; }

    value_type& operator[](string k) { return *(value_type 
*)impl.set(k.c_str()); }
};

#include "Judy.h"

judysmap_impl::~judysmap_impl() { if (!impl) return; int rc; JSLFA(rc, impl); }

void judysmap_impl::remove(const char* k) { int rc; JSLD(rc, impl, (const 
unsigned char *)k); }
void judysmap_impl::set(const char* k, void *v) { void *val; JSLI(val, impl, 
(const unsigned char *)k); *(void**)val = v; }
void **judysmap_impl::set(const char *k) { void *val; JSLI(val, impl, (const 
unsigned char *)k); return (void**)val; }
void **judysmap_impl::get(const char* k) { void *val; JSLG(val, impl, (const 
unsigned char *)k); return (void**)val; }

#define MyStrMapIter ((unsigned char*)iter->buf)
void judysmap_impl::begin(iterator *iter) const { *MyStrMapIter=0; void *val; 
JSLF(val, impl, MyStrMapIter); _fill(iter, val); }
void judysmap_impl::next(iterator *iter) const { void *val; JSLN(val, impl, 
MyStrMapIter); _fill(iter, val); }
void judysmap_impl::_fill(iterator *iter, void *arg) const { if ((iter->done = 
!arg)) return; iter->k = (char*)MyStrMapIter; iter->v = (void **)arg; }

int main(int argc, char *argv[]) {

    typedef judysmap<string, int> map_t;
    map_t test;

    test["cat"] = 33;
    test["dog"] = 55;

    for (map_t::const_iterator i = test.begin(); i != test.end(); i++)
        printf("%s = %d\n", (*i).first.c_str(), (*i).second);

    return 0;
}

--- On Thu, 2/3/11, john skaller <sk...@us...> wrote:

>From: john skaller <sk...@us...>
>Subject: Future
>To: "judy" <jud...@li...>
>Date: Thursday, February 3, 2011, 12:23 AM
>
>
>What's going to happen with Judy? Is there any interest doing some
>development on GitHub? [Felix project already has Judy on GitHub]
>
>What I'd like to see, initially:
>
>1. Get rid of the confusing macros. Nice idea, but the confusion between 
lvalues
>and values is made worse with the macros.
>
>More precisely, keep the macros but move them to a separate file.
>
>2. Fix the documentation to provide more detailed explanation of each
>function. At present you have to understand the conventions and 
>mentally figure out what should be happening. 
>
>3. Provide a lightweight C++ wrapper.
>
>4. Think about re-entrant version of the Google version, which 
>reduces the overhead in JudyNext having to lookup the key
>it found last time. The google version stores the internal state
>so the next call can proceed without a full scale lookup from
>the top. However it does it the wrong way, embedding the state
>in the array, instead of making the client hold it.
>
>5. Fix the disgusting build system.
>
>6. Make it possible to build BOTH 32 and 64 bit versions on all
>platforms. It's not clear 32->64 and 64->32 bit JudyL can be done,
>but is there a reason I can't have a 32 bit version on a 64 bit machine?
>The 32 bit version does 4 level lookups .. the 64 bit one does 8,
>if my key is an "int" it is only 32 bits anyhow, so the first 4 bytes of
>the key will always be zero.
>
>My basic opinion is: Judy is very well designed. but it isn't well known
>or used as often as it should be. 
>
>--
>john skaller
>sk...@us...
>
>
>
>
>
>------------------------------------------------------------------------------
>Special Offer-- Download ArcSight Logger for FREE (a $49 USD value)!
>Finally, a world-class log management solution at an even better price-free!
>Download using promo code Free_Logger_4_Dev2Dev. Offer expires 
>February 28th, so secure your free ArcSight Logger TODAY! 
>http://p.sf.net/sfu/arcsight-sfd2d
>_______________________________________________
>Judy-devel mailing list
>Jud...@li...
>https://lists.sourceforge.net/lists/listinfo/judy-devel
> 