Hi,
The following code results in an error:
| tree | tree := BTree new. 1 to: 15 do: [:i | tree at: i put: i]. 1 to: 15 do: [:i | tree removeKey: i]
I first discovered it with Collections-BTree-avi.38 under Jasmine, and verified that it also happens with Collections-BTree-avi.42 under Squeak-3.7-5989-full.
Thanks, Josh
On Thu, 23 Dec 2004 01:37:04 -0500, Joshua Gargus schwa@fastmail.us wrote:
Hi,
The following code results in an error:
| tree | tree := BTree new. 1 to: 15 do: [:i | tree at: i put: i]. 1 to: 15 do: [:i | tree removeKey: i]
Hi Josh,
Sorry for the delay on this - I've integrated your (off list) fix and put the result at http://beta4.com/mc/Collections-BTree-avi.43.mcz. Once SqueakMap comes back online I'll release it there too.
Avi
Hi!
SM back up.
regards, Göran
Avi Bryant avi.bryant@gmail.com wrote: [SNIP]
ry for the delay on this - I've integrated your (off list) fix and put the result at http://beta4.com/mc/Collections-BTree-avi.43.mcz. Once SqueakMap comes back online I'll release it there too.
Avi
Thanks Avi,
I also implemented #removeKey:ifAbsent:; I'll send that to you soon.
Josh
Avi Bryant wrote:
On Thu, 23 Dec 2004 01:37:04 -0500, Joshua Gargus schwa@fastmail.us wrote:
Hi,
The following code results in an error:
| tree | tree := BTree new. 1 to: 15 do: [:i | tree at: i put: i]. 1 to: 15 do: [:i | tree removeKey: i]
Hi Josh,
Sorry for the delay on this - I've integrated your (off list) fix and put the result at http://beta4.com/mc/Collections-BTree-avi.43.mcz. Once SqueakMap comes back online I'll release it there too.
Avi
Oops, seems like there is still a problem. Attached is some workspace code with a logged sequence of adds/removes that causes an error. I don't have time to dig into it immediately, but will soon since I need it working within a week.
Josh
Avi Bryant wrote:
On Thu, 23 Dec 2004 01:37:04 -0500, Joshua Gargus schwa@fastmail.us wrote:
Hi,
The following code results in an error:
| tree | tree := BTree new. 1 to: 15 do: [:i | tree at: i put: i]. 1 to: 15 do: [:i | tree removeKey: i]
Hi Josh,
Sorry for the delay on this - I've integrated your (off list) fix and put the result at http://beta4.com/mc/Collections-BTree-avi.43.mcz. Once SqueakMap comes back online I'll release it there too.
Avi
Hi Avi,
The attached changeset fixes the problem. The cause appears to have been that #at: could modify the tree in a bad way if you give it a key smaller smaller than any already in the tree (and possibly in other cases; I'm not sure if these exist, what they are, and if this changeset addresses them).
I don't claim that this changeset provides optimal factoring of the code; it is just the simplest way that I thought of to fix the problem. I also haven't tested it extensively (I haven't even proven it correct ;-)
Sorry for not being more thorough; time is tight right now. Josh
Joshua Gargus wrote:
Oops, seems like there is still a problem. Attached is some workspace code with a logged sequence of adds/removes that causes an error. I don't have time to dig into it immediately, but will soon since I need it working within a week.
Josh
Avi Bryant wrote:
On Thu, 23 Dec 2004 01:37:04 -0500, Joshua Gargus schwa@fastmail.us wrote:
Hi,
The following code results in an error:
| tree | tree := BTree new. 1 to: 15 do: [:i | tree at: i put: i]. 1 to: 15 do: [:i | tree removeKey: i]
Hi Josh,
Sorry for the delay on this - I've integrated your (off list) fix and put the result at http://beta4.com/mc/Collections-BTree-avi.43.mcz. Once SqueakMap comes back online I'll release it there too.
Avi
'From Squeak3.7 of ''4 September 2004'' [latest update: #5989] on 17 January 2005 at 11:16:13 pm'! "Change Set: BTree-fixes Date: 17 January 2005 Author: Joshua Gargus
#at:ifAbsent: was causing problems if you look for a key smaller than any other keys in the tree; in such a case, it would cause a change in the tree. This changeset makes it so that #at:ifAbsent: does not change the tree at all, regardless of whether the key is found."!
!BTree methodsFor: 'accessing' stamp: 'jcg 1/17/2005 23:09'! at: aMagnitude ifAbsent: errorBlock | leaf | leaf _ root existingLeafForKey: aMagnitude. leaf ifNil: [^ errorBlock value]. ^ leaf valueForKey: aMagnitude ifAbsent: errorBlock! !
!BTreeInteriorNode methodsFor: 'as yet unclassified' stamp: 'jcg 1/17/2005 22:59'! existingChildForKey: aMagnitude "Unlike #childForKey:, this method looks for a child, but doesn't mess with the tree if it doesn't exist." | index | index _ keys findIndexForKey: aMagnitude. index = 0 ifTrue: [^ nil] ifFalse: [^ self at: index].! !
!BTreeInteriorNode methodsFor: 'as yet unclassified' stamp: 'jcg 1/17/2005 23:00'! existingLeafForKey: aMagnitude "Unlike #leafForKey:, this method looks for a leaf but doesn't mess with the tree if it doesn't exist." | child | child _ self existingChildForKey: aMagnitude. ^ child ifNotNil: [child existingLeafForKey: aMagnitude]! !
!BTreeLeafNode methodsFor: 'as yet unclassified' stamp: 'jcg 1/17/2005 23:08'! existingLeafForKey: aMagnitude ^ self! !
squeak-dev@lists.squeakfoundation.org