Re: [patch] Re: HashMap putAll/putAllInternal bug
Brian Jones wrote:
Cool, don't want to hold you up on that too much. Wondering how Sun's
impl makes a copy of the given Collection while avoiding copying an
object being modified in another thread. Anyone know? I think the
Iterators are supposed to throw exceptions when this occurs too.
I don't think this is affected too much either way by my patch. If
another thread is actively modifying the collection being added at the
time we're trying to add it, and it's not a thread-safe collection, the
results are undefined. If it *is* a thread-safe collection, the most
that's guaranteed is that you'll get a ConcurrentModificationException
in the right place.
(Actually, my patch probably helps with that case too: by only
incrementing this.size as each item is actually added, the state of the
Map is closer to valid if a ConcurrentModificationException is thrown
part-way through the iteration. Perhaps it could be tweaked to be even
better in that regard by putting the size++ *after* the call to next()).
My patch really only affects what happens if the value returned by
size() is incorrect for a particular Map. Without the patch, Classpath
blindly believes size() and attempts to add exactly that many elements,
throwing an exception if there are actually less and not adding all of
them if there are actually more. With the patch, it relies on the
iterator to determine how many items there actually are.
I have a map where it's prohibitively expensive[1] to calculate the
correct value of size(). It would be possible, but a LOT of
collections-using code assumes that size() is fast - the very code that
this patch changes is an example, where it was assumed that calling
size() was much faster than calling hasNext() for each element and
therefore treated as an optimization. So the best I could do was to
cache a best guess at the size and return that from size(), and have
iterator() give the canonical information. On Sun's JDK, or on Classpath
with the patch, this works. Without it, it doesn't.
Stuart.
[1] A correct implementation of size() for my map would actually look
something like this:
public int size() {
int size = 0;
for (Iterator i = iterator(); i.hasNext(); ) {
i.next();
size++;
}
return size;
}
--
Stuart Ballard, Senior Web Developer
FASTNET - Web Solutions
(215) 283-2300, ext. 126
www.fast.net
___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
Re: [patch] Re: HashMap putAll/putAllInternal bug
Stuart Ballard wrote: Stuart Ballard wrote: The HashMap putAll and putAllInternal (called from constructor) methods use size() to get the size of the map to be added, and then iterate over the iterator that many times to add elements. Instead, they should call hasNext() on the iterator. Attached is a patch to HashMap and Hashtable to fix this issue. Not attached here ;) If someone would test and apply this patch, I'd be extremely grateful. (my paperwork was completed years ago, in case it matters - this patch is probably too small to care, anyway). The patch is untested as I've never been able to successfully build Classpath from source. Could you give it spin on kaffe from CVS? It uses Classpath's collection classes. cheers, dalibor topic ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: [patch] Re: HashMap putAll/putAllInternal bug
Dalibor Topic wrote:
Not attached here ;)
I already resent it but just in case that didn't make it through, I've
re-attached it here.
Could you give it spin on kaffe from CVS? It uses Classpath's collection
classes.
It applies cleanly to Kaffe CVS (of course) and passes all 144 make
check tests; I also confirmed that it does have the desired behavior of
allowing nrdo's first pass to run unmodified on Kaffe and generate
correct results. If this gets accepted (and barring any problems in the
second phase, which is mostly pretty simple JDBC) I can put nrdo on
Savannah! Woo!
Stuart.
--
Stuart Ballard, Senior Web Developer
FASTNET - Web Solutions
(215) 283-2300, ext. 126
www.fast.net
Index: HashMap.java
===
RCS file: /cvsroot/classpath/classpath/java/util/HashMap.java,v
retrieving revision 1.24
diff -u -r1.24 HashMap.java
--- HashMap.java1 Aug 2003 03:31:32 - 1.24
+++ HashMap.java25 Sep 2003 18:16:52 -
@@ -381,8 +381,7 @@
public void putAll(Map m)
{
Iterator itr = m.entrySet().iterator();
-int msize = m.size();
-while (msize-- 0)
+while (itr.hasNext())
{
Map.Entry e = (Map.Entry) itr.next();
// Optimize in case the Entry is one of our own.
@@ -709,10 +708,10 @@
void putAllInternal(Map m)
{
Iterator itr = m.entrySet().iterator();
-int msize = m.size();
-size = msize;
-while (msize-- 0)
+size = 0;
+while (itr.hasNext())
{
+size++;
Map.Entry e = (Map.Entry) itr.next();
Object key = e.getKey();
int idx = hash(key);
Index: Hashtable.java
===
RCS file: /cvsroot/classpath/classpath/java/util/Hashtable.java,v
retrieving revision 1.28
diff -u -r1.28 Hashtable.java
--- Hashtable.java 7 May 2002 05:13:05 - 1.28
+++ Hashtable.java 25 Sep 2003 18:16:52 -
@@ -510,7 +510,7 @@
{
Iterator itr = m.entrySet().iterator();
-for (int msize = m.size(); msize 0; msize--)
+while (itr.hasNext())
{
Map.Entry e = (Map.Entry) itr.next();
// Optimize in case the Entry is one of our own.
@@ -859,11 +859,11 @@
void putAllInternal(Map m)
{
Iterator itr = m.entrySet().iterator();
-int msize = m.size();
-this.size = msize;
+size = 0;
-for (; msize 0; msize--)
+while (itr.hasNext())
{
+size++;
Map.Entry e = (Map.Entry) itr.next();
Object key = e.getKey();
int idx = hash(key);
___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
Re: [patch] Re: HashMap putAll/putAllInternal bug
Stuart Ballard [EMAIL PROTECTED] writes: Dalibor Topic wrote: Not attached here ;) I already resent it but just in case that didn't make it through, I've re-attached it here. Could you give it spin on kaffe from CVS? It uses Classpath's collection classes. It applies cleanly to Kaffe CVS (of course) and passes all 144 make check tests; I also confirmed that it does have the desired behavior of allowing nrdo's first pass to run unmodified on Kaffe and generate correct results. If this gets accepted (and barring any problems in the second phase, which is mostly pretty simple JDBC) I can put nrdo on Savannah! Woo! Cool, don't want to hold you up on that too much. Wondering how Sun's impl makes a copy of the given Collection while avoiding copying an object being modified in another thread. Anyone know? I think the Iterators are supposed to throw exceptions when this occurs too. Brian -- Brian Jones [EMAIL PROTECTED] ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
RE: [patch] Re: HashMap putAll/putAllInternal bug
Brian Jones wrote: Wondering how Sun's impl makes a copy of the given Collection while avoiding copying an object being modified in another thread. Anyone know? I think the Iterators are supposed to throw exceptions when this occurs too. Most collections are not defined as being thread-safe. Even the synchronized collections require that the user lock the collection before iterating through it. Bottom line: It is up to the user to ensure that a collection that is used with addAll etc is not being modified whilst it is being added. The ConcurrentModificationException thrown by Iterators is not just for detecting concurrent modification by different threads (which they may detect) but also for detecting modification of the collection by the same thread that has an iterator active at the time the modification is made. In simple terms they detect if you add while iterating, or remove while iterating - other than via the iterators remove() method. David Holmes ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
