mcf@tardis.trl.OZ.AU (Michael Flower) (05/15/91)
I am posting this as it may be of interest to several people, and I have no direct address for the people at Rogue Wave. If you don't have Rogue Wave, then this probably isn't of much interest. There is a bug in the RWSet class of their 3.1.0.1 release. I believe that the 4.0 release is available, but don't have a copy or know if the bug has been fixed in this release. The bug is that the library can go into an infinite loop under certain circumstances when using RWSet or classes derived from it. The problem occurs when inserting and deleting from a set. Under certain circumstances the 'info' table can have no 'empty' entries causing the hash collision mechanism to search unendingly in findIndex(). The reason that there are no 'empty' entries is that the 'info' table is expanded when the value of 'items' gets to greater than 2/3 of the current table size. The problem is that 'items' should specify the number of used table entries, not the number of obeject currently inserted into the set. The bug is caused by decrementing 'items' in removeAtIndex() when an object is removed from the RWSet. This should not be done since removing an object does not free an info table slot, it marks it only marks it deleted (this is because of the way that primary collision detection is handled). Thus decrementing 'items' in this context causes the class to believe that the 'info' table is not getting full, despite the fact that all the entries have been used and thus it does not resize the table before it fills up. BUG fix: in RWset::removeAtIndex(unsigned index) delete the line items--; and the problem goes away. I hope that this is some use to somebody. Michael Flower Artificial Intelligence Systems Email: m.flower@trl.oz.au Telecom Research Laboratories Voice: +61 3 541 6179 Melbourne, AUSTRALIA Fax: +61 3 543 8863
mcf@trlamct.trl.oz.au (Michael Flower) (05/15/91)
From article <3481@trlluna.trl.oz>, by mcf@tardis.trl.OZ.AU (Michael Flower): > Thus decrementing 'items' in this context causes the class to believe that the > 'info' table is not getting full, despite the fact that all the entries have > been used and thus it does not resize the table before it fills up. > > BUG fix: > > in RWset::removeAtIndex(unsigned index) > > delete the line > items--; Ah, Umm, Ah.... What I have said is correct in as much as this is what causes the class to go into an infinte loop however the fix causes a problem. (Think first, post later, damn!) This fix breaks the 'entries()' and 'isempty()' functions. I missed this because these functions are inline in the header 'rwset.h'. It might break other things as well. (May as well say it now, rather than be flamed later!). The problem solution will be a little more complex, since 'items' can't be used as a count of the number of object in the set and the fullness (or usedness) of the 'info' table at the same time. Probably another variable is required. I would call it 'used'. Michael Flower Artificial Intelligence Systems Email: m.flower@trl.oz.au Telecom Research Laboratories Voice: +61 3 541 6179 Melbourne, AUSTRALIA Fax: +61 3 543 8863
griswolf@frisby.CS.ORST.EDU (Frank Griswold) (05/16/91)
In article <3481@trlluna.trl.oz> mcf@tardis.trl.OZ.AU (Michael Flower) writes: >I am posting this as it may be of interest to several people, and I have >no direct address for the people at Rogue Wave. > >If you don't have Rogue Wave, then this probably isn't of much interest. true. > >There is a bug in the RWSet class of their 3.1.0.1 release. I believe that >the 4.0 release is available, but don't have a copy or know if the bug >has been fixed in this release. It is fixed in 4.0. > >The bug is that the library can go into an infinite loop under certain >circumstances when using RWSet or classes derived from it. > >The problem occurs when inserting and deleting from a set. Under certain >circumstances the 'info' table can have no 'empty' entries >causing the hash collision mechanism to search unendingly in findIndex(). true. ...(much removed, including a fix)... >Michael Flower >Artificial Intelligence Systems Email: m.flower@trl.oz.au >Telecom Research Laboratories Voice: +61 3 541 6179 >Melbourne, AUSTRALIA Fax: +61 3 543 8863 I want to tread lightly here: I work for Rogue Wave. I have an email address. But I don't work for Rogue Wave while I'm reading email (and vice versa). And I want to avoid any commercial use of this posting. However, for the sake of *information only* I would like to make clear that M. Flower's statement about the availability of version 4.0 is correct. Folk should be able to contact Rogue Wave about upgrades: Rogue Wave Software 1325 NW 9th St Corvallis OR, 97330 USA (503) 754 2311 Still treading lightly: If you are a user of the library, and have not sent in your registration, it will be hard for the folk at Rogue Wave to justify giving you a "current user's price". Of course it is never too late... Word to the wise, eh? If you wish to assume that I will correctly handle email for Rogue Wave, you may use my address. I make *no* guarantees with respect to speed or accuracy, but I will attempt to do the right thing. As and when it is convenient. For me. Frank Griswold griswolf@cs.orst.edu disclaimer.real() = "careful"; disclaimer.imaginary() = "standard";