Tk Library Source Code

Hello out there,
all of a sudden I got the error message 'malformed
bucket chain in Tcl_DeleteHashEntry'.
The only significant change I could think of was the
introduction of tcllib's tree module, so I started
investigating a bit.
The attached file demonstrates the bug.

I only observed it on Win98 (because my XP machine runs
Tcl 8.4.9) and on 8.4.9 the bug doesn't happen. Also,
it is limited to the C(ritcl) version - the pure Tcl
version is clean. So I got a workaround and am still a
happy camper.

Best regards and keep up the good work
Helmut Giese

Logged In: YES 
user_id=75003

Hm. Could actually have a huge impact on runtime in
pathological cases. For the better. Consider a very large
tree, several thousand nodes, all auto-generated.

I start from the bottom (node1) to find and fill any gaps.
If there are none I have to iterate over the thousands of
names to to find the max. Takes a long time.

The tcl version is most impacted by this. The C version is
way faster, but even so this only means that the point where
such the iteration takes a noticeable amount of time is
pushed to higher numbers of nodes, not that the problem goes
away.

So, doing some precomputation when desrializaing makes sense.

On the other hand, this precomputation has to 'string match'
or 'regexp' each node name and see if it is of the form
'nodeFOO', FOO an integer number. This is not cheap in
runtime I believe.

Well, in the end what we need is to benchmark this and see
how the various cases behave and what the big-O constants are.


--
And thanks again for the concise test case. This made the
debugging a snap.

Logged In: YES 
user_id=75003

Fix committed to head.
t_newnodename extended to skip existing nodes while
generating names.
tn_new extended with check for duplicate name, panic. This
latter ensures that, should we have other places which can
cause generation of dup names, we panic early and with a
good error message, and with damaged hashtable during
destruction.

Logged In: YES 
user_id=522169

Hi Andreas,
just a last thought:
On deserialising you are bound to look at each node. Why not
note 'in passing' the highest "auto generated name" and when
thru using it to initialise the 'unique number'?
This should be negligible wrt changes in the code and
run-time impact.
Ok, I'll forget about it now and leave the rest to you.
Greetings
Helmut

Logged In: YES 
user_id=522169

Hi Andreas,
I have been thinking a bit about this issue.
You can use the same approach the Tcl version uses - that is
on every node creation you keep incrementing the counter and
compare the resulting name against all existing nodes. This
is an O(n) operation for each newly created node.
How about the following approach: On deserialisiation you
check for the highest node index present and set your
'unique number' from there. This is also an O(n) operation
but it happens only once.

Why aren't you on vacation at this time of the year?
Greetings from a very hot place
Helmut

Logged In: YES 
user_id=75003

This can actually be seen as two problems.

(1) The auto-generation of node-names is out of whack for a
tree loaded from a serialization. It creates node-names
which are already present.

(2) The code for the destruction of tree is not able to
handle a tree with duplicate node names.

The latter is the crash. However (1) is the real problem.
All parts of the tree implementation assume that node names
are unique. all the methods for rename, etc. check that the
result is not violating this assumption.

Ok, the plan: Make the destruction more robust against dup
names, if possible. By detecting an already deleted node.
Panic with a proper message. Then fix the generation of dup
names by the C impl. after a tree was loaded from file. Put
this example into the testsuite.

File Added - 186333: valgrind.txt

Logged In: YES 
user_id=75003

I can confirm the same crash with Tcl 8.4.CVS and
struct::tree critcl. (Aborted with a "malformed bucket chain
in Tcl_DeleteHashEntry").

And I managed to get some more information where the
problems by using valgrind.

Hm. I wonder if I can manage to get more by compiling
struct::tree with symbols.

Ok, than you very much Helmut for investigating this so far,
i.e. making the problem reproducible, and also reducing it
to such a simple and small script.

File Added - 186221: treetst2.tcl