commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Peter Firmstone <peter.firmst...@zeus.net.au>
Subject [collections] Reference Collection Utilities
Date Wed, 28 Sep 2011 23:07:27 GMT
These reference collection utilities don't really belong in our project, 
but they do assist to solve some fundamental problems using references 
in collections, the implementation is abstracted so it can be utilised 
for any valid Collections Framework Interface implementation, allowing 
the user to use any of the Java Collections Framework classes with any 
mix of weak, weak identity, soft, soft identity or strong references, 
while keeping the references abstracted out of the collections api under 
the covers.  While not directly focused on Concurrency problems, it is 
intended to be used with concurrent code.

If you guys want to take it over and improve it, provided you think it 
might be of some use, or just give it some peer review and suggest 
improvements, that would certainly benefit us.

See below for more info.

P.S. can you cc me in your reply?  I'm not subscribed to commons dev.

Regards,

Peter.

-------- Original Message --------
Subject:     Re: New Collection Utilities.
Date:     Mon, 26 Sep 2011 10:24:16 -0500
From:     Gregg Wonderly <gergg@cox.net>
To:     Peter Firmstone <peter.firmstone@zeus.net.au>



You might think about announcing this on the concurrency list to see if 
you can
elicit any thoughts on their interest in it, as well as more eyes that 
might be
able to point out anything that could be even better on concurrency control.

Gregg

On 9/26/2011 2:52 AM, Peter Firmstone wrote:
 >  The new reference collection utilities I've just committed, probably 
appear a
 >  little daunting, so many classes...
 >
 >  Anyway, all the client needs are these two, the rest is private 
implementation.
 >  It has an extremely compact API.
 >
 >  org.apache.river.impl.util.RC - Stands for ReferenceCollection, 
contains static
 >  methods.
 >  org.apache.river.impl.util.Ref - An enum parameter, allows the 
developer to
 >  select the desired reference type.
 >
 >  RC provides static methods to encapsulate Collections containing 
references
 >  behind facades handling reference creation, calls to get, removal 
and garbage
 >  collecting of References.
 >
 >  All Java Collection Framework interfaces are implemented fully, 
right down to
 >  the correct equals behaviour for Set, List and Map, and Map.Entry 
and Set's of
 >  Entry's. Even the reference classes themselves are overridden 
(although package
 >  private) to implement the correct equals and hashcode behaviour. 
It's all been
 >  tested with unit tests.
 >
 >  Two Sets, one utilising Weak References and any other Set containing 
the same
 >  objects will be equal as per the Set interface requirement, no 
matter what
 >  reference types are utilised, the same goes for List's, Maps, 
NavigableMap,
 >  SortedMap, SortedSet, ConcurrentMap, ConcurrentNavigableMap and all 
the other
 >  JCF interfaces you can think of.
 >
 >  All views remain referenced, so their referents don't inadvertantly 
become
 >  strongly referenced. Only the developers calling classes will make 
the referents
 >  strongly referenced upon retrieval.
 >
 >  Synchronization must be performed by the internal collection passed 
in by the
 >  developer, it can't be performed externally - garbage collection causes
 >  mutation. To assist concurrency there's a third class with static 
methods
 >  org.apache.river.impl.utils.ConcurrentCollections to provide 
synchronization
 >  wrappers (multi read, single write) similar to wrapper classes 
provided in
 >  java.util.Collections
 >
 >  The RC class makes it extremely simple to create Reference based 
Collections:
 >
 >  Set<String>  strings = RC.set(new TreeSet<Reference<String>>(), 
Ref.SOFT);
 >
 >  Static methods were chosen over constructors because they're easier 
to read (not
 >  filled with generics) and make the API appear much smaller, you only 
need two
 >  new classes and don't need to know the implementation details.
 >
 >  Yes it supports Comparator's too:
 >
 >  ConcurrentNavigableMap<Integer, String>  instance;
 >  Comparator<Integer>  comparator;
 >
 >  // A simple comparator - demonstration purposes only.
 >  comparator = new Comparator<Integer>(){
 >
 >  @Override
 >  public int compare(Integer o1, Integer o2) {
 >  return o1.compareTo(o2);
 >  }
 >
 >  };
 >
 >  Comparator<Reference<Integer>>  ci = RC.comparator(comparator);
 >
 >  ConcurrentNavigableMap<Reference<Integer>, Reference<String>>  internal
 >  = new ConcurrentSkipListMap<Reference<Integer>, Reference<String>>(ci);
 >
 >  instance = RC.concurrentNavigableMap(internal, Ref.WEAK, Ref.STRONG);
 >
 >
 >  The developer gets to choose the collection implementation and the 
