[cl-containers-devel] dlist-container bug fixes
J.P. Larocque
jpl at thoughtcrime.us
Mon Aug 3 11:52:18 UTC 2009
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
-------------- next part --------------
Fri Jul 31 17:22:09 PDT 2009 J.P. Larocque <jpl at thoughtcrime.us>
* Fixed bugs in deleting nodes from a dlist-container
Previously, the list was searched for matching nodes. Now the node is
deleted directly, giving the expected O(1) time.
Also, when the element of the node to be deleted appears identically
elsewhere in the dlist, the other instances are not affected (making
TEST-DLIST-DELETE-DUPLICATE-NODE pass).
Fri Jul 31 18:50:51 PDT 2009 J.P. Larocque <jpl at thoughtcrime.us>
* Added several tests for doubly-linked lists
Mon Aug 3 04:12:42 PDT 2009 J.P. Larocque <jpl at thoughtcrime.us>
* Don't accept non-NIL non-nodes as the reference node for insert-item-after and insert-item-before
This change prevents accidental list obliteration when a
non-dlist-container-node is passed as NODE to insert-item-after.
Passing NIL as NODE is still supported in order to insert into an
empty list, but only after double-checking that the list really is
empty.
Also fixed a bug in the non-node-as-NODE method of insert-item-after
in order to correctly set the previous and next references of the
NEW-NODE.
Similarly changed insert-item-before to only take
dlist-container-nodes and NIL as the NODE. Like insert-item-after,
NIL is supported only for insertion when the list is empty.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
New patches:
[Fixed bugs in deleting nodes from a dlist-container
J.P. Larocque <jpl at thoughtcrime.us>**20090801002209
Previously, the list was searched for matching nodes. Now the node is
deleted directly, giving the expected O(1) time.
Also, when the element of the node to be deleted appears identically
elsewhere in the dlist, the other instances are not affected (making
TEST-DLIST-DELETE-DUPLICATE-NODE pass).
] {
hunk ./dev/lists.lisp 274
- - (cond
- - ((eq node (last-element list))
- - (cond
- - ((eq node (first-element list))
- - (setf (first-element list) nil)
- - (setf (last-element list) nil)
- - (decf (size list))
- - (element node))
- - (t (delete-item-after
- - list
- - (previous-item node)))))
- - (t (delete-item-before
- - list
- - (next-item node))))))))
+ (delete-item list node)))))
hunk ./dev/lists.lisp 277
- - (delete-item list (element node)))
+ (cond
+ ((eq node (last-element list))
+ (cond
+ ((eq node (first-element list))
+ (setf (first-element list) nil)
+ (setf (last-element list) nil)
+ (decf (size list))
+ (element node))
+ (t (delete-item-after
+ list
+ (previous-item node)))))
+ (t (delete-item-before
+ list
+ (next-item node)))))
}
[Added several tests for doubly-linked lists
J.P. Larocque <jpl at thoughtcrime.us>**20090801015051] {
hunk ./tests/dlist.lisp 3
+(defun ensure-dlist-consistent (dlist)
+ "Ensures the internal structure of DLIST and its nodes are consistent."
+ (declare (optimize safety debug))
+ (let* ((*lift-equality-test* 'eq)
+ (size (size dlist))
+ (nodes (make-array size :element-type 'dlist-container-node)))
+ (loop for node = (first-item dlist) then (next-item node)
+ for i from 0 below size
+ until (null node)
+ ;; Check this now to prevent taking NEXT-ITEM of some random
+ ;; object.
+ doing (ensure (typep node 'dlist-container-node)
+ :report "NEXT-ITEM of node references a non-NIL non-node: ~S"
+ :arguments (node))
+ doing (setf (elt nodes i) node)
+ finally (ensure (null node)
+ :report "NEXT-ITEM chain extends beyond SIZE")
+ finally (ensure (= i size)
+ :report "NEXT-ITEM chain exhausted before SIZE"))
+ (when (zerop size)
+ (ensure (null (first-item dlist))
+ :report "FIRST-ITEM of empty DLIST-CONTAINER is not NIL")
+ (ensure (null (last-item dlist))
+ :report "LAST-ITEM of empty DLIST-CONTAINER is not NIL"))
+ (unless (zerop size)
+ (ensure-same (first-item dlist) (elt nodes 0)
+ :report "Unexpected FIRST-ITEM of DLIST-CONTAINER")
+ (ensure-same (last-item dlist) (elt nodes (1- size))
+ :report "Unexpected LAST-ITEM of DLIST-CONTAINER")
+ (ensure (null (previous-item (elt nodes 0)))
+ :report "PREVIOUS-ITEM of first node isn't NIL")
+ (ensure (null (next-item (elt nodes (1- size))))
+ :report "NEXT-ITEM of last node isn't NIL")
+ (loop for i1 from 0 below (1- size)
+ for i2 from 1 below size
+ for node1 = (elt nodes i1)
+ for node2 = (elt nodes i2)
+ doing (ensure-same (next-item node1) node2
+ :report "Unexpected NEXT-ITEM of node at position ~D"
+ :arguments (i1))
+ doing (ensure-same node1 (previous-item node2)
+ :report "Unexpected PREVIOUS-ITEM of node at position ~D"
+ :arguments (i2))))))
+
hunk ./tests/dlist.lisp 48
- - ())
+ (dlist)
+ (:setup (setf dlist (make-container 'dlist-container)))
+ (:equality-test 'equal))
hunk ./tests/dlist.lisp 55
- - (ensure-same (size (make-container 'dlist-container)) 0))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (size dlist) 0))
+
+(addtest (test-dlist-container)
+ test-dlist-empty!
+ (insert-item dlist 'a)
+ (insert-item dlist 'b)
+ (empty! dlist)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (size dlist) 0))
+
+
+(addtest (test-dlist-container)
+ test-dlist-add-elements
+ (insert-item dlist 'a)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a))
+
+ (insert-item dlist 'b)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b))
+
+ (insert-item dlist 'c)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c)))
+
+(addtest (test-dlist-container)
+ test-dlist-add-nodes
+ (flet ((make-node (element)
+ (make-node-for-container dlist element)))
+ (let ((a-node (make-node 'a))
+ (b-node (make-node 'b))
+ (c-node (make-node 'c)))
+ (insert-item dlist a-node)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a))
+
+ (insert-item dlist b-node)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b))
+
+ (insert-item dlist c-node)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c))
+
+ (ensure-same (collect-nodes dlist) `(,a-node ,b-node ,c-node)
+ :report "actual nodes don't share identity with given nodes after insertion"))))
+
+
+(addtest (test-dlist-container)
+ test-dlist-insert-item-after
+ ;; Use FLET rather than LAMBDAs for informative failure reports.
+ (flet ((new-item/node (element)
+ (make-node-for-container dlist element))
+ (new-item/element (element)
+ element))
+ (dolist (new-item `(,#'new-item/node ,#'new-item/element))
+ (empty! dlist)
+ (dolist (element '(a c))
+ (insert-item dlist element))
+
+ ;; Ensure we test new items in the middle and at the end.
+ (insert-item-after dlist (item-at dlist 0) (funcall new-item 'b))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c)
+ :report "Middle-insertion failed with ~S and ~S"
+ :arguments (new-item))
+
+ (insert-item-after dlist (item-at dlist 2) (funcall new-item 'd))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c d)
+ :report "End-insertion failed with ~S and ~S"
+ :arguments (new-item)))))
+
+(addtest (test-dlist-container)
+ 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.
+ (dolist (element '(a b))
+ (insert-item dlist element))
+ (let ((succeeded? (ignore-errors
+ (insert-item-after dlist 'b 'c)
+ t)))
+ (when succeeded?
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c)))))
+
+(addtest (test-dlist-container)
+ test-dlist-insert-item-before
+ ;; Use FLET rather than LAMBDAs for informative failure reports.
+ (flet ((new-item/node (element)
+ (make-node-for-container dlist element))
+ (new-item/element (element)
+ element))
+ (dolist (new-item `(,#'new-item/node ,#'new-item/element))
+ (empty! dlist)
+ (dolist (element '(b d))
+ (insert-item dlist element))
+
+ ;; Ensure we test new items in the middle and at the beginning.
+ (insert-item-before dlist (item-at dlist 1) (funcall new-item 'c))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(b c d)
+ :report "Middle-insertion failed with ~S and ~S"
+ :arguments (new-item))
+
+ (insert-item-before dlist (item-at dlist 0) (funcall new-item 'a))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c d)
+ :report "Beginning-insertion failed with ~S and ~S"
+ :arguments (new-item)))))
+
+(addtest (test-dlist-container)
+ 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.
+ (dolist (element '(b c))
+ (insert-item dlist element))
+ (let ((succeeded? (ignore-errors
+ (insert-item-before dlist 'b 'a)
+ t)))
+ (when succeeded?
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c)))))
+
+;; FIXME: REPLACE-ITEM should be tested.
+
+(addtest (test-dlist-container)
+ test-dlist-delete-elements
+ (dolist (element '(a b c))
+ (insert-item dlist element))
+
+ ;; Ensure we delete a middle element, then a first, then a last,
+ ;; then a first-and-last.
+
+ (delete-item dlist 'b)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a c))
+
+ (delete-item dlist 'a)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(c))
+
+ (insert-item dlist 'd)
+ (ensure-same (collect-elements dlist) '(c d))
+ (delete-item dlist 'd)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(c))
+
+ (delete-item dlist 'c)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '()))
+
+(addtest (test-dlist-container)
+ test-dlist-delete-duplicate-elements
+ ;; Test:
+ ;; * Contiguous repetition.
+ ;; * Non-contiguous repetition.
+ ;; * Repetition at the beginning.
+ ;; * Repetition in the middle.
+ ;; * Repetition at the end.
+ (dolist (element '(x x a x x b x c x))
+ (insert-item dlist element))
+ (delete-item dlist 'x)
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c)))
+
+(addtest (test-dlist-container)
+ test-dlist-delete-duplicate-node
+ ;; Ensure that calling DELETE-ITEM on a node whose element appears
+ ;; multiple times doesn't affect other nodes with identical
+ ;; elements.
+ (dolist (element '(a x b x c))
+ (insert-item dlist element))
+ (delete-item dlist (item-at dlist 1))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b x c)))
+
+(addtest (test-dlist-container)
+ test-dlist-delete-item-before
+ (dolist (element '(a b c))
+ (insert-item dlist element))
+
+ ;; Ensure we delete a middle node, then a first.
+ (delete-item-before dlist (item-at dlist 0))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c))
+
+ (delete-item-before dlist (item-at dlist 2))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a c))
+
+ (delete-item-before dlist (item-at dlist 1))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(c)))
hunk ./tests/dlist.lisp 251
+(addtest (test-dlist-container)
+ test-dlist-delete-item-after
+ (dolist (element '(a b c))
+ (insert-item dlist element))
+
+ ;; Ensure we delete a middle node, then a last.
+ (delete-item-after dlist (item-at dlist 2))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a b c))
+
+ (delete-item-after dlist (item-at dlist 0))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a c))
+
+ (delete-item-after dlist (item-at dlist 0))
+ (ensure-dlist-consistent dlist)
+ (ensure-same (collect-elements dlist) '(a)))
}
[Don't accept non-NIL non-nodes as the reference node for insert-item-after and insert-item-before
J.P. Larocque <jpl at thoughtcrime.us>**20090803111242
This change prevents accidental list obliteration when a
non-dlist-container-node is passed as NODE to insert-item-after.
Passing NIL as NODE is still supported in order to insert into an
empty list, but only after double-checking that the list really is
empty.
Also fixed a bug in the non-node-as-NODE method of insert-item-after
in order to correctly set the previous and next references of the
NEW-NODE.
Similarly changed insert-item-before to only take
dlist-container-nodes and NIL as the NODE. Like insert-item-after,
NIL is supported only for insertion when the list is empty.
] {
hunk ./dev/lists.lisp 201
+ ;; This method is necessary when INSERT-ITEM-AFTER is called with a
+ ;; non-NIL non-node as NODE and a non-NODE as NEW-NODE. Otherwise,
+ ;; infinite recursion results in the (DLIST-CONTAINER T T) method.
+ (declare (ignore list node new-node))
+ (error "Cannot insert-item-after an object that is not a dlist-container-node or nil"))
+
+(defmethod insert-item-after ((list dlist-container) (node null)
+ (new-node dlist-container-node))
hunk ./dev/lists.lisp 210
+ (unless (empty-p list)
+ (error "Cannot insert-item-after nil, unless the dlist-container is empty."))
hunk ./dev/lists.lisp 213
- - (last-element list) new-node)
+ (last-element list) new-node
+ (previous-item new-node) nil
+ (next-item new-node) nil)
hunk ./dev/lists.lisp 219
- -(defmethod insert-item-after ((list dlist-container)
- - (node dlist-container-node) item)
- - (insert-item-after list node (make-node-for-container list item)))
- -
hunk ./dev/lists.lisp 232
+ (insert-item-before list node (make-node-for-container list item)))
+
+(defmethod insert-item-before ((list dlist-container) node
+ (new-node dlist-container-node))
+ ;; This method is necessary when INSERT-ITEM-BEFORE is called with a
+ ;; non-NIL non-node as NODE and a non-NODE as NEW-NODE. Otherwise,
+ ;; infinite recursion results in the (DLIST-CONTAINER T T) method.
+ (declare (ignore list node new-node))
+ (error "Cannot insert-item-before an object that is not a dlist-container-node or nil"))
+
+(defmethod insert-item-before ((list dlist-container) (node null)
+ (item dlist-container-node))
hunk ./dev/lists.lisp 245
+ (unless (empty-p list)
+ (error "Cannot insert-item-before nil, unless the dlist-container is empty."))
hunk ./dev/lists.lisp 249
- -(defmethod insert-item-before ((list dlist-container)
- - (node dlist-container-node) item)
- - (insert-item-before list node (make-node-for-container list item)))
- -
}
Context:
[TAG version-0.11.5
Gary King <gwking at metabang.com>**20090427022540]
[bump version
Gary King <gwking at metabang.com>**20090427022527]
[add container-dynamic-classes system (only defined when asdf-system-connections is _not_ loaded
Gary King <gwking at metabang.com>**20090427022521]
[TAG version-0.11.4
Gary King <gwking at metabang.com>**20090308154821]
[bump version
Gary King <gwking at metabang.com>**20090308154810]
[removed misc.lisp from test system file
Gary King <gwking at metabang.com>**20090308154728]
[updated tests for lift 1.7.0
Gary King <gwking at metabang.com>**20090308154706]
[Use node-empty-p function to test for empty node instead of looking at the element directly
Nathan Bird <nathan at acceleration.net>**20090307191211]
[Getting rid of miscellaneous tests that were commented out.
Nathan Bird <nathan at acceleration.net>**20090307191034
The one chunk of code in here (not active) got fixed up and moved to the other trees test file.
]
[Adding several more tests on the trees
Nathan Bird <nathan at acceleration.net>**20090307191014]
[When searching for an item in a bst, make sure that the node isn't a placeholder and actually has an element
Nathan Bird <nathan at acceleration.net>**20090306165250]
[TAG version-0.11.3
Gary King <gwking at metabang.com>**20090206172358]
[bump version
Gary King <gwking at metabang.com>**20090206172340]
[remove moptilities file
Gary King <gwking at metabang.com>**20090206164543]
[Fix naming problems, add find-successor-item to tree functions and export
eslick at media.mit.edu**20090202233414]
[TAG version-0.11.2
Gary King <gwking at metabang.com>**20081117131945]
[bump version
Gary King <gwking at metabang.com>**20081117131936]
[Patch from Daniel Herring to keep load order happy after the recent changes.
Gary King <gwking at metabang.com>**20081117131308]
[TAG version-0.11.1
Gary King <gwking at metabang.com>**20081027010936]
[fix test package
Gary King <gwking at metabang.com>**20081027010931]
[bump version
Gary King <gwking at metabang.com>**20081027010620]
[added user-guide
Gary King <gwking at metabang.com>**20081027010539]
[documentation system
Gary King <gwking at metabang.com>**20081026000042]
[documentation and docstring tweaks
Gary King <gwking at metabang.com>**20081025235952]
[Document collect-keys for lists
Gary King <gwking at metabang.com>**20081025235843]
[some website tweaks
Gary King <gwking at metabang.com>**20081025235740]
[Added documentation system and some support files
Gary King <gwking at metabang.com>**20081025235729]
[Added GNUmakefile with shared-copy target
Gary King <gwking at metabang.com>**20081025235702]
[removed ;;; -+ lines
Gary King <gwking at metabang.com>**20080930023432]
[First steps towards a user's guide
Gary King <gwking at metabang.com>**20080928230744]
[TAG version-0.11.0
Gary King <gwking at metabang.com>**20080928194030]
Patch bundle hash:
b39f2fd9988c5c91e2b89417fabd13516d81667f
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
iD8DBQFKds3IgFVc7XOU+UgRAgw5AJ9WA0xWjMJsTN3iV/YQtk3nVJGRzQCdEWgD
mLioQJ4nee+LAVdq/3ORh4U=
=LyNX
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <https://mailman.common-lisp.net/pipermail/cl-containers-devel/attachments/20090803/5d549f64/attachment.sig>
More information about the cl-containers-devel
mailing list