You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@myfaces.apache.org by lu...@apache.org on 2013/10/25 23:24:10 UTC
svn commit: r1535874 [6/9] - in /myfaces/shared/trunk/core/src:
main/java/org/apache/myfaces/shared/application/
main/java/org/apache/myfaces/shared/config/
main/java/org/apache/myfaces/shared/context/flash/
main/java/org/apache/myfaces/shared/renderki...
Modified: myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java
URL: http://svn.apache.org/viewvc/myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java?rev=1535874&r1=1535873&r2=1535874&view=diff
==============================================================================
--- myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java (original)
+++ myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/ConcurrentLRUCache.java Fri Oct 25 21:24:09 2013
@@ -1,829 +1,829 @@
-/*
- * 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.myfaces.shared.util;
-
-import java.lang.ref.WeakReference;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.LinkedHashMap;
-import java.util.Map;
-import java.util.TreeSet;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.atomic.AtomicInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.concurrent.locks.ReentrantLock;
-
-/**
- * A LRU cache implementation based upon ConcurrentHashMap and other techniques to reduce
- * contention and synchronization overhead to utilize multiple CPU cores more effectively.
- * <p/>
- * Note that the implementation does not follow a true LRU (least-recently-used) eviction
- * strategy. Instead it strives to remove least recently used items but when the initial
- * cleanup does not remove enough items to reach the 'acceptableWaterMark' limit, it can
- * remove more items forcefully regardless of access order.
- *
- *
- * @since solr 1.4
- * @see org.apache.solr.util.ConcurrentLRUCache
- */
-public class ConcurrentLRUCache<K, V>
-{
- //private static Logger log = Logger.getLogger(ConcurrentLRUCache.class
- // .getName());
-
- private final ConcurrentHashMap<Object, CacheEntry<K, V>> map;
- private final int upperWaterMark;
- private final int lowerWaterMark;
- private final ReentrantLock markAndSweepLock = new ReentrantLock(true);
- private boolean isCleaning = false; // not volatile... piggybacked on other volatile vars
- private final boolean newThreadForCleanup;
- private volatile boolean islive = true;
- private final Stats stats = new Stats();
- private final int acceptableWaterMark;
- private long oldestEntry = 0; // not volatile, only accessed in the cleaning method
- private final EvictionListener<K, V> evictionListener;
- private CleanupThread cleanupThread;
-
- public ConcurrentLRUCache(int upperWaterMark, final int lowerWaterMark,
- int acceptableWatermark, int initialSize, boolean runCleanupThread,
- boolean runNewThreadForCleanup,
- EvictionListener<K, V> evictionListener)
- {
- if (upperWaterMark < 1)
- {
- throw new IllegalArgumentException("upperWaterMark must be > 0");
- }
- if (lowerWaterMark >= upperWaterMark)
- {
- throw new IllegalArgumentException(
- "lowerWaterMark must be < upperWaterMark");
- }
- map = new ConcurrentHashMap<Object, CacheEntry<K, V>>(initialSize);
- newThreadForCleanup = runNewThreadForCleanup;
- this.upperWaterMark = upperWaterMark;
- this.lowerWaterMark = lowerWaterMark;
- this.acceptableWaterMark = acceptableWatermark;
- this.evictionListener = evictionListener;
- if (runCleanupThread)
- {
- cleanupThread = new CleanupThread(this);
- cleanupThread.start();
- }
- }
-
- public ConcurrentLRUCache(int size, int lowerWatermark)
- {
- this(size, lowerWatermark, (int) Math
- .floor((lowerWatermark + size) / 2), (int) Math
- .ceil(0.75 * size), false, false, null);
- }
-
- public void setAlive(boolean live)
- {
- islive = live;
- }
-
- public V get(K key)
- {
- CacheEntry<K, V> e = map.get(key);
- if (e == null)
- {
- if (islive)
- {
- stats.missCounter.incrementAndGet();
- }
- return null;
- }
- if (islive)
- {
- e.lastAccessed = stats.accessCounter.incrementAndGet();
- }
- return e.value;
- }
-
- public V remove(K key)
- {
- CacheEntry<K, V> cacheEntry = map.remove(key);
- if (cacheEntry != null)
- {
- stats.size.decrementAndGet();
- return cacheEntry.value;
- }
- return null;
- }
-
- public V put(K key, V val)
- {
- if (val == null)
- {
- return null;
- }
- CacheEntry<K, V> e = new CacheEntry<K, V>(key, val,
- stats.accessCounter.incrementAndGet());
- CacheEntry<K, V> oldCacheEntry = map.put(key, e);
- int currentSize;
- if (oldCacheEntry == null)
- {
- currentSize = stats.size.incrementAndGet();
- }
- else
- {
- currentSize = stats.size.get();
- }
- if (islive)
- {
- stats.putCounter.incrementAndGet();
- }
- else
- {
- stats.nonLivePutCounter.incrementAndGet();
- }
-
- // Check if we need to clear out old entries from the cache.
- // isCleaning variable is checked instead of markAndSweepLock.isLocked()
- // for performance because every put invokation will check until
- // the size is back to an acceptable level.
- //
- // There is a race between the check and the call to markAndSweep, but
- // it's unimportant because markAndSweep actually aquires the lock or returns if it can't.
- //
- // Thread safety note: isCleaning read is piggybacked (comes after) other volatile reads
- // in this method.
- if (currentSize > upperWaterMark && !isCleaning)
- {
- if (newThreadForCleanup)
- {
- new Thread()
- {
- @Override
- public void run()
- {
- markAndSweep();
- }
- }.start();
- }
- else if (cleanupThread != null)
- {
- cleanupThread.wakeThread();
- }
- else
- {
- markAndSweep();
- }
- }
- return oldCacheEntry == null ? null : oldCacheEntry.value;
- }
-
- /**
- * Removes items from the cache to bring the size down
- * to an acceptable value ('acceptableWaterMark').
- * <p/>
- * It is done in two stages. In the first stage, least recently used items are evicted.
- * If, after the first stage, the cache size is still greater than 'acceptableSize'
- * config parameter, the second stage takes over.
- * <p/>
- * The second stage is more intensive and tries to bring down the cache size
- * to the 'lowerWaterMark' config parameter.
- */
- private void markAndSweep()
- {
- // if we want to keep at least 1000 entries, then timestamps of
- // current through current-1000 are guaranteed not to be the oldest (but that does
- // not mean there are 1000 entries in that group... it's acutally anywhere between
- // 1 and 1000).
- // Also, if we want to remove 500 entries, then
- // oldestEntry through oldestEntry+500 are guaranteed to be
- // removed (however many there are there).
-
- if (!markAndSweepLock.tryLock())
- {
- return;
- }
- try
- {
- long oldestEntry = this.oldestEntry;
- isCleaning = true;
- this.oldestEntry = oldestEntry; // volatile write to make isCleaning visible
-
- long timeCurrent = stats.accessCounter.get();
- int sz = stats.size.get();
-
- int numRemoved = 0;
- int numKept = 0;
- long newestEntry = timeCurrent;
- long newNewestEntry = -1;
- long newOldestEntry = Long.MAX_VALUE;
-
- int wantToKeep = lowerWaterMark;
- int wantToRemove = sz - lowerWaterMark;
-
- @SuppressWarnings("unchecked")
- // generic array's are anoying
- CacheEntry<K, V>[] eset = new CacheEntry[sz];
- int eSize = 0;
-
- // System.out.println("newestEntry="+newestEntry + " oldestEntry="+oldestEntry);
- // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
- // " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
-
- for (CacheEntry<K, V> ce : map.values())
- {
- // set lastAccessedCopy to avoid more volatile reads
- ce.lastAccessedCopy = ce.lastAccessed;
- long thisEntry = ce.lastAccessedCopy;
-
- // since the wantToKeep group is likely to be bigger than wantToRemove, check it first
- if (thisEntry > newestEntry - wantToKeep)
- {
- // this entry is guaranteed not to be in the bottom
- // group, so do nothing.
- numKept++;
- newOldestEntry = Math.min(thisEntry, newOldestEntry);
- }
- else if (thisEntry < oldestEntry + wantToRemove)
- { // entry in bottom group?
- // this entry is guaranteed to be in the bottom group
- // so immediately remove it from the map.
- evictEntry(ce.key);
- numRemoved++;
- }
- else
- {
- // This entry *could* be in the bottom group.
- // Collect these entries to avoid another full pass... this is wasted
- // effort if enough entries are normally removed in this first pass.
- // An alternate impl could make a full second pass.
- if (eSize < eset.length - 1)
- {
- eset[eSize++] = ce;
- newNewestEntry = Math.max(thisEntry, newNewestEntry);
- newOldestEntry = Math.min(thisEntry, newOldestEntry);
- }
- }
- }
-
- // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
- // " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
- // TODO: allow this to be customized in the constructor?
- int numPasses = 1; // maximum number of linear passes over the data
-
- // if we didn't remove enough entries, then make more passes
- // over the values we collected, with updated min and max values.
- while (sz - numRemoved > acceptableWaterMark && --numPasses >= 0)
- {
-
- oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
- : newOldestEntry;
- newOldestEntry = Long.MAX_VALUE;
- newestEntry = newNewestEntry;
- newNewestEntry = -1;
- wantToKeep = lowerWaterMark - numKept;
- wantToRemove = sz - lowerWaterMark - numRemoved;
-
- // iterate backward to make it easy to remove items.
- for (int i = eSize - 1; i >= 0; i--)
- {
- CacheEntry<K, V> ce = eset[i];
- long thisEntry = ce.lastAccessedCopy;
-
- if (thisEntry > newestEntry - wantToKeep)
- {
- // this entry is guaranteed not to be in the bottom
- // group, so do nothing but remove it from the eset.
- numKept++;
- // remove the entry by moving the last element to it's position
- eset[i] = eset[eSize - 1];
- eSize--;
-
- newOldestEntry = Math.min(thisEntry, newOldestEntry);
-
- }
- else if (thisEntry < oldestEntry + wantToRemove)
- { // entry in bottom group?
-
- // this entry is guaranteed to be in the bottom group
- // so immediately remove it from the map.
- evictEntry(ce.key);
- numRemoved++;
-
- // remove the entry by moving the last element to it's position
- eset[i] = eset[eSize - 1];
- eSize--;
- }
- else
- {
- // This entry *could* be in the bottom group, so keep it in the eset,
- // and update the stats.
- newNewestEntry = Math.max(thisEntry, newNewestEntry);
- newOldestEntry = Math.min(thisEntry, newOldestEntry);
- }
- }
- // System.out.println("items removed:" + numRemoved + " numKept=" +
- // numKept + " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
- }
-
- // if we still didn't remove enough entries, then make another pass while
- // inserting into a priority queue
- if (sz - numRemoved > acceptableWaterMark)
- {
-
- oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
- : newOldestEntry;
- newOldestEntry = Long.MAX_VALUE;
- newestEntry = newNewestEntry;
- newNewestEntry = -1;
- wantToKeep = lowerWaterMark - numKept;
- wantToRemove = sz - lowerWaterMark - numRemoved;
-
- PQueue<K, V> queue = new PQueue<K, V>(wantToRemove);
-
- for (int i = eSize - 1; i >= 0; i--)
- {
- CacheEntry<K, V> ce = eset[i];
- long thisEntry = ce.lastAccessedCopy;
-
- if (thisEntry > newestEntry - wantToKeep)
- {
- // this entry is guaranteed not to be in the bottom
- // group, so do nothing but remove it from the eset.
- numKept++;
- // removal not necessary on last pass.
- // eset[i] = eset[eSize-1];
- // eSize--;
-
- newOldestEntry = Math.min(thisEntry, newOldestEntry);
-
- }
- else if (thisEntry < oldestEntry + wantToRemove)
- { // entry in bottom group?
- // this entry is guaranteed to be in the bottom group
- // so immediately remove it.
- evictEntry(ce.key);
- numRemoved++;
-
- // removal not necessary on last pass.
- // eset[i] = eset[eSize-1];
- // eSize--;
- }
- else
- {
- // This entry *could* be in the bottom group.
- // add it to the priority queue
-
- // everything in the priority queue will be removed, so keep track of
- // the lowest value that ever comes back out of the queue.
-
- // first reduce the size of the priority queue to account for
- // the number of items we have already removed while executing
- // this loop so far.
- queue.myMaxSize = sz - lowerWaterMark - numRemoved;
- while (queue.size() > queue.myMaxSize
- && queue.size() > 0)
- {
- CacheEntry otherEntry = (CacheEntry) queue.pop();
- newOldestEntry = Math
- .min(otherEntry.lastAccessedCopy,
- newOldestEntry);
- }
- if (queue.myMaxSize <= 0)
- {
- break;
- }
-
- Object o = queue.myInsertWithOverflow(ce);
- if (o != null)
- {
- newOldestEntry = Math.min(
- ((CacheEntry) o).lastAccessedCopy,
- newOldestEntry);
- }
- }
- }
-
- // Now delete everything in the priority queue.
- // avoid using pop() since order doesn't matter anymore
- for (CacheEntry<K, V> ce : queue.getValues())
- {
- if (ce == null)
- {
- continue;
- }
- evictEntry(ce.key);
- numRemoved++;
- }
-
- // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
- // " initialQueueSize="+ wantToRemove + " finalQueueSize=" +
- // queue.size() + " sz-numRemoved=" + (sz-numRemoved));
- }
-
- oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
- : newOldestEntry;
- this.oldestEntry = oldestEntry;
- }
- finally
- {
- isCleaning = false; // set before markAndSweep.unlock() for visibility
- markAndSweepLock.unlock();
- }
- }
-
- private static class PQueue<K, V> extends PriorityQueue<CacheEntry<K, V>>
- {
- int myMaxSize;
- final Object[] heap;
-
- PQueue(int maxSz)
- {
- super(maxSz);
- heap = getHeapArray();
- myMaxSize = maxSz;
- }
-
- @SuppressWarnings("unchecked")
- Iterable<CacheEntry<K, V>> getValues()
- {
- return (Iterable) Collections.unmodifiableCollection(Arrays
- .asList(heap));
- }
-
- @Override
- protected boolean lessThan(CacheEntry a, CacheEntry b)
- {
- // reverse the parameter order so that the queue keeps the oldest items
- return b.lastAccessedCopy < a.lastAccessedCopy;
- }
-
- // necessary because maxSize is private in base class
- @SuppressWarnings("unchecked")
- public CacheEntry<K, V> myInsertWithOverflow(CacheEntry<K, V> element)
- {
- if (size() < myMaxSize)
- {
- add(element);
- return null;
- }
- else if (size() > 0
- && !lessThan(element, (CacheEntry<K, V>) heap[1]))
- {
- CacheEntry<K, V> ret = (CacheEntry<K, V>) heap[1];
- heap[1] = element;
- updateTop();
- return ret;
- }
- else
- {
- return element;
- }
- }
- }
-
- private void evictEntry(K key)
- {
- CacheEntry<K, V> o = map.remove(key);
- if (o == null)
- {
- return;
- }
- stats.size.decrementAndGet();
- stats.evictionCounter.incrementAndGet();
- if (evictionListener != null)
- {
- evictionListener.evictedEntry(o.key, o.value);
- }
- }
-
- /**
- * Returns 'n' number of oldest accessed entries present in this cache.
- *
- * This uses a TreeSet to collect the 'n' oldest items ordered by ascending last access time
- * and returns a LinkedHashMap containing 'n' or less than 'n' entries.
- * @param n the number of oldest items needed
- * @return a LinkedHashMap containing 'n' or less than 'n' entries
- */
- public Map<K, V> getOldestAccessedItems(int n)
- {
- Map<K, V> result = new LinkedHashMap<K, V>();
- if (n <= 0)
- {
- return result;
- }
- TreeSet<CacheEntry<K, V>> tree = new TreeSet<CacheEntry<K, V>>();
- markAndSweepLock.lock();
- try
- {
- for (Map.Entry<Object, CacheEntry<K, V>> entry : map.entrySet())
- {
- CacheEntry<K, V> ce = entry.getValue();
- ce.lastAccessedCopy = ce.lastAccessed;
- if (tree.size() < n)
- {
- tree.add(ce);
- }
- else
- {
- if (ce.lastAccessedCopy < tree.first().lastAccessedCopy)
- {
- tree.remove(tree.first());
- tree.add(ce);
- }
- }
- }
- }
- finally
- {
- markAndSweepLock.unlock();
- }
- for (CacheEntry<K, V> e : tree)
- {
- result.put(e.key, e.value);
- }
- return result;
- }
-
- public Map<K, V> getLatestAccessedItems(int n)
- {
- Map<K, V> result = new LinkedHashMap<K, V>();
- if (n <= 0)
- {
- return result;
- }
- TreeSet<CacheEntry<K, V>> tree = new TreeSet<CacheEntry<K, V>>();
- // we need to grab the lock since we are changing lastAccessedCopy
- markAndSweepLock.lock();
- try
- {
- for (Map.Entry<Object, CacheEntry<K, V>> entry : map.entrySet())
- {
- CacheEntry<K, V> ce = entry.getValue();
- ce.lastAccessedCopy = ce.lastAccessed;
- if (tree.size() < n)
- {
- tree.add(ce);
- }
- else
- {
- if (ce.lastAccessedCopy > tree.last().lastAccessedCopy)
- {
- tree.remove(tree.last());
- tree.add(ce);
- }
- }
- }
- }
- finally
- {
- markAndSweepLock.unlock();
- }
- for (CacheEntry<K, V> e : tree)
- {
- result.put(e.key, e.value);
- }
- return result;
- }
-
- public int size()
- {
- return stats.size.get();
- }
-
- public void clear()
- {
- map.clear();
- }
-
- public Map<Object, CacheEntry<K, V>> getMap()
- {
- return map;
- }
-
- private static class CacheEntry<K, V> implements
- Comparable<CacheEntry<K, V>>
- {
- K key;
- V value;
- volatile long lastAccessed = 0;
- long lastAccessedCopy = 0;
-
- public CacheEntry(K key, V value, long lastAccessed)
- {
- this.key = key;
- this.value = value;
- this.lastAccessed = lastAccessed;
- }
-
- public void setLastAccessed(long lastAccessed)
- {
- this.lastAccessed = lastAccessed;
- }
-
- public int compareTo(CacheEntry<K, V> that)
- {
- if (this.lastAccessedCopy == that.lastAccessedCopy)
- {
- return 0;
- }
- return this.lastAccessedCopy < that.lastAccessedCopy ? 1 : -1;
- }
-
- @Override
- public int hashCode()
- {
- return value.hashCode();
- }
-
- @Override
- public boolean equals(Object obj)
- {
- return value.equals(obj);
- }
-
- @Override
- public String toString()
- {
- return "key: " + key + " value: " + value + " lastAccessed:"
- + lastAccessed;
- }
- }
-
- private boolean isDestroyed = false;
-
- public void destroy()
- {
- try
- {
- if (cleanupThread != null)
- {
- cleanupThread.stopThread();
- }
- }
- finally
- {
- isDestroyed = true;
- }
- }
-
- public Stats getStats()
- {
- return stats;
- }
-
- public static class Stats
- {
- private final AtomicLong accessCounter = new AtomicLong(0);
- private final AtomicLong putCounter = new AtomicLong(0);
- private final AtomicLong nonLivePutCounter = new AtomicLong(0);
- private final AtomicLong missCounter = new AtomicLong();
- private final AtomicInteger size = new AtomicInteger();
- private AtomicLong evictionCounter = new AtomicLong();
-
- public long getCumulativeLookups()
- {
- return (accessCounter.get() - putCounter.get() - nonLivePutCounter
- .get()) + missCounter.get();
- }
-
- public long getCumulativeHits()
- {
- return accessCounter.get() - putCounter.get()
- - nonLivePutCounter.get();
- }
-
- public long getCumulativePuts()
- {
- return putCounter.get();
- }
-
- public long getCumulativeEvictions()
- {
- return evictionCounter.get();
- }
-
- public int getCurrentSize()
- {
- return size.get();
- }
-
- public long getCumulativeNonLivePuts()
- {
- return nonLivePutCounter.get();
- }
-
- public long getCumulativeMisses()
- {
- return missCounter.get();
- }
-
- public void add(Stats other)
- {
- accessCounter.addAndGet(other.accessCounter.get());
- putCounter.addAndGet(other.putCounter.get());
- nonLivePutCounter.addAndGet(other.nonLivePutCounter.get());
- missCounter.addAndGet(other.missCounter.get());
- evictionCounter.addAndGet(other.evictionCounter.get());
- size.set(Math.max(size.get(), other.size.get()));
- }
- }
-
- public static interface EvictionListener<K, V>
- {
- public void evictedEntry(K key, V value);
- }
-
- private static class CleanupThread extends Thread
- {
- private WeakReference<ConcurrentLRUCache> cache;
-
- private boolean stop = false;
-
- public CleanupThread(ConcurrentLRUCache c)
- {
- cache = new WeakReference<ConcurrentLRUCache>(c);
- }
-
- @Override
- public void run()
- {
- while (true)
- {
- synchronized (this)
- {
- if (stop)
- {
- break;
- }
- try
- {
- this.wait();
- }
- catch (InterruptedException e)
- {
- }
- }
- if (stop)
- {
- break;
- }
- ConcurrentLRUCache c = cache.get();
- if (c == null)
- {
- break;
- }
- c.markAndSweep();
- }
- }
-
- void wakeThread()
- {
- synchronized (this)
- {
- this.notify();
- }
- }
-
- void stopThread()
- {
- synchronized (this)
- {
- stop = true;
- this.notify();
- }
- }
- }
-
- @Override
- protected void finalize() throws Throwable
- {
- try
- {
- if (!isDestroyed)
- {
- // This log message is useless, because it is not supposed to use
- // thread cleanup strategy for this class.
- //log.severe("ConcurrentLRUCache was not destroyed prior to finalize()," +
- // " indicates a bug -- POSSIBLE RESOURCE LEAK!!!");
- destroy();
- }
- }
- finally
- {
- super.finalize();
- }
- }
-}
+/*
+ * 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.myfaces.shared.util;
+
+import java.lang.ref.WeakReference;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.TreeSet;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.locks.ReentrantLock;
+
+/**
+ * A LRU cache implementation based upon ConcurrentHashMap and other techniques to reduce
+ * contention and synchronization overhead to utilize multiple CPU cores more effectively.
+ * <p/>
+ * Note that the implementation does not follow a true LRU (least-recently-used) eviction
+ * strategy. Instead it strives to remove least recently used items but when the initial
+ * cleanup does not remove enough items to reach the 'acceptableWaterMark' limit, it can
+ * remove more items forcefully regardless of access order.
+ *
+ *
+ * @since solr 1.4
+ * @see org.apache.solr.util.ConcurrentLRUCache
+ */
+public class ConcurrentLRUCache<K, V>
+{
+ //private static Logger log = Logger.getLogger(ConcurrentLRUCache.class
+ // .getName());
+
+ private final ConcurrentHashMap<Object, CacheEntry<K, V>> map;
+ private final int upperWaterMark;
+ private final int lowerWaterMark;
+ private final ReentrantLock markAndSweepLock = new ReentrantLock(true);
+ private boolean isCleaning = false; // not volatile... piggybacked on other volatile vars
+ private final boolean newThreadForCleanup;
+ private volatile boolean islive = true;
+ private final Stats stats = new Stats();
+ private final int acceptableWaterMark;
+ private long oldestEntry = 0; // not volatile, only accessed in the cleaning method
+ private final EvictionListener<K, V> evictionListener;
+ private CleanupThread cleanupThread;
+
+ public ConcurrentLRUCache(int upperWaterMark, final int lowerWaterMark,
+ int acceptableWatermark, int initialSize, boolean runCleanupThread,
+ boolean runNewThreadForCleanup,
+ EvictionListener<K, V> evictionListener)
+ {
+ if (upperWaterMark < 1)
+ {
+ throw new IllegalArgumentException("upperWaterMark must be > 0");
+ }
+ if (lowerWaterMark >= upperWaterMark)
+ {
+ throw new IllegalArgumentException(
+ "lowerWaterMark must be < upperWaterMark");
+ }
+ map = new ConcurrentHashMap<Object, CacheEntry<K, V>>(initialSize);
+ newThreadForCleanup = runNewThreadForCleanup;
+ this.upperWaterMark = upperWaterMark;
+ this.lowerWaterMark = lowerWaterMark;
+ this.acceptableWaterMark = acceptableWatermark;
+ this.evictionListener = evictionListener;
+ if (runCleanupThread)
+ {
+ cleanupThread = new CleanupThread(this);
+ cleanupThread.start();
+ }
+ }
+
+ public ConcurrentLRUCache(int size, int lowerWatermark)
+ {
+ this(size, lowerWatermark, (int) Math
+ .floor((lowerWatermark + size) / 2), (int) Math
+ .ceil(0.75 * size), false, false, null);
+ }
+
+ public void setAlive(boolean live)
+ {
+ islive = live;
+ }
+
+ public V get(K key)
+ {
+ CacheEntry<K, V> e = map.get(key);
+ if (e == null)
+ {
+ if (islive)
+ {
+ stats.missCounter.incrementAndGet();
+ }
+ return null;
+ }
+ if (islive)
+ {
+ e.lastAccessed = stats.accessCounter.incrementAndGet();
+ }
+ return e.value;
+ }
+
+ public V remove(K key)
+ {
+ CacheEntry<K, V> cacheEntry = map.remove(key);
+ if (cacheEntry != null)
+ {
+ stats.size.decrementAndGet();
+ return cacheEntry.value;
+ }
+ return null;
+ }
+
+ public V put(K key, V val)
+ {
+ if (val == null)
+ {
+ return null;
+ }
+ CacheEntry<K, V> e = new CacheEntry<K, V>(key, val,
+ stats.accessCounter.incrementAndGet());
+ CacheEntry<K, V> oldCacheEntry = map.put(key, e);
+ int currentSize;
+ if (oldCacheEntry == null)
+ {
+ currentSize = stats.size.incrementAndGet();
+ }
+ else
+ {
+ currentSize = stats.size.get();
+ }
+ if (islive)
+ {
+ stats.putCounter.incrementAndGet();
+ }
+ else
+ {
+ stats.nonLivePutCounter.incrementAndGet();
+ }
+
+ // Check if we need to clear out old entries from the cache.
+ // isCleaning variable is checked instead of markAndSweepLock.isLocked()
+ // for performance because every put invokation will check until
+ // the size is back to an acceptable level.
+ //
+ // There is a race between the check and the call to markAndSweep, but
+ // it's unimportant because markAndSweep actually aquires the lock or returns if it can't.
+ //
+ // Thread safety note: isCleaning read is piggybacked (comes after) other volatile reads
+ // in this method.
+ if (currentSize > upperWaterMark && !isCleaning)
+ {
+ if (newThreadForCleanup)
+ {
+ new Thread()
+ {
+ @Override
+ public void run()
+ {
+ markAndSweep();
+ }
+ }.start();
+ }
+ else if (cleanupThread != null)
+ {
+ cleanupThread.wakeThread();
+ }
+ else
+ {
+ markAndSweep();
+ }
+ }
+ return oldCacheEntry == null ? null : oldCacheEntry.value;
+ }
+
+ /**
+ * Removes items from the cache to bring the size down
+ * to an acceptable value ('acceptableWaterMark').
+ * <p/>
+ * It is done in two stages. In the first stage, least recently used items are evicted.
+ * If, after the first stage, the cache size is still greater than 'acceptableSize'
+ * config parameter, the second stage takes over.
+ * <p/>
+ * The second stage is more intensive and tries to bring down the cache size
+ * to the 'lowerWaterMark' config parameter.
+ */
+ private void markAndSweep()
+ {
+ // if we want to keep at least 1000 entries, then timestamps of
+ // current through current-1000 are guaranteed not to be the oldest (but that does
+ // not mean there are 1000 entries in that group... it's acutally anywhere between
+ // 1 and 1000).
+ // Also, if we want to remove 500 entries, then
+ // oldestEntry through oldestEntry+500 are guaranteed to be
+ // removed (however many there are there).
+
+ if (!markAndSweepLock.tryLock())
+ {
+ return;
+ }
+ try
+ {
+ long oldestEntry = this.oldestEntry;
+ isCleaning = true;
+ this.oldestEntry = oldestEntry; // volatile write to make isCleaning visible
+
+ long timeCurrent = stats.accessCounter.get();
+ int sz = stats.size.get();
+
+ int numRemoved = 0;
+ int numKept = 0;
+ long newestEntry = timeCurrent;
+ long newNewestEntry = -1;
+ long newOldestEntry = Long.MAX_VALUE;
+
+ int wantToKeep = lowerWaterMark;
+ int wantToRemove = sz - lowerWaterMark;
+
+ @SuppressWarnings("unchecked")
+ // generic array's are anoying
+ CacheEntry<K, V>[] eset = new CacheEntry[sz];
+ int eSize = 0;
+
+ // System.out.println("newestEntry="+newestEntry + " oldestEntry="+oldestEntry);
+ // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
+ // " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
+
+ for (CacheEntry<K, V> ce : map.values())
+ {
+ // set lastAccessedCopy to avoid more volatile reads
+ ce.lastAccessedCopy = ce.lastAccessed;
+ long thisEntry = ce.lastAccessedCopy;
+
+ // since the wantToKeep group is likely to be bigger than wantToRemove, check it first
+ if (thisEntry > newestEntry - wantToKeep)
+ {
+ // this entry is guaranteed not to be in the bottom
+ // group, so do nothing.
+ numKept++;
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+ }
+ else if (thisEntry < oldestEntry + wantToRemove)
+ { // entry in bottom group?
+ // this entry is guaranteed to be in the bottom group
+ // so immediately remove it from the map.
+ evictEntry(ce.key);
+ numRemoved++;
+ }
+ else
+ {
+ // This entry *could* be in the bottom group.
+ // Collect these entries to avoid another full pass... this is wasted
+ // effort if enough entries are normally removed in this first pass.
+ // An alternate impl could make a full second pass.
+ if (eSize < eset.length - 1)
+ {
+ eset[eSize++] = ce;
+ newNewestEntry = Math.max(thisEntry, newNewestEntry);
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+ }
+ }
+ }
+
+ // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
+ // " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
+ // TODO: allow this to be customized in the constructor?
+ int numPasses = 1; // maximum number of linear passes over the data
+
+ // if we didn't remove enough entries, then make more passes
+ // over the values we collected, with updated min and max values.
+ while (sz - numRemoved > acceptableWaterMark && --numPasses >= 0)
+ {
+
+ oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
+ : newOldestEntry;
+ newOldestEntry = Long.MAX_VALUE;
+ newestEntry = newNewestEntry;
+ newNewestEntry = -1;
+ wantToKeep = lowerWaterMark - numKept;
+ wantToRemove = sz - lowerWaterMark - numRemoved;
+
+ // iterate backward to make it easy to remove items.
+ for (int i = eSize - 1; i >= 0; i--)
+ {
+ CacheEntry<K, V> ce = eset[i];
+ long thisEntry = ce.lastAccessedCopy;
+
+ if (thisEntry > newestEntry - wantToKeep)
+ {
+ // this entry is guaranteed not to be in the bottom
+ // group, so do nothing but remove it from the eset.
+ numKept++;
+ // remove the entry by moving the last element to it's position
+ eset[i] = eset[eSize - 1];
+ eSize--;
+
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+
+ }
+ else if (thisEntry < oldestEntry + wantToRemove)
+ { // entry in bottom group?
+
+ // this entry is guaranteed to be in the bottom group
+ // so immediately remove it from the map.
+ evictEntry(ce.key);
+ numRemoved++;
+
+ // remove the entry by moving the last element to it's position
+ eset[i] = eset[eSize - 1];
+ eSize--;
+ }
+ else
+ {
+ // This entry *could* be in the bottom group, so keep it in the eset,
+ // and update the stats.
+ newNewestEntry = Math.max(thisEntry, newNewestEntry);
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+ }
+ }
+ // System.out.println("items removed:" + numRemoved + " numKept=" +
+ // numKept + " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
+ }
+
+ // if we still didn't remove enough entries, then make another pass while
+ // inserting into a priority queue
+ if (sz - numRemoved > acceptableWaterMark)
+ {
+
+ oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
+ : newOldestEntry;
+ newOldestEntry = Long.MAX_VALUE;
+ newestEntry = newNewestEntry;
+ newNewestEntry = -1;
+ wantToKeep = lowerWaterMark - numKept;
+ wantToRemove = sz - lowerWaterMark - numRemoved;
+
+ PQueue<K, V> queue = new PQueue<K, V>(wantToRemove);
+
+ for (int i = eSize - 1; i >= 0; i--)
+ {
+ CacheEntry<K, V> ce = eset[i];
+ long thisEntry = ce.lastAccessedCopy;
+
+ if (thisEntry > newestEntry - wantToKeep)
+ {
+ // this entry is guaranteed not to be in the bottom
+ // group, so do nothing but remove it from the eset.
+ numKept++;
+ // removal not necessary on last pass.
+ // eset[i] = eset[eSize-1];
+ // eSize--;
+
+ newOldestEntry = Math.min(thisEntry, newOldestEntry);
+
+ }
+ else if (thisEntry < oldestEntry + wantToRemove)
+ { // entry in bottom group?
+ // this entry is guaranteed to be in the bottom group
+ // so immediately remove it.
+ evictEntry(ce.key);
+ numRemoved++;
+
+ // removal not necessary on last pass.
+ // eset[i] = eset[eSize-1];
+ // eSize--;
+ }
+ else
+ {
+ // This entry *could* be in the bottom group.
+ // add it to the priority queue
+
+ // everything in the priority queue will be removed, so keep track of
+ // the lowest value that ever comes back out of the queue.
+
+ // first reduce the size of the priority queue to account for
+ // the number of items we have already removed while executing
+ // this loop so far.
+ queue.myMaxSize = sz - lowerWaterMark - numRemoved;
+ while (queue.size() > queue.myMaxSize
+ && queue.size() > 0)
+ {
+ CacheEntry otherEntry = (CacheEntry) queue.pop();
+ newOldestEntry = Math
+ .min(otherEntry.lastAccessedCopy,
+ newOldestEntry);
+ }
+ if (queue.myMaxSize <= 0)
+ {
+ break;
+ }
+
+ Object o = queue.myInsertWithOverflow(ce);
+ if (o != null)
+ {
+ newOldestEntry = Math.min(
+ ((CacheEntry) o).lastAccessedCopy,
+ newOldestEntry);
+ }
+ }
+ }
+
+ // Now delete everything in the priority queue.
+ // avoid using pop() since order doesn't matter anymore
+ for (CacheEntry<K, V> ce : queue.getValues())
+ {
+ if (ce == null)
+ {
+ continue;
+ }
+ evictEntry(ce.key);
+ numRemoved++;
+ }
+
+ // System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
+ // " initialQueueSize="+ wantToRemove + " finalQueueSize=" +
+ // queue.size() + " sz-numRemoved=" + (sz-numRemoved));
+ }
+
+ oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
+ : newOldestEntry;
+ this.oldestEntry = oldestEntry;
+ }
+ finally
+ {
+ isCleaning = false; // set before markAndSweep.unlock() for visibility
+ markAndSweepLock.unlock();
+ }
+ }
+
+ private static class PQueue<K, V> extends PriorityQueue<CacheEntry<K, V>>
+ {
+ int myMaxSize;
+ final Object[] heap;
+
+ PQueue(int maxSz)
+ {
+ super(maxSz);
+ heap = getHeapArray();
+ myMaxSize = maxSz;
+ }
+
+ @SuppressWarnings("unchecked")
+ Iterable<CacheEntry<K, V>> getValues()
+ {
+ return (Iterable) Collections.unmodifiableCollection(Arrays
+ .asList(heap));
+ }
+
+ @Override
+ protected boolean lessThan(CacheEntry a, CacheEntry b)
+ {
+ // reverse the parameter order so that the queue keeps the oldest items
+ return b.lastAccessedCopy < a.lastAccessedCopy;
+ }
+
+ // necessary because maxSize is private in base class
+ @SuppressWarnings("unchecked")
+ public CacheEntry<K, V> myInsertWithOverflow(CacheEntry<K, V> element)
+ {
+ if (size() < myMaxSize)
+ {
+ add(element);
+ return null;
+ }
+ else if (size() > 0
+ && !lessThan(element, (CacheEntry<K, V>) heap[1]))
+ {
+ CacheEntry<K, V> ret = (CacheEntry<K, V>) heap[1];
+ heap[1] = element;
+ updateTop();
+ return ret;
+ }
+ else
+ {
+ return element;
+ }
+ }
+ }
+
+ private void evictEntry(K key)
+ {
+ CacheEntry<K, V> o = map.remove(key);
+ if (o == null)
+ {
+ return;
+ }
+ stats.size.decrementAndGet();
+ stats.evictionCounter.incrementAndGet();
+ if (evictionListener != null)
+ {
+ evictionListener.evictedEntry(o.key, o.value);
+ }
+ }
+
+ /**
+ * Returns 'n' number of oldest accessed entries present in this cache.
+ *
+ * This uses a TreeSet to collect the 'n' oldest items ordered by ascending last access time
+ * and returns a LinkedHashMap containing 'n' or less than 'n' entries.
+ * @param n the number of oldest items needed
+ * @return a LinkedHashMap containing 'n' or less than 'n' entries
+ */
+ public Map<K, V> getOldestAccessedItems(int n)
+ {
+ Map<K, V> result = new LinkedHashMap<K, V>();
+ if (n <= 0)
+ {
+ return result;
+ }
+ TreeSet<CacheEntry<K, V>> tree = new TreeSet<CacheEntry<K, V>>();
+ markAndSweepLock.lock();
+ try
+ {
+ for (Map.Entry<Object, CacheEntry<K, V>> entry : map.entrySet())
+ {
+ CacheEntry<K, V> ce = entry.getValue();
+ ce.lastAccessedCopy = ce.lastAccessed;
+ if (tree.size() < n)
+ {
+ tree.add(ce);
+ }
+ else
+ {
+ if (ce.lastAccessedCopy < tree.first().lastAccessedCopy)
+ {
+ tree.remove(tree.first());
+ tree.add(ce);
+ }
+ }
+ }
+ }
+ finally
+ {
+ markAndSweepLock.unlock();
+ }
+ for (CacheEntry<K, V> e : tree)
+ {
+ result.put(e.key, e.value);
+ }
+ return result;
+ }
+
+ public Map<K, V> getLatestAccessedItems(int n)
+ {
+ Map<K, V> result = new LinkedHashMap<K, V>();
+ if (n <= 0)
+ {
+ return result;
+ }
+ TreeSet<CacheEntry<K, V>> tree = new TreeSet<CacheEntry<K, V>>();
+ // we need to grab the lock since we are changing lastAccessedCopy
+ markAndSweepLock.lock();
+ try
+ {
+ for (Map.Entry<Object, CacheEntry<K, V>> entry : map.entrySet())
+ {
+ CacheEntry<K, V> ce = entry.getValue();
+ ce.lastAccessedCopy = ce.lastAccessed;
+ if (tree.size() < n)
+ {
+ tree.add(ce);
+ }
+ else
+ {
+ if (ce.lastAccessedCopy > tree.last().lastAccessedCopy)
+ {
+ tree.remove(tree.last());
+ tree.add(ce);
+ }
+ }
+ }
+ }
+ finally
+ {
+ markAndSweepLock.unlock();
+ }
+ for (CacheEntry<K, V> e : tree)
+ {
+ result.put(e.key, e.value);
+ }
+ return result;
+ }
+
+ public int size()
+ {
+ return stats.size.get();
+ }
+
+ public void clear()
+ {
+ map.clear();
+ }
+
+ public Map<Object, CacheEntry<K, V>> getMap()
+ {
+ return map;
+ }
+
+ private static class CacheEntry<K, V> implements
+ Comparable<CacheEntry<K, V>>
+ {
+ K key;
+ V value;
+ volatile long lastAccessed = 0;
+ long lastAccessedCopy = 0;
+
+ public CacheEntry(K key, V value, long lastAccessed)
+ {
+ this.key = key;
+ this.value = value;
+ this.lastAccessed = lastAccessed;
+ }
+
+ public void setLastAccessed(long lastAccessed)
+ {
+ this.lastAccessed = lastAccessed;
+ }
+
+ public int compareTo(CacheEntry<K, V> that)
+ {
+ if (this.lastAccessedCopy == that.lastAccessedCopy)
+ {
+ return 0;
+ }
+ return this.lastAccessedCopy < that.lastAccessedCopy ? 1 : -1;
+ }
+
+ @Override
+ public int hashCode()
+ {
+ return value.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj)
+ {
+ return value.equals(obj);
+ }
+
+ @Override
+ public String toString()
+ {
+ return "key: " + key + " value: " + value + " lastAccessed:"
+ + lastAccessed;
+ }
+ }
+
+ private boolean isDestroyed = false;
+
+ public void destroy()
+ {
+ try
+ {
+ if (cleanupThread != null)
+ {
+ cleanupThread.stopThread();
+ }
+ }
+ finally
+ {
+ isDestroyed = true;
+ }
+ }
+
+ public Stats getStats()
+ {
+ return stats;
+ }
+
+ public static class Stats
+ {
+ private final AtomicLong accessCounter = new AtomicLong(0);
+ private final AtomicLong putCounter = new AtomicLong(0);
+ private final AtomicLong nonLivePutCounter = new AtomicLong(0);
+ private final AtomicLong missCounter = new AtomicLong();
+ private final AtomicInteger size = new AtomicInteger();
+ private AtomicLong evictionCounter = new AtomicLong();
+
+ public long getCumulativeLookups()
+ {
+ return (accessCounter.get() - putCounter.get() - nonLivePutCounter
+ .get()) + missCounter.get();
+ }
+
+ public long getCumulativeHits()
+ {
+ return accessCounter.get() - putCounter.get()
+ - nonLivePutCounter.get();
+ }
+
+ public long getCumulativePuts()
+ {
+ return putCounter.get();
+ }
+
+ public long getCumulativeEvictions()
+ {
+ return evictionCounter.get();
+ }
+
+ public int getCurrentSize()
+ {
+ return size.get();
+ }
+
+ public long getCumulativeNonLivePuts()
+ {
+ return nonLivePutCounter.get();
+ }
+
+ public long getCumulativeMisses()
+ {
+ return missCounter.get();
+ }
+
+ public void add(Stats other)
+ {
+ accessCounter.addAndGet(other.accessCounter.get());
+ putCounter.addAndGet(other.putCounter.get());
+ nonLivePutCounter.addAndGet(other.nonLivePutCounter.get());
+ missCounter.addAndGet(other.missCounter.get());
+ evictionCounter.addAndGet(other.evictionCounter.get());
+ size.set(Math.max(size.get(), other.size.get()));
+ }
+ }
+
+ public static interface EvictionListener<K, V>
+ {
+ public void evictedEntry(K key, V value);
+ }
+
+ private static class CleanupThread extends Thread
+ {
+ private WeakReference<ConcurrentLRUCache> cache;
+
+ private boolean stop = false;
+
+ public CleanupThread(ConcurrentLRUCache c)
+ {
+ cache = new WeakReference<ConcurrentLRUCache>(c);
+ }
+
+ @Override
+ public void run()
+ {
+ while (true)
+ {
+ synchronized (this)
+ {
+ if (stop)
+ {
+ break;
+ }
+ try
+ {
+ this.wait();
+ }
+ catch (InterruptedException e)
+ {
+ }
+ }
+ if (stop)
+ {
+ break;
+ }
+ ConcurrentLRUCache c = cache.get();
+ if (c == null)
+ {
+ break;
+ }
+ c.markAndSweep();
+ }
+ }
+
+ void wakeThread()
+ {
+ synchronized (this)
+ {
+ this.notify();
+ }
+ }
+
+ void stopThread()
+ {
+ synchronized (this)
+ {
+ stop = true;
+ this.notify();
+ }
+ }
+ }
+
+ @Override
+ protected void finalize() throws Throwable
+ {
+ try
+ {
+ if (!isDestroyed)
+ {
+ // This log message is useless, because it is not supposed to use
+ // thread cleanup strategy for this class.
+ //log.severe("ConcurrentLRUCache was not destroyed prior to finalize()," +
+ // " indicates a bug -- POSSIBLE RESOURCE LEAK!!!");
+ destroy();
+ }
+ }
+ finally
+ {
+ super.finalize();
+ }
+ }
+}
Modified: myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/DebugUtils.java
URL: http://svn.apache.org/viewvc/myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/DebugUtils.java?rev=1535874&r1=1535873&r2=1535874&view=diff
==============================================================================
--- myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/DebugUtils.java (original)
+++ myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/DebugUtils.java Fri Oct 25 21:24:09 2013
@@ -1,85 +1,85 @@
-/*
- * 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.myfaces.shared.util;
-
-import javax.faces.component.UIComponent;
-import javax.faces.component.UIViewRoot;
-
-/**
- *
- * @author Leonardo Uribe
- * @since 1.0.2
- *
- */
-public class DebugUtils
-{
- /**
- * Provide debug information about the path of a component
- *
- * @param component
- * @return
- */
- public static String getPathToComponent(UIComponent component)
- {
- StringBuffer buf = new StringBuffer();
-
- if(component == null)
- {
- buf.append("{Component-Path : ");
- buf.append("[null]}");
- return buf.toString();
- }
-
- getPathToComponent(component,buf);
-
- buf.insert(0,"{Component-Path : ");
- buf.append("}");
-
- return buf.toString();
- }
-
- private static void getPathToComponent(UIComponent component, StringBuffer buf)
- {
- if(component == null)
- {
- return;
- }
-
- StringBuffer intBuf = new StringBuffer();
-
- intBuf.append("[Class: ");
- intBuf.append(component.getClass().getName());
- if(component instanceof UIViewRoot)
- {
- intBuf.append(",ViewId: ");
- intBuf.append(((UIViewRoot) component).getViewId());
- }
- else
- {
- intBuf.append(",Id: ");
- intBuf.append(component.getId());
- }
- intBuf.append("]");
-
- buf.insert(0,intBuf.toString());
-
- getPathToComponent(component.getParent(), buf);
- }
-
-}
+/*
+ * 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.myfaces.shared.util;
+
+import javax.faces.component.UIComponent;
+import javax.faces.component.UIViewRoot;
+
+/**
+ *
+ * @author Leonardo Uribe
+ * @since 1.0.2
+ *
+ */
+public class DebugUtils
+{
+ /**
+ * Provide debug information about the path of a component
+ *
+ * @param component
+ * @return
+ */
+ public static String getPathToComponent(UIComponent component)
+ {
+ StringBuffer buf = new StringBuffer();
+
+ if(component == null)
+ {
+ buf.append("{Component-Path : ");
+ buf.append("[null]}");
+ return buf.toString();
+ }
+
+ getPathToComponent(component,buf);
+
+ buf.insert(0,"{Component-Path : ");
+ buf.append("}");
+
+ return buf.toString();
+ }
+
+ private static void getPathToComponent(UIComponent component, StringBuffer buf)
+ {
+ if(component == null)
+ {
+ return;
+ }
+
+ StringBuffer intBuf = new StringBuffer();
+
+ intBuf.append("[Class: ");
+ intBuf.append(component.getClass().getName());
+ if(component instanceof UIViewRoot)
+ {
+ intBuf.append(",ViewId: ");
+ intBuf.append(((UIViewRoot) component).getViewId());
+ }
+ else
+ {
+ intBuf.append(",Id: ");
+ intBuf.append(component.getId());
+ }
+ intBuf.append("]");
+
+ buf.insert(0,intBuf.toString());
+
+ getPathToComponent(component.getParent(), buf);
+ }
+
+}
Modified: myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java
URL: http://svn.apache.org/viewvc/myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java?rev=1535874&r1=1535873&r2=1535874&view=diff
==============================================================================
--- myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java (original)
+++ myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/PriorityQueue.java Fri Oct 25 21:24:09 2013
@@ -1,304 +1,304 @@
-/*
- * 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.myfaces.shared.util;
-
-/** A PriorityQueue maintains a partial ordering of its elements such that the
- * least element can always be found in constant time. Put()'s and pop()'s
- * require log(size) time.
- *
- * <p><b>NOTE</b>: This class will pre-allocate a full array of
- * length <code>maxSize+1</code> if instantiated via the
- * {@link #PriorityQueue(int,boolean)} constructor with
- * <code>prepopulate</code> set to <code>true</code>.
- *
- * @lucene.internal
- * @see org.apache.lucene.util.PriorityQueue
-*/
-public abstract class PriorityQueue<T>
-{
- private int size;
- private final int maxSize;
- private final T[] heap;
-
- public PriorityQueue(int maxSize)
- {
- this(maxSize, true);
- }
-
- @SuppressWarnings("unchecked")
- public PriorityQueue(int maxSize, boolean prepopulate)
- {
- size = 0;
- int heapSize;
- if (0 == maxSize)
- {
- // We allocate 1 extra to avoid if statement in top()
- heapSize = 2;
- }
- else
- {
- if (maxSize == Integer.MAX_VALUE)
- {
- // Don't wrap heapSize to -1, in this case, which
- // causes a confusing NegativeArraySizeException.
- // Note that very likely this will simply then hit
- // an OOME, but at least that's more indicative to
- // caller that this values is too big. We don't +1
- // in this case, but it's very unlikely in practice
- // one will actually insert this many objects into
- // the PQ:
- heapSize = Integer.MAX_VALUE;
- }
- else
- {
- // NOTE: we add +1 because all access to heap is
- // 1-based not 0-based. heap[0] is unused.
- heapSize = maxSize + 1;
- }
- }
- heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
- this.maxSize = maxSize;
-
- if (prepopulate)
- {
- // If sentinel objects are supported, populate the queue with them
- T sentinel = getSentinelObject();
- if (sentinel != null)
- {
- heap[1] = sentinel;
- for (int i = 2; i < heap.length; i++)
- {
- heap[i] = getSentinelObject();
- }
- size = maxSize;
- }
- }
- }
-
- /** Determines the ordering of objects in this priority queue. Subclasses
- * must define this one method.
- * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter <tt>b</tt>.
- */
- protected abstract boolean lessThan(T a, T b);
-
- /**
- * This method can be overridden by extending classes to return a sentinel
- * object which will be used by the {@link PriorityQueue#PriorityQueue(int,boolean)}
- * constructor to fill the queue, so that the code which uses that queue can always
- * assume it's full and only change the top without attempting to insert any new
- * object.<br>
- *
- * Those sentinel values should always compare worse than any non-sentinel
- * value (i.e., {@link #lessThan} should always favor the
- * non-sentinel values).<br>
- *
- * By default, this method returns false, which means the queue will not be
- * filled with sentinel values. Otherwise, the value returned will be used to
- * pre-populate the queue. Adds sentinel values to the queue.<br>
- *
- * If this method is extended to return a non-null value, then the following
- * usage pattern is recommended:
- *
- * <pre>
- * // extends getSentinelObject() to return a non-null value.
- * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
- * // save the 'top' element, which is guaranteed to not be null.
- * MyObject pqTop = pq.top();
- * <...>
- * // now in order to add a new element, which is 'better' than top (after
- * // you've verified it is better), it is as simple as:
- * pqTop.change().
- * pqTop = pq.updateTop();
- * </pre>
- *
- * <b>NOTE:</b> if this method returns a non-null value, it will be called by
- * the {@link PriorityQueue#PriorityQueue(int,boolean)} constructor
- * {@link #size()} times, relying on a new object to be returned and will not
- * check if it's null again. Therefore you should ensure any call to this
- * method creates a new instance and behaves consistently, e.g., it cannot
- * return null if it previously returned non-null.
- *
- * @return the sentinel object to use to pre-populate the queue, or null if
- * sentinel objects are not supported.
- */
- protected T getSentinelObject()
- {
- return null;
- }
-
- /**
- * Adds an Object to a PriorityQueue in log(size) time. If one tries to add
- * more objects than maxSize from initialize an
- * {@link ArrayIndexOutOfBoundsException} is thrown.
- *
- * @return the new 'top' element in the queue.
- */
- public final T add(T element)
- {
- size++;
- heap[size] = element;
- upHeap();
- return heap[1];
- }
-
- /**
- * Adds an Object to a PriorityQueue in log(size) time.
- * It returns the object (if any) that was
- * dropped off the heap because it was full. This can be
- * the given parameter (in case it is smaller than the
- * full heap's minimum, and couldn't be added), or another
- * object that was previously the smallest value in the
- * heap and now has been replaced by a larger one, or null
- * if the queue wasn't yet full with maxSize elements.
- */
- public T insertWithOverflow(T element)
- {
- if (size < maxSize)
- {
- add(element);
- return null;
- }
- else if (size > 0 && !lessThan(element, heap[1]))
- {
- T ret = heap[1];
- heap[1] = element;
- updateTop();
- return ret;
- }
- else
- {
- return element;
- }
- }
-
- /** Returns the least element of the PriorityQueue in constant time. */
- public final T top()
- {
- // We don't need to check size here: if maxSize is 0,
- // then heap is length 2 array with both entries null.
- // If size is 0 then heap[1] is already null.
- return heap[1];
- }
-
- /** Removes and returns the least element of the PriorityQueue in log(size)
- time. */
- public final T pop()
- {
- if (size > 0)
- {
- T result = heap[1]; // save first value
- heap[1] = heap[size]; // move last to first
- heap[size] = null; // permit GC of objects
- size--;
- downHeap(); // adjust heap
- return result;
- }
- else
- {
- return null;
- }
- }
-
- /**
- * Should be called when the Object at top changes values. Still log(n) worst
- * case, but it's at least twice as fast to
- *
- * <pre>
- * pq.top().change();
- * pq.updateTop();
- * </pre>
- *
- * instead of
- *
- * <pre>
- * o = pq.pop();
- * o.change();
- * pq.push(o);
- * </pre>
- *
- * @return the new 'top' element.
- */
- public final T updateTop()
- {
- downHeap();
- return heap[1];
- }
-
- /** Returns the number of elements currently stored in the PriorityQueue. */
- public final int size()
- {
- return size;
- }
-
- /** Removes all entries from the PriorityQueue. */
- public final void clear()
- {
- for (int i = 0; i <= size; i++)
- {
- heap[i] = null;
- }
- size = 0;
- }
-
- private final void upHeap()
- {
- int i = size;
- T node = heap[i]; // save bottom node
- int j = i >>> 1;
- while (j > 0 && lessThan(node, heap[j]))
- {
- heap[i] = heap[j]; // shift parents down
- i = j;
- j = j >>> 1;
- }
- heap[i] = node; // install saved node
- }
-
- private final void downHeap()
- {
- int i = 1;
- T node = heap[i]; // save top node
- int j = i << 1; // find smaller child
- int k = j + 1;
- if (k <= size && lessThan(heap[k], heap[j]))
- {
- j = k;
- }
- while (j <= size && lessThan(heap[j], node))
- {
- heap[i] = heap[j]; // shift up child
- i = j;
- j = i << 1;
- k = j + 1;
- if (k <= size && lessThan(heap[k], heap[j]))
- {
- j = k;
- }
- }
- heap[i] = node; // install saved node
- }
-
- /** This method returns the internal heap array as Object[].
- * @lucene.internal
- */
- protected final Object[] getHeapArray()
- {
- return (Object[]) heap;
- }
-}
+/*
+ * 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.myfaces.shared.util;
+
+/** A PriorityQueue maintains a partial ordering of its elements such that the
+ * least element can always be found in constant time. Put()'s and pop()'s
+ * require log(size) time.
+ *
+ * <p><b>NOTE</b>: This class will pre-allocate a full array of
+ * length <code>maxSize+1</code> if instantiated via the
+ * {@link #PriorityQueue(int,boolean)} constructor with
+ * <code>prepopulate</code> set to <code>true</code>.
+ *
+ * @lucene.internal
+ * @see org.apache.lucene.util.PriorityQueue
+*/
+public abstract class PriorityQueue<T>
+{
+ private int size;
+ private final int maxSize;
+ private final T[] heap;
+
+ public PriorityQueue(int maxSize)
+ {
+ this(maxSize, true);
+ }
+
+ @SuppressWarnings("unchecked")
+ public PriorityQueue(int maxSize, boolean prepopulate)
+ {
+ size = 0;
+ int heapSize;
+ if (0 == maxSize)
+ {
+ // We allocate 1 extra to avoid if statement in top()
+ heapSize = 2;
+ }
+ else
+ {
+ if (maxSize == Integer.MAX_VALUE)
+ {
+ // Don't wrap heapSize to -1, in this case, which
+ // causes a confusing NegativeArraySizeException.
+ // Note that very likely this will simply then hit
+ // an OOME, but at least that's more indicative to
+ // caller that this values is too big. We don't +1
+ // in this case, but it's very unlikely in practice
+ // one will actually insert this many objects into
+ // the PQ:
+ heapSize = Integer.MAX_VALUE;
+ }
+ else
+ {
+ // NOTE: we add +1 because all access to heap is
+ // 1-based not 0-based. heap[0] is unused.
+ heapSize = maxSize + 1;
+ }
+ }
+ heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
+ this.maxSize = maxSize;
+
+ if (prepopulate)
+ {
+ // If sentinel objects are supported, populate the queue with them
+ T sentinel = getSentinelObject();
+ if (sentinel != null)
+ {
+ heap[1] = sentinel;
+ for (int i = 2; i < heap.length; i++)
+ {
+ heap[i] = getSentinelObject();
+ }
+ size = maxSize;
+ }
+ }
+ }
+
+ /** Determines the ordering of objects in this priority queue. Subclasses
+ * must define this one method.
+ * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter <tt>b</tt>.
+ */
+ protected abstract boolean lessThan(T a, T b);
+
+ /**
+ * This method can be overridden by extending classes to return a sentinel
+ * object which will be used by the {@link PriorityQueue#PriorityQueue(int,boolean)}
+ * constructor to fill the queue, so that the code which uses that queue can always
+ * assume it's full and only change the top without attempting to insert any new
+ * object.<br>
+ *
+ * Those sentinel values should always compare worse than any non-sentinel
+ * value (i.e., {@link #lessThan} should always favor the
+ * non-sentinel values).<br>
+ *
+ * By default, this method returns false, which means the queue will not be
+ * filled with sentinel values. Otherwise, the value returned will be used to
+ * pre-populate the queue. Adds sentinel values to the queue.<br>
+ *
+ * If this method is extended to return a non-null value, then the following
+ * usage pattern is recommended:
+ *
+ * <pre>
+ * // extends getSentinelObject() to return a non-null value.
+ * PriorityQueue<MyObject> pq = new MyQueue<MyObject>(numHits);
+ * // save the 'top' element, which is guaranteed to not be null.
+ * MyObject pqTop = pq.top();
+ * <...>
+ * // now in order to add a new element, which is 'better' than top (after
+ * // you've verified it is better), it is as simple as:
+ * pqTop.change().
+ * pqTop = pq.updateTop();
+ * </pre>
+ *
+ * <b>NOTE:</b> if this method returns a non-null value, it will be called by
+ * the {@link PriorityQueue#PriorityQueue(int,boolean)} constructor
+ * {@link #size()} times, relying on a new object to be returned and will not
+ * check if it's null again. Therefore you should ensure any call to this
+ * method creates a new instance and behaves consistently, e.g., it cannot
+ * return null if it previously returned non-null.
+ *
+ * @return the sentinel object to use to pre-populate the queue, or null if
+ * sentinel objects are not supported.
+ */
+ protected T getSentinelObject()
+ {
+ return null;
+ }
+
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time. If one tries to add
+ * more objects than maxSize from initialize an
+ * {@link ArrayIndexOutOfBoundsException} is thrown.
+ *
+ * @return the new 'top' element in the queue.
+ */
+ public final T add(T element)
+ {
+ size++;
+ heap[size] = element;
+ upHeap();
+ return heap[1];
+ }
+
+ /**
+ * Adds an Object to a PriorityQueue in log(size) time.
+ * It returns the object (if any) that was
+ * dropped off the heap because it was full. This can be
+ * the given parameter (in case it is smaller than the
+ * full heap's minimum, and couldn't be added), or another
+ * object that was previously the smallest value in the
+ * heap and now has been replaced by a larger one, or null
+ * if the queue wasn't yet full with maxSize elements.
+ */
+ public T insertWithOverflow(T element)
+ {
+ if (size < maxSize)
+ {
+ add(element);
+ return null;
+ }
+ else if (size > 0 && !lessThan(element, heap[1]))
+ {
+ T ret = heap[1];
+ heap[1] = element;
+ updateTop();
+ return ret;
+ }
+ else
+ {
+ return element;
+ }
+ }
+
+ /** Returns the least element of the PriorityQueue in constant time. */
+ public final T top()
+ {
+ // We don't need to check size here: if maxSize is 0,
+ // then heap is length 2 array with both entries null.
+ // If size is 0 then heap[1] is already null.
+ return heap[1];
+ }
+
+ /** Removes and returns the least element of the PriorityQueue in log(size)
+ time. */
+ public final T pop()
+ {
+ if (size > 0)
+ {
+ T result = heap[1]; // save first value
+ heap[1] = heap[size]; // move last to first
+ heap[size] = null; // permit GC of objects
+ size--;
+ downHeap(); // adjust heap
+ return result;
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+ /**
+ * Should be called when the Object at top changes values. Still log(n) worst
+ * case, but it's at least twice as fast to
+ *
+ * <pre>
+ * pq.top().change();
+ * pq.updateTop();
+ * </pre>
+ *
+ * instead of
+ *
+ * <pre>
+ * o = pq.pop();
+ * o.change();
+ * pq.push(o);
+ * </pre>
+ *
+ * @return the new 'top' element.
+ */
+ public final T updateTop()
+ {
+ downHeap();
+ return heap[1];
+ }
+
+ /** Returns the number of elements currently stored in the PriorityQueue. */
+ public final int size()
+ {
+ return size;
+ }
+
+ /** Removes all entries from the PriorityQueue. */
+ public final void clear()
+ {
+ for (int i = 0; i <= size; i++)
+ {
+ heap[i] = null;
+ }
+ size = 0;
+ }
+
+ private final void upHeap()
+ {
+ int i = size;
+ T node = heap[i]; // save bottom node
+ int j = i >>> 1;
+ while (j > 0 && lessThan(node, heap[j]))
+ {
+ heap[i] = heap[j]; // shift parents down
+ i = j;
+ j = j >>> 1;
+ }
+ heap[i] = node; // install saved node
+ }
+
+ private final void downHeap()
+ {
+ int i = 1;
+ T node = heap[i]; // save top node
+ int j = i << 1; // find smaller child
+ int k = j + 1;
+ if (k <= size && lessThan(heap[k], heap[j]))
+ {
+ j = k;
+ }
+ while (j <= size && lessThan(heap[j], node))
+ {
+ heap[i] = heap[j]; // shift up child
+ i = j;
+ j = i << 1;
+ k = j + 1;
+ if (k <= size && lessThan(heap[k], heap[j]))
+ {
+ j = k;
+ }
+ }
+ heap[i] = node; // install saved node
+ }
+
+ /** This method returns the internal heap array as Object[].
+ * @lucene.internal
+ */
+ protected final Object[] getHeapArray()
+ {
+ return (Object[]) heap;
+ }
+}
Modified: myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/RendererUtils.java
URL: http://svn.apache.org/viewvc/myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/RendererUtils.java?rev=1535874&r1=1535873&r2=1535874&view=diff
==============================================================================
--- myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/RendererUtils.java (original)
+++ myfaces/shared/trunk/core/src/main/java/org/apache/myfaces/shared/util/RendererUtils.java Fri Oct 25 21:24:09 2013
@@ -1,69 +1,69 @@
-/*
- * 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.myfaces.shared.util;
-
-import java.io.IOException;
-import java.util.Iterator;
-
-import javax.faces.component.UIComponent;
-import javax.faces.context.FacesContext;
-
-/**
- *
- * @author Leonardo Uribe
- * @since 1.0.1
- */
-public class RendererUtils
-{
-
- public static void renderChildren(FacesContext facesContext, UIComponent component)
- throws IOException
- {
- if (component.getChildCount() > 0)
- {
- for (Iterator it = component.getChildren().iterator(); it.hasNext(); )
- {
- UIComponent child = (UIComponent)it.next();
- renderChild(facesContext, child);
- }
- }
- }
-
-
- public static void renderChild(FacesContext facesContext, UIComponent child)
- throws IOException
- {
- if (!child.isRendered())
- {
- return;
- }
-
- child.encodeBegin(facesContext);
- if (child.getRendersChildren())
- {
- child.encodeChildren(facesContext);
- }
- else
- {
- renderChildren(facesContext, child);
- }
- child.encodeEnd(facesContext);
- }
-
-}
+/*
+ * 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.myfaces.shared.util;
+
+import java.io.IOException;
+import java.util.Iterator;
+
+import javax.faces.component.UIComponent;
+import javax.faces.context.FacesContext;
+
+/**
+ *
+ * @author Leonardo Uribe
+ * @since 1.0.1
+ */
+public class RendererUtils
+{
+
+ public static void renderChildren(FacesContext facesContext, UIComponent component)
+ throws IOException
+ {
+ if (component.getChildCount() > 0)
+ {
+ for (Iterator it = component.getChildren().iterator(); it.hasNext(); )
+ {
+ UIComponent child = (UIComponent)it.next();
+ renderChild(facesContext, child);
+ }
+ }
+ }
+
+
+ public static void renderChild(FacesContext facesContext, UIComponent child)
+ throws IOException
+ {
+ if (!child.isRendered())
+ {
+ return;
+ }
+
+ child.encodeBegin(facesContext);
+ if (child.getRendersChildren())
+ {
+ child.encodeChildren(facesContext);
+ }
+ else
+ {
+ renderChildren(facesContext, child);
+ }
+ child.encodeEnd(facesContext);
+ }
+
+}