commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From scolebou...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections CommonsLinkedList.java NodeCachingLinkedList.java
Date Tue, 07 Jan 2003 23:40:58 GMT
scolebourne    2003/01/07 15:40:58

  Modified:    collections/src/java/org/apache/commons/collections
                        CommonsLinkedList.java NodeCachingLinkedList.java
  Log:
  Add Apache licence
  
  Revision  Changes    Path
  1.2       +57 -2     jakarta-commons/collections/src/java/org/apache/commons/collections/CommonsLinkedList.java
  
  Index: CommonsLinkedList.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/CommonsLinkedList.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- CommonsLinkedList.java	7 Jan 2003 15:18:14 -0000	1.1
  +++ CommonsLinkedList.java	7 Jan 2003 23:40:55 -0000	1.2
  @@ -1,3 +1,56 @@
  +/* ====================================================================
  + * The Apache Software License, Version 1.1
  + *
  + * Copyright (c) 2003 The Apache Software Foundation.  All rights
  + * reserved.
  + *
  + * Redistribution and use in source and binary forms, with or without
  + * modification, are permitted provided that the following conditions
  + * are met:
  + *
  + * 1. Redistributions of source code must retain the above copyright
  + *    notice, this list of conditions and the following disclaimer.
  + *
  + * 2. Redistributions in binary form must reproduce the above copyright
  + *    notice, this list of conditions and the following disclaimer in
  + *    the documentation and/or other materials provided with the
  + *    distribution.
  + *
  + * 3. The end-user documentation included with the redistribution, if
  + *    any, must include the following acknowlegement:
  + *       "This product includes software developed by the
  + *        Apache Software Foundation (http://www.apache.org/)."
  + *    Alternately, this acknowlegement may appear in the software itself,
  + *    if and wherever such third-party acknowlegements normally appear.
  + *
  + * 4. The names "The Jakarta Project", "Commons", and "Apache Software
  + *    Foundation" must not be used to endorse or promote products derived
  + *    from this software without prior written permission. For written
  + *    permission, please contact apache@apache.org.
  + *
  + * 5. Products derived from this software may not be called "Apache"
  + *    nor may "Apache" appear in their names without prior written
  + *    permission of the Apache Software Foundation.
  + *
  + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  + * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  + * SUCH DAMAGE.
  + * ====================================================================
  + *
  + * This software consists of voluntary contributions made by many
  + * individuals on behalf of the Apache Software Foundation.  For more
  + * information on the Apache Software Foundation, please see
  + * <http://www.apache.org/>.
  + */
   package org.apache.commons.collections;
   
   import java.io.IOException;
  @@ -19,10 +72,12 @@
    * of {@link java.util.LinkedList}, but which provides a more open interface for
    * subclasses to extend.
    * 
  + * @since 2.2
    * @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
  + * @version $Revision$ $Date$
    */
   class CommonsLinkedList extends LinkedList
  -    implements List, Serializable {
  +        implements List, Serializable {
   
       /*
        * Implementation notes:
  @@ -232,7 +287,7 @@
       private static final long serialVersionUID = 1L;
   
       /**
  -     * A {@link Node} which ndicates the start and end of the list and does not
  +     * A {@link Node} which indicates the start and end of the list and does not
        * hold a value. The value of <code>next</code> is the first item in the
        * list. The value of of <code>previous</code> is the last item in the
list.
        */
  
  
  
  1.3       +243 -175  jakarta-commons/collections/src/java/org/apache/commons/collections/NodeCachingLinkedList.java
  
  Index: NodeCachingLinkedList.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/NodeCachingLinkedList.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- NodeCachingLinkedList.java	7 Jan 2003 15:18:14 -0000	1.2
  +++ NodeCachingLinkedList.java	7 Jan 2003 23:40:57 -0000	1.3
  @@ -1,175 +1,243 @@
  -package org.apache.commons.collections;
  -
  -import java.util.Collection;
  -
  -/**
  - * A linked list implementation that caches the nodes used internally to prevent
  - * unnecessary object creates and deletion. This should result in a performance
  - * improvement.
  - * 
  - * @author Jeff Varszegi
  - * @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
  - */
  -public class NodeCachingLinkedList extends CommonsLinkedList {
  -
  -    private static final long serialVersionUID = 1;
  -
  -    /**
  -     * The default value for {@link #maximumCacheSize}.
  -     */
  -    private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
  -
  -    /**
  -     * The first cached node, or <code>null</code> if no nodes are cached.
  -     * Cached nodes are stored in a singly-linked list with {@link Node#next}
  -     * pointing to the next element.
  -     */
  -    private transient Node firstCachedNode;
  -    
  -    /**
  -     * The size of the cache.
  -     */
  -    private transient int cacheSize = 0;
  -
  -    /**
  -     * The maximum size of the cache.
  -     */
  -    private int maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
  -
  -    public NodeCachingLinkedList() {
  -        super();
  -    }
  -
  -    public NodeCachingLinkedList(Collection c) {
  -        super(c);
  -    }
  -    
  -    public NodeCachingLinkedList(int maximumCacheSize) {
  -        super();
  -        this.maximumCacheSize = maximumCacheSize;
  -    }
  -
  -    // Cache operations
  -
  -    /**
  -     * Gets the maximum size of the cache.
  -     */
  -    public int getMaximumCacheSize() {
  -        return maximumCacheSize;
  -    }
  -
  -    /**
  -     * Sets the maximum size of the cache.
  -     */
  -    public void setMaximumCacheSize(int maximumCacheSize) {
  -        this.maximumCacheSize = maximumCacheSize;
  -        shrinkCacheToMaximumSize();
  -    }
  -
  -    /**
  -     * Reduce the size of the cache to the maximum, if necessary.
  -     */
  -    private void shrinkCacheToMaximumSize() {
  -        // Rich Dougherty: This could be more efficient.
  -        while (cacheSize > maximumCacheSize) {
  -            getNodeFromCache();
  -        }
  -    }
  -    
  -    /**
  -     * Gets a node from the cache. If a node is returned, then the value of
  -     * {@link #cacheSize} is decreased accordingly. The node that is returned
  -     * will have <code>null</code> values for next, previous and element.
  -     * 
  -     * @return A node, or <code>null</code> if there are no nodes in the cache.
  -     */
  -    private Node getNodeFromCache() {
  -        if (cacheSize == 0) {
  -            return null;
  -        }
  -        Node cachedNode = firstCachedNode;
  -        firstCachedNode = cachedNode.next;
  -        cachedNode.next = null; // This should be changed anyway, but defensively
  -                                             // set it to null.
  -        cacheSize--;
  -        return cachedNode;
  -    }
  -    
  -    private boolean cacheFull() {
  -        return cacheSize >= maximumCacheSize;
  -    }
  -    
  -    /**
  -     * Adds a node to the cache, if the cache isn't full. The node's contents
  -     * are cleared to so they can be garbage collected.
  -     */
  -    private void addNodeToCache(Node node) {
  -        if (cacheFull()) {
  -            // Don't cache the node.
  -            return;
  -        }
  -        // Clear the node's contents and add it to the cache.
  -        Node nextCachedNode = firstCachedNode;
  -        node.previous = null;
  -        node.next = nextCachedNode;
  -        node.element = null;
  -        firstCachedNode = node;
  -        cacheSize++;
  -    }
  -    
  -    // Node operations
  -
  -    /**
  -     * Create a node, getting it from the cache if possible.
  -     */
  -    protected Node createNode() {
  -        Node cachedNode = getNodeFromCache();
  -        if (cachedNode == null) {
  -            return super.createNode();
  -        } else {
  -            return cachedNode;
  -        }
  -    }
  -    
  -    /**
  -     * Create a node, getting it from the cache if possible.
  -     */
  -    protected Node createNode(Node next, Node previous, Object element) {
  -        Node cachedNode = getNodeFromCache();
  -        if (cachedNode == null) {
  -            return super.createNode(next, previous, element);
  -        } else {
  -            cachedNode.next = next;
  -            cachedNode.previous = previous;
  -            cachedNode.element = element;
  -            return cachedNode;
  -        }
  -    }
  -
  -    /**
  -     * Calls the superclass' implementation then calls
  -     * {@link #addNodeToCache(Node)} on the node which has been removed.
  -     * 
  -     * @see org.apache.commons.collections.CommonsLinkedList#removeNode(Node)
  -     */
  -    protected void removeNode(Node node) {
  -        super.removeNode(node);
  -        addNodeToCache(node);
  -    }
  -    
  -    protected void removeAllNodes() {
  -        // Add the removed nodes to the cache, then remove the rest.
  -        // We can add them to the cache before removing them, since
  -        // {@link CommonsLinkedList.removeAllNodes()} removes the
  -        // nodes by removing references directly from {@link #marker}.
  -        int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
  -        Node node = marker.next;
  -        for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++)
{
  -            Node oldNode = node;
  -            node = node.next;
  -            addNodeToCache(oldNode);
  -        }
  -        super.removeAllNodes();        
  -    }
  -
  -}
  +/* ====================================================================
  + * The Apache Software License, Version 1.1
  + *
  + * Copyright (c) 2002-2003 The Apache Software Foundation.  All rights
  + * reserved.
  + *
  + * Redistribution and use in source and binary forms, with or without
  + * modification, are permitted provided that the following conditions
  + * are met:
  + *
  + * 1. Redistributions of source code must retain the above copyright
  + *    notice, this list of conditions and the following disclaimer.
  + *
  + * 2. Redistributions in binary form must reproduce the above copyright
  + *    notice, this list of conditions and the following disclaimer in
  + *    the documentation and/or other materials provided with the
  + *    distribution.
  + *
  + * 3. The end-user documentation included with the redistribution, if
  + *    any, must include the following acknowlegement:
  + *       "This product includes software developed by the
  + *        Apache Software Foundation (http://www.apache.org/)."
  + *    Alternately, this acknowlegement may appear in the software itself,
  + *    if and wherever such third-party acknowlegements normally appear.
  + *
  + * 4. The names "The Jakarta Project", "Commons", and "Apache Software
  + *    Foundation" must not be used to endorse or promote products derived
  + *    from this software without prior written permission. For written
  + *    permission, please contact apache@apache.org.
  + *
  + * 5. Products derived from this software may not be called "Apache"
  + *    nor may "Apache" appear in their names without prior written
  + *    permission of the Apache Software Foundation.
  + *
  + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  + * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  + * SUCH DAMAGE.
  + * ====================================================================
  + *
  + * This software consists of voluntary contributions made by many
  + * individuals on behalf of the Apache Software Foundation.  For more
  + * information on the Apache Software Foundation, please see
  + * <http://www.apache.org/>.
  + */
  +package org.apache.commons.collections;
  +
  +import java.util.Collection;
  +
  +/**
  + * A linked list implementation that caches the nodes used internally to prevent
  + * unnecessary object creates and deletion. This should result in a performance
  + * improvement.
  + * 
  + * @since 2.2
  + * @author Jeff Varszegi
  + * @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
  + * @version $Revision$ $Date$
  + */
  +public class NodeCachingLinkedList extends CommonsLinkedList {
  +
  +    private static final long serialVersionUID = 1;
  +
  +    /**
  +     * The default value for {@link #maximumCacheSize}.
  +     */
  +    private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
  +
  +    /**
  +     * The first cached node, or <code>null</code> if no nodes are cached.
  +     * Cached nodes are stored in a singly-linked list with {@link Node#next}
  +     * pointing to the next element.
  +     */
  +    private transient Node firstCachedNode;
  +    
  +    /**
  +     * The size of the cache.
  +     */
  +    private transient int cacheSize = 0;
  +
  +    /**
  +     * The maximum size of the cache.
  +     */
  +    private int maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
  +
  +    /**
  +     * Constructor.
  +     */
  +    public NodeCachingLinkedList() {
  +        super();
  +    }
  +
  +    /**
  +     * Constructor that copies the specified collection
  +     * 
  +     * @param coll  the collection to copy
  +     */
  +    public NodeCachingLinkedList(Collection coll) {
  +        super(coll);
  +    }
  +    
  +    /**
  +     * Constructor that species the maximum cache size.
  +     * 
  +     * @param maximumCacheSize  the maximum cache size
  +     */
  +    public NodeCachingLinkedList(int maximumCacheSize) {
  +        super();
  +        this.maximumCacheSize = maximumCacheSize;
  +    }
  +
  +    // Cache operations
  +
  +    /**
  +     * Gets the maximum size of the cache.
  +     */
  +    public int getMaximumCacheSize() {
  +        return maximumCacheSize;
  +    }
  +
  +    /**
  +     * Sets the maximum size of the cache.
  +     */
  +    public void setMaximumCacheSize(int maximumCacheSize) {
  +        this.maximumCacheSize = maximumCacheSize;
  +        shrinkCacheToMaximumSize();
  +    }
  +
  +    /**
  +     * Reduce the size of the cache to the maximum, if necessary.
  +     */
  +    private void shrinkCacheToMaximumSize() {
  +        // Rich Dougherty: This could be more efficient.
  +        while (cacheSize > maximumCacheSize) {
  +            getNodeFromCache();
  +        }
  +    }
  +    
  +    /**
  +     * Gets a node from the cache. If a node is returned, then the value of
  +     * {@link #cacheSize} is decreased accordingly. The node that is returned
  +     * will have <code>null</code> values for next, previous and element.
  +     * 
  +     * @return A node, or <code>null</code> if there are no nodes in the cache.
  +     */
  +    private Node getNodeFromCache() {
  +        if (cacheSize == 0) {
  +            return null;
  +        }
  +        Node cachedNode = firstCachedNode;
  +        firstCachedNode = cachedNode.next;
  +        cachedNode.next = null; // This should be changed anyway, but defensively
  +                                             // set it to null.
  +        cacheSize--;
  +        return cachedNode;
  +    }
  +    
  +    private boolean cacheFull() {
  +        return cacheSize >= maximumCacheSize;
  +    }
  +    
  +    /**
  +     * Adds a node to the cache, if the cache isn't full. The node's contents
  +     * are cleared to so they can be garbage collected.
  +     */
  +    private void addNodeToCache(Node node) {
  +        if (cacheFull()) {
  +            // Don't cache the node.
  +            return;
  +        }
  +        // Clear the node's contents and add it to the cache.
  +        Node nextCachedNode = firstCachedNode;
  +        node.previous = null;
  +        node.next = nextCachedNode;
  +        node.element = null;
  +        firstCachedNode = node;
  +        cacheSize++;
  +    }
  +    
  +    // Node operations
  +
  +    /**
  +     * Create a node, getting it from the cache if possible.
  +     */
  +    protected Node createNode() {
  +        Node cachedNode = getNodeFromCache();
  +        if (cachedNode == null) {
  +            return super.createNode();
  +        } else {
  +            return cachedNode;
  +        }
  +    }
  +    
  +    /**
  +     * Create a node, getting it from the cache if possible.
  +     */
  +    protected Node createNode(Node next, Node previous, Object element) {
  +        Node cachedNode = getNodeFromCache();
  +        if (cachedNode == null) {
  +            return super.createNode(next, previous, element);
  +        } else {
  +            cachedNode.next = next;
  +            cachedNode.previous = previous;
  +            cachedNode.element = element;
  +            return cachedNode;
  +        }
  +    }
  +
  +    /**
  +     * Calls the superclass' implementation then calls
  +     * {@link #addNodeToCache(Node)} on the node which has been removed.
  +     * 
  +     * @see org.apache.commons.collections.CommonsLinkedList#removeNode(Node)
  +     */
  +    protected void removeNode(Node node) {
  +        super.removeNode(node);
  +        addNodeToCache(node);
  +    }
  +    
  +    protected void removeAllNodes() {
  +        // Add the removed nodes to the cache, then remove the rest.
  +        // We can add them to the cache before removing them, since
  +        // {@link CommonsLinkedList.removeAllNodes()} removes the
  +        // nodes by removing references directly from {@link #marker}.
  +        int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
  +        Node node = marker.next;
  +        for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++)
{
  +            Node oldNode = node;
  +            node = node.next;
  +            addNodeToCache(oldNode);
  +        }
  +        super.removeAllNodes();        
  +    }
  +
  +}
  
  
  

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


Mime
View raw message