Sorry, bugfix in judysmap_impl.

-        iterator(const iterator &r) : impl(r.impl), k(r.k), v(r.v), done(r.done) { strncpy(buf, r.buf, sizeof(buf)); }
+        iterator(const iterator &r) : impl(r.impl), k(buf), v(r.v), done(r.done) { strncpy(buf, r.buf, sizeof(buf)); }

-Justin

--- On Wed, 2/9/11, Justin Foutts <jmfoutts@yahoo.com> wrote:

From: Justin Foutts <jmfoutts@yahoo.com>
Subject: Re: Future
To: "john skaller" <skaller@users.sourceforge.net>
Cc: "judy" <judy-devel@lists.sourceforge.net>
Date: Wednesday, February 9, 2011, 1:33 PM

Hi John,

Thanks.  Great points.

Yes there is no error handling :)  In my own philosophy data-structures should assert or throw if they detect internal corruption and crash on null dereference if malloc returns zero.

Sorry I'm still using the macros :/.  Should I upgrade my Judy to the new small implementation?

Most of std::map is implemented below.  I am using the code as a drop in replacement by changing a few typedefs.

Yes the STL iterator model does not fit Judy perfectly.

Great suggestion regarding boost::enable_if.  I am still trying to figure out how it works :)

Thanks,
Justin

/* This code is free as in beer -Justin Foutts */

/* QUICK START:
using namespace std;
Replace map<string, X> with judysmap<string, X> and map<void*, X> with judymap<void *, X> 

-* DESCRIPTION: 
Implements std::map according to http: //www.cplusplus.com/reference/stl/map/
EXCEPT FOR: operator=, swap, rbegin, rend, key_comp, value_comp, erase(beg, end), equal_range, get_alloactor, and max_size

-* EXAMPLE:

typedef judysmap<string, int> map_t;

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

for (map_t::iterator i = test.begin(); i != test.end(); i++) {
    info("%s %d\n", (*i).first.c_str(), (*i).second);
    if (i == test.begin()) (*i).second = 99;
}

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

struct judymap_impl {
    void *impl;

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

    void clear();
    int remove(void *k);
    void set(void *k, void *v);
    void **set(void *k);
    void **get(void *k);
    int size() const;

    struct iterator {
        judymap_impl *impl;
        void *k, **v;
        bool done;

        iterator(judymap_impl *Impl, void *K=0) : impl(Impl), k(K), v(0), done(0) { if (k) done = !(v = impl->get(k)); }
        iterator(const iterator &r) : impl(r.impl), k(r.k), v(r.v), done(r.done) {}

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

    void begin(iterator *iter) const;
    void next(iterator *iter) const;
    void next(iterator *iter, void *k) const;
    void assignKV(iterator *iter, void *arg) const;
};

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

    typedef judymap<X, Y> this_type;
    typedef X             key_type;
    typedef Y             value_type;

    struct pair {
        key_type first;
        value_type &second;
        pair(key_type k, value_type *v) : first(k), second(*v) {}
    };

    struct const_pair {
        const key_type first;
        const value_type &second;
        const_pair(key_type k, value_type *v) : first(k), second(*v) {}
    };

    struct iterator {
        judymap_impl::iterator impl;

        iterator()                                   : impl(0) {}
        iterator(const iterator &r)                  : impl(r.impl) {}
        iterator(const this_type *parent, void *k=0) : impl((judymap_impl*)&parent->impl, k) {}

        iterator& operator=(const iterator &r) { impl=r.impl; return *this; }

        pair       operator*()       { return       pair((key_type)impl.k, (value_type*)impl.v); } /* non const dereference */
        const_pair operator*() const { return const_pair((key_type)impl.k, (value_type*)impl.v); }

        bool operator==(const iterator &r) { return   impl == r.impl;  }
        bool operator!=(const iterator &r) { return !(impl == r.impl); }

        void operator++()    { impl++; }
        void operator++(int) { impl++; }
    };

    struct const_iterator {
        judymap_impl::iterator impl;
        
        const_iterator()                                   : impl(0) {}
        const_iterator(const const_iterator &r)            : impl(r.impl) {}
        const_iterator(const iterator &r)                  : impl(r.impl) {} /* cross copy constructor */
        const_iterator(const this_type *parent, void *k=0) : impl((judymap_impl*)&parent->impl, k) {}

        const_iterator& operator=(const const_iterator &r) { impl=r.impl; return *this; }

        const_pair operator*() const { return const_pair((key_type)impl.k, (value_type*)impl.v); }

        bool operator==(const const_iterator &r) { return   impl == r.impl;  }
        bool operator!=(const const_iterator &r) { return !(impl == r.impl); }

        void operator++()    { impl++; }
        void operator++(int) { impl++; }
    };

    int size() const { return impl.size(); }
    bool empty() const { return !size(); }

    void clear() { impl.clear(); }

    iterator       begin()       { iterator       iter(this); impl.begin(&iter.impl); return iter; }
    const_iterator begin() const { const_iterator iter(this); impl.begin(&iter.impl); return iter; }

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

    iterator       find(const key_type &k)       { iterator       iter(this, (void*)k); return iter; }
    const_iterator find(const key_type &k) const { const_iterator iter(this, (void*)k); return iter; }

    iterator       lower_bound(const key_type &k)       { iterator       iter(this, (void*)k); if (!iter.impl.done) return iter; impl.next(&iter.impl, (void*)k); return iter; }
    const_iterator lower_bound(const key_type &k) const { const_iterator iter(this, (void*)k); if (!iter.impl.done) return iter; impl.next(&iter.impl, (void*)k); return iter; }

    iterator       upper_bound(const key_type &k)       { iterator       iter(this, (void*)k);                                   impl.next(&iter.impl, (void*)k); return iter; }
    const_iterator upper_bound(const key_type &k) const { const_iterator iter(this, (void*)k);                                   impl.next(&iter.impl, (void*)k); return iter; }

    void erase(iterator it) { impl.remove(it.impl.k); }
    int  erase(const key_type &k) { return impl.remove((void*)k); }

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

