Re: Bug in Linked Lists?

[Ken Cline]

Kevin,

I experienced the same problem while writing a "remove
dupplicates" routine a while ago.  I managed to get
something working, but it was *painful*.

I should have taken my debugging one more step and created a
simple piece of code that illustrated the problem (as Roger
suggests) but I never quite got around to doing that.

Anyway, I'll show what I did and maybe it'll help.  I don't
have alot of time to edit this right now, but let me know if
you need any further explanation of my code. (My apologies
for the less than elegant ObjC style!) NOTE: I've only
tested this under the beta release.

-(void) removeDuplicateMsgs {
//  Remove "duplicate" messages for the message spool. Message2
//  is a "duplicate" of Message1 if "[Message1 sameAs: Message2]"
//  returns TRUE. (The current implementation of "sameAs" is
//  symmetric, as far as I can tell.) -K.Cline (SAIC), 2/7/97
//
//  WARNING: We MUST be careful NOT to remove the list/spool member
//  currently be used to test against (i.e. msg1). That's why we
//  call "[spoolIndex2 setOffset: [spoolIndex1 getOffset]]" to
//  position the 2nd index at the 1st index. We DO NOT call
//  "[spoolIndex setLoc: Start]" which would possibly put the
//  spoolIndex2 before spoolIndex1 on the list!  If the spoolIndex2
//  is before spoolIndex1 then we would end up testing whether
//  "[msg1 sameAs: msg1]", which, of course, is true and therefore
//  msg1 would be removed!!
//  AND we call "[spoolIndex2 prev]" after we remove the current
//  "duplicate" message because (as I've learned thru hours of
//  painful debugging) if you remove the last message on the
//  spool then the spoolIndex2 is positioned by the Index class
//  so that when we call "[spoolIndex2 next]" the next time we'll
//  get the first element on the list.  So again, spoolIndex2
//  is at the beginning of the list and msg1 will be removed!!
//  On the other hand, "[spoolIndex2 prev]" moves the index back
//  to the message that preceeded the one removed. So when we call
//  "[spoolIndex2 next]" the next time we either continue down the
//  list/spool or, if we'll at the end, we get a NULL returned.
//  -K.Cline (SAIC), 2/7/97
 
   Msg * msg1 = NULL;
   Msg * msg2 = NULL;
   id <ListIndex> spoolIndex1 = NULL;
   id <ListIndex> spoolIndex2 = NULL;
 
   if ( messageSpool == NULL ) return;
 
   spoolIndex1 = [ messageSpool begin: [self getZone] ];
   spoolIndex2 = [ messageSpool begin: [self getZone] ];
 
   while ( (msg1 = [spoolIndex1 next]) != NULL ) {
      [ spoolIndex2 setOffset: [spoolIndex1 getOffset] ];
 
      while ( (msg2 = [spoolIndex2 next]) != NULL ) {
 
         if ( [ msg1 sameAs: msg2 ] ) {
            [ [spoolIndex2 get] drop ];
            [ spoolIndex2 remove ];
            [ spoolIndex2 prev ];
         }
      }
   }
 
   [ spoolIndex1 drop ];
   [ spoolIndex2 drop ];
 
}


BTW, just so you don't get the wrong impression, this is
probably the most commented method I've written.

Well I hope this helps.

Ken.

_________________________________________________________
Ken Cline                             address@hidden
SAIC                                 VOICE (410) 571-0413
Annapolis, MD                          FAX (301) 261-8427


On Sun, 29 Jun 1997, Roger M. Burkhart wrote:

