[cl-containers-devel] dlist-container bug fixes
Gary King
gwking at metabang.com
Mon Aug 3 21:39:51 UTC 2009
Hi J.P.,
Thanks for the tests and the patches. I've only skimmed your e-mail so
far but everything I've read seems right. I'll respond in more detail
soon and apply the patches soon too!
Regards,
On Aug 3, 2009, at 7:52 AM, J.P. Larocque wrote:
> Hi,
>
> I've written a few tests for DLIST-CONTAINERs. Three of the tests
> fail because of some problems that I think are bugs in the
> DLIST-CONTAINER implementation. The failing tests are:
>
> TEST-DLIST-DELETE-DUPLICATE-NODE
> Ensures that calling DELETE-ITEM on a node whose element appears
> multiple times doesn't affect other nodes with identical elements.
>
> TEST-DLIST-INSERT-ITEM-BEFORE/ELEMENT
> Ensure trying to INSERT-ITEM-BEFORE a non-node either looks up the
> node of the given element and proceeds, or signals an error.
>
> TEST-DLIST-INSERT-ITEM-AFTER/ELEMENT
> Ensure trying to INSERT-ITEM-AFTER a non-node either looks up the
> node of the given element and proceeds, or signals an error.
>
> I've included three patches: one for the tests, and two others to fix
> the problems and let the tests pass. I'll explain each of the
> non-test patches below.
>
>
> --- Fixed bugs in deleting nodes from a dlist-container
>
>
> From what I understand of cl-containers, "elements" refer to the
> objects that we think of as belonging to containers, and "nodes" are
> the objects that wrap elements for bookkeeping.
>
> In my current project, I'm using DLIST-CONTAINERs, and tracking
> DLIST-CONTAINER-NODEs in my own custom data structure so that I can
> efficiently (O(1) time) delete an element from the DLIST-CONTAINER, so
> long as I know what its corresponding node is. That's why I chose a
> doubly-linked list.
>
> I noticed this definition in lists.lisp:
>
> (defmethod delete-item ((list dlist-container) (node dlist-
> container-node))
> (delete-item list (element node)))
>
> The method for DELETE-ITEM on (DLIST-CONTAINER T) iterates through the
> LIST, deleting whichever elements pass the TEST with ITEM (where TEST
> is the equality predicate in the TEST slot of LIST, i.e. EQL).
>
> If that's really the method that gets called, then deletion of a
> DLIST-CONTAINER-NODE with DELETE-ITEM is O(n).
>
> This confirms my suspicion:
>
> CL-USER> (let ((dlist (containers:make-container 'containers:dlist-
> container)))
> (dolist (element '(a b c d))
> (containers:insert-item dlist element))
> (format t "~&original contents: ~S~
> %" (containers:collect-elements dlist))
> (format t "~&last node: ~S~%" (containers:last-item
> dlist))
> (trace containers:delete-item containers:next-item)
> (containers:delete-item dlist (containers:last-item
> dlist))
> (untrace containers:delete-item containers:next-item)
> (format t "~&new contents: ~S~
> %" (containers:collect-elements dlist))
> (values))
> original contents: (A B C D)
> last node: #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE D {AAD5241}>
> 0: (METABANG.CL-CONTAINERS:DELETE-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER {AAD1C01}>
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE D {AAD5241}>)
> 1: (METABANG.CL-CONTAINERS:DELETE-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER {AAD1C01}> D)
> 2: (METABANG.CL-CONTAINERS:NEXT-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE A {AAD2F71}>)
> 2: METABANG.CL-CONTAINERS:NEXT-ITEM returned
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE B {AAD3B01}>
> 2: (METABANG.CL-CONTAINERS:NEXT-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE B {AAD3B01}>)
> 2: METABANG.CL-CONTAINERS:NEXT-ITEM returned
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE C {AAD46B1}>
> 2: (METABANG.CL-CONTAINERS:NEXT-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE C {AAD46B1}>)
> 2: METABANG.CL-CONTAINERS:NEXT-ITEM returned
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE D {AAD5241}>
> 2: (METABANG.CL-CONTAINERS:NEXT-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE C {AAD46B1}>)
> 2: METABANG.CL-CONTAINERS:NEXT-ITEM returned
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE D {AAD5241}>
> 2: (METABANG.CL-CONTAINERS:NEXT-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE D {AAD5241}>)
> 2: METABANG.CL-CONTAINERS:NEXT-ITEM returned NIL
> 2: (METABANG.CL-CONTAINERS:NEXT-ITEM
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER-NODE D {AAD5241}>)
> 2: METABANG.CL-CONTAINERS:NEXT-ITEM returned NIL
> 1: METABANG.CL-CONTAINERS:DELETE-ITEM returned
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER {AAD1C01}>
> 0: METABANG.CL-CONTAINERS:DELETE-ITEM returned
> #<METABANG.CL-CONTAINERS:DLIST-CONTAINER {AAD1C01}>
> new contents: (A B C)
> ; No value
>
> The relationships between DELETE-ITEM, DELETE-ELEMENT, and DELETE-NODE
> are unclear to me (and only the first two are defined for
> DLIST-CONTAINERs). If we have the element/node divide, what
> constitutes an "item"?
>
> Assuming we want to just stick with DELETE-ITEM for both elements and
> nodes, fixing this is simple. This patch moves the bulk of the
> (DLIST-CONTAINER T) method to the (DLIST-CONTAINER
> DLIST-CONTAINER-NODE) method, and then simplifies the former to use
> the latter after identifying a node to delete.
>
> This also fixes another problem with the implementation of
> DELETE-ITEM: if I have two identical elements in a dlist, and then I
> call DELETE-ITEM on one of the _nodes_ (not an element), DELETE-ITEM
> will delete both nodes for that element, not just the one I wanted.
> This is what the test TEST-DLIST-DELETE-DUPLICATE-NODE checks for, and
> this patch makes that test pass.
>
>
> --- Don't accept non-NIL non-nodes as the reference node for
> insert-item-after and insert-item-before
>
>
> There are some problems with INSERT-ITEM-BEFORE and INSERT-ITEM-AFTER.
> These are the generic function signatures:
>
> INSERT-ITEM-AFTER (LIST NODE NEW-NODE)
> INSERT-ITEM-BEFORE (LIST NODE NEW-NODE)
>
> Where NODE is ordinarily the reference DLIST-CONTAINER-NODE to place
> NEW-NODE after or before.
>
> There are methods defined on NODE arguments which are not
> DLIST-CONTAINER-NODEs, and the problems occur when you pass a non-node
> object as NODE to one of these functions.
>
> What should be the proper behavior here is kind of unclear in the
> first place. It's reasonable to assume that if you're not passing a
> node when you're referencing something in the dlist, you must be
> trying to pass one of its element. But what's the right thing to do
> if the element does not occur? Or if it occurs more than once?
>
> None of the methods seem to do anything special with _elements_ of
> dlists passed as NODE, so for simplicity, I'll guess that passing an
> element in order to reference the node containing that element is not
> intended or supported.
>
> Let's take a look at the methods in question and see what they do:
>
> (defmethod insert-item-after ((list dlist-container) node
> (new-node dlist-container-node))
> (declare (ignore node))
> (setf (first-element list) new-node
> (last-element list) new-node)
> (setf (size list) 1)
> list)
>
> Yikes! If you call:
>
> (insert-item-after dlist 'x (make-node-for-container dlist 'y))
>
> The list is erased and replaced with Y.
>
> My guess is that this method exists in order to be able to append to
> the end of the list using code of this style like this (as the
> INSERT-ITEM method does):
>
> (insert-item-after (last-element dlist) new-node)
>
> I don't think this is the best way to go about doing that--INSERT-ITEM
> should be preferred, and INSERT-ITEM itself should handle this
> special-case. Or, if the contract for INSERT-ITEM doesn't specify the
> position of a new item, then I think an APPEND-ITEM generic function
> (and matching PREPEND-ITEM GF) should be defined in order for client
> code to reliably (and more clearly) append and prepend items.
>
> This method also has a bug: it doesn't update the NEXT-ITEM and
> PREVIOUS-ITEM slots of NEW-NODE to NIL.
>
> That aside, and operating under the above assumption that referencing
> dlist nodes by their element should not be supported, this patch
> changes the signature of this method to only apply when NODE is NIL.
> And even then, the method will now signal an error if the dlist is not
> empty, before blowing everything away.
>
> This makes TEST-DLIST-INSERT-ITEM-AFTER/ELEMENT pass.
>
> Small changes were also made to the methods of INSERT-ITEM-AFTER so
> that infinite recursion won't occur when the function is given a NODE
> argument that is not either a DLIST-CONTAINER-NODE or NIL.
> Specifically, the method on any types for the arguments NODE and
> NEW-NODE, which wraps NEW-NODE in a DLIST-CONTAINER-NODE, calls
> INSERT-ITEM-AFTER on the NODE and the wrapped NEW-NODE. The effective
> method would be that same method, so I defined another method to catch
> this case and prevent the infinite recursion. (I hope the comments in
> this new method adequately explain the intention.) I also removed a
> seemingly redundant method which also wraps NEW-NODE in a
> DLIST-CONTAINER-NODE; this method was on NODE of type
> DLIST-CONTAINER-NODE and NEW-NODE of any type.
>
>
> Here's another method which I'm not 100% clear on the intention of:
>
> (defmethod insert-item-before ((list dlist-container) node item)
> (declare (ignore node))
> (insert-item list item))
>
> In this case, if NODE is not a node, then the item is simply appended
> to the end of LIST without regard to the position of NODE in LIST (if
> it appears as an element of some node).
>
> I'm guessing this method exists as a symmetry to the above NIL-node
> special case for INSERT-ITEM-AFTER, so that you can prepend an element
> to the beginning of a dlist by writing:
>
> (insert-item-before (first-element dlist) new-node)
>
> If this is the actual intent, we should make that more clear by only
> accepting NIL or DLIST-CONTAINER-NODEs for the NODE parameter of
> INSERT-ITEM-BEFORE. In the NIL case, we should also ensure that the
> list really is empty. This patch also makes this change, which in
> turn makes TEST-DLIST-INSERT-ITEM-AFTER/ELEMENT pass.
>
> Nothing in cl-containers itself seems to use this method of
> INSERT-ITEM-BEFORE, so this change shouldn't break anything
> internally. Hopefully nobody else is counting on the old behavior.
>
> INSERT-ITEM-BEFORE doesn't wrap non-node NEW-NODE arguments with a new
> DLIST-CONTAINER-NODE instance when NODE is NIL. To be consistent with
> INSERT-ITEM-AFTER, I've also changed the DLIST-CONTAINER-NODE-wrapping
> method of INSERT-ITEM-BEFORE to accept a NODE of any type. To prevent
> the same infinite recursion problem, I added a similar check for
> INSERT-ITEM-BEFORE as I did for INSERT-ITEM-AFTER.
>
>
> Thank you for taking the time to look over all of this. I hope you
> find the patches helpful.
>
> --
> J.P. Larocque: <jpl at thoughtcrime.us>, +1 509 324-2410
> <dlist-container-
> fixes.dpatch>_______________________________________________
> cl-containers-devel mailing list
> cl-containers-devel at common-lisp.net
> http://common-lisp.net/cgi-bin/mailman/listinfo/cl-containers-devel
--
Gary Warren King, metabang.com
Cell: (413) 559 8738
Fax: (206) 338-4052
gwkkwg on Skype * garethsan on AIM * gwking on twitter
More information about the cl-containers-devel
mailing list