[PATCH][Collections] Thread-safe fast collection classes

["Jack, Paul" <pj...@sfaf.org>]

Attached are modifications to FastArrayList, FastHashMap,
and FastTreeMap...

1.  Sublists, submaps, map collection views, iterators
and list iterators are all thread-safe now.  Many many 
package-protected classes were added to achieve this.

2.  Serialization has been somewhat improved.

3.  toString() methods have been added to FastHashMap and
FastTreeMap -- the previous implementation would always return
an empty map ("{}") if toString() were invoked.

4.  The classes are now, controversially, cross-platform.
The earlier versions were plagued by the same problems as 
the double-checked locking idiom; on some platforms, an
optimizing compiler or pipeline could conceivably write an
object reference before the object was fully modified.  Or,
with multiple processors, some kind of read barrier is needed
to make sure a processor has the most recent object reference...

The attached versions don't have these problems.  But, it's a
controversial fix for the following reasons:

a.  In order to do it, the following fields were demoted from 
protected to private:  FastArrayList.list, FastHashMap.map, 
FastTreeMap.map.  This of course breaks binary compatibility.
However, it's impossible to do the fix if these fields are 
accessible.  There are now protected accessor and mutator 
methods for those fields, so code that uses them can be made to
work with a minimal migration effort.

b.  One new class (SafeReference) and one new interface 
(SafeReferenceFactory) were added to the commons.collection
package.  These classes probably don't belong there however,
as their scope is more generic.  

c.  The new class and interface utilize a system property,
org.apache.SafeReferenceFactoryClass.  

d.  By default, read operation in the fast collection classes now
actually enter a monitor.  I realize the whole point of the
classes was to avoid synchronization on read operations, but it
simply cannot be done in a platform-independent way.  However,
the classes are still "fast" for two reasons:

* The critical section on a read operation is "the shortest 
imaginable".  Basically fast mode reads look like this by default:

    public String toString() {
        Collection local;
        synchronized (this) {
            local = this.global;
        }
        return local.toString();
    }

So multiple threads won't have to wait for a lengthy read op like
toString() to complete before acquiring the monitor.  This seemed 
like the next best thing to unsynchronized reads.

* The default synchronization can be overridden, if you know your 
platform can support safe unsynchronized reads.  That's the point of
the SafeReferenceFactory interface and the system property...you
can provide a custom implementation of SafeReference that doesn't
synchronize on reads.  In particular, the forthcoming revision to the
Java Memory Model will probably allow a SafeReference impl based on
the volatile keyword.

Again, it's controversial.  But it seems having platform-independent
code is worth it.  Lemme know what you think...

-Paul