From: john s. <sk...@us...> - 2011-02-03 08:23:51
|
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... |
From: john s. <sk...@us...> - 2011-02-03 15:23:46
|
On 03/02/2011, at 7:23 PM, john skaller wrote: > 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: 7. Add first/next or so to JudyHS. Even though there's no order I don't care, there has to be a way to get all entries: I can't use it with my garbage collector unless I can find all reachable pointers, which means I have to be able to scan all values in all kinds of containers. -- john skaller sk...@us... |
From: Alan S. <aj...@fr...> - 2011-02-03 17:32:40
|
> 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. Amen! I think I mentioned before that late in the project Doug ditched my highly technical manual entries (written by a programmer, for programmers) for the lighter-weight ones you see today, aiming to get greater acceptance. I don't think it worked. > 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. Sounds right, and good, to me. > 5. Fix the disgusting build system. Yeah, for that I apologize myself, it was the best I knew how to do at the time with the tools in hand. Linux autoconf/etc weren't well known to us. > My basic opinion is: Judy is very well designed. but it isn't well > known or used as often as it should be. Yeah, that's about right I think. I've always been disappointed that something so profoundly significant we discovered turned out to be so hard to embody, explain, share, and put into use. So it goes. Cheers, Alan Silverstein |
From: john s. <sk...@us...> - 2011-02-04 10:00:23
|
On 04/02/2011, at 4:32 AM, Alan Silverstein wrote: > >> 5. Fix the disgusting build system. > > Yeah, for that I apologize myself, it was the best I knew how to do at > the time with the tools in hand. Linux autoconf/etc weren't well known > to us. Gak, they're even more disgusting! :) Judy needs very little configuration data: 32 or 64 bit and a typename for "Word_t" = uintptr_t is about it. However a lot of stuff is done to avoid duplication by generating various information. In Felix version of the code base, I just generated the only two sane options (32, 64 bit) and the choose between them. Nothing wrong with generating tables, but it should be necessary for the building of Judy, since that involves compiling and running code on the target platform which doesn't do well if you're cross compiling. Anyhow I think a small team can easily fix this stuff without changing any of the actual code. BTW: Felix uses Python script to build Judy. We won't touch make, let alone autoconf. We need code that builds on Windows too. >> My basic opinion is: Judy is very well designed. but it isn't well >> known or used as often as it should be. > > Yeah, that's about right I think. I've always been disappointed that > something so profoundly significant we discovered turned out to be so > hard to embody, explain, share, and put into use. So it goes. Ah well .. Felix is becoming the best programming language around but has no users apart from me :) So it goes.. -- john skaller sk...@us... |
From: Justin F. <jmf...@ya...> - 2011-02-08 21:51:15
|
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 |
From: john s. <sk...@us...> - 2011-02-08 23:59:34
|
On 09/02/2011, at 8:51 AM, Justin Foutts wrote: > 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. 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. > > 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 > > ------------------------------------------------------------------------------ > 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_______________________________________________ > Judy-devel mailing list > Jud...@li... > https://lists.sourceforge.net/lists/listinfo/judy-devel -- john skaller sk...@us... |
From: Justin F. <jmf...@ya...> - 2011-02-09 21:33:23
|
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 <sk...@us...> 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. ____________________________________________________________________________________ Food fight? Enjoy some healthy debate in the Yahoo! Answers Food & Drink Q&A. http://answers.yahoo.com/dir/?link=list&sid=396545367 |
From: Justin F. <jmf...@ya...> - 2011-02-09 23:54:24
|
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 <jmf...@ya...> wrote: From: Justin Foutts <jmf...@ya...> Subject: Re: Future To: "john skaller" <sk...@us...> Cc: "judy" <jud...@li...> 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 <sk...@us...> 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 Jud...@li... https://lists.sourceforge.net/lists/listinfo/judy-devel ____________________________________________________________________________________ Now that's room service! Choose from over 150,000 hotels in 45,000 destinations on Yahoo! Travel to find your fit. http://farechase.yahoo.com/promo-generic-14795097 |
From: john s. <sk...@us...> - 2011-02-10 00:07:13
|
On 10/02/2011, at 8:33 AM, Justin Foutts wrote: > 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. Generally I agree. However, you still need the error flag because some Judy functions require you to examine it for normal operation: I think JudyByCount or something. Also, you need the error code to be able to throw something meaningful, in fact you should make a wrapper for the error code and throw that. > > Sorry I'm still using the macros :/. Should I upgrade my Judy to the new small implementation? Don't know what that is. Just expand the macros by hand. Macros suck. So do C++ references: generally pointers should be used instead. Same reason: they hide when a variable is required to be an lvalue. > > 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. If I were doing this, the first thing I would do would be to make a *lightweight* wrapper. That is, I'd implement the Judy C functions in C++ *exactly* the same signatures *except* that the array variable and error is replaced by a C++ class. Eg instead of Judy1First(array, key, error) you'd have array->Judy1First(key, error) The array is the object now. The point of this wrapper is that there's nothing to learn to use it, all the Judy docs are still applicable (except that the array argument is now a class and the functions are method). There is the issue whether to put the error in the class or not. If you don't, you have to provide it everywhere, but the class is then exactly one pointer size, and its compatible with a C Judy array so you can actually cast between them. Otherwise, you could eliminate the error by throwing it: that gets rid of the variable easily :) > > Great suggestion regarding boost::enable_if. I am still trying to figure out how it works :) It uses a side-effect that certain constructions can fail to compile without error. I think this arose from smart pointers: you can use some methods of a class when other method can't compile. That's allowed. There's a name for it, SNAFE or something. -- john skaller sk...@us... |
From: Justin F. <jmf...@ya...> - 2011-02-10 01:05:17
|
John, I see what you mean about a proper Judy wrapper. My goal was to implement std::map, rather than to best wrap Judy. I also just realized that Aleksey Cheusov has already done the same thing: http://judyhash.sourceforge.net/ However Aleksey's implementation does not appear to support JudySL, and instead handles string maps with a hash function. I will continue to maintain my version at: http://lucidfusionlabs.com/svn/lflpub/lfapp/judymap.h Thanks, Justin --- On Wed, 2/9/11, john skaller <sk...@us...> wrote: From: john skaller <sk...@us...> Subject: Re: Future To: "Justin Foutts" <jmf...@ya...> Cc: "judy" <jud...@li...> Date: Wednesday, February 9, 2011, 4:06 PM On 10/02/2011, at 8:33 AM, Justin Foutts wrote: > 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. Generally I agree. However, you still need the error flag because some Judy functions require you to examine it for normal operation: I think JudyByCount or something. Also, you need the error code to be able to throw something meaningful, in fact you should make a wrapper for the error code and throw that. > > Sorry I'm still using the macros :/. Should I upgrade my Judy to the new small implementation? Don't know what that is. Just expand the macros by hand. Macros suck. So do C++ references: generally pointers should be used instead. Same reason: they hide when a variable is required to be an lvalue. > > 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. If I were doing this, the first thing I would do would be to make a *lightweight* wrapper. That is, I'd implement the Judy C functions in C++ *exactly* the same signatures *except* that the array variable and error is replaced by a C++ class. Eg instead of Judy1First(array, key, error) you'd have array->Judy1First(key, error) The array is the object now. The point of this wrapper is that there's nothing to learn to use it, all the Judy docs are still applicable (except that the array argument is now a class and the functions are method). There is the issue whether to put the error in the class or not. If you don't, you have to provide it everywhere, but the class is then exactly one pointer size, and its compatible with a C Judy array so you can actually cast between them. Otherwise, you could eliminate the error by throwing it: that gets rid of the variable easily :) > > Great suggestion regarding boost::enable_if. I am still trying to figure out how it works :) It uses a side-effect that certain constructions can fail to compile without error. I think this arose from smart pointers: you can use some methods of a class when other method can't compile. That's allowed. There's a name for it, SNAFE or something. -- john skaller sk...@us... |
From: Justin F. <jmf...@ya...> - 2011-02-11 01:05:32
|
http://lucidfusionlabs.com/svn/lflpub/lfapp/judymap.h I have updated the code to use template partial specialization to unify the string and word implementations into one judymap. And updated the integration recommendations: #ifdef USING_JUDY#define Map(K, V) judymap<K, V>#else#define Map(K, V) map<K, V>#endif By substituting "typedef Map(k, v) map_t" in place of "typedef map<k, v> map_t" Judy can be used as a complete drop in replacement for std::map. I happily use Judy for my default map implementation on Windows, Mac OSX, and Linux. However on iPhone I substitute EASTL's map. Thanks,Justin --- On Wed, 2/9/11, Justin Foutts <jmf...@ya...> wrote: From: Justin Foutts <jmf...@ya...> Subject: Re: Future To: "john skaller" <sk...@us...> Cc: "judy" <jud...@li...> Date: Wednesday, February 9, 2011, 5:05 PM John, I see what you mean about a proper Judy wrapper. My goal was to implement std::map, rather than to best wrap Judy. I also just realized that Aleksey Cheusov has already done the same thing: http://judyhash.sourceforge.net/ However Aleksey's implementation does not appear to support JudySL, and instead handles string maps with a hash function. I will continue to maintain my version at: http://lucidfusionlabs.com/svn/lflpub/lfapp/judymap.h Thanks, Justin --- On Wed, 2/9/11, john skaller <sk...@us...> wrote: From: john skaller <sk...@us...> Subject: Re: Future To: "Justin Foutts" <jmf...@ya...> Cc: "judy" <jud...@li...> Date: Wednesday, February 9, 2011, 4:06 PM On 10/02/2011, at 8:33 AM, Justin Foutts wrote: > 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. Generally I agree. However, you still need the error flag because some Judy functions require you to examine it for normal operation: I think JudyByCount or something. Also, you need the error code to be able to throw something meaningful, in fact you should make a wrapper for the error code and throw that. > > Sorry I'm still using the macros :/. Should I upgrade my Judy to the new small implementation? Don't know what that is. Just expand the macros by hand. Macros suck. So do C++ references: generally pointers should be used instead. Same reason: they hide when a variable is required to be an lvalue. > > 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. If I were doing this, the first thing I would do would be to make a *lightweight* wrapper. That is, I'd implement the Judy C functions in C++ *exactly* the same signatures *except* that the array variable and error is replaced by a C++ class. Eg instead of Judy1First(array, key, error) you'd have array->Judy1First(key, error) The array is the object now. The point of this wrapper is that there's nothing to learn to use it, all the Judy docs are still applicable (except that the array argument is now a class and the functions are method). There is the issue whether to put the error in the class or not. If you don't, you have to provide it everywhere, but the class is then exactly one pointer size, and its compatible with a C Judy array so you can actually cast between them. Otherwise, you could eliminate the error by throwing it: that gets rid of the variable easily :) > > Great suggestion regarding boost::enable_if. I am still trying to figure out how it works :) It uses a side-effect that certain constructions can fail to compile without error. I think this arose from smart pointers: you can use some methods of a class when other method can't compile. That's allowed. There's a name for it, SNAFE or something. -- john skaller sk...@us... -----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 Jud...@li... https://lists.sourceforge.net/lists/listinfo/judy-devel |
From: john s. <sk...@us...> - 2011-02-11 01:31:53
|
On 11/02/2011, at 12:05 PM, Justin Foutts wrote: > http://lucidfusionlabs.com/svn/lflpub/lfapp/judymap.h > > I have updated the code to use template partial specialization to unify the string and word implementations into one judymap. And updated the integration recommendations: > > #ifdef USING_JUDY > #define Map(K, V) judymap<K, V> > #else > #define Map(K, V) map<K, V> > #endif > > By substituting "typedef Map(k, v) map_t" in place of "typedef map<k, v> map_t" Judy can be used as a complete drop in replacement for std::map. Well, not quite: you still have a restriction on sizeof(Y). You can get rid of that: if Y is too big, you can just clone it onto the heap and store a pointer. This shouldn't be done automatically: should be another class (JudyLPtr or something). Clearly there's an issue here if you delete something, you have to also delete the heap object. Although Felix generates C++ it also uses a GC, so if that were used by Felix you'd actually NOT want to delete anything (the GC would do it automatically which is much better because there's no issue of invalidating pointers). Rather, the GC needs a way to scan Judy arrays, which it can do now. In fact Felix can't can STL containers yet, but it can scan Judy arrays :) -- john skaller sk...@us... |
From: Justin F. <jmf...@ya...> - 2011-02-11 02:09:50
|
Ah yes, you're right. :) A "complete drop in replacement" given that "the key and value parameters meet the restrictions (sizeof(K) <= sizeof(void*) || K==string) && sizeof(V) <= sizeof(void*)" The majority of my maps meet this criteria, however when they do not I fall back to an STL implementation. Also the restrictions are now statically asserted by the trick you recommended. Thanks,Justin --- On Thu, 2/10/11, john skaller <sk...@us...> wrote: From: john skaller <sk...@us...> Subject: Re: Future To: "Justin Foutts" <jmf...@ya...> Cc: "judy" <jud...@li...> Date: Thursday, February 10, 2011, 5:31 PM On 11/02/2011, at 12:05 PM, Justin Foutts wrote: > http://lucidfusionlabs.com/svn/lflpub/lfapp/judymap.h > > I have updated the code to use template partial specialization to unify the string and word implementations into one judymap. And updated the integration recommendations: > > #ifdef USING_JUDY > #define Map(K, V) judymap<K, V> > #else > #define Map(K, V) map<K, V> > #endif > > By substituting "typedef Map(k, v) map_t" in place of "typedef map<k, v> map_t" Judy can be used as a complete drop in replacement for std::map. Well, not quite: you still have a restriction on sizeof(Y). You can get rid of that: if Y is too big, you can just clone it onto the heap and store a pointer. This shouldn't be done automatically: should be another class (JudyLPtr or something). Clearly there's an issue here if you delete something, you have to also delete the heap object. Although Felix generates C++ it also uses a GC, so if that were used by Felix you'd actually NOT want to delete anything (the GC would do it automatically which is much better because there's no issue of invalidating pointers). Rather, the GC needs a way to scan Judy arrays, which it can do now. In fact Felix can't can STL containers yet, but it can scan Judy arrays :) -- john skaller sk...@us... |
From: Bisht, P. <pra...@ya...> - 2011-02-12 00:27:32
|
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 > |
From: john s. <sk...@us...> - 2011-02-12 00:57:50
|
On 12/02/2011, at 11:27 AM, Bisht, Pradeep wrote: > 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. I think Judy1 can do this easily. You can use Judy1First and Judy1Next to find all the extant entries. Since there's only 256 entries per set, it's not too hard to put all of the entries in a range in. You can find all the "holes" the same way. After you get these results you can optimise them to use ranges. If you want to use ranges directly, I think you can also do it with JudyL. This is a bit harder, but I do a similar thing with my garbage collector. You make a map: lowvalue --> high value to represent a range. Then when scanning you do this: JudyLFirst will find the NEXT key after the one you want most of the time (unless you actually hit the key). So then you use JudyLPrev to go back one key, and get the previous start/end range. Now you can check if your input start value is in that range or not: if so it's the start of the range and you have the end as the minimum of the stored end and your input end of range. Otherwise the key you previously found is the start of the range provided it is greater than your input end of range. So now you can use JudyLNext to get all the subsequent ranges until you overshoot. This is O(1). No way to do it faster. The inverse (holes between the selected ranges) is trivial. So yes, I'd say Judy is perfect for this job :) -- john skaller sk...@us... |
From: Bisht, P. <pra...@ya...> - 2011-02-12 02:22:08
|
Thanks John. I was using JudyL and was wondering if there is any clever way of avoiding that back and forth search. ________________________________ From: john skaller <sk...@us...> To: "Bisht, Pradeep" <pra...@ya...> Cc: judy <jud...@li...> Sent: Fri, February 11, 2011 4:57:20 PM Subject: Re: range lookup using Judy; On 12/02/2011, at 11:27 AM, Bisht, Pradeep wrote: > 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. I think Judy1 can do this easily. You can use Judy1First and Judy1Next to find all the extant entries. Since there's only 256 entries per set, it's not too hard to put all of the entries in a range in. You can find all the "holes" the same way. After you get these results you can optimise them to use ranges. If you want to use ranges directly, I think you can also do it with JudyL. This is a bit harder, but I do a similar thing with my garbage collector. You make a map: lowvalue --> high value to represent a range. Then when scanning you do this: JudyLFirst will find the NEXT key after the one you want most of the time (unless you actually hit the key). So then you use JudyLPrev to go back one key, and get the previous start/end range. Now you can check if your input start value is in that range or not: if so it's the start of the range and you have the end as the minimum of the stored end and your input end of range. Otherwise the key you previously found is the start of the range provided it is greater than your input end of range. So now you can use JudyLNext to get all the subsequent ranges until you overshoot. This is O(1). No way to do it faster. The inverse (holes between the selected ranges) is trivial. So yes, I'd say Judy is perfect for this job :) -- john skaller sk...@us... |
From: john s. <sk...@us...> - 2011-02-12 07:34:03
|
On 12/02/2011, at 1:22 PM, Bisht, Pradeep wrote: > Thanks John. I was using JudyL and was wondering if there is any clever way of avoiding that back and forth search. but you only need to do that once at the start. My GC code looks like this: void flx_collector_t::scan_object(void *p, int reclimit) { Word_t reachable = (parity & 1UL) ^ 1UL; Word_t cand = (Word_t)p; Word_t fp=cand; Word_t *w = (Word_t*)JudyLLast(j_shape,&fp,&je); if(w==(Word_t*)PPJERR)judyerror("scan_object"); if(w == NULL) return; // no lower object if( (*w & 1UL) == reachable) return; // already handled gc_shape_t *shape = (gc_shape_t*)(*w & ~1UL); unsigned long n = get_count((void*)fp) * shape->count * shape->amt; if(cand >= (Word_t)(void*)((unsigned char*)(void*)fp+n)) return; // not interior *w = (*w & ~1uL) | reachable; ... This take a pointer which may be interior to an object, and looks it up. The shape contains a length which is added to the adjusted pointer then the original pointer is compare to see if it sits higher than that. If so, it's between the start and end of the object. Your code would be the same, but only for the first range. After that you can just scan sequentially for the rest of the ranges. -- john skaller sk...@us... |