You can subscribe to this list here.
2005 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(2) |
Aug
(1) |
Sep
|
Oct
(16) |
Nov
(6) |
Dec
(5) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2006 |
Jan
|
Feb
|
Mar
(1) |
Apr
(1) |
May
|
Jun
|
Jul
|
Aug
|
Sep
(7) |
Oct
|
Nov
|
Dec
(8) |
2007 |
Jan
|
Feb
|
Mar
(14) |
Apr
|
May
(57) |
Jun
(4) |
Jul
(6) |
Aug
(2) |
Sep
(16) |
Oct
|
Nov
(3) |
Dec
(12) |
2008 |
Jan
(16) |
Feb
(3) |
Mar
|
Apr
|
May
(11) |
Jun
(1) |
Jul
|
Aug
|
Sep
|
Oct
(2) |
Nov
(2) |
Dec
(2) |
2009 |
Jan
(1) |
Feb
(13) |
Mar
(9) |
Apr
|
May
(16) |
Jun
(4) |
Jul
(5) |
Aug
|
Sep
(15) |
Oct
|
Nov
(3) |
Dec
(4) |
2010 |
Jan
|
Feb
|
Mar
|
Apr
(2) |
May
|
Jun
|
Jul
|
Aug
|
Sep
(1) |
Oct
|
Nov
|
Dec
(14) |
2011 |
Jan
(13) |
Feb
(61) |
Mar
(5) |
Apr
(5) |
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
(8) |
Nov
(6) |
Dec
(2) |
2012 |
Jan
|
Feb
|
Mar
|
Apr
(13) |
May
(3) |
Jun
|
Jul
(2) |
Aug
(14) |
Sep
(1) |
Oct
(36) |
Nov
(37) |
Dec
(1) |
2013 |
Jan
|
Feb
(1) |
Mar
|
Apr
|
May
(2) |
Jun
|
Jul
(3) |
Aug
|
Sep
|
Oct
(4) |
Nov
(5) |
Dec
|
2014 |
Jan
(1) |
Feb
(35) |
Mar
(3) |
Apr
|
May
(7) |
Jun
(2) |
Jul
|
Aug
(1) |
Sep
(3) |
Oct
|
Nov
|
Dec
|
2015 |
Jan
|
Feb
|
Mar
(7) |
Apr
(4) |
May
(1) |
Jun
|
Jul
|
Aug
|
Sep
(1) |
Oct
|
Nov
|
Dec
|
2016 |
Jan
|
Feb
|
Mar
|
Apr
|
May
(3) |
Jun
|
Jul
|
Aug
(10) |
Sep
|
Oct
|
Nov
|
Dec
|
2017 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(1) |
Aug
|
Sep
(9) |
Oct
|
Nov
(3) |
Dec
(4) |
2020 |
Jan
(5) |
Feb
|
Mar
(2) |
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
(4) |
Dec
|
From: John S. <sk...@in...> - 2020-11-23 05:40:34
|
> On 23 Nov 2020, at 10:00, mat...@gm... wrote: > > That helped. Bug free now. Thank you :). The macro interface was a really bad idea. The problem is that it does not make explicit the crucial distinction between an lvalue and rvalue. OTOH the C interface is the most perfect interface I have seen. Once you understand it, it is always obvious what the functions return and what they accept as arguments. For example, attempting to add a key to a JudyLArray, you get a result telling if the key was found or not, and, you provide a pointer to a location into which the pointer to the value is put, whether or not the original key existed. So you can immediately store a new value or overwrite the old one, or, fetch the value already stored if the result was to find an existing key and you want to modify it. I didn’t bother looking at the code to write that explanation, I haven’t written an Judy for some time. It’s just that, what I described, is the only possible way it could work efficiently, and, therefore, that is how it actually does work :-) In other words, you can deduce the interface using logic, without looking at the specs or the code. The hallmark of quality: an empty Judy array is a NULL pointer. Beautiful. — John Skaller sk...@in... |
From: <mat...@gm...> - 2020-11-22 23:01:11
|
That helped. Bug free now. Thank you :). -----Original Message----- From: John Skaller2 <sk...@in...> Sent: Thursday, 19 November 2020 5:12 pm To: Matthew Brown <mat...@gm...> Cc: jud...@li... Subject: Re: Think I'm doing something wrong with Judy arrays Try using the bare no-macros C interface, its easier to reason about. — John Skaller sk...@in... |
From: John S. <sk...@in...> - 2020-11-19 04:28:33
|
Try using the bare no-macros C interface, its easier to reason about. — John Skaller sk...@in... |
From: <mat...@gm...> - 2020-11-19 02:55:55
|
Hi All Hope all is well with you. I think I might be doing something wrong and I'm a bit stuck. I would be grateful for any help. First off, I'm compiling with icc on Redhat 8.2 with no optimisation. Second off, the following reproduces my problem. Most of the time, it runs fine, with no issues. Maybe 1 in every 20 runs, for the same input, it crashes with the following error: "free(), invalid pointer. Aborted. Core dumped." So, .. I have a JL array. The index of the JL array is either 1,2 or 3. The 1,2 or 3 maps to one of 3 Word_t casted J1 Arrays. The 3 J1 Arrays contain Word_t casted versions of an indeterminate number of J1 Arrays that in turn contain either 1, 2 or 3 Words. In other words, I'm trying to map to all the J1 Arrays that contain a certain number (either 1, 2 or 3) of items in my program. So here's the guts of the code that I'm running to reproduce the problem. This is all it does. Just reads stuff in, stores it, then deletes it. Laid out, this is the code . Pseudo Code::::::::::::: //Declare and set the top JLArray Pvoid_t storage = (Pvoid_t)NULL; //Declare the J1Array Pvoid_t J1Array; //This is the main loop to store stuff - this NEVER crashes. The loop that works perfectly most times, but crashes sometimes, is below. Pseudo Outer Loop To Store Stuff{ //Initialise J1Array = (Pvoid_t)NULL; Pseudo Inner Loop To Get the Words for individual J1 Arrays{ //Get a Word from a file or something Get a Word from a file or something; //Set the Word in the J1Array J1S(Rc_int, J1Array, Word); }End Inner Pseudo Loop //Count how many items in the J1Array and store total in counter - either 1, 2 or 3 J1C(counter, J1Array, 0, -1); //get the mapping for the J1 Array that stores the J1 Arrays with counter items JLG(PSet, storage, counter); //if there are no J1 Arrays with counter items yet If (PSet == (PWord_t)NULL){ JLI(PSet, storage, counter); *PSet = 0; } J1S(Rc_int, (Pvoid_t)*Pset, (Word_t)J1Array); }End Outer Pseudo Loop PWord_t Pset; Word_t counter; //This is the main loop to delete stuff. This is the loop that works most of the time, but crashes sometimes. //Keep deleting stuff from storage until there is nothing left, starting with the J1Array's with 1 item, then 2 items, then 3 items. //It's inefficient, I know, but I don't mind. It is a big outer loop in the proper program, and occurs infrequently. While (storage != (Pvoid_t)NULL){ //initialise counter counter = 1; //Get the mapping (PSet) to the first Word_t casted version of the J1 Array and store the number of items in counter JLF(PSet, storage, counter); //initialise the Word_t casted version of the J1Array, which stores the J1 Arrays, which in turn store the counter items J1Array_Word = 0; //Get the first Word_t casted version of the J1Array in *PSet J1F(Rc_int, (Pvoid_t)*PSet, J1Array_Word); //Unset the same Word_t casted version of the J1Array J1U(Rc_int, (Pvoid_t)*PSet, J1Array_Word); //if there are no more If (*PSet == 0){ JLD(Rc_int, storage, counter); } //free the memory for each J1 Array storing counter items J1FA(bytes, (Pvoid_t)J1Array_Word); } |
From: John S. <sk...@in...> - 2020-03-25 00:20:24
|
Lack or resources probably. — John Skaller sk...@in... |
From: Jeff N. <jn...@tn...> - 2020-03-24 22:30:58
|
Perhaps this is explained deep in the shop manual somewhere, but I decided to be lazy and try asking here first. I'd like to have a *Boolean* array indexed by an array-of-bytes, or perhaps a string. This can be accomplished with, e.g., JHSI(PValue, PJHSArray, data, N); if (*PValue !=0 ) { Code to run when the N bytes from data were previously seen. } else { *PValue=1; Code to run when the data is new. } This allocates an 8-byte integer which is set to 1 in addition to recording the data string itself. If my data strings are relatively short, perhaps 10 or 20 bytes, would it be faster and/or smaller to "roll my own" version which would create a tree with one or more JudyL levels at the top and Judy1 trees at the bottom? Or, would this not be worth it? In the application I'm looking at right now, the strings have a fixed length, which means I can determine the geometry in advance. Also, now that 128 bit integers are fairly common, would it be possible, easy/hard, advisable/or-not, to create a 128 bit version of Judy? Then Judy1 would be able to handle a 16-byte string. Thanks in advance, -Jeff Norden, jn...@tn... Dept of Math, Tenn Tech Univ, Cookeville TN 38505 (931)372-3441 PS: hope everyone reading this is safe and healthy. |
From: John S. <sk...@in...> - 2020-01-24 09:57:13
|
> On 24 Jan 2020, at 06:29, <mat...@gm...> <mat...@gm...> wrote: > > Just to clarify, I need to walk all set indexes in random order. I thought you meant Judy1Test as you mentioned below, might be a good bet to modify to create Judy1Rand to randomly walk the Judy data structure 1 bit at a time. But checking one bit at a time would not return the Indices uniformly in a tree, without taking into account the count of Indices below a certain bit level. It would just be more fun to select an integer between 1,...,(no of indices left in Judy1 Array) and use J1BC to pick it out. Then keep repeating until none left. It doesn't need to happen too often, so all good. > > Thanks everyone for your help :). I think I've got what I need. > > Judy Arrays are awesome. indeed. There is no other data structure in existence I know of with its properties: O(1) random access O(1) linear scanning O(1) insert and delete Hashtables can do O(1) random access but do not support linear scanning. Various trees exist with good performance, such as C++ map, which is red-black tree. It has O(log N) access and scanning though. I did some tests and C++ map is actually quite good. Its not quite as fast or scalable as Judy but comes close. Its BIG advantage over Judy is that the keys can be anything totally ordered whereas Judy only supports a machine word as a key. Also, JudyL data has to be a machine word, but that can be a pointer to anything, at the cost of an extra heap allocation and a headache remembering to delete the data object. I implemented a naive digital trie and the performance was disgusting. I also implemented a smarter hybrid with reasonable performance designed to replace my use of JudyL for tracking heap allocations (in my GC). It was OK, but both Judy and C++ map were better (and bug free). The authors of Judy spent a decade tuning it. — John Skaller sk...@in... |
From: <mat...@gm...> - 2020-01-23 19:29:33
|
Just to clarify, I need to walk all set indexes in random order. I thought you meant Judy1Test as you mentioned below, might be a good bet to modify to create Judy1Rand to randomly walk the Judy data structure 1 bit at a time. But checking one bit at a time would not return the Indices uniformly in a tree, without taking into account the count of Indices below a certain bit level. It would just be more fun to select an integer between 1,...,(no of indices left in Judy1 Array) and use J1BC to pick it out. Then keep repeating until none left. It doesn't need to happen too often, so all good. Thanks everyone for your help :). I think I've got what I need. Judy Arrays are awesome. -----Original Message----- From: John Skaller2 <sk...@in...> Sent: Wednesday, 22 January 2020 7:30 PM To: Matthew Brown <mat...@gm...> Cc: judy <jud...@li...> Subject: Re: Select value in Judy1 Array at random > On 22 Jan 2020, at 07:34, Matthew Brown <mat...@gm...> wrote: > > Hi Again > > Thank you very much for your help last time (2017). > > I need to be able to get a value from a Judy1 array at random. Judy1Test(PJ1Array, Index, &JError) #define J1T(Rc_int, PJ1Array, Index) \ Rc_int = Judy1Test(PJ1Array, Index, PJE0) — John Skaller sk...@in... |
From: Matthew B. <mat...@gm...> - 2020-01-22 21:09:23
|
Gotcha. Legend :). I'll have a go. Probably beyond me though. On Wed, Jan 22, 2020 at 7:30 PM John Skaller2 <sk...@in...> wrote: > > > > On 22 Jan 2020, at 07:34, Matthew Brown <mat...@gm...> wrote: > > > > Hi Again > > > > Thank you very much for your help last time (2017). > > > > I need to be able to get a value from a Judy1 array at random. > > Judy1Test(PJ1Array, Index, &JError) > #define J1T(Rc_int, PJ1Array, Index) \ > Rc_int = Judy1Test(PJ1Array, Index, PJE0) > > > > — > John Skaller > sk...@in... > > > > > > |
From: John S. <sk...@in...> - 2020-01-22 06:46:49
|
> On 22 Jan 2020, at 07:34, Matthew Brown <mat...@gm...> wrote: > > Hi Again > > Thank you very much for your help last time (2017). > > I need to be able to get a value from a Judy1 array at random. Judy1Test(PJ1Array, Index, &JError) #define J1T(Rc_int, PJ1Array, Index) \ Rc_int = Judy1Test(PJ1Array, Index, PJE0) — John Skaller sk...@in... |
From: Matthew B. <mat...@gm...> - 2020-01-21 20:34:30
|
Hi Again Thank you very much for your help last time (2017). I need to be able to get a value from a Judy1 array at random. I'm extensively using the awesome features of Judy arrays like automatically sorted, but I need to be able to select at random too for the same data from time to time. Do you have any suggestions about the best way to do this. I know I can create an auxiliary structure using more memory and work independent of the Judy array, i.e. a random map to the data. It would be nice to write a Judy function that searches the radix-tree randomly instead, like Judy1First, but instead of ending up at the first element, zipping around in the tree at random when selecting. I'm not a C master but generally figure things out eventually. I would appreciate any help at all. Thanks very much Matt |
From: john s. <sk...@in...> - 2017-12-30 04:49:04
|
> On 30 Dec. 2017, at 14:50, Doug Baskins via Judy-devel <jud...@li...> wrote: > > Robert: > > I am afraid I mislead you. I failed to notice you were using a Microsoft 64 bit compiler. That 64 bit compiler makes > a long 32 bits in length instead of 64 bits. I.e. a constant 1L is only 32 bits. I never anticipated Microsoft would > do that. No, but you didn’t follow the ISO C standard :-) > So, every constant that has a L or UL needs to be cast to probably ((Word_t) <constant>). There is > another issue. Unless forced by casting all struct members are long long aligned. That make the jp_t struct > not correct. I dont have a Microsoft platform to do testing, You don’t need one. You can use Appveyor. However *I* do have one. I have had problems despite the changes I made to constants. If you could explain the jp_t struct issue I could fix that as well. Here is a log of the Felix build which includes the Judy build, on MS WIndows using Appveyor: https://ci.appveyor.com/project/skaller/felix/build/1.0.1461 > so I suggest you try finding a Judy that works with > Microsoft 64 bit compiler on the Web. Please send me a copy if you find one that works. Link was given to mine. I had issues until I forced by build system to 64 bit. — john skaller sk...@us... http://felix-lang.org |
From: Doug B. <dou...@ya...> - 2017-12-30 03:50:52
|
Robert: I am afraid I mislead you. I failed to notice you were using a Microsoft 64 bit compiler. That 64 bit compiler makesa long 32 bits in length instead of 64 bits. I.e. a constant 1L is only 32 bits. I never anticipated Microsoft woulddo that. So, every constant that has a L or UL needs to be cast to probably ((Word_t) <constant>). There is another issue. Unless forced by casting all struct members are long long aligned. That make the jp_t struct not correct. I dont have a Microsoft platform to do testing, so I suggest you try finding a Judy that works withMicrosoft 64 bit compiler on the Web. Please send me a copy if you find one that works. Thanks in advance, Doug Doug Baskins <dou...@ya...> On Thursday, December 28, 2017, 4:40:45 PM GMT+7, Robert Gregory <gr...@bl...> wrote: <!--#yiv5479465615 _filtered #yiv5479465615 {font-family:"Cambria Math";panose-1:2 4 5 3 5 4 6 3 2 4;} _filtered #yiv5479465615 {font-family:Calibri;panose-1:2 15 5 2 2 2 4 3 2 4;}#yiv5479465615 #yiv5479465615 p.yiv5479465615MsoNormal, #yiv5479465615 li.yiv5479465615MsoNormal, #yiv5479465615 div.yiv5479465615MsoNormal {margin:0in;margin-bottom:.0001pt;font-size:11.0pt;font-family:"Calibri", sans-serif;}#yiv5479465615 p.yiv5479465615MsoListParagraph, #yiv5479465615 li.yiv5479465615MsoListParagraph, #yiv5479465615 div.yiv5479465615MsoListParagraph {margin-top:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in;margin-bottom:.0001pt;font-size:11.0pt;font-family:"Calibri", sans-serif;}#yiv5479465615 .yiv5479465615MsoChpDefault {} _filtered #yiv5479465615 {margin:1.0in 1.0in 1.0in 1.0in;}#yiv5479465615 div.yiv5479465615WordSection1 {}#yiv5479465615 _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {} _filtered #yiv5479465615 {}#yiv5479465615 ol {margin-bottom:0in;}#yiv5479465615 ul {margin-bottom:0in;}--> Two Questions – - Are you still alive? - Would you mind answering a highly targeted question regarding your 64-bit implementation of Judy arrays? If the answer to question 1 is “no”, no reply is expected and question 2 is moot. If the answer to question 1 is “yes,” a reply to question #2 would be appreciated. If the reply to question 2 is “no,” have a happy new year (albeit free from further cheerful e-mail interruptions by me). [My question deals with an issue in JudyPrivate.h not directly addressed by the Wiki page version of the file. Using VC2013 (or Pelles C), lines 1586, 1593, and 1600 reference defined code which raises warning 4293 (shift too large) due to the fact that *something* which should be a Word_T (unsigned long long) is being treated instead as an unsigned long. I’ve stared at this for a while and don’t see anything obvious… but I may just be tired. In any event, everything is fine with 32 bit… and the first insertion works on 64 bit; however, subsequent insertions appear to work but indeed do not.] -Rob Gregory |
From: john s. <sk...@in...> - 2017-12-29 04:52:15
|
> > 64 bit machines and compilers were rare back in 2002. Obviously, the Judy code was > not tested in 64 bit with "-DSEARCH_LINEAR" defined. It was released with with > "-DSEARCH_BINARY" which means the bug at line 523 would of not be caught. > > Instead of "JU_COPY3_PINDEX_TO_LONG(i_ndex, P_leaf);" it should of been > "COPYINDEX(i_ndex, P_leaf);" on line 523. > > It works in 32 bit because the only "NONNAT" Leaf is 3, whereas 64bit has 3,5,6,7. > > If this does not work, feel free to email me and I will take the time to try it out. Er specifically is there a bug to be fixed? [I dont know off hand how we build Judy] > be faster in the future. That is why it was released that way. However, in 15 years > of testing, we have discovered a lot of things on how computers really work. Except .. they mutate so just when you think you learned something, you’re knowledge is out of date. They’re a true virus! > [My question deals with an issue in JudyPrivate.h not directly addressed by the Wiki page version of the file. Using VC2013 (or Pelles C), lines 1586, 1593, and 1600 reference defined code which raises warning 4293 (shift too large) due to the fact that *something* which should be a Word_T (unsigned long long) is being treated instead as an unsigned long. I’ve stared at this for a while and don’t see anything obvious… but I may just be tired. In any event, everything is fine with 32 bit… and the first insertion works on 64 bit; however, subsequent insertions appear to work but indeed do not.] I haven’t seen that, i build Judy on Windows regularly, but I use a version I modified myself. Basically almost all the constants written ~1L are wrong. The correction is universal: ~(intptr_t)1 Also, there’s a small patch so when built as a DLL only the public symbols are exported. https://github.com/felix-lang/felix/tree/master/src/judy Contains my fixed up version. No assurance I did it right though, since I didn’t and still don’t understand how it works. — john skaller sk...@us... http://felix-lang.org |
From: Doug B. <dou...@ya...> - 2017-12-29 04:41:14
|
Robert: Yes I am still alive and still working on Judy -- believe it or not. I would be delighted to answer very technical questions about Judy. Also hard to believe is Judy was released "-Wall" free. Compilers have improved a lot. 64 bit machines and compilers were rare back in 2002. Obviously, the Judy code wasnot tested in 64 bit with "-DSEARCH_LINEAR" defined. It was released with with "-DSEARCH_BINARY" which means the bug at line 523 would of not be caught. Instead of "JU_COPY3_PINDEX_TO_LONG(i_ndex, P_leaf);" it should of been"COPYINDEX(i_ndex, P_leaf);" on line 523. It works in 32 bit because the only "NONNAT" Leaf is 3, whereas 64bit has 3,5,6,7. If this does not work, feel free to email me and I will take the time to try it out. BTW, We have much faster Leaf search routines now. In 2002 the LINEAR andBINARY searches were about the same speed. I expected the BINARY tobe faster in the future. That is why it was released that way. However, in 15 yearsof testing, we have discovered a lot of things on how computers really work. Thank you for interest. doug Doug Baskins <dou...@ya...> On Thursday, December 28, 2017, 4:40:45 PM GMT+7, Robert Gregory <gr...@bl...> wrote: <!--#yiv7431109212 _filtered #yiv7431109212 {font-family:"Cambria Math";panose-1:2 4 5 3 5 4 6 3 2 4;} _filtered #yiv7431109212 {font-family:Calibri;panose-1:2 15 5 2 2 2 4 3 2 4;}#yiv7431109212 #yiv7431109212 p.yiv7431109212MsoNormal, #yiv7431109212 li.yiv7431109212MsoNormal, #yiv7431109212 div.yiv7431109212MsoNormal {margin:0in;margin-bottom:.0001pt;font-size:11.0pt;font-family:"Calibri", sans-serif;}#yiv7431109212 p.yiv7431109212MsoListParagraph, #yiv7431109212 li.yiv7431109212MsoListParagraph, #yiv7431109212 div.yiv7431109212MsoListParagraph {margin-top:0in;margin-right:0in;margin-bottom:0in;margin-left:.5in;margin-bottom:.0001pt;font-size:11.0pt;font-family:"Calibri", sans-serif;}#yiv7431109212 .yiv7431109212MsoChpDefault {} _filtered #yiv7431109212 {margin:1.0in 1.0in 1.0in 1.0in;}#yiv7431109212 div.yiv7431109212WordSection1 {}#yiv7431109212 _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {} _filtered #yiv7431109212 {}#yiv7431109212 ol {margin-bottom:0in;}#yiv7431109212 ul {margin-bottom:0in;}--> Two Questions – - Are you still alive? - Would you mind answering a highly targeted question regarding your 64-bit implementation of Judy arrays? If the answer to question 1 is “no”, no reply is expected and question 2 is moot. If the answer to question 1 is “yes,” a reply to question #2 would be appreciated. If the reply to question 2 is “no,” have a happy new year (albeit free from further cheerful e-mail interruptions by me). [My question deals with an issue in JudyPrivate.h not directly addressed by the Wiki page version of the file. Using VC2013 (or Pelles C), lines 1586, 1593, and 1600 reference defined code which raises warning 4293 (shift too large) due to the fact that *something* which should be a Word_T (unsigned long long) is being treated instead as an unsigned long. I’ve stared at this for a while and don’t see anything obvious… but I may just be tired. In any event, everything is fine with 32 bit… and the first insertion works on 64 bit; however, subsequent insertions appear to work but indeed do not.] -Rob Gregory |
From: john s. <sk...@us...> - 2017-11-24 06:45:42
|
> On 24 Nov. 2017, at 16:24, Doug Baskins via Judy-devel <jud...@li...> wrote: > > Matthew: > > NO, you are not using Judy correctly. I think you are being deceived by the macros > J1S and JLI. Its a bit unfortunate but the rule is DO NOT USE JUDY MACROS. The macros are very bad because they confuse values with lvalues. Unfortunately, it is the macros that are documented, rather than the underlying functions. You need instead to examine carefully the C interface in the header files. The interface is precise but also hard to understand for a reason I’ll explain in a moment. A Judy array is represented by a single machine address. When you query it, you give that address to a Judy function. However, when you wish to *modify* it, you have to instead put the address in a variable and give the address of the variable. That’s because, a new Judy array is created and the old one lost by a modification, and you have to tell Judy where to put the new one. What makes this really confusing is the woeful type system of C. JudyL arrays have keys which are single machine word and associate with them values which are single machine words. The array itself is a data structure which is represented by the machine address of the top level node, so in fact NULL is a valid Judy array, its an empy Judy array. Judy actually tries hard to use names to distinguish a machine address (pointer) form a data word (integer) by naming conventions, but in real life when you use a Judy array you often want your keys or data to actually be pointers, not pointer sized integer, and you have to cast. And so the typing is extremely hard to get right, because you have to cheat C, and because C has a very weak type system. The MACRO’s tried to make Judy easier to use but they just add another layer of confusion on top of the problems inherent in C itself. Luckily, the actual interface is perfect. Which means, when you understand what a function actually is intended to do, you will immediately know the interface. For example, JudyLGet is accepts a key (machine word), and returns the address *in* the JudyL array where the user data is stored. So you can then store a new value there. If the key doesn’t exist, you get a NULL back instead. On the other GetNext returns the next key after the given one, so instead of giving it the key, you have to give it the address of a variable containing the key, so it can replace that key with the next one. So it still returns the location of the user value, not the key. Its exactly what you want when scanning through the array. I didn’t even bother looking up the docs. I know how it works because I can *reason* what the interface must be. Perhaps the trickiest thing to understand is errors. Most Judy functions *cannot* have an error. If a real error occurs, the error code at the location you gave the function is updated. Trying to Get a key that doesn’t exist is not an error! What about trying to GetNext? Nope, that cannot be an error, how else would you find the end but to run past the last key? So for example from my own code: //fprintf(stderr,"Calling Judy for next object\n"); pshape = (Word_t*)JudyLNext(j_shape,(Word_t*)(void*)¤t,&je); // GT This is in my garbage collector. The key is the machine address of an object allocated by malloc. The value here is the “shape” of the object, which is a pointer to type descriptor. The function *returns* the pointer to the storage location *inside the Judy array* where my shape pointer lives, and it finds that location based on the key stored in the variable current. It updates the key to the next one. So you have to give Judy the *address* of the variable containing the key, not just the value of the key. At the end, the function returns NULL because there is no location *inside* the Judy array for the next value because there is no next key. If there’s an actual error, such as corrupted memory, then the error code in variable je is updated, so I have to pass it a pointer to where my error variable is. I don’t bother checking it. If you read the above explanation very carefully you understand why that function has *exactly* the correct interface, and that there is no other possible correct interface that is not more complex. Which is why I say, the interface is actually perfect. Logical reasoning plus Occams razor is enough to know what the interface HAS to be. You can rely on it. You cannot rely on the MACROS. — john skaller sk...@us... http://felix-lang.org |
From: Doug B. <dou...@ya...> - 2017-11-24 05:25:01
|
Matthew: NO, you are not using Judy correctly. I think you are being deceived by the macrosJ1S and JLI. They call JudyLIns(&storage, ..) and Judy1Set(&newPair,..); Noticethat "storage" and "newPair" etc. are actually pointers to the pointer to the actual Judy arrays.The contents of newPair and storage change as the Judy array grows. When you setnewPair and storage to NULL, you are destroying the pointers to the actual Judy arrays.After setting them to NULL, and then do a J1S() or JLI(), you are actually creatinga new Judy Arrays and abandoning the old ones. I miss comments describing whatyou are trying to accomplish. Good Luck. I hope that helps Doug Baskins <dou...@ya...> On Saturday, November 18, 2017 11:15 AM, Matthew Brown <mat...@gm...> wrote: Dear Judy Masters, I am having trouble with the following program that uses Judy Arrays. I know the program appears to be an inefficient method to achieve a certain goal, but it is the simplest program that demonstrates my problem. I would be very grateful if someone could take a look at what I am doing wrong. The problem is essentially this: stepping through the program with the debugger causes the counter variable to follow the sequence 0,1,2,1. Rather, I am expecting the sequence to be 0,1,2,3 by the successive addition of a new entry to the relevant J1 Array. I am using icc to compile both Judy and the sample program. Thank you very muchMatthew #include <stdio.h>#include <stdlib.h> #include "Judy.h" int main(void){ printf("Hello Everyone"); int Rc_int; Word_t *PValue; Word_t Value; Pvoid_t PArray; Pvoid_t Ref; Pvoid_t newPair; Pvoid_t storage; //A counter variableWord_t counter=0; newPair = (Pvoid_t) NULL; J1S(Rc_int, newPair, 1);J1S(Rc_int, newPair, 2); PArray = (Pvoid_t) NULL; J1S(Rc_int, PArray, (Word_t)newPair); storage = (Pvoid_t) NULL; JLI(PValue, storage, 2);*PValue = (Word_t)PArray; JLG(PValue, storage, 2);Value = *PValue; Ref = (Pvoid_t)Value; J1C(counter, Ref, 0, -1); newPair = (Pvoid_t)NULL; J1S(Rc_int, newPair, 3);J1S(Rc_int, newPair, 4); JLG(PValue, storage, 2);Value = *PValue; PArray = (Pvoid_t)Value;J1S(Rc_int, PArray, (Word_t)newPair); JLG(PValue, storage, 2);Value = *PValue; Ref = (Pvoid_t)Value; J1C(counter, Ref, 0, -1); newPair = (Pvoid_t) NULL; J1S(Rc_int, newPair, 5);J1S(Rc_int, newPair, 6); JLG(PValue, storage, 2);Value = *PValue; PArray = (Pvoid_t)Value;J1S(Rc_int, PArray, (Word_t)newPair); JLG(PValue, storage, 2);Value = *PValue; Ref = (Pvoid_t)Value; J1C(counter, Ref, 0, -1); return 0; }------------------------------------------------------------------------------ Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot_______________________________________________ Judy-devel mailing list Jud...@li... https://lists.sourceforge.net/lists/listinfo/judy-devel |
From: Matthew B. <mat...@gm...> - 2017-11-18 04:15:13
|
Dear Judy Masters, I am having trouble with the following program that uses Judy Arrays. I know the program appears to be an inefficient method to achieve a certain goal, but it is the simplest program that demonstrates my problem. I would be very grateful if someone could take a look at what I am doing wrong. The problem is essentially this: stepping through the program with the debugger causes the counter variable to follow the sequence 0,1,2,1. Rather, I am expecting the sequence to be 0,1,2,3 by the successive addition of a new entry to the relevant J1 Array. I am using icc to compile both Judy and the sample program. Thank you very much Matthew #include <stdio.h> #include <stdlib.h> #include "Judy.h" int main(void){ printf("Hello Everyone"); int Rc_int; Word_t *PValue; Word_t Value; Pvoid_t PArray; Pvoid_t Ref; Pvoid_t newPair; Pvoid_t storage; //A counter variable Word_t counter=0; newPair = (Pvoid_t) NULL; J1S(Rc_int, newPair, 1); J1S(Rc_int, newPair, 2); PArray = (Pvoid_t) NULL; J1S(Rc_int, PArray, (Word_t)newPair); storage = (Pvoid_t) NULL; JLI(PValue, storage, 2); *PValue = (Word_t)PArray; JLG(PValue, storage, 2); Value = *PValue; Ref = (Pvoid_t)Value; J1C(counter, Ref, 0, -1); newPair = (Pvoid_t)NULL; J1S(Rc_int, newPair, 3); J1S(Rc_int, newPair, 4); JLG(PValue, storage, 2); Value = *PValue; PArray = (Pvoid_t)Value; J1S(Rc_int, PArray, (Word_t)newPair); JLG(PValue, storage, 2); Value = *PValue; Ref = (Pvoid_t)Value; J1C(counter, Ref, 0, -1); newPair = (Pvoid_t) NULL; J1S(Rc_int, newPair, 5); J1S(Rc_int, newPair, 6); JLG(PValue, storage, 2); Value = *PValue; PArray = (Pvoid_t)Value; J1S(Rc_int, PArray, (Word_t)newPair); JLG(PValue, storage, 2); Value = *PValue; Ref = (Pvoid_t)Value; J1C(counter, Ref, 0, -1); return 0; } |
From: john s. <sk...@us...> - 2017-09-21 04:56:00
|
Ouch. On my Windows box, 32 bit Judy is selected. I have no idea why, fbuild junk. I am getting annoyed. My stupid ASUS box keeps hibernating for no good reason. I turned ALL the setting off. I have to keep loggin in again and again. Is it ASUS or Windows power management at fault? It didn’t do that before, I just tried to change the idiot setting i made to the power key to sleep the computer instead of power down. The problem was .. any vibration at all the triggered the mouse woke the thing up again .. and then it didn’t go back to sleep. Now it logs me off every 5 minutes no matter what I’m doing. On Appveyor, its selecting 64 bit build. Different compiler. I’m using free 32 bit to 64 bit cross compiler. Windows is 64 bit. Appveyor is using the 64 bit to 64 bit compiler. I am not seeing the JU_64BIT macro on my box .. unsuprisingly. I can’t see the log file on Appveyor. The evidence is the macro isn’t being set. But I can tell you fbuild DOES correctly set the macro (because it set the wrong one on my box :) — john skaller sk...@us... http://felix-lang.org |
From: john s. <sk...@us...> - 2017-09-21 01:57:37
|
Hmm .. that’s WERID: switch (IndexSize) { case 1: JU_CHECKSORTED(uint8_t *); case 2: JU_CHECKSORTED(uint16_t *); case 3: JU_CHECKSORTED_ODD(JU_COPY3_PINDEX_TO_LONG); case 4: JU_CHECKSORTED(uint32_t *); #ifdef JU_64BIT case 5: JU_CHECKSORTED_ODD(JU_COPY5_PINDEX_TO_LONG); case 6: JU_CHECKSORTED_ODD(JU_COPY6_PINDEX_TO_LONG); case 7: JU_CHECKSORTED_ODD(JU_COPY7_PINDEX_TO_LONG); case 8: JU_CHECKSORTED(Pjlw_t); #endif default: fprintf(stderr, "JU_CHECKSORTED_ODD: Bad index size %ld\n",IndexSize); assert(FALSE); // invalid IndexSize. } It’s printing 8! How can that possibly happen when: #define JU_CHECKSORTED(PType) \ while (--Pop1 > 0) \ assert(((PType) Pjll)[Pop1 - 1] < ((PType) Pjll)[Pop1]); \ break There is ONLY one way that this can happen: JU_64BIT is not set. on OSX: Its clearly set. Hmm .. now I get this on OSX: Assertion failed: ((JU_ERRNO_CORRUPT) != JU_ERRNO_CORRUPT), function j__udyInsWalk, file build/release/share/src/judy/src/JudyL/../JudyCommon/JudyIns.c, line 1627. — john skaller sk...@us... http://felix-lang.org |
From: john s. <sk...@us...> - 2017-09-21 01:36:20
|
And here we go: on Windows: JU_CHECKSORTED_ODD: Bad index size 8 So something is messing up the choice of the kind of node Judy is using in the trie. Probably due to my port. On the other platforms, either there’s a serious corruption from other parts of Felix or its a bug in the Judy Check routines. Unfortunately its not so easy to run the debugger to find a stack trace because I don’t have Linux, the double free report is from Travis which is a remote continuous integration server. Of course .. stuff could well be broken on Linux and OSX without the Judy Check, however mostly it did run without crashing before the checking code was enabled (on those platforms I mean). Note also my port impacts Linux and OSX as well. The changes aren’t Windows specific, they’re universal. They just shouldn’t make any difference on Linux. Eg ~1L ==> ~(uinptr_t)1L should have no impact on Linux, but fix the Windows build. — john skaller sk...@us... http://felix-lang.org |
From: john s. <sk...@us...> - 2017-09-21 01:17:07
|
OK, so after a bit of hackery to get this code to link, the first program using the DEBUG version of Judy now crashes with a segfault: Error running ‘build/release/host/bin/flx_pkgconfig --path+=build/release/host/config --field=includes @build/release/cache/text/Users/skaller/felix/build/release/share/src/tools/bootflx.resh' exited with -11 I had to do a couple of changes: In JudyDel.c: add “static” DBGCODE(static uint8_t parentJPtype;) // parent branch JP type. In Judy.h: interfaces for debug routines: #ifdef DEBUG extern void JUDY_EXTERN Judy1CheckPop ( Pvoid_t PArray); extern void JUDY_EXTERN JudyLCheckPop ( Pvoid_t PArray); extern void JUDY_EXTERN Judy1CheckSorted ( Pvoid_t x, // leaf or list to check. Word_t y, // number of indexes to check. long z// bytes per index in list. ); extern void JUDY_EXTERN JudyLCheckSorted ( Pvoid_t x, // leaf or list to check. Word_t y, // number of indexes to check. long z// bytes per index in list. ); #endif In JudyPrivate1L.h: arrange debug routines to make two versions: #ifdef DEBUG #define JudyCheckPop Judy1CheckPop #define JudyCheckSorted Judy1CheckSorted #endif and #ifdef DEBUG #define JudyCheckPop JudyLCheckPop #define JudyCheckSorted JudyLCheckSorted #endif in JudyGet.c: Corrrect linkage specification with JUDY_EXTERN FUNCTION void JUDY_EXTERN JudyCheckPop ( Pvoid_t PArray) FUNCTION void JUDY_EXTERN JudyCheckSorted( Pjll_t Pjll, // leaf or list to check. Word_t Pop1, // number of indexes to check. long IndexSize) // bytes per index in list. { FYI: JUDY_EXTERN is a macro that Felix uses when building or using Judy that changes in meaning depending on whether you’re building or using it. For dynamic linkage, it ensures _dllexport on building and _dllimport on using. This has always been mandatory on Windows when using DLLs. It is also now recommended for Linux (and OSX), although .. as you might expect .. the Unix nerds in their wisdom implement something different. Export and import linkage controls provide visibility control similar to static/extern, but one level up, at the DLL/shared library level. Felix demands this control so no code designed for static linkage only can work for Felix, it all has to be modified to pick out exactly which extern symbols are actually exported from a DLL. So now, the results: On OSX under Clang: I get a segfault with no diagnostics. On Travis, running Linux with gcc, I get a run time library diagnostic: *** Error in `build/release/host/bin/flx_pkgconfig': double free or corruption (!prev): 0x000000000139bb20 *** + build/release/host/bin/flx_pkgconfig --path+=build/release/host/config --field=includes @build/release/cache/text/home/travis/build/felix-lang/felix/build/release/share/src/tools/bootflx.resh Error running ‘build/release/host/bin/flx_pkgconfig --path+=build/release/host/config --field=includes @build/release/cache/text/home/travis/build/felix-lang/felix/build/release/share/src/tools/bootflx.resh' exited with -6 On Appveyor, running Windows with MSVc++ I get an assertion failure: Assertion failed: FALSE, file c:\projects\felix\build\release\share\src\judy\src\judyl\../JudyCommon/JudyGet.c, line 1150 Error running 'build\\release\\host\\bin\\flx_pkgconfig --path+=build\\release\\host\\config --field=includes @build\\release\\cache\\text\\C\\\\projects\\felix\\build\\release\\share\\src\\tools\\bootflx.resh' exited with 3 NMAKE : fatal error U1077: 'C:\Python35-x64\python.EXE' : return code '0x1' Stop. My file is modified so I will show the source code: #define JU_CHECKSORTED_ODD(CopyIndex) \ { \ Word_t indexlow; \ Word_t indexhigh; \ long offset; \ \ CopyIndex(indexlow, (uint8_t *) Pjll); \ \ for (offset = 1; offset < Pop1; ++offset) \ { \ CopyIndex(indexhigh, \ ((uint8_t *) Pjll) + (offset * IndexSize)); \ assert(indexlow < indexhigh); \ indexlow = indexhigh; \ } \ break; \ } switch (IndexSize) { case 1: JU_CHECKSORTED(uint8_t *); case 2: JU_CHECKSORTED(uint16_t *); case 3: JU_CHECKSORTED_ODD(JU_COPY3_PINDEX_TO_LONG); case 4: JU_CHECKSORTED(uint32_t *); #ifdef JU_64BIT case 5: JU_CHECKSORTED_ODD(JU_COPY5_PINDEX_TO_LONG); case 6: JU_CHECKSORTED_ODD(JU_COPY6_PINDEX_TO_LONG); case 7: JU_CHECKSORTED_ODD(JU_COPY7_PINDEX_TO_LONG); case 8: JU_CHECKSORTED(Pjlw_t); #endif default: assert(FALSE); // invalid IndexSize. } That final assert is the error. So to me, all this means: (1) The Judy Check routines have bugs in them :) (2) The diagnostic on Windows is because there is a bug in MY PORT of Judy so it works on Windows. I didn’t try to port the Check routines. I think I will change that default case to actually print the bad index size. — john skaller sk...@us... http://felix-lang.org |
From: john s. <sk...@us...> - 2017-09-21 00:12:07
|
> > Found in src/JudyCommon/JudyGet.c; merely appending, hope you can copy/paste or whatever without losing alignment. This one is already in place: JudCheckPop. > > Found in src/JudyCommon/JudySearchLeaf.c (no idea about why I placed > them where I found them): That file doesn’t exist in the repository. That would explain the absence. I added the code to JudyGet. Thanks. — john skaller sk...@us... http://felix-lang.org |
From: Alan S. <aj...@fr...> - 2017-09-20 19:56:03
|
John, > No no, you misunderstand. No, no, you miscommunicated. :-) > Its the subroutines INSIDE the actual uses of it that are not. I see. > The problemn is JudyCheckPop and JudyCheckSorted are not defined > anywhere. I unpacked my tarchive and found sources for them, see below. > Those specific checks must have previously existed, but didn't make it > into the repository. No clue about whether/why Doug or someone would have left them out. > ...The Windows port primarily consisted of fixing the incorrect > assumption that long is 64 bits on Win64. Its not... Right. You've mentioned that before. > Anyhow whatever I messed up, or *failed* to convert, I have not been > able to find it. Maybe this will help, see below. Do these source files exist in your source set? Does #ifdef DEBUG appear in them, or was that removed? Cheers, Alan ------------- Found in src/JudyCommon/JudyGet.c; merely appending, hope you can copy/paste or whatever without losing alignment. #ifndef JUDYGETINLINE // only compile the following function once: #ifdef DEBUG // **************************************************************************** // J U D Y C H E C K P O P // // Given a pointer to a Judy array, traverse the entire array to ensure // population counts add up correctly. This can catch various coding errors. // // Since walking the entire tree is probably time-consuming, enable this // function by setting env parameter $CHECKPOP to first call at which to start // checking. Note: This function is called both from insert and delete code. // // Note: Even though this function does nothing useful for JAP leaves, it's // good practice to call it anyway, and cheap too. // // TBD: This is a debug-only check function similar to JudyCheckSorted(), but // since it walks the tree it is Judy1/JudyL-specific and must live in a source // file that is built both ways. // // TBD: As feared, enabling this code for every insert/delete makes Judy // deathly slow, even for a small tree (10K indexes). It's not so bad if // present but disabled (<1% slowdown measured). Still, should it be ifdef'd // other than DEBUG and/or called less often? // // TBD: Should this "population checker" be expanded to a comprehensive tree // checker? It currently detects invalid JAP/JP types as well as inconsistent // pop1's. Other possible checks, all based on essentially redundant data in // the Judy tree, include: // // - Zero LS bits in jp_Addr field. // // - Correct Dcd bits. // // - Consistent JP types (always descending down the tree). // // - Sorted linear lists in BranchL's and leaves (using JudyCheckSorted(), but // ideally that function is already called wherever appropriate after any // linear list is modified). // // - Any others possible? #include <stdlib.h> // for getenv() and atol(). static Word_t JudyCheckPopSM(Pjp_t Pjp, Word_t RootPop1); FUNCTION void JudyCheckPop( Pvoid_t PArray) { static bool_t checked = FALSE; // already checked env parameter. static bool_t enabled = FALSE; // env parameter set. static bool_t active = FALSE; // calls >= callsmin. static Word_t callsmin; // start point from $CHECKPOP. static Word_t calls = 0; // times called so far. Word_t JAPtype; // JAP type part of PArray. // CHECK FOR EXTERNAL ENABLING: if (! checked) // only check once. { char * value; // for getenv(). checked = TRUE; if ((value = getenv("CHECKPOP")) == (char *) NULL) { #ifdef notdef // Take this out because nightly tests want to be flavor-independent; it's not // OK to emit special non-error output from the debug flavor: (void) puts("JudyCheckPop() present but not enabled by " "$CHECKPOP env parameter; set it to the number of " "calls at which to begin checking"); #endif return; } callsmin = atol(value); // note: non-number evaluates to 0. enabled = TRUE; (void) printf("JudyCheckPop() present and enabled; callsmin = " "%lu\n", callsmin); } else if (! enabled) return; // Previously or just now enabled; check if non-active or newly active: if (! active) { if (++calls < callsmin) return; (void) printf("JudyCheckPop() activated at call %lu\n", calls); active = TRUE; } // START AT TOP OF TREE: JAPtype = JAPTYPE(PArray); switch (JAPtype) { case cJU_JAPNULL: { Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf. assert(Pjlw == (Pjlw_t) NULL); // rest of word must be null. return; // valid null JAP. } #if (LOW_POP && JUDYL) // Little or no pop checking is possible for these types, but see function // header comments: case cJL_JAPLEAF_POPU1: return; case cJL_JAPLEAF_POPU2: return; #endif case cJU_JAPLEAF: { Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf. assert(*Pjlw + 1 <= cJU_JAPLEAF_MAXPOP1); return; } // Check JPM pop0 against tree, recursively: // // Note: The traversal code in JudyCheckPopSM() is simplest when the case // statement for each JP type compares the pop1 for that JP to its subtree (if // any) after traversing the subtree (that's the hard part) and adding up // actual pop1's. A top branch's JP in the JPM does not have room for a // full-word pop1, so pass it in as a special case. case cJU_JAPBRANCH: { Pjpm_t Pjpm = P_JPM(PArray); (void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1); return; } } assert(FALSE); // unrecognized JAP type => corruption. } // JudyCheckPop() // **************************************************************************** // J U D Y C H E C K P O P S M // // Recursive state machine (subroutine) for JudyCheckPop(): Given a Pjp (other // than JPNULL*; caller should shortcut) and the root population for top-level // branches, check the subtree's actual pop1 against its nominal value, and // return the total pop1 for the subtree. // // Note: Expect RootPop1 to be ignored at lower levels, so pass down 0, which // should pop an assertion if this expectation is violated. FUNCTION static Word_t JudyCheckPopSM( Pjp_t Pjp, // top of subtree. Word_t RootPop1) // whole array, for top-level branches only. { Word_t pop1_jp; // nominal population from the JP. Word_t pop1 = 0; // actual population at this level. Word_t offset; // in a branch. #define PREPBRANCH(cPopBytes,Next) \ pop1_jp = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, cPopBytes) + 1; goto Next assert((((Word_t) (Pjp->jp_Addr)) & 7) == 3); switch (Pjp->jp_Type) { case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL); case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL); #ifdef JU_64BIT case cJU_JPBRANCH_L4: PREPBRANCH(4, BranchL); case cJU_JPBRANCH_L5: PREPBRANCH(5, BranchL); case cJU_JPBRANCH_L6: PREPBRANCH(6, BranchL); case cJU_JPBRANCH_L7: PREPBRANCH(7, BranchL); #endif case cJU_JPBRANCH_L: pop1_jp = RootPop1; { Pjbl_t Pjbl; BranchL: Pjbl = P_JBL(Pjp->jp_Addr); for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset) pop1 += JudyCheckPopSM((Pjbl->jbl_jp) + offset, 0); assert(pop1_jp == pop1); return(pop1); } case cJU_JPBRANCH_B2: PREPBRANCH(2, BranchB); case cJU_JPBRANCH_B3: PREPBRANCH(3, BranchB); #ifdef JU_64BIT case cJU_JPBRANCH_B4: PREPBRANCH(4, BranchB); case cJU_JPBRANCH_B5: PREPBRANCH(5, BranchB); case cJU_JPBRANCH_B6: PREPBRANCH(6, BranchB); case cJU_JPBRANCH_B7: PREPBRANCH(7, BranchB); #endif case cJU_JPBRANCH_B: pop1_jp = RootPop1; { Word_t subexp; Word_t jpcount; Pjbb_t Pjbb; BranchB: Pjbb = P_JBB(Pjp->jp_Addr); for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) { jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)); for (offset = 0; offset < jpcount; ++offset) { pop1 += JudyCheckPopSM(P_JP(JU_JBB_PJP(Pjbb, subexp)) + offset, 0); } } assert(pop1_jp == pop1); return(pop1); } case cJU_JPBRANCH_U2: PREPBRANCH(2, BranchU); case cJU_JPBRANCH_U3: PREPBRANCH(3, BranchU); #ifdef JU_64BIT case cJU_JPBRANCH_U4: PREPBRANCH(4, BranchU); case cJU_JPBRANCH_U5: PREPBRANCH(5, BranchU); case cJU_JPBRANCH_U6: PREPBRANCH(6, BranchU); case cJU_JPBRANCH_U7: PREPBRANCH(7, BranchU); #endif case cJU_JPBRANCH_U: pop1_jp = RootPop1; { Pjbu_t Pjbu; BranchU: Pjbu = P_JBU(Pjp->jp_Addr); for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset) { if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1) && ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX)) { continue; // skip null JP to save time. } pop1 += JudyCheckPopSM((Pjbu->jbu_jp) + offset, 0); } assert(pop1_jp == pop1); return(pop1); } // -- Cases below here terminate and do not recurse. -- // // For all of these cases except JPLEAF_B1, there is no way to check the JP's // pop1 against the object itself; just return the pop1; but for linear leaves, // a bounds check is possible. #define CHECKLEAF(MaxPop1) \ pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1; \ assert(pop1 >= 1); \ assert(pop1 <= (MaxPop1)); \ return(pop1) #if (JUDYL || (! JU_64BIT )) case cJU_JPLEAF1: CHECKLEAF(cJU_LEAF1_MAXPOP1); #endif case cJU_JPLEAF2: CHECKLEAF(cJU_LEAF2_MAXPOP1); case cJU_JPLEAF3: CHECKLEAF(cJU_LEAF3_MAXPOP1); #ifdef JU_64BIT case cJU_JPLEAF4: CHECKLEAF(cJU_LEAF4_MAXPOP1); case cJU_JPLEAF5: CHECKLEAF(cJU_LEAF5_MAXPOP1); case cJU_JPLEAF6: CHECKLEAF(cJU_LEAF6_MAXPOP1); case cJU_JPLEAF7: CHECKLEAF(cJU_LEAF7_MAXPOP1); #endif case cJU_JPLEAF_B1: { Word_t subexp; Pjlb_t Pjlb; pop1_jp = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1; Pjlb = P_JLB(Pjp->jp_Addr); for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp) pop1 += __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp)); assert(pop1_jp == pop1); return(pop1); } JUDY1CODE(case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0);) case cJU_JPIMMED_1_01: return(1); case cJU_JPIMMED_2_01: return(1); case cJU_JPIMMED_3_01: return(1); #ifdef JU_64BIT case cJU_JPIMMED_4_01: return(1); case cJU_JPIMMED_5_01: return(1); case cJU_JPIMMED_6_01: return(1); case cJU_JPIMMED_7_01: return(1); #endif case cJU_JPIMMED_1_02: return(2); case cJU_JPIMMED_1_03: return(3); #if (JUDY1 || JU_64BIT) case cJU_JPIMMED_1_04: return(4); case cJU_JPIMMED_1_05: return(5); case cJU_JPIMMED_1_06: return(6); case cJU_JPIMMED_1_07: return(7); #endif #if (JUDY1 && JU_64BIT) case cJ1_JPIMMED_1_08: return(8); case cJ1_JPIMMED_1_09: return(9); case cJ1_JPIMMED_1_10: return(10); case cJ1_JPIMMED_1_11: return(11); case cJ1_JPIMMED_1_12: return(12); case cJ1_JPIMMED_1_13: return(13); case cJ1_JPIMMED_1_14: return(14); case cJ1_JPIMMED_1_15: return(15); #endif #if (JUDY1 || JU_64BIT) case cJU_JPIMMED_2_02: return(2); case cJU_JPIMMED_2_03: return(3); #endif #if (JUDY1 && JU_64BIT) case cJ1_JPIMMED_2_04: return(4); case cJ1_JPIMMED_2_05: return(5); case cJ1_JPIMMED_2_06: return(6); case cJ1_JPIMMED_2_07: return(7); #endif #if (JUDY1 || JU_64BIT) case cJU_JPIMMED_3_02: return(2); #endif #if (JUDY1 && JU_64BIT) case cJ1_JPIMMED_3_03: return(3); case cJ1_JPIMMED_3_04: return(4); case cJ1_JPIMMED_3_05: return(5); case cJ1_JPIMMED_4_02: return(2); case cJ1_JPIMMED_4_03: return(3); case cJ1_JPIMMED_5_02: return(2); case cJ1_JPIMMED_5_03: return(3); case cJ1_JPIMMED_6_02: return(2); case cJ1_JPIMMED_7_02: return(2); #endif } // switch (Pjp->jp_Type) assert(FALSE); // unrecognized JP type => corruption. return(0); // to make some compilers happy. } // JudyCheckPopSM() #endif // DEBUG #endif // ! JUDYGETINLINE ------------- Found in src/JudyCommon/JudySearchLeaf.c (no idea about why I placed them where I found them): #ifdef DEBUG // **************************************************************************** // J U D Y C H E C K S O R T E D // // Given a pointer to a packed list of Pop1 N-byte indexes (N = IndexSize), // assert that the list is in order. FUNCTION void JudyCheckSorted( Pjll_t Pjll, // leaf or list to check. Word_t Pop1, // number of indexes to check. long IndexSize) // bytes per index in list. { // Macros for common code: // // Check a list of "even"-sized indexes, counting backwards from last to first: // // Pjll and Pop1 are in the context. #define JU_CHECKSORTED(PType) \ while (--Pop1 > 0) \ assert(((PType) Pjll)[Pop1 - 1] < ((PType) Pjll)[Pop1]); \ break // Check a list of "odd"-sized indexes, which requires first copying each one // to an aligned word: // // Pjll, Pop1, and IndexSize are in the context. #define JU_CHECKSORTED_ODD(CopyIndex) \ { \ Word_t indexlow; \ Word_t indexhigh; \ long offset; \ \ CopyIndex(indexlow, (uint8_t *) Pjll); \ \ for (offset = 1; offset < Pop1; ++offset) \ { \ CopyIndex(indexhigh, \ ((uint8_t *) Pjll) + (offset * IndexSize)); \ assert(indexlow < indexhigh); \ indexlow = indexhigh; \ } \ break; \ } switch (IndexSize) { case 1: JU_CHECKSORTED(uint8_t *); case 2: JU_CHECKSORTED(uint16_t *); case 3: JU_CHECKSORTED_ODD(JU_COPY3_PINDEX_TO_LONG); case 4: JU_CHECKSORTED(uint32_t *); #ifdef JU_64BIT case 5: JU_CHECKSORTED_ODD(JU_COPY5_PINDEX_TO_LONG); case 6: JU_CHECKSORTED_ODD(JU_COPY6_PINDEX_TO_LONG); case 7: JU_CHECKSORTED_ODD(JU_COPY7_PINDEX_TO_LONG); case 8: JU_CHECKSORTED(Pjlw_t); #endif default: assert(FALSE); // invalid IndexSize. } } // JudyCheckSorted() #endif // DEBUG |
From: john s. <sk...@us...> - 2017-09-20 05:14:40
|
> On 20 Sep. 2017, at 13:18, Alan Silverstein <aj...@fr...> wrote: > > John, > >> Judy code has some debugging calls to check functions. Inside >> DBGCODE(). >> >> Unfortunately, the code for these functions aren't in the tarball or >> repository. Any available? > > I'm surprised at that. I have nearly zero recollection of this, but I > do have some libJudy sources on my home tree, where a find/grep > revealed in tool/jhton.c (not in any release?) the following: > > > This is probably a clone of, but identical to, something that appeared > in a released header file -- but I don't know why you have DBGCODE() > macros in the source without a definition anywhere. No no, you misunderstand. DBGCODE is defined. Its the subroutines INSIDE the actual uses of it that are not. For example in JudyCommon/JudyIns.c we have: DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);) DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);) and later: JU_INSERTINPLACE(Pjbl->jbl_Expanse, numJPs, offset, digit); JU_INSERTINPLACE(Pjbl->jbl_jp, numJPs, offset, newJP); DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse), numJPs + 1, /* IndexSize = */ 1);) ++(Pjbl->jbl_NumJPs); The problemn is JudyCheckPop and JudyCheckSorted are not defined anywhere. We have a bug in my Windows port of Judy, and I want to enable these checks. But they don’t exist. And there’s NO WAY I have the expertise to write them. Those specific checks must have previously existed, but didn’t make it into the repository. We have a failure where an insert into a JudyL array is simply not happening, causing 50% of all windows builds to fail. Because I have no idea how Judy works .. I mean I have an idea but not enough to search for a bug .. I thought to enable these checks. We know the bug is occuring when the top level linear node has to be split. The bug does not appear to happen on OSX or Linux so it is probably due to me failing to port it to Windows correctly. The crash is deterministic, but it is critically dependent on the exact bit pattern of keys being inserted, which are in fact memory addresses returned by malloc(). So the keys depend on the exact process environment of the build. A tiny, one character change in the Felix source, and the bug appears or goes away. Run a crashing build 100 times and it crashes 100 times. Once it runs, it runs. The Windows port primarily consisted of fixing the incorrect assumption that long is 64 bits on Win64. Its not. Long is 32 bits on all Windows platforms. Plain int is 16 bits on all Windows platforms. The main bug was code like this: ~1L which tries to set all bits on except the lowest, but instead leaves the top 32 bits clear. My change is ~(uintptr_t)1L which works correctly on all platforms (32 or 64 bits as well). Thats an unsigned integer the size of a void*. Not every integer in Judy is 64 bits. Indexes for linear nodes can be 8 bits for example. Of course code like: index = ~index is not standards conforming, it only works for twos complement integers. That’s used all over the place too, but most boxes do use twos complement. Anyhow whatever I messed up, or *failed* to convert, I have not been able to find it. If we can’t find the problem we’ll probably have to throw Judy out. STL map isn’t as fast and uses more storage but it provides all the same access methods. (Its just a pain to use, being stuck having to use the stupid iterators :) It is, of course, possible, that Judy is working, and the JudyL array is being corrupted by something else. But I doubt that, I’m pretty confident the bug is in Windows Judy. Note that the ported code runs on both Unix and Windows, its not a separate Judy. Same judy, just fixed to work on windows as well as unix. Except it isn’t :) — john skaller sk...@us... http://felix-lang.org |