001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.pool2.impl;
018
019import java.util.ArrayList;
020import java.util.Deque;
021import java.util.HashMap;
022import java.util.Iterator;
023import java.util.List;
024import java.util.Map;
025import java.util.Map.Entry;
026import java.util.NoSuchElementException;
027import java.util.TreeMap;
028import java.util.concurrent.ConcurrentHashMap;
029import java.util.concurrent.TimeUnit;
030import java.util.concurrent.atomic.AtomicInteger;
031import java.util.concurrent.atomic.AtomicLong;
032import java.util.concurrent.locks.Lock;
033import java.util.concurrent.locks.ReadWriteLock;
034import java.util.concurrent.locks.ReentrantReadWriteLock;
035
036import org.apache.commons.pool2.KeyedObjectPool;
037import org.apache.commons.pool2.KeyedPooledObjectFactory;
038import org.apache.commons.pool2.PoolUtils;
039import org.apache.commons.pool2.PooledObject;
040import org.apache.commons.pool2.PooledObjectState;
041import org.apache.commons.pool2.SwallowedExceptionListener;
042
043/**
044 * A configurable <code>KeyedObjectPool</code> implementation.
045 * <p>
046 * When coupled with the appropriate {@link KeyedPooledObjectFactory},
047 * <code>GenericKeyedObjectPool</code> provides robust pooling functionality for
048 * keyed objects. A <code>GenericKeyedObjectPool</code> can be viewed as a map
049 * of sub-pools, keyed on the (unique) key values provided to the
050 * {@link #preparePool preparePool}, {@link #addObject addObject} or
051 * {@link #borrowObject borrowObject} methods. Each time a new key value is
052 * provided to one of these methods, a sub-new pool is created under the given
053 * key to be managed by the containing <code>GenericKeyedObjectPool.</code>
054 * <p>
055 * Note that the current implementation uses a ConcurrentHashMap which uses
056 * equals() to compare keys.
057 * This means that distinct instance keys must be distinguishable using equals.
058 * <p>
059 * Optionally, one may configure the pool to examine and possibly evict objects
060 * as they sit idle in the pool and to ensure that a minimum number of idle
061 * objects is maintained for each key. This is performed by an "idle object
062 * eviction" thread, which runs asynchronously. Caution should be used when
063 * configuring this optional feature. Eviction runs contend with client threads
064 * for access to objects in the pool, so if they run too frequently performance
065 * issues may result.
066 * <p>
067 * Implementation note: To prevent possible deadlocks, care has been taken to
068 * ensure that no call to a factory method will occur within a synchronization
069 * block. See POOL-125 and DBCP-44 for more information.
070 * <p>
071 * This class is intended to be thread-safe.
072 *
073 * @see GenericObjectPool
074 *
075 * @param <K> The type of keys maintained by this pool.
076 * @param <T> Type of element pooled in this pool.
077 *
078 * @since 2.0
079 */
080public class GenericKeyedObjectPool<K, T> extends BaseGenericObjectPool<T>
081        implements KeyedObjectPool<K, T>, GenericKeyedObjectPoolMXBean<K> {
082
083    /**
084     * Create a new <code>GenericKeyedObjectPool</code> using defaults from
085     * {@link GenericKeyedObjectPoolConfig}.
086     * @param factory the factory to be used to create entries
087     */
088    public GenericKeyedObjectPool(final KeyedPooledObjectFactory<K,T> factory) {
089        this(factory, new GenericKeyedObjectPoolConfig<T>());
090    }
091
092    /**
093     * Create a new <code>GenericKeyedObjectPool</code> using a specific
094     * configuration.
095     *
096     * @param factory the factory to be used to create entries
097     * @param config    The configuration to use for this pool instance. The
098     *                  configuration is used by value. Subsequent changes to
099     *                  the configuration object will not be reflected in the
100     *                  pool.
101     */
102    public GenericKeyedObjectPool(final KeyedPooledObjectFactory<K, T> factory,
103            final GenericKeyedObjectPoolConfig<T> config) {
104
105        super(config, ONAME_BASE, config.getJmxNamePrefix());
106
107        if (factory == null) {
108            jmxUnregister(); // tidy up
109            throw new IllegalArgumentException("factory may not be null");
110        }
111        this.factory = factory;
112        this.fairness = config.getFairness();
113
114        setConfig(config);
115    }
116
117    /**
118     * Returns the limit on the number of object instances allocated by the pool
119     * (checked out or idle), per key. When the limit is reached, the sub-pool
120     * is said to be exhausted. A negative value indicates no limit.
121     *
122     * @return the limit on the number of active instances per key
123     *
124     * @see #setMaxTotalPerKey
125     */
126    @Override
127    public int getMaxTotalPerKey() {
128        return maxTotalPerKey;
129    }
130
131    /**
132     * Sets the limit on the number of object instances allocated by the pool
133     * (checked out or idle), per key. When the limit is reached, the sub-pool
134     * is said to be exhausted. A negative value indicates no limit.
135     *
136     * @param maxTotalPerKey the limit on the number of active instances per key
137     *
138     * @see #getMaxTotalPerKey
139     */
140    public void setMaxTotalPerKey(final int maxTotalPerKey) {
141        this.maxTotalPerKey = maxTotalPerKey;
142    }
143
144
145    /**
146     * Returns the cap on the number of "idle" instances per key in the pool.
147     * If maxIdlePerKey is set too low on heavily loaded systems it is possible
148     * you will see objects being destroyed and almost immediately new objects
149     * being created. This is a result of the active threads momentarily
150     * returning objects faster than they are requesting them, causing the
151     * number of idle objects to rise above maxIdlePerKey. The best value for
152     * maxIdlePerKey for heavily loaded system will vary but the default is a
153     * good starting point.
154     *
155     * @return the maximum number of "idle" instances that can be held in a
156     *         given keyed sub-pool or a negative value if there is no limit
157     *
158     * @see #setMaxIdlePerKey
159     */
160    @Override
161    public int getMaxIdlePerKey() {
162        return maxIdlePerKey;
163    }
164
165    /**
166     * Sets the cap on the number of "idle" instances per key in the pool.
167     * If maxIdlePerKey is set too low on heavily loaded systems it is possible
168     * you will see objects being destroyed and almost immediately new objects
169     * being created. This is a result of the active threads momentarily
170     * returning objects faster than they are requesting them, causing the
171     * number of idle objects to rise above maxIdlePerKey. The best value for
172     * maxIdlePerKey for heavily loaded system will vary but the default is a
173     * good starting point.
174     *
175     * @param maxIdlePerKey the maximum number of "idle" instances that can be
176     *                      held in a given keyed sub-pool. Use a negative value
177     *                      for no limit
178     *
179     * @see #getMaxIdlePerKey
180     */
181    public void setMaxIdlePerKey(final int maxIdlePerKey) {
182        this.maxIdlePerKey = maxIdlePerKey;
183    }
184
185    /**
186     * Sets the target for the minimum number of idle objects to maintain in
187     * each of the keyed sub-pools. This setting only has an effect if it is
188     * positive and {@link #getTimeBetweenEvictionRunsMillis()} is greater than
189     * zero. If this is the case, an attempt is made to ensure that each
190     * sub-pool has the required minimum number of instances during idle object
191     * eviction runs.
192     * <p>
193     * If the configured value of minIdlePerKey is greater than the configured
194     * value for maxIdlePerKey then the value of maxIdlePerKey will be used
195     * instead.
196     *
197     * @param minIdlePerKey The minimum size of the each keyed pool
198     *
199     * @see #getMinIdlePerKey
200     * @see #getMaxIdlePerKey()
201     * @see #setTimeBetweenEvictionRunsMillis
202     */
203    public void setMinIdlePerKey(final int minIdlePerKey) {
204        this.minIdlePerKey = minIdlePerKey;
205    }
206
207    /**
208     * Returns the target for the minimum number of idle objects to maintain in
209     * each of the keyed sub-pools. This setting only has an effect if it is
210     * positive and {@link #getTimeBetweenEvictionRunsMillis()} is greater than
211     * zero. If this is the case, an attempt is made to ensure that each
212     * sub-pool has the required minimum number of instances during idle object
213     * eviction runs.
214     * <p>
215     * If the configured value of minIdlePerKey is greater than the configured
216     * value for maxIdlePerKey then the value of maxIdlePerKey will be used
217     * instead.
218     *
219     * @return minimum size of the each keyed pool
220     *
221     * @see #setTimeBetweenEvictionRunsMillis
222     */
223    @Override
224    public int getMinIdlePerKey() {
225        final int maxIdlePerKeySave = getMaxIdlePerKey();
226        if (this.minIdlePerKey > maxIdlePerKeySave) {
227            return maxIdlePerKeySave;
228        }
229        return minIdlePerKey;
230    }
231
232    /**
233     * Sets the configuration.
234     *
235     * @param conf the new configuration to use. This is used by value.
236     *
237     * @see GenericKeyedObjectPoolConfig
238     */
239    public void setConfig(final GenericKeyedObjectPoolConfig<T> conf) {
240        super.setConfig(conf);
241        setMaxIdlePerKey(conf.getMaxIdlePerKey());
242        setMaxTotalPerKey(conf.getMaxTotalPerKey());
243        setMaxTotal(conf.getMaxTotal());
244        setMinIdlePerKey(conf.getMinIdlePerKey());
245    }
246
247    /**
248     * Obtain a reference to the factory used to create, destroy and validate
249     * the objects used by this pool.
250     *
251     * @return the factory
252     */
253    public KeyedPooledObjectFactory<K, T> getFactory() {
254        return factory;
255    }
256
257    /**
258     * Equivalent to <code>{@link #borrowObject(Object, long) borrowObject}(key,
259     * {@link #getMaxWaitMillis()})</code>.
260     * <p>
261     * {@inheritDoc}
262     */
263    @Override
264    public T borrowObject(final K key) throws Exception {
265        return borrowObject(key, getMaxWaitMillis());
266    }
267
268    /**
269     * Borrows an object from the sub-pool associated with the given key using
270     * the specified waiting time which only applies if
271     * {@link #getBlockWhenExhausted()} is true.
272     * <p>
273     * If there is one or more idle instances available in the sub-pool
274     * associated with the given key, then an idle instance will be selected
275     * based on the value of {@link #getLifo()}, activated and returned.  If
276     * activation fails, or {@link #getTestOnBorrow() testOnBorrow} is set to
277     * <code>true</code> and validation fails, the instance is destroyed and the
278     * next available instance is examined.  This continues until either a valid
279     * instance is returned or there are no more idle instances available.
280     * <p>
281     * If there are no idle instances available in the sub-pool associated with
282     * the given key, behavior depends on the {@link #getMaxTotalPerKey()
283     * maxTotalPerKey}, {@link #getMaxTotal() maxTotal}, and (if applicable)
284     * {@link #getBlockWhenExhausted()} and the value passed in to the
285     * <code>borrowMaxWaitMillis</code> parameter. If the number of instances checked
286     * out from the sub-pool under the given key is less than
287     * <code>maxTotalPerKey</code> and the total number of instances in
288     * circulation (under all keys) is less than <code>maxTotal</code>, a new
289     * instance is created, activated and (if applicable) validated and returned
290     * to the caller. If validation fails, a <code>NoSuchElementException</code>
291     * will be thrown.
292     * <p>
293     * If the associated sub-pool is exhausted (no available idle instances and
294     * no capacity to create new ones), this method will either block
295     * ({@link #getBlockWhenExhausted()} is true) or throw a
296     * <code>NoSuchElementException</code>
297     * ({@link #getBlockWhenExhausted()} is false).
298     * The length of time that this method will block when
299     * {@link #getBlockWhenExhausted()} is true is determined by the value
300     * passed in to the <code>borrowMaxWait</code> parameter.
301     * <p>
302     * When <code>maxTotal</code> is set to a positive value and this method is
303     * invoked when at the limit with no idle instances available under the requested
304     * key, an attempt is made to create room by clearing the oldest 15% of the
305     * elements from the keyed sub-pools.
306     * <p>
307     * When the pool is exhausted, multiple calling threads may be
308     * simultaneously blocked waiting for instances to become available. A
309     * "fairness" algorithm has been implemented to ensure that threads receive
310     * available instances in request arrival order.
311     *
312     * @param key pool key
313     * @param borrowMaxWaitMillis The time to wait in milliseconds for an object
314     *                            to become available
315     *
316     * @return object instance from the keyed pool
317     *
318     * @throws NoSuchElementException if a keyed object instance cannot be
319     *                                returned because the pool is exhausted.
320     *
321     * @throws Exception if a keyed object instance cannot be returned due to an
322     *                   error
323     */
324    public T borrowObject(final K key, final long borrowMaxWaitMillis) throws Exception {
325        assertOpen();
326
327        PooledObject<T> p = null;
328
329        // Get local copy of current config so it is consistent for entire
330        // method execution
331        final boolean blockWhenExhausted = getBlockWhenExhausted();
332
333        boolean create;
334        final long waitTime = System.currentTimeMillis();
335        final ObjectDeque<T> objectDeque = register(key);
336
337        try {
338            while (p == null) {
339                create = false;
340                p = objectDeque.getIdleObjects().pollFirst();
341                if (p == null) {
342                    p = create(key);
343                    if (p != null) {
344                        create = true;
345                    }
346                }
347                if (blockWhenExhausted) {
348                    if (p == null) {
349                        if (borrowMaxWaitMillis < 0) {
350                            p = objectDeque.getIdleObjects().takeFirst();
351                        } else {
352                            p = objectDeque.getIdleObjects().pollFirst(
353                                    borrowMaxWaitMillis, TimeUnit.MILLISECONDS);
354                        }
355                    }
356                    if (p == null) {
357                        throw new NoSuchElementException(
358                                "Timeout waiting for idle object");
359                    }
360                } else {
361                    if (p == null) {
362                        throw new NoSuchElementException("Pool exhausted");
363                    }
364                }
365                if (!p.allocate()) {
366                    p = null;
367                }
368
369                if (p != null) {
370                    try {
371                        factory.activateObject(key, p);
372                    } catch (final Exception e) {
373                        try {
374                            destroy(key, p, true);
375                        } catch (final Exception e1) {
376                            // Ignore - activation failure is more important
377                        }
378                        p = null;
379                        if (create) {
380                            final NoSuchElementException nsee = new NoSuchElementException(
381                                    "Unable to activate object");
382                            nsee.initCause(e);
383                            throw nsee;
384                        }
385                    }
386                    if (p != null && getTestOnBorrow()) {
387                        boolean validate = false;
388                        Throwable validationThrowable = null;
389                        try {
390                            validate = factory.validateObject(key, p);
391                        } catch (final Throwable t) {
392                            PoolUtils.checkRethrow(t);
393                            validationThrowable = t;
394                        }
395                        if (!validate) {
396                            try {
397                                destroy(key, p, true);
398                                destroyedByBorrowValidationCount.incrementAndGet();
399                            } catch (final Exception e) {
400                                // Ignore - validation failure is more important
401                            }
402                            p = null;
403                            if (create) {
404                                final NoSuchElementException nsee = new NoSuchElementException(
405                                        "Unable to validate object");
406                                nsee.initCause(validationThrowable);
407                                throw nsee;
408                            }
409                        }
410                    }
411                }
412            }
413        } finally {
414            deregister(key);
415        }
416
417        updateStatsBorrow(p, System.currentTimeMillis() - waitTime);
418
419        return p.getObject();
420    }
421
422
423    /**
424     * Returns an object to a keyed sub-pool.
425     * <p>
426     * If {@link #getMaxIdlePerKey() maxIdle} is set to a positive value and the
427     * number of idle instances under the given key has reached this value, the
428     * returning instance is destroyed.
429     * <p>
430     * If {@link #getTestOnReturn() testOnReturn} == true, the returning
431     * instance is validated before being returned to the idle instance sub-pool
432     * under the given key. In this case, if validation fails, the instance is
433     * destroyed.
434     * <p>
435     * Exceptions encountered destroying objects for any reason are swallowed
436     * but notified via a {@link SwallowedExceptionListener}.
437     *
438     * @param key pool key
439     * @param obj instance to return to the keyed pool
440     *
441     * @throws IllegalStateException if an object is returned to the pool that
442     *                               was not borrowed from it or if an object is
443     *                               returned to the pool multiple times
444     */
445    @Override
446    public void returnObject(final K key, final T obj) {
447
448        final ObjectDeque<T> objectDeque = poolMap.get(key);
449
450        final PooledObject<T> p = objectDeque.getAllObjects().get(new IdentityWrapper<>(obj));
451
452        if (p == null) {
453            throw new IllegalStateException(
454                    "Returned object not currently part of this pool");
455        }
456
457        markReturningState(p);
458
459        final long activeTime = p.getActiveTimeMillis();
460
461        try {
462            if (getTestOnReturn() && !factory.validateObject(key, p)) {
463                try {
464                    destroy(key, p, true);
465                } catch (final Exception e) {
466                    swallowException(e);
467                }
468                whenWaitersAddObject(key, objectDeque.idleObjects);
469                return;
470            }
471
472            try {
473                factory.passivateObject(key, p);
474            } catch (final Exception e1) {
475                swallowException(e1);
476                try {
477                    destroy(key, p, true);
478                } catch (final Exception e) {
479                    swallowException(e);
480                }
481                whenWaitersAddObject(key, objectDeque.idleObjects);
482                return;
483            }
484
485            if (!p.deallocate()) {
486                throw new IllegalStateException(
487                        "Object has already been returned to this pool");
488            }
489
490            final int maxIdle = getMaxIdlePerKey();
491            final LinkedBlockingDeque<PooledObject<T>> idleObjects =
492                    objectDeque.getIdleObjects();
493
494            if (isClosed() || maxIdle > -1 && maxIdle <= idleObjects.size()) {
495                try {
496                    destroy(key, p, true);
497                } catch (final Exception e) {
498                    swallowException(e);
499                }
500            } else {
501                if (getLifo()) {
502                    idleObjects.addFirst(p);
503                } else {
504                    idleObjects.addLast(p);
505                }
506                if (isClosed()) {
507                    // Pool closed while object was being added to idle objects.
508                    // Make sure the returned object is destroyed rather than left
509                    // in the idle object pool (which would effectively be a leak)
510                    clear(key);
511                }
512            }
513        } finally {
514            if (hasBorrowWaiters()) {
515                reuseCapacity();
516            }
517            updateStatsReturn(activeTime);
518        }
519    }
520
521    /**
522     * Whether there is at least one thread waiting on this deque, add an pool object.
523     * @param key pool key.
524     * @param idleObjects list of idle pool objects.
525     */
526    private void whenWaitersAddObject(final K key, final LinkedBlockingDeque<PooledObject<T>> idleObjects) {
527        if (idleObjects.hasTakeWaiters()) {
528            try {
529                addObject(key);
530            } catch (final Exception e) {
531                swallowException(e);
532            }
533        }
534    }
535
536    /**
537     * {@inheritDoc}
538     * <p>
539     * Activation of this method decrements the active count associated with
540     * the given keyed pool and attempts to destroy <code>obj.</code>
541     *
542     * @param key pool key
543     * @param obj instance to invalidate
544     *
545     * @throws Exception             if an exception occurs destroying the
546     *                               object
547     * @throws IllegalStateException if obj does not belong to the pool
548     *                               under the given key
549     */
550    @Override
551    public void invalidateObject(final K key, final T obj) throws Exception {
552
553        final ObjectDeque<T> objectDeque = poolMap.get(key);
554
555        final PooledObject<T> p = objectDeque.getAllObjects().get(new IdentityWrapper<>(obj));
556        if (p == null) {
557            throw new IllegalStateException(
558                    "Object not currently part of this pool");
559        }
560        synchronized (p) {
561            if (p.getState() != PooledObjectState.INVALID) {
562                destroy(key, p, true);
563            }
564        }
565        if (objectDeque.idleObjects.hasTakeWaiters()) {
566            addObject(key);
567        }
568    }
569
570
571    /**
572     * Clears any objects sitting idle in the pool by removing them from the
573     * idle instance sub-pools and then invoking the configured
574     * PoolableObjectFactory's
575     * {@link KeyedPooledObjectFactory#destroyObject(Object, PooledObject)}
576     * method on each idle instance.
577     * <p>
578     * Implementation notes:
579     * <ul>
580     * <li>This method does not destroy or effect in any way instances that are
581     * checked out when it is invoked.</li>
582     * <li>Invoking this method does not prevent objects being returned to the
583     * idle instance pool, even during its execution. Additional instances may
584     * be returned while removed items are being destroyed.</li>
585     * <li>Exceptions encountered destroying idle instances are swallowed
586     * but notified via a {@link SwallowedExceptionListener}.</li>
587     * </ul>
588     */
589    @Override
590    public void clear() {
591        final Iterator<K> iter = poolMap.keySet().iterator();
592
593        while (iter.hasNext()) {
594            clear(iter.next());
595        }
596    }
597
598
599    /**
600     * Clears the specified sub-pool, removing all pooled instances
601     * corresponding to the given <code>key</code>. Exceptions encountered
602     * destroying idle instances are swallowed but notified via a
603     * {@link SwallowedExceptionListener}.
604     *
605     * @param key the key to clear
606     */
607    @Override
608    public void clear(final K key) {
609
610        final ObjectDeque<T> objectDeque = register(key);
611
612        try {
613            final LinkedBlockingDeque<PooledObject<T>> idleObjects =
614                    objectDeque.getIdleObjects();
615
616            PooledObject<T> p = idleObjects.poll();
617
618            while (p != null) {
619                try {
620                    destroy(key, p, true);
621                } catch (final Exception e) {
622                    swallowException(e);
623                }
624                p = idleObjects.poll();
625            }
626        } finally {
627            deregister(key);
628        }
629    }
630
631
632    @Override
633    public int getNumActive() {
634        return numTotal.get() - getNumIdle();
635    }
636
637
638    @Override
639    public int getNumIdle() {
640        final Iterator<ObjectDeque<T>> iter = poolMap.values().iterator();
641        int result = 0;
642
643        while (iter.hasNext()) {
644            result += iter.next().getIdleObjects().size();
645        }
646
647        return result;
648    }
649
650
651    @Override
652    public int getNumActive(final K key) {
653        final ObjectDeque<T> objectDeque = poolMap.get(key);
654        if (objectDeque != null) {
655            return objectDeque.getAllObjects().size() -
656                    objectDeque.getIdleObjects().size();
657        }
658        return 0;
659    }
660
661
662    @Override
663    public int getNumIdle(final K key) {
664        final ObjectDeque<T> objectDeque = poolMap.get(key);
665        return objectDeque != null ? objectDeque.getIdleObjects().size() : 0;
666    }
667
668
669    /**
670     * Closes the keyed object pool. Once the pool is closed,
671     * {@link #borrowObject(Object)} will fail with IllegalStateException, but
672     * {@link #returnObject(Object, Object)} and
673     * {@link #invalidateObject(Object, Object)} will continue to work, with
674     * returned objects destroyed on return.
675     * <p>
676     * Destroys idle instances in the pool by invoking {@link #clear()}.
677     */
678    @Override
679    public void close() {
680        if (isClosed()) {
681            return;
682        }
683
684        synchronized (closeLock) {
685            if (isClosed()) {
686                return;
687            }
688
689            // Stop the evictor before the pool is closed since evict() calls
690            // assertOpen()
691            stopEvictor();
692
693            closed = true;
694            // This clear removes any idle objects
695            clear();
696
697            jmxUnregister();
698
699            // Release any threads that were waiting for an object
700            final Iterator<ObjectDeque<T>> iter = poolMap.values().iterator();
701            while (iter.hasNext()) {
702                iter.next().getIdleObjects().interuptTakeWaiters();
703            }
704            // This clear cleans up the keys now any waiting threads have been
705            // interrupted
706            clear();
707        }
708    }
709
710
711    /**
712     * Clears oldest 15% of objects in pool.  The method sorts the objects into
713     * a TreeMap and then iterates the first 15% for removal.
714     */
715    public void clearOldest() {
716
717        // build sorted map of idle objects
718        final Map<PooledObject<T>, K> map = new TreeMap<>();
719
720        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
721            final K k = entry.getKey();
722            final ObjectDeque<T> deque = entry.getValue();
723            // Protect against possible NPE if key has been removed in another
724            // thread. Not worth locking the keys while this loop completes.
725            if (deque != null) {
726                final LinkedBlockingDeque<PooledObject<T>> idleObjects =
727                        deque.getIdleObjects();
728                for (final PooledObject<T> p : idleObjects) {
729                    // each item into the map using the PooledObject object as the
730                    // key. It then gets sorted based on the idle time
731                    map.put(p, k);
732                }
733            }
734        }
735
736        // Now iterate created map and kill the first 15% plus one to account
737        // for zero
738        int itemsToRemove = ((int) (map.size() * 0.15)) + 1;
739        final Iterator<Map.Entry<PooledObject<T>, K>> iter =
740                map.entrySet().iterator();
741
742        while (iter.hasNext() && itemsToRemove > 0) {
743            final Map.Entry<PooledObject<T>, K> entry = iter.next();
744            // kind of backwards on naming.  In the map, each key is the
745            // PooledObject because it has the ordering with the timestamp
746            // value.  Each value that the key references is the key of the
747            // list it belongs to.
748            final K key = entry.getValue();
749            final PooledObject<T> p = entry.getKey();
750            // Assume the destruction succeeds
751            boolean destroyed = true;
752            try {
753                destroyed = destroy(key, p, false);
754            } catch (final Exception e) {
755                swallowException(e);
756            }
757            if (destroyed) {
758                itemsToRemove--;
759            }
760        }
761    }
762
763    /**
764     * Attempt to create one new instance to serve from the most heavily
765     * loaded pool that can add a new instance.
766     *
767     * This method exists to ensure liveness in the pool when threads are
768     * parked waiting and capacity to create instances under the requested keys
769     * subsequently becomes available.
770     *
771     * This method is not guaranteed to create an instance and its selection
772     * of the most loaded pool that can create an instance may not always be
773     * correct, since it does not lock the pool and instances may be created,
774     * borrowed, returned or destroyed by other threads while it is executing.
775     */
776    private void reuseCapacity() {
777        final int maxTotalPerKeySave = getMaxTotalPerKey();
778
779        // Find the most loaded pool that could take a new instance
780        int maxQueueLength = 0;
781        LinkedBlockingDeque<PooledObject<T>> mostLoaded = null;
782        K loadedKey = null;
783        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
784            final K k = entry.getKey();
785            final ObjectDeque<T> deque = entry.getValue();
786            if (deque != null) {
787                final LinkedBlockingDeque<PooledObject<T>> pool = deque.getIdleObjects();
788                final int queueLength = pool.getTakeQueueLength();
789                if (getNumActive(k) < maxTotalPerKeySave && queueLength > maxQueueLength) {
790                    maxQueueLength = queueLength;
791                    mostLoaded = pool;
792                    loadedKey = k;
793                }
794            }
795        }
796
797        // Attempt to add an instance to the most loaded pool
798        if (mostLoaded != null) {
799            register(loadedKey);
800            try {
801                final PooledObject<T> p = create(loadedKey);
802                if (p != null) {
803                    addIdleObject(loadedKey, p);
804                }
805            } catch (final Exception e) {
806                swallowException(e);
807            } finally {
808                deregister(loadedKey);
809            }
810        }
811    }
812
813    /**
814     * Checks to see if there are any threads currently waiting to borrow
815     * objects but are blocked waiting for more objects to become available.
816     *
817     * @return {@code true} if there is at least one thread waiting otherwise
818     *         {@code false}
819     */
820    private boolean hasBorrowWaiters() {
821        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
822            final ObjectDeque<T> deque = entry.getValue();
823            if (deque != null) {
824                final LinkedBlockingDeque<PooledObject<T>> pool =
825                        deque.getIdleObjects();
826                if(pool.hasTakeWaiters()) {
827                    return true;
828                }
829            }
830        }
831        return false;
832    }
833
834
835    /**
836     * {@inheritDoc}
837     * <p>
838     * Successive activations of this method examine objects in keyed sub-pools
839     * in sequence, cycling through the keys and examining objects in
840     * oldest-to-youngest order within the keyed sub-pools.
841     */
842    @Override
843    public void evict() throws Exception {
844        assertOpen();
845
846        if (getNumIdle() == 0) {
847            return;
848        }
849
850        PooledObject<T> underTest = null;
851        final EvictionPolicy<T> evictionPolicy = getEvictionPolicy();
852
853        synchronized (evictionLock) {
854            final EvictionConfig evictionConfig = new EvictionConfig(
855                    getMinEvictableIdleTimeMillis(),
856                    getSoftMinEvictableIdleTimeMillis(),
857                    getMinIdlePerKey());
858
859            final boolean testWhileIdle = getTestWhileIdle();
860
861            for (int i = 0, m = getNumTests(); i < m; i++) {
862                if(evictionIterator == null || !evictionIterator.hasNext()) {
863                    if (evictionKeyIterator == null ||
864                            !evictionKeyIterator.hasNext()) {
865                        final List<K> keyCopy = new ArrayList<>();
866                        final Lock readLock = keyLock.readLock();
867                        readLock.lock();
868                        try {
869                            keyCopy.addAll(poolKeyList);
870                        } finally {
871                            readLock.unlock();
872                        }
873                        evictionKeyIterator = keyCopy.iterator();
874                    }
875                    while (evictionKeyIterator.hasNext()) {
876                        evictionKey = evictionKeyIterator.next();
877                        final ObjectDeque<T> objectDeque = poolMap.get(evictionKey);
878                        if (objectDeque == null) {
879                            continue;
880                        }
881
882                        final Deque<PooledObject<T>> idleObjects = objectDeque.getIdleObjects();
883                        evictionIterator = new EvictionIterator(idleObjects);
884                        if (evictionIterator.hasNext()) {
885                            break;
886                        }
887                        evictionIterator = null;
888                    }
889                }
890                if (evictionIterator == null) {
891                    // Pools exhausted
892                    return;
893                }
894                final Deque<PooledObject<T>> idleObjects;
895                try {
896                    underTest = evictionIterator.next();
897                    idleObjects = evictionIterator.getIdleObjects();
898                } catch (final NoSuchElementException nsee) {
899                    // Object was borrowed in another thread
900                    // Don't count this as an eviction test so reduce i;
901                    i--;
902                    evictionIterator = null;
903                    continue;
904                }
905
906                if (!underTest.startEvictionTest()) {
907                    // Object was borrowed in another thread
908                    // Don't count this as an eviction test so reduce i;
909                    i--;
910                    continue;
911                }
912
913                // User provided eviction policy could throw all sorts of
914                // crazy exceptions. Protect against such an exception
915                // killing the eviction thread.
916                boolean evict;
917                try {
918                    evict = evictionPolicy.evict(evictionConfig, underTest,
919                            poolMap.get(evictionKey).getIdleObjects().size());
920                } catch (final Throwable t) {
921                    // Slightly convoluted as SwallowedExceptionListener
922                    // uses Exception rather than Throwable
923                    PoolUtils.checkRethrow(t);
924                    swallowException(new Exception(t));
925                    // Don't evict on error conditions
926                    evict = false;
927                }
928
929                if (evict) {
930                    destroy(evictionKey, underTest, true);
931                    destroyedByEvictorCount.incrementAndGet();
932                } else {
933                    if (testWhileIdle) {
934                        boolean active = false;
935                        try {
936                            factory.activateObject(evictionKey, underTest);
937                            active = true;
938                        } catch (final Exception e) {
939                            destroy(evictionKey, underTest, true);
940                            destroyedByEvictorCount.incrementAndGet();
941                        }
942                        if (active) {
943                            if (!factory.validateObject(evictionKey, underTest)) {
944                                destroy(evictionKey, underTest, true);
945                                destroyedByEvictorCount.incrementAndGet();
946                            } else {
947                                try {
948                                    factory.passivateObject(evictionKey, underTest);
949                                } catch (final Exception e) {
950                                    destroy(evictionKey, underTest, true);
951                                    destroyedByEvictorCount.incrementAndGet();
952                                }
953                            }
954                        }
955                    }
956                    if (!underTest.endEvictionTest(idleObjects)) {
957                        // TODO - May need to add code here once additional
958                        // states are used
959                    }
960                }
961            }
962        }
963    }
964
965    /**
966     * Create a new pooled object.
967     *
968     * @param key Key associated with new pooled object
969     *
970     * @return The new, wrapped pooled object
971     *
972     * @throws Exception If the objection creation fails
973     */
974    private PooledObject<T> create(final K key) throws Exception {
975        int maxTotalPerKeySave = getMaxTotalPerKey(); // Per key
976        if (maxTotalPerKeySave < 0) {
977            maxTotalPerKeySave = Integer.MAX_VALUE;
978        }
979        final int maxTotal = getMaxTotal();   // All keys
980
981        final ObjectDeque<T> objectDeque = poolMap.get(key);
982
983        // Check against the overall limit
984        boolean loop = true;
985
986        while (loop) {
987            final int newNumTotal = numTotal.incrementAndGet();
988            if (maxTotal > -1 && newNumTotal > maxTotal) {
989                numTotal.decrementAndGet();
990                if (getNumIdle() == 0) {
991                    return null;
992                }
993                clearOldest();
994            } else {
995                loop = false;
996            }
997        }
998
999        // Flag that indicates if create should:
1000        // - TRUE:  call the factory to create an object
1001        // - FALSE: return null
1002        // - null:  loop and re-test the condition that determines whether to
1003        //          call the factory
1004        Boolean create = null;
1005        while (create == null) {
1006            synchronized (objectDeque.makeObjectCountLock) {
1007                final long newCreateCount = objectDeque.getCreateCount().incrementAndGet();
1008                // Check against the per key limit
1009                if (newCreateCount > maxTotalPerKeySave) {
1010                    // The key is currently at capacity or in the process of
1011                    // making enough new objects to take it to capacity.
1012                    objectDeque.getCreateCount().decrementAndGet();
1013                    if (objectDeque.makeObjectCount == 0) {
1014                        // There are no makeObject() calls in progress for this
1015                        // key so the key is at capacity. Do not attempt to
1016                        // create a new object. Return and wait for an object to
1017                        // be returned.
1018                        create = Boolean.FALSE;
1019                    } else {
1020                        // There are makeObject() calls in progress that might
1021                        // bring the pool to capacity. Those calls might also
1022                        // fail so wait until they complete and then re-test if
1023                        // the pool is at capacity or not.
1024                        objectDeque.makeObjectCountLock.wait();
1025                    }
1026                } else {
1027                    // The pool is not at capacity. Create a new object.
1028                    objectDeque.makeObjectCount++;
1029                    create = Boolean.TRUE;
1030                }
1031            }
1032        }
1033
1034        if (!create.booleanValue()) {
1035            numTotal.decrementAndGet();
1036            return null;
1037        }
1038
1039        PooledObject<T> p = null;
1040        try {
1041            p = factory.makeObject(key);
1042            if (getTestOnCreate() && !factory.validateObject(key, p)) {
1043                numTotal.decrementAndGet();
1044                objectDeque.getCreateCount().decrementAndGet();
1045                return null;
1046            }
1047        } catch (final Exception e) {
1048            numTotal.decrementAndGet();
1049            objectDeque.getCreateCount().decrementAndGet();
1050            throw e;
1051        } finally {
1052            synchronized (objectDeque.makeObjectCountLock) {
1053                objectDeque.makeObjectCount--;
1054                objectDeque.makeObjectCountLock.notifyAll();
1055            }
1056        }
1057
1058        createdCount.incrementAndGet();
1059        objectDeque.getAllObjects().put(new IdentityWrapper<>(p.getObject()), p);
1060        return p;
1061    }
1062
1063    /**
1064     * Destroy the wrapped, pooled object.
1065     *
1066     * @param key The key associated with the object to destroy.
1067     * @param toDestroy The wrapped object to be destroyed
1068     * @param always Should the object be destroyed even if it is not currently
1069     *               in the set of idle objects for the given key
1070     * @return {@code true} if the object was destroyed, otherwise {@code false}
1071     * @throws Exception If the object destruction failed
1072     */
1073    private boolean destroy(final K key, final PooledObject<T> toDestroy, final boolean always)
1074            throws Exception {
1075
1076        final ObjectDeque<T> objectDeque = register(key);
1077
1078        try {
1079            final boolean isIdle = objectDeque.getIdleObjects().remove(toDestroy);
1080
1081            if (isIdle || always) {
1082                objectDeque.getAllObjects().remove(new IdentityWrapper<>(toDestroy.getObject()));
1083                toDestroy.invalidate();
1084
1085                try {
1086                    factory.destroyObject(key, toDestroy);
1087                } finally {
1088                    objectDeque.getCreateCount().decrementAndGet();
1089                    destroyedCount.incrementAndGet();
1090                    numTotal.decrementAndGet();
1091                }
1092                return true;
1093            }
1094            return false;
1095        } finally {
1096            deregister(key);
1097        }
1098    }
1099
1100
1101    /**
1102     * Register the use of a key by an object.
1103     * <p>
1104     * register() and deregister() must always be used as a pair.
1105     *
1106     * @param k The key to register
1107     *
1108     * @return The objects currently associated with the given key. If this
1109     *         method returns without throwing an exception then it will never
1110     *         return null.
1111     */
1112    private ObjectDeque<T> register(final K k) {
1113        Lock lock = keyLock.readLock();
1114        ObjectDeque<T> objectDeque = null;
1115        try {
1116            lock.lock();
1117            objectDeque = poolMap.get(k);
1118            if (objectDeque == null) {
1119                // Upgrade to write lock
1120                lock.unlock();
1121                lock = keyLock.writeLock();
1122                lock.lock();
1123                objectDeque = poolMap.get(k);
1124                if (objectDeque == null) {
1125                    objectDeque = new ObjectDeque<>(fairness);
1126                    objectDeque.getNumInterested().incrementAndGet();
1127                    // NOTE: Keys must always be added to both poolMap and
1128                    //       poolKeyList at the same time while protected by
1129                    //       keyLock.writeLock()
1130                    poolMap.put(k, objectDeque);
1131                    poolKeyList.add(k);
1132                } else {
1133                    objectDeque.getNumInterested().incrementAndGet();
1134                }
1135            } else {
1136                objectDeque.getNumInterested().incrementAndGet();
1137            }
1138        } finally {
1139            lock.unlock();
1140        }
1141        return objectDeque;
1142    }
1143
1144    /**
1145     * De-register the use of a key by an object.
1146     * <p>
1147     * register() and deregister() must always be used as a pair.
1148     *
1149     * @param k The key to de-register
1150     */
1151    private void deregister(final K k) {
1152        Lock lock = keyLock.readLock();
1153        ObjectDeque<T> objectDeque;
1154        try {
1155            lock.lock();
1156            objectDeque = poolMap.get(k);
1157            final long numInterested = objectDeque.getNumInterested().decrementAndGet();
1158            if (numInterested == 0 && objectDeque.getCreateCount().get() == 0) {
1159                // Potential to remove key
1160                // Upgrade to write lock
1161                lock.unlock();
1162                lock = keyLock.writeLock();
1163                lock.lock();
1164                if (objectDeque.getCreateCount().get() == 0 && objectDeque.getNumInterested().get() == 0) {
1165                    // NOTE: Keys must always be removed from both poolMap and
1166                    //       poolKeyList at the same time while protected by
1167                    //       keyLock.writeLock()
1168                    poolMap.remove(k);
1169                    poolKeyList.remove(k);
1170                }
1171            }
1172        } finally {
1173            lock.unlock();
1174        }
1175    }
1176
1177    @Override
1178    void ensureMinIdle() throws Exception {
1179        final int minIdlePerKeySave = getMinIdlePerKey();
1180        if (minIdlePerKeySave < 1) {
1181            return;
1182        }
1183
1184        for (final K k : poolMap.keySet()) {
1185            ensureMinIdle(k);
1186        }
1187    }
1188
1189    /**
1190     * Ensure that the configured number of minimum idle objects is available in
1191     * the pool for the given key.
1192     *
1193     * @param key The key to check for idle objects
1194     *
1195     * @throws Exception If a new object is required and cannot be created
1196     */
1197    private void ensureMinIdle(final K key) throws Exception {
1198        // Calculate current pool objects
1199        ObjectDeque<T> objectDeque = poolMap.get(key);
1200
1201        // objectDeque == null is OK here. It is handled correctly by both
1202        // methods called below.
1203
1204        // this method isn't synchronized so the
1205        // calculateDeficit is done at the beginning
1206        // as a loop limit and a second time inside the loop
1207        // to stop when another thread already returned the
1208        // needed objects
1209        final int deficit = calculateDeficit(objectDeque);
1210
1211        for (int i = 0; i < deficit && calculateDeficit(objectDeque) > 0; i++) {
1212            addObject(key);
1213            // If objectDeque was null, it won't be any more. Obtain a reference
1214            // to it so the deficit can be correctly calculated. It needs to
1215            // take account of objects created in other threads.
1216            if (objectDeque == null) {
1217                objectDeque = poolMap.get(key);
1218            }
1219        }
1220    }
1221
1222    /**
1223     * Create an object using the {@link KeyedPooledObjectFactory#makeObject
1224     * factory}, passivate it, and then place it in the idle object pool.
1225     * <code>addObject</code> is useful for "pre-loading" a pool with idle
1226     * objects.
1227     *
1228     * @param key the key a new instance should be added to
1229     *
1230     * @throws Exception when {@link KeyedPooledObjectFactory#makeObject}
1231     *                   fails.
1232     */
1233    @Override
1234    public void addObject(final K key) throws Exception {
1235        assertOpen();
1236        register(key);
1237        try {
1238            final PooledObject<T> p = create(key);
1239            addIdleObject(key, p);
1240        } finally {
1241            deregister(key);
1242        }
1243    }
1244
1245    /**
1246     * Add an object to the set of idle objects for a given key.
1247     *
1248     * @param key The key to associate with the idle object
1249     * @param p The wrapped object to add.
1250     *
1251     * @throws Exception If the associated factory fails to passivate the object
1252     */
1253    private void addIdleObject(final K key, final PooledObject<T> p) throws Exception {
1254
1255        if (p != null) {
1256            factory.passivateObject(key, p);
1257            final LinkedBlockingDeque<PooledObject<T>> idleObjects =
1258                    poolMap.get(key).getIdleObjects();
1259            if (getLifo()) {
1260                idleObjects.addFirst(p);
1261            } else {
1262                idleObjects.addLast(p);
1263            }
1264        }
1265    }
1266
1267    /**
1268     * Registers a key for pool control and ensures that
1269     * {@link #getMinIdlePerKey()} idle instances are created.
1270     *
1271     * @param key - The key to register for pool control.
1272     *
1273     * @throws Exception If the associated factory throws an exception
1274     */
1275    public void preparePool(final K key) throws Exception {
1276        final int minIdlePerKeySave = getMinIdlePerKey();
1277        if (minIdlePerKeySave < 1) {
1278            return;
1279        }
1280        ensureMinIdle(key);
1281    }
1282
1283    /**
1284     * Calculate the number of objects to test in a run of the idle object
1285     * evictor.
1286     *
1287     * @return The number of objects to test for validity
1288     */
1289    private int getNumTests() {
1290        final int totalIdle = getNumIdle();
1291        final int numTests = getNumTestsPerEvictionRun();
1292        if (numTests >= 0) {
1293            return Math.min(numTests, totalIdle);
1294        }
1295        return(int)(Math.ceil(totalIdle/Math.abs((double)numTests)));
1296    }
1297
1298    /**
1299     * Calculate the number of objects that need to be created to attempt to
1300     * maintain the minimum number of idle objects while not exceeded the limits
1301     * on the maximum number of objects either per key or totally.
1302     *
1303     * @param objectDeque   The set of objects to check
1304     *
1305     * @return The number of new objects to create
1306     */
1307    private int calculateDeficit(final ObjectDeque<T> objectDeque) {
1308
1309        if (objectDeque == null) {
1310            return getMinIdlePerKey();
1311        }
1312
1313        // Used more than once so keep a local copy so the value is consistent
1314        final int maxTotal = getMaxTotal();
1315        final int maxTotalPerKeySave = getMaxTotalPerKey();
1316
1317        int objectDefecit = 0;
1318
1319        // Calculate no of objects needed to be created, in order to have
1320        // the number of pooled objects < maxTotalPerKey();
1321        objectDefecit = getMinIdlePerKey() - objectDeque.getIdleObjects().size();
1322        if (maxTotalPerKeySave > 0) {
1323            final int growLimit = Math.max(0,
1324                    maxTotalPerKeySave - objectDeque.getIdleObjects().size());
1325            objectDefecit = Math.min(objectDefecit, growLimit);
1326        }
1327
1328        // Take the maxTotal limit into account
1329        if (maxTotal > 0) {
1330            final int growLimit = Math.max(0, maxTotal - getNumActive() - getNumIdle());
1331            objectDefecit = Math.min(objectDefecit, growLimit);
1332        }
1333
1334        return objectDefecit;
1335    }
1336
1337
1338    //--- JMX support ----------------------------------------------------------
1339
1340    @Override
1341    public Map<String,Integer> getNumActivePerKey() {
1342        final HashMap<String,Integer> result = new HashMap<>();
1343
1344        final Iterator<Entry<K,ObjectDeque<T>>> iter = poolMap.entrySet().iterator();
1345        while (iter.hasNext()) {
1346            final Entry<K,ObjectDeque<T>> entry = iter.next();
1347            if (entry != null) {
1348                final K key = entry.getKey();
1349                final ObjectDeque<T> objectDequeue = entry.getValue();
1350                if (key != null && objectDequeue != null) {
1351                    result.put(key.toString(), Integer.valueOf(
1352                            objectDequeue.getAllObjects().size() -
1353                            objectDequeue.getIdleObjects().size()));
1354                }
1355            }
1356        }
1357        return result;
1358    }
1359
1360    /**
1361     * Return an estimate of the number of threads currently blocked waiting for
1362     * an object from the pool. This is intended for monitoring only, not for
1363     * synchronization control.
1364     *
1365     * @return The estimate of the number of threads currently blocked waiting
1366     *         for an object from the pool
1367     */
1368    @Override
1369    public int getNumWaiters() {
1370        int result = 0;
1371
1372        if (getBlockWhenExhausted()) {
1373            final Iterator<ObjectDeque<T>> iter = poolMap.values().iterator();
1374
1375            while (iter.hasNext()) {
1376                // Assume no overflow
1377                result += iter.next().getIdleObjects().getTakeQueueLength();
1378            }
1379        }
1380
1381        return result;
1382    }
1383
1384    /**
1385     * Return an estimate of the number of threads currently blocked waiting for
1386     * an object from the pool for each key. This is intended for
1387     * monitoring only, not for synchronization control.
1388     *
1389     * @return The estimate of the number of threads currently blocked waiting
1390     *         for an object from the pool for each key
1391     */
1392    @Override
1393    public Map<String,Integer> getNumWaitersByKey() {
1394        final Map<String,Integer> result = new HashMap<>();
1395
1396        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
1397            final K k = entry.getKey();
1398            final ObjectDeque<T> deque = entry.getValue();
1399            if (deque != null) {
1400                if (getBlockWhenExhausted()) {
1401                    result.put(k.toString(), Integer.valueOf(
1402                            deque.getIdleObjects().getTakeQueueLength()));
1403                } else {
1404                    result.put(k.toString(), Integer.valueOf(0));
1405                }
1406            }
1407        }
1408        return result;
1409    }
1410
1411    /**
1412     * Provides information on all the objects in the pool, both idle (waiting
1413     * to be borrowed) and active (currently borrowed).
1414     * <p>
1415     * Note: This is named listAllObjects so it is presented as an operation via
1416     * JMX. That means it won't be invoked unless the explicitly requested
1417     * whereas all attributes will be automatically requested when viewing the
1418     * attributes for an object in a tool like JConsole.
1419     *
1420     * @return Information grouped by key on all the objects in the pool
1421     */
1422    @Override
1423    public Map<String,List<DefaultPooledObjectInfo>> listAllObjects() {
1424        final Map<String,List<DefaultPooledObjectInfo>> result =
1425                new HashMap<>();
1426
1427        for (final Map.Entry<K, ObjectDeque<T>> entry : poolMap.entrySet()) {
1428            final K k = entry.getKey();
1429            final ObjectDeque<T> deque = entry.getValue();
1430            if (deque != null) {
1431                final List<DefaultPooledObjectInfo> list =
1432                        new ArrayList<>();
1433                result.put(k.toString(), list);
1434                for (final PooledObject<T> p : deque.getAllObjects().values()) {
1435                    list.add(new DefaultPooledObjectInfo(p));
1436                }
1437            }
1438        }
1439        return result;
1440    }
1441
1442
1443    //--- inner classes ----------------------------------------------
1444
1445    /**
1446     * Maintains information on the per key queue for a given key.
1447     *
1448     * @param <S> type of objects in the pool
1449     */
1450    private class ObjectDeque<S> {
1451
1452        private final LinkedBlockingDeque<PooledObject<S>> idleObjects;
1453
1454        /*
1455         * Number of instances created - number destroyed.
1456         * Invariant: createCount <= maxTotalPerKey
1457         */
1458        private final AtomicInteger createCount = new AtomicInteger(0);
1459
1460        private long makeObjectCount = 0;
1461        private final Object makeObjectCountLock = new Object();
1462
1463        /*
1464         * The map is keyed on pooled instances, wrapped to ensure that
1465         * they work properly as keys.
1466         */
1467        private final Map<IdentityWrapper<S>, PooledObject<S>> allObjects =
1468                new ConcurrentHashMap<>();
1469
1470        /*
1471         * Number of threads with registered interest in this key.
1472         * register(K) increments this counter and deRegister(K) decrements it.
1473         * Invariant: empty keyed pool will not be dropped unless numInterested
1474         *            is 0.
1475         */
1476        private final AtomicLong numInterested = new AtomicLong(0);
1477
1478        /**
1479         * Create a new ObjecDeque with the given fairness policy.
1480         * @param fairness true means client threads waiting to borrow / return instances
1481         * will be served as if waiting in a FIFO queue.
1482         */
1483        public ObjectDeque(final boolean fairness) {
1484            idleObjects = new LinkedBlockingDeque<>(fairness);
1485        }
1486
1487        /**
1488         * Obtain the idle objects for the current key.
1489         *
1490         * @return The idle objects
1491         */
1492        public LinkedBlockingDeque<PooledObject<S>> getIdleObjects() {
1493            return idleObjects;
1494        }
1495
1496        /**
1497         * Obtain the count of the number of objects created for the current
1498         * key.
1499         *
1500         * @return The number of objects created for this key
1501         */
1502        public AtomicInteger getCreateCount() {
1503            return createCount;
1504        }
1505
1506        /**
1507         * Obtain the number of threads with an interest registered in this key.
1508         *
1509         * @return The number of threads with a registered interest in this key
1510         */
1511        public AtomicLong getNumInterested() {
1512            return numInterested;
1513        }
1514
1515        /**
1516         * Obtain all the objects for the current key.
1517         *
1518         * @return All the objects
1519         */
1520        public Map<IdentityWrapper<S>, PooledObject<S>> getAllObjects() {
1521            return allObjects;
1522        }
1523
1524        @Override
1525        public String toString() {
1526            final StringBuilder builder = new StringBuilder();
1527            builder.append("ObjectDeque [idleObjects=");
1528            builder.append(idleObjects);
1529            builder.append(", createCount=");
1530            builder.append(createCount);
1531            builder.append(", allObjects=");
1532            builder.append(allObjects);
1533            builder.append(", numInterested=");
1534            builder.append(numInterested);
1535            builder.append("]");
1536            return builder.toString();
1537        }
1538
1539    }
1540
1541    //--- configuration attributes ---------------------------------------------
1542    private volatile int maxIdlePerKey =
1543            GenericKeyedObjectPoolConfig.DEFAULT_MAX_IDLE_PER_KEY;
1544    private volatile int minIdlePerKey =
1545            GenericKeyedObjectPoolConfig.DEFAULT_MIN_IDLE_PER_KEY;
1546    private volatile int maxTotalPerKey =
1547            GenericKeyedObjectPoolConfig.DEFAULT_MAX_TOTAL_PER_KEY;
1548    private final KeyedPooledObjectFactory<K,T> factory;
1549    private final boolean fairness;
1550
1551
1552    //--- internal attributes --------------------------------------------------
1553
1554    /*
1555     * My hash of sub-pools (ObjectQueue). The list of keys <b>must</b> be kept
1556     * in step with {@link #poolKeyList} using {@link #keyLock} to ensure any
1557     * changes to the list of current keys is made in a thread-safe manner.
1558     */
1559    private final Map<K,ObjectDeque<T>> poolMap =
1560            new ConcurrentHashMap<>(); // @GuardedBy("keyLock") for write access (and some read access)
1561    /*
1562     * List of pool keys - used to control eviction order. The list of keys
1563     * <b>must</b> be kept in step with {@link #poolMap} using {@link #keyLock}
1564     * to ensure any changes to the list of current keys is made in a
1565     * thread-safe manner.
1566     */
1567    private final List<K> poolKeyList = new ArrayList<>(); // @GuardedBy("keyLock")
1568    private final ReadWriteLock keyLock = new ReentrantReadWriteLock(true);
1569    /*
1570     * The combined count of the currently active objects for all keys and those
1571     * in the process of being created. Under load, it may exceed
1572     * {@link #maxTotal} but there will never be more than {@link #maxTotal}
1573     * created at any one time.
1574     */
1575    private final AtomicInteger numTotal = new AtomicInteger(0);
1576    private Iterator<K> evictionKeyIterator = null; // @GuardedBy("evictionLock")
1577    private K evictionKey = null; // @GuardedBy("evictionLock")
1578
1579    // JMX specific attributes
1580    private static final String ONAME_BASE =
1581            "org.apache.commons.pool2:type=GenericKeyedObjectPool,name=";
1582
1583    @Override
1584    protected void toStringAppendFields(final StringBuilder builder) {
1585        super.toStringAppendFields(builder);
1586        builder.append(", maxIdlePerKey=");
1587        builder.append(maxIdlePerKey);
1588        builder.append(", minIdlePerKey=");
1589        builder.append(minIdlePerKey);
1590        builder.append(", maxTotalPerKey=");
1591        builder.append(maxTotalPerKey);
1592        builder.append(", factory=");
1593        builder.append(factory);
1594        builder.append(", fairness=");
1595        builder.append(fairness);
1596        builder.append(", poolMap=");
1597        builder.append(poolMap);
1598        builder.append(", poolKeyList=");
1599        builder.append(poolKeyList);
1600        builder.append(", keyLock=");
1601        builder.append(keyLock);
1602        builder.append(", numTotal=");
1603        builder.append(numTotal);
1604        builder.append(", evictionKeyIterator=");
1605        builder.append(evictionKeyIterator);
1606        builder.append(", evictionKey=");
1607        builder.append(evictionKey);
1608    }
1609}