- changed milestone to Next Minor Release
NPE after tLinkedList.removeFirst()
Example:
TLinkedList list = new TLinkedList();
TLinkableAdapter linkable1 = new TLinkableAdapter() {
};
TLinkableAdapter linkable2 = new TLinkableAdapter() {
};
TLinkableAdapter linkable3 = new TLinkableAdapter() {
};
list.add(linkable1);
list.add(linkable2);
list.add(linkable3);
list.add(linkable1);
list.add(linkable2);
list.add(linkable3);
list.removeFirst();
list.removeFirst();
list.removeFirst();
System.out.println(list.get(0));
System.out.println(list.get(1));
System.out.println(list.get(2));
list.toString();
The output is:
net.catharos.engine.core.util.structures.TopologicalSort$1@a62812d
null
net.catharos.engine.core.util.structures.TopologicalSort$3@490eb6ae
Exception in thread "main" java.lang.NullPointerException
at gnu.trove.list.linked.TLinkedList$IteratorImpl.next(TLinkedList.java:703)
at gnu.trove.list.linked.TLinkedList$IteratorImpl.next(TLinkedList.java:613)
at java.util.AbstractCollection.toString(AbstractCollection.java:449)
at net.catharos.engine.core.util.structures.TopologicalSort.main(TopologicalSort.java:94)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)
So after the removeFirst() statements somehow the second entry becomes null.
Comments (10)
-
-
- marked as major
Bumping the priority down a bit (though I'll still fix it right away).
-
- changed status to invalid
Oh wait, the problem is that you're adding the same Linkable item twice, which won't work.
When you add "linkable1" the second time, it's still stored as the head but it's now also added as the tail and its previous entry is now pointing at linkable3. And so on...
When the first remove is performed, linkable1's "next" pointer is nulled and it's removed as the head, but it still exists in the "next" pointer for linkable3.
We could potentially prevent this by either:
- Crawling through all the elements in the list to ensure the element doesn't already exist (very expensive)
- Tracking an extra field with the list the element belongs to (not totally reliable, requires API change and also a slight performance hit)
None of those are really good options, IMO, so for the moment I think I'd have to leave it with "don't do that".
If you disagree or have another idea for a solution, please comment on the bug and we'll discuss more.
-
reporter I'll think about a solution tomorrow, but it definitely needs to be fixed. For example if I use the default java LinkedList it works. But this should work, a linked list should be able to contain the same object twice.
-
reporter The behaviour of the TLinkedList should be the same as the java LinkedList.
-
Sorry, I disagree. This implementation is solving additional problems beyond what java.util.LinkedList is, namely not allocating temporary objects. In addition the limitations are detailed in the class docs:
- the same object cannot be put into more than one list at the same time.
- the same object cannot be put into the same list more than once at the same time.
- objects must only be removed from list they are in. That is, if you have an object A and lists l1 and l2, you must ensure that you invoke List.remove(A) on the correct list.
- It is also forbidden to invoke List.remove() with an unaffiliated TLinkable (one that belongs to no list): this will destroy the list you invoke it on.
-
I should also note that this doesn't mean you can't stick the same data in the list multiple times. If you are using wrapper nodes for the Linkable implementations, you can point to the same object with different wrappers. Example:
Linkable1 Linkable2 Linkable3 | | | | v | | Value2 | v / Value1 <----------------
-
- changed milestone to 3.0.5.b1
-
- changed milestone to 3.0.5.m1
-
- changed milestone to 3.1
- Log in to comment
I've reproduced this with the provided unit test.