struct judysmap_impl {
    void *impl;

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

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

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

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

        iterator(judysmap_impl *Impl, const char *K=0) : impl(Impl), k(K), v(0), done(0) { buf[0]=0; if (k) { done = !(v = impl->get(k)); k = buf; } }
        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 && !r.done && !strcmp(buf, r.buf)); }
        void operator++(int) { impl->next(this); }
    };

    void begin(iterator *) const;
    void next(iterator *) const;
    void next(iterator *, const char *k) const;
    void assignKV(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 X              key_type;
    typedef Y              value_type;
    
    struct charptr { /* emulate std::string */
        const char *v;
        charptr(const char *V=0) : v(V) {}
        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 pair {
        charptr first;
        value_type &second;
        pair(const char *k, value_type *v) : first(k), second(*v) {}
    };
    
    struct const_pair {
        const charptr first;
        const value_type &second;
        const_pair(const char *k, value_type *v) : first(k), second(*v) {}
    };

    struct iterator {
        judysmap_impl::iterator impl;

        iterator()                  : impl(0)      {}
        iterator(const iterator &r) : impl(r.impl) {}

        iterator(const this_type *parent, string k) : impl((judysmap_impl*)&parent->impl, k.c_str()) {}
        iterator(const this_type *parent)           : impl((judysmap_impl*)&parent->impl) {}

        iterator& operator=(const iterator &r) { impl=r.impl; return *this; }

        pair       operator*()       { return       pair(impl.buf, (value_type*)impl.v); } /* non const dereference */
        const_pair operator*() const { return const_pair(impl.buf, (value_type*)impl.v); }

        bool operator==(const iterator &r) { return   impl == r.impl;  }
        bool operator!=(const iterator &r) { return !(impl == r.impl); }

        void operator++()    { impl++; }
        void operator++(int) { impl++; }
    };

    struct const_iterator {
        judysmap_impl::iterator impl;

        const_iterator()                        : impl(0)      {}
        const_iterator(const const_iterator &r) : impl(r.impl) {}
        const_iterator(const       iterator &r) : impl(r.impl) {} /* cross copy constructor */

        const_iterator(const this_type *parent, string k) : impl((judysmap_impl*)&parent->impl, k.c_str()) {}
        const_iterator(const this_type *parent)           : impl((judysmap_impl*)&parent->impl) {}

        const_iterator& operator=(const const_iterator &r) { impl=r.impl; return *this; }

        const_pair operator*() const { return const_pair(impl.buf, (value_type *)impl.v); }

        bool operator==(const const_iterator &r) { return   impl == r.impl;  }
        bool operator!=(const const_iterator &r) { return !(impl == r.impl); }

        void operator++()    { impl++; }
        void operator++(int) { impl++; }
    };

    void clear() { impl.clear(); }

    iterator       begin()       { iterator       iter(this); impl.begin(&iter.impl); return iter; }
    const_iterator begin() const { const_iterator iter(this); impl.begin(&iter.impl); return iter; }

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

    iterator       find(const key_type &k)       { iterator       iter(this, k); return iter; }
    const_iterator find(const key_type &k) const { const_iterator iter(this, k); return iter; }

    iterator       lower_bound(const key_type &k)       { iterator       iter(this, k); if (!iter.impl.done) return iter; impl.next(&iter.impl, k.c_str()); return iter; }
    const_iterator lower_bound(const key_type &k) const { const_iterator iter(this, k); if (!iter.impl.done) return iter; impl.next(&iter.impl, k.c_str()); return iter; }

    iterator       upper_bound(const key_type &k)       { iterator       iter(this, k);                                   impl.next(&iter.impl, k.c_str()); return iter; }
    const_iterator upper_bound(const key_type &k) const { const_iterator iter(this, k);                                   impl.next(&iter.impl, k.c_str()); return iter; }

    void erase(iterator it) { impl.remove((*it).first.c_str()); }
    int  erase(const key_type &k) { return impl.remove(k.c_str()); }

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

#include "Judy.h"

judymap_impl::~judymap_impl() { clear(); }
void judymap_impl::clear() { if (!impl) return; int rc; JLFA(rc, impl); impl=0; }
int judymap_impl::remove(void *k) { Word_t key=(Word_t)k; int rc; JLD(rc, impl, key); return rc; }
void judymap_impl::set(void *k, void *v) { Word_t key=(Word_t)k; void *val; JLI(val, impl, key); *(void**)val = v; }
void **judymap_impl::set(void *k) { Word_t key=(Word_t)k; void *val; JLI(val, impl, key); return (void**)val; }
void **judymap_impl::get(void *k) { Word_t key=(Word_t)k; void *val; JLG(val, impl, key); return (void**)val; }
int judymap_impl::size() const { if (!impl) return 0; int rc; JLC(rc, impl, 0, -1); return rc; }

#define MyJudyPtrMapIter (*(Word_t*)&iter->k)
void judymap_impl::begin(iterator *iter) const { MyJudyPtrMapIter=0; void *val; JLF(val, impl, MyJudyPtrMapIter); assignKV(iter, val); }
void judymap_impl::next(iterator *iter) const { void *val; JLN(val, impl, MyJudyPtrMapIter); assignKV(iter, val); }
void judymap_impl::next(iterator *iter, void *k) const { MyJudyPtrMapIter = (Word_t)k; next(iter); }
void judymap_impl::assignKV(iterator *iter, void *arg) const { if ((iter->done = !arg)) return; iter->k = (void*)MyJudyPtrMapIter; iter->v = (void **)arg; }

judysmap_impl::~judysmap_impl() { clear(); }
void judysmap_impl::clear() { if (!impl) return; int rc; JSLFA(rc, impl); impl=0; }
int judysmap_impl::remove(const char* k) { int rc; JSLD(rc, impl, (const unsigned char *)k); return rc; }
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 MyJudyStrMapIter ((unsigned char*)iter->buf)
void judysmap_impl::begin(iterator *iter) const { *MyJudyStrMapIter=0; void *val; JSLF(val, impl, MyJudyStrMapIter); assignKV(iter, val); }
void judysmap_impl::next(iterator *iter) const { void *val; JSLN(val, impl, MyJudyStrMapIter); assignKV(iter, val); }
void judysmap_impl::next(iterator *iter, const char *k) const { strncpy((char*)MyJudyStrMapIter, k, sizeof(MyJudyStrMapIter)); next(iter); }
void judysmap_impl::assignKV(iterator *iter, void *arg) const { if ((iter->done = !arg)) return; iter->k = (char*)MyJudyStrMapIter; iter->v = (void **)arg; }



--- On Tue, 2/8/11, john skaller <skaller@users.sourceforge.net> wrote:
This is pretty reasonable. It's a bit higher level than what I would have done first,
which is a lightweight wrapper (same function calls, but just use a class for the array).

I can't see how your error handling works. Please use the C functions in the implementation,
not macros. I'd put the JError_t variable in the class, although that does have the downside
that the class value isn't compatible with a real Judy array (which is just one machine word).

Be interested to see how you integrate the other functions. You have the traditional begin()
and end() but you also need first(key), etc etc to match Judy. Perhaps even an iterator
that finds things NOT in the array (JudyFirstEmpty etc :)

It's not entirely clear to me that iterators provide the best model, but trying to use it
is the only way to tell.

BTW: have you considered Boost::enable_of style of silliness to detect
key/value size > sizeof(void*) instead of a dynamic test in the constructor?

The other way to do this would be to provide specialisations:
not sure how to do that. Judy only works with integers and pointers.



Need Mail bonding?
Go to the Yahoo! Mail Q&A for great tips from Yahoo! Answers users.

-----Inline Attachment Follows-----

------------------------------------------------------------------------------
The ultimate all-in-one performance toolkit: Intel(R) Parallel Studio XE:
Pinpoint memory and threading errors before they happen.
Find and fix more than 250 security defects in the development cycle.
Locate bottlenecks in serial and parallel code that limit performance.
http://p.sf.net/sfu/intel-dev2devfeb

-----Inline Attachment Follows-----

_______________________________________________
Judy-devel mailing list
Judy-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/judy-devel


Sucker-punch spam with award-winning protection.
Try the free Yahoo! Mail Beta.