> Kevin Crowston writes:
> 
> > The bug is that the list ends up empty.  Apparently when I remove the last
> > item in the list, the next next puts me back to the beginning--so I go
> > through the list a second time and this time delete everything, thinking
> > it's a repeat.
> 
> I haven't been able to reproduce your problem in an independent test, at
> least with as simple a cause as you suggest.  Here's a sample loop that
> duplicates the sequence of index operations you're performing, but without
> anything else:
> 
>   index = [aList begin: scratchZone];
> 
>   [index setLoc: Start];
>   [index next];
>   while ( [index getLoc] == Member ) {
>     [index remove];
>     printf( "after [index remove]: %s\n", [[index getLoc] getName] );
>     [index next];
>     printf( "after [index next]: %s\n", [[index getLoc] getName] );
>   }
> 
> (BTW, your use of setLoc: and getLoc in a list that may contain zero
> integer values is exactly how these messages are intended to be used.  I
> keep them in the example but took out your operations on a separate array
> that you perform on selected members.)
> 
> When the input to this code block is a list containing two members, each of
> these two members is removed, with the last remove being on the one and
> only member remaining in the list at that time.  Here's the resulting output
> from the print statements:
> 
> after [index remove]: Removed
> after [index next]: Member
> after [index remove]: Removed
> after [index next]: End
> 
> This is the intended, correct behavior -- remove always leaves the index
> set at a special "Removed" location, but next advances it to the next
> location that would have followed.  If the member removed was the
> one-and-only member remaining, and the next operation is "next," then the
> next location obtained is End.  (If the next operation had been "prev,"
> the subsequent location obtained would have been Start; everything is
> supposed to be entirely symmetrical in both directions.  The index has no
> notion of a current direction of processing; the next location obtained is
> determined by the operation requested.)
> 
> > The documentation says that removing the last element leaves you at End,
> > but in fact it leaves you with [point getLoc] == "Removed".  Doing a next
> > from this Removed node seems to take you to the front of the list.
> 
> In looking carefully at the List code, I can't find a logical path that
> would ever take an index back around to the beginning (short of a new
> [... setLoc: Start]), but that isn't saying there isn't such a possibility,
> just that I haven't found it or been able to reproduce it in a simple test
> case.
> 
> On the documentation for removing the last element using an index, the
> Index interface reference (in
> www.santafe.edu/projects/swarm/swarmdocs/src/collections/Index.html)
> indicates that the immediate location is always "Removed," followed by the
> location that would have followed the member had it not been removed:
> 
>   The remove message removes the member at the current location of an
>   index, and returns the member value removed. The index position is set
>   to a special position between the members which previously preceded and
>   followed the removed member. If there is no preceding or following
>   member, the index is set to the special location before the start or
>   after the end of all members. After a current member is removed, there
>   is no member at the current index location, but a subsequent next or
>   prev message will continue with the same member that would have been
>   accessed had the current member not been removed.
> 
> I scarcely claim that this is the most transparent wording to explain how
> an index behaves after removing a member, but I think it does match the
> values returned by the test case above.
> 
> Index traversal behavior is extremely basic to all collections (where they
> play the same role as the lightweight iterators that Alexander Stepanov
> promoted convincingly for the C++ Standard Template Library), so if
> there's any case at all where they don't behave as they're supposed to
> it's extremely critical that we track it down.  The best form of bug
> report is a block of code that can be independently compiled to reliably
> create an example of the problem, and which does so in as simple a form as
> possible.  If the problem can be created in a self-contained test file, it's
> usually easy to track down what's happening very quickly.  (Finding the
> right test case is often the hardest part.)  Can you suggest anything else
> that might differ in your usage of a list and index than the case I tried?
> 
> Roger Burkhart
> 
> 

On Sat, 28 Jun 1997, Kevin Crowston wrote:
 
> I think I have found a bug in the List type collections. I have a list of
> numbers, and am trying to delete duplicates.  Here's a code fragment:
>   
>   
>   [point setLoc: Start] ;   
>   next = (int)[point next] ;
>   while ( [point getLoc] == Member ) {
>     if ( nextVect[next] == 0 )
>       nextVect[next] = -1 ;
>     else
>       [point remove] ;
>     next = (int)[point next] ;
>   }
>
> (point is a previously created ListIndex, i.e., point = [list begin:...] )
> 
> The nextVect[next] is used to keep track of which elements I've already
> seen and is initially all 0's (I created the array for use in the next
> step, so I figured I'd just reuse it here).
> 
> I'm using the [point getLoc] == Member construction because the list
> contains integers, including 0 (meaning that nil is a perfectly acceptable
> return value).
>
> Okay--without looking, can you figure out what the fragment leaves in the 
> list?
> 
> 
> The bug is that the list ends up empty.  Apparently when I remove the last
> item in the list, the next next puts me back to the beginning--so I go  
> through the list a second time and this time delete everything, thinking
> it's a repeat.
> 
> The documentation says that removing the last element leaves you at End, 
> but in fact it leaves you with [point getLoc] == "Removed".  Doing a next
> from this Removed node seems to take you to the front of the list.
>
> Kevin
>
>                   



                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.
                  ==================================