reference
 >  types, all the hard work's done. I hope you find these reference 
utilities as
 >  useful as I have.
 >
 >  N.B. I'll create a jar archive for them and merge this back into the 
main trunk,
 >  after peer review.
 >
 >  Check it out from svn:
 >
 >  https://svn.apache.org/repos/asf/river/jtsk/skunk/peterConcurrentPolicy/
 >
 >  Or browse at:
 >
 >  http://svn.apache.org/viewvc/river/jtsk/skunk/peterConcurrentPolicy/
 >
 >  /*
 >  * Licensed to the Apache Software Foundation (ASF) under one
 >  * or more contributor license agreements. See the NOTICE file
 >  * distributed with this work for additional information
 >  * regarding copyright ownership. The ASF licenses this file
 >  * to you under the Apache License, Version 2.0 (the
 >  * "License"); you may not use this file except in compliance
 >  * with the License. You may obtain a copy of the License at
 >  *
 >  *http://www.apache.org/licenses/LICENSE-2.0
 >  *
 >  * Unless required by applicable law or agreed to in writing, software
 >  * distributed under the License is distributed on an "AS IS" BASIS,
 >  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 
implied.
 >  * See the License for the specific language governing permissions and
 >  * limitations under the License.
 >  */
 >
 >  package org.apache.river.impl.util;
 >
 >  /**
 >  * Ref enum represents the types of references provided by the jvm, 
it also
 >  * defines equals contract behaviour for Reference implementations 
suitable
 >  * for use in Collections.
 >  *
 >  * It is recommended to use STRONG or IDENTITY based references as keys
 >  * in Maps, due to the unpredictability that occurs, when an equal
 >  * Reference Key disappears due to garbage collection.
 >  *
 >  * Map implementations must delete their key ->  value mapping when 
either the
 >  * key or value References become unreachable.
 >  *
 >  * Object.toString() is overridden in the reference implementations 
to return
 >  * toString() of the referent, if it is still reachable, otherwise 
the reference
 >  * calls their superclass toString() method, where superclass is a java
 >  * Reference subclass.
 >  *
 >  * Phantom references are not used, they are designed to replace
 >  * {@link Object#finalize() } and remain unreachable, but not garbage 
collected
 >  until
 >  * the {@link PhantomReference} also becomes unreachable, get() 
always returns
 >  * null.
 >  *
 >  * @see Reference
 >  * @see WeakReference
 >  * @see SoftReference
 >  * @see PhantomReference
 >  * @see Map
 >  * @see ConcurrentMap
 >  * @see List
 >  * @see Set
 >  * @see Collection
 >  * @see Comparable
 >  * @author Peter Firmstone.
 >  */
 >  public enum Ref {
 >  /**
 >  * SOFT References implement equals based on equality of the referent
 >  * objects, while the referent is still reachable. The hashCode
 >  * implementation is based on the referent implementation of hashCode,
 >  * while the referent is reachable.
 >  *
 >  * After garbage collection, Reference equality is based
 >  * on the original identity of the referents using 
System.identityHashCode().
 >  *
 >  * Because {@link System#identityHashCode(java.lang.Object)} is not 
unique,
 >  * the referents Class.hashCode() is also used to calculate the hashCode,
 >  * generated during Reference construction.
 >  *
 >  * SOFT References implement Comparable allowing the referent Objects
 >  * to be compared if they implement Comparable. If the referent Object
 >  * doesn't implement Comparable, the hashCode's of the Reference is
 >  * compared instead. If the referent Objects don't implement Comparable,
 >  * then they shouldn't really be used in sorted collections.
 >  *
 >  * Garbage collection must be the same as SoftReference.
 >  * @see SoftReference
 >  * @see WeakReference
 >  * @see Comparable
 >  */
 >  SOFT,
 >  /**
 >  * SOFT_IDENTY References implement equals based on identity == of the
 >  * referent objects.
 >  *
 >  * Garbage collection must be the same as SoftReference.
 >  * @see SoftReference
 >  */
 >  SOFT_IDENTITY,
 >  /**
 >  * WEAK References implement equals based on equality of the referent
 >  * objects, while the referent is still reachable. The hashCode
 >  * implementation is based on the referent implementation of hashCode,
 >  * while the referent is reachable.
 >  *
 >  * After garbage collection, Reference equality is based
 >  * on the original identity of the referents using 
System.identityHashCode().
 >  *
 >  * Because System.identityHashCode() is not unique, the referents
 >  * Class.hashCode() is also used to calculate the hashCode, generated 
during
 >  * Reference construction.
 >  *
 >  * WEAK References implement comparable allowing the referent Objects
 >  * to be compared if they implement Comparable. If the referent Object
 >  * doesn't implement Comparable, the hashCode's of the Reference is
 >  * compared instead. If the referent Object's don't implement Comparable,
 >  * then they shouldn't really be used in sorted collections.
 >  *
 >  * Garbage collection must be the same as WeakReference.
 >  * @see WeakReference
 >  * @see Comparable
 >  */
 >  WEAK,
 >  /**
 >  * WEAK_IDENTY References implement equals based on identity == of the
 >  * referent objects.
 >  *
 >  * Garbage collection must be the same as WeakReference.
 >  *
 >  * @see WeakReference
 >  */
 >  WEAK_IDENTITY,
 >  /**
 >  * STRONG References implement equals and hashCode() based on the
 >  * equality of the underlying Object.
 >  *
 >  * STRONG References implement Comparable allowing the referent Objects
 >  * to be compared if they implement Comparable. If the referent Object
 >  * doesn't implement Comparable, the hashCode's of the Reference is
 >  * compared instead. If the referent Object's don't implement Comparable,
 >  * then they shouldn't really be used in sorted collections.
 >  *
 >  * Garbage collection doesn't occur until the Reference is cleared.
 >  * @see Comparable
 >  */
 >  STRONG
 >  }
 >
 >
 >  /*
 >  * Licensed to the Apache Software Foundation (ASF) under one
 >  * or more contributor license agreements. See the NOTICE file
 >  * distributed with this work for additional information
 >  * regarding copyright ownership. The ASF licenses this file
 >  * to you under the Apache License, Version 2.0 (the
 >  * "License"); you may not use this file except in compliance
 >  * with the License. You may obtain a copy of the License at
 >  *
 >  *http://www.apache.org/licenses/LICENSE-2.0
 >  *
 >  * Unless required by applicable law or agreed to in writing, software
 >  * distributed under the License is distributed on an "AS IS" BASIS,
 >  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 
implied.
 >  * See the License for the specific language governing permissions and
 >  * limitations under the License.
 >  */
 >
 >  package org.apache.river.impl.util;
 >
 >  import java.lang.ref.Reference;
 >  import java.lang.Comparable;
 >  import java.util.Collection;
 >  import java.util.Collections;
 >  import java.util.Comparator;
 >  import java.util.Deque;
 >  import java.util.List;
 >  import java.util.Map;
 >  import java.util.Map.Entry;
 >  import java.util.ListIterator;
 >  import java.util.NavigableMap;
 >  import java.util.NavigableSet;
 >  import java.util.Queue;
 >  import java.util.Set;
 >  import java.util.SortedMap;
 >  import java.util.SortedSet;
 >  import java.util.concurrent.BlockingDeque;
 >  import java.util.concurrent.BlockingQueue;
 >  import java.util.concurrent.ConcurrentMap;
 >  import java.util.concurrent.ConcurrentNavigableMap;
 >
 >  /**
 >  *<p>
 >  * This class contains a number of static methods for using and 
abstracting
 >  * References in Collections. Interfaces from the Java Collections 
Framework
 >  * are supported.
 >  *</p><p>
 >  * Referents in these collections may implement {@link Comparable} or
 >  * a {@link Comparator} may be used for sorting. When Comparator's 
are utilised,
 >  * they must first be encapsulated {@link 
RC#comparator(java.util.Comparator) },
 >  * before passing to a constructor for your preferred underlying 
Collection
 >  * implementation.
 >  *</p><p>
 >  * {@link Comparable} is not supported for IDENTITY == referenced 
Collections,
 >  * in this case a Comparator must be used.
 >  *</p><p>
 >  * All other references support {@link Comparable}, if the referent 
Object
 >  * doesn't implement {@link Comparable}, then {@link 
Reference#hashCode()} is used
 >  * for sorting. If two referent Objects have identical hashCodes,
 >  * but are unequal and do not implement {@link Comparable}, their 
references
 >  * will also have identical hashCodes, so only one of the referents can
 >  * be added to a {@link SortedSet} or {@link SortedMap}. This can be 
fixed by
 >  using a
 >  * {@link Comparator}.
 >  *</p><p>
 >  * For all intents and purposes these utilities behave the same as 
your preferred
 >  * underlying {@link Collection} implementation, with the exception of
 >  * {@link Reference} reachability. An Object or Key,Value entry is 
removed
 >  * from a {@link Collection} or {@link Map}, upon becoming eligible for
 >  * garbage collection.
 >  *</p><p>
 >  * Synchronisation must be implemented by your preferred {@link 
Collection}
 >  * and cannot be performed externally to the returned {@link Collection}.
 >  * Your chosen underlying {@link Collection} must also be mutable.
 >  * Objects will be removed automatically from underlying Collections when
 >  * they are eligible for garbage collection, this breaks external 
synchronisation.
 >  * {@link 
CollectionsConcurrent#multiReadCollection(java.util.Collection)} may
 >  * be useful for synchronising your chosen underlying {@link Collection},
 >  * especially if Objects are not being garbage collected often and writes
 >  * are minimal.
 >  *</p><p>
 >  * An Unmodifiable wrapper {@link
 >  Collections#unmodifiableCollection(java.util.Collection)}
 >  * may be used externally to prevent additions to the underlying 
Collections,
 >  * referents will still be removed as they become unreachable however.
 >  *</p><p>
 >  * Note that any Sub List, Sub Set or Sub Map obtained by any of the Java
 >  * Collections Framework interfaces, must be views of the underlying
 >  * Collection, if the Collection uses defensive copies instead of views,
 >  * References could potentially remain in one copy after garbage 
collection,
 >  * causing null returns. If using standard Java Collections Framework
 >  * implementations, these problems don't occur as all Sub Lists,
 >  * Sub Sets or Sub Maps are views only.
 >  *</p><p>
 >  * {@link Map#entrySet() } view instances returned preserve your 
chosen reference
 >  * behaviour, they even support {@link Set#add(java.lang.Object)} or
 >  * {@link Set#addAll(java.util.Collection)} methods, although you'll 
be hard
 >  * pressed to find a standard java implementation that does. If you 
have a
 >  * Map with a Set of Entry's implementing add, the implementation 
will need a
 >  * Comparator, that compares Entry's only by their keys, to avoid 
duplicating
 >  * keys, primarily because an Entry hashCode includes the both key 
and value in its
 >  * calculation. {@link Entry#hashCode() }
 >  *</p><p>
 >  * All other {@link Map#entrySet() } methods are fully implemented 
and supported.
 >  *</p><p>
 >  * {@link Entry} view instances returned by these methods preserve 
reference
 >  * behaviour, all methods are fully implemented and supported.
 >  *</p><p>
 >  * {@link Set} and it's sub interfaces {@link SortedSet} and
 >  * {@link NavigableSet}, return views that preserve reference behaviour,
 >  * all methods are fully implemented and supported.
 >  *</p><p>
 >  * {@link Map} and it's sub interfaces {@link SortedMap}, {@link 
NavigableMap},
 >  * {@link ConcurrentMap} and {@link ConcurrentNavigableMap} return
 >  * views that preserve reference behaviour, all methods are fully 
implemented
 >  * and supported.
 >  *</p><p>
 >  * {@link List} returns views that preserve reference behaviour, all 
methods are
 >  * fully implemented and supported.
 >  *</p><p>
 >  * {@link Queue} and it's sub interfaces {@link Deque}, {@link 
BlockingQueue} and
 >  * {@link BlockingDeque} return views that preserve reference behaviour,
 >  * all methods are fully implemented and supported.
 >  *</p><p>
 >  * {@link Iterator} and {@link ListIterator} views preserve reference 
behaviour,
 >  all methods
 >  * are fully implemented and supported.
 >  *</p><p>
 >  * RC stands for Reference Collection and is abbreviated due to the 
length of
 >  * generic parameter arguments typically required.
 >  *</p>
 >  * @see Ref
 >  * @see Reference
 >  * @author Peter Firmstone.
 >  */
 >  public class RC {
 >  private RC(){} // Non instantiable
 >
 >  /**
 >  * When using a Comparator in SortedSet's and SortedMap's, the Comparator
 >  * must be encapsulated using this method, to order the Set or Map
 >  * by referents and not References.
 >  *
 >  * @param<T>
 >  * @param comparator
 >  * @return
 >  */
 >  public static<T>  Comparator<Reference<T>>  comparator(Comparator<?

super T>
 >  comparator){
 >  return new ReferenceComparator<T>(comparator);
 >  }
 >
 >  /**
 >  * Wrap a Collection for holding references so it appears as a Collection
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  Collection<T>  
collection(Collection<Reference<T>>  internal,
 >  Ref type){
 >  return new ReferenceCollection<T>(internal, type);
 >  }
 >
 >  /**
 >  * Wrap a List for holding references so it appears as a List
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  List<T>  list(List<Reference<T>>  internal,
Ref type){
 >  return new ReferenceList<T>(internal, type);
 >  }
 >
 >  /**
 >  * Wrap a Set for holding references so it appears as a Set
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  Set<T>  set(Set<Reference<T>>  internal,
Ref type){
 >  return new ReferenceSet<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a SortedSet for holding references so it appears as a SortedSet
 >  * containing referents.
 >  *
 >  * @para m<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  SortedSet<T>  sortedSet(
 >  SortedSet<Reference<T>>  internal, Ref type){
 >  return new ReferenceSortedSet<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a NavigableSet for holding references so it appears as a 
NavigableSet
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  NavigableSet<T>  navigableSet(
 >  NavigableSet<Reference<T>>  internal, Ref type){
 >  return new ReferenceNavigableSet<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a Queue for holding references so it appears as a Queue
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  Queue<T>  queue(Queue<Reference<T>>  internal,
Ref 
type){
 >  return new ReferencedQueue<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a Deque for holding references so it appears as a Deque
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  Deque<T>  deque(Deque<Reference<T>>  internal,
Ref 
type){
 >  return new ReferenceDeque<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a BlockingQueue for holding references so it appears as a 
BlockingQueue
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  BlockingQueue<T>  blockingQueue(
 >  BlockingQueue<Reference<T>>  internal, Ref type){
 >  return new ReferenceBlockingQueue<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a BlockingDeque for holding references so it appears as a 
BlockingDeque
 >  * containing referents.
 >  *
 >  * @param<T>
 >  * @param internal
 >  * @param type
 >  * @return
 >  */
 >  public static<T>  BlockingDeque<T>  blockingDeque(
 >  BlockingDeque<Reference<T>>  internal, Ref type){
 >  return new ReferenceBlockingDeque<T>(internal, type);
 >  }
 >  /**
 >  * Wrap a Map for holding references so it appears as a Map
 >  * containing referents.
 >  *
 >  * @param<K>
 >  * @param<V>
 >  * @param internal
 >  * @param key
 >  * @param value
 >  * @return
 >  */
 >  public static<K, V>  Map<K, V>  map(
 >  Map<Reference<K>, Reference<V>>  internal, Ref key, Ref value){
 >  return new ReferenceMap<K, V>(internal, key, value);
 >  }
 >  /**
 >  * Wrap a SortedMap for holding references so it appears as a SortedMap
 >  * containing referents.
 >  *
 >  * @param<K>
 >  * @param<V>
 >  * @param internal
 >  * @param key
 >  * @param value
 >  * @return
 >  */
 >  public static<K, V>  SortedMap<K, V>  sortedMap(
 >  SortedMap<Reference<K>, Reference<V>>  internal, Ref key, Ref value){
 >  return new ReferenceSortedMap<K, V>(internal, key, value);
 >  }
 >  /**
 >  * Wrap a NavigableMap for holding references so it appears as a 
NavigableMap
 >  * containing referents.
 >  *
 >  * @param<K>
 >  * @param<V>
 >  * @param internal
 >  * @param key
 >  * @param value
 >  * @return
 >  */
 >  public static<K, V>  NavigableMap<K, V>  navigableMap(
 >  NavigableMap<Reference<K>, Reference<V>>  internal, Ref key, Ref
value){
 >  return new ReferenceNavigableMap<K, V>(internal, key, value);
 >  }
 >  /**
 >  * Wrap a ConcurrentMap for holding references so it appears as a 
ConcurrentMap
 >  * containing referents.
 >  *
 >  * @param<K>  - key type.
 >  * @param<V>  - value type.
 >  * @param internal - for holding references.
 >  * @param key - key reference type.
 >  * @param value - value reference type.
 >  * @return
 >  */
 >  public static<K, V>  ConcurrentMap<K, V>  concurrentMap(
 >  ConcurrentMap<Reference<K>, Reference<V>>  internal, Ref key, Ref

value){
 >  return new ReferenceConcurrentMap<K, V>(internal, key, value);
 >  }
 >
 >  /**
 >  * Wrap a ConcurrentNavigableMap for holding references so it appears 
as a
 >  * ConcurrentNavigableMap containing referents.
 >  *
 >  * @param<K>
 >  * @param<V>
 >  * @param internal
 >  * @param key
 >  * @param value
 >  * @return
 >  */
 >  public static<K, V>  ConcurrentNavigableMap<K, V>  
concurrentNavigableMap(
 >  ConcurrentNavigableMap<Reference<K>, Reference<V>>  internal, Ref

key, Ref value){
 >  return new ReferenceConcurrentNavigableMap<K, V>(internal, key, value);
 >  }
 >  }
 >
 >
 >
 >
 >


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message