You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tomcat.apache.org by re...@apache.org on 2003/04/24 19:02:46 UTC
cvs commit: jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources CacheEntry.java ResourceCache.java ProxyDirContext.java
remm 2003/04/24 10:02:45
Modified: catalina/src/share/org/apache/naming/resources
ProxyDirContext.java
Added: catalina/src/share/org/apache/naming/resources
CacheEntry.java ResourceCache.java
Log:
- Move the main cache algorithm to a separate class.
Revision Changes Path
1.10 +34 -332 jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources/ProxyDirContext.java
Index: ProxyDirContext.java
===================================================================
RCS file: /home/cvs/jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources/ProxyDirContext.java,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- ProxyDirContext.java 24 Apr 2003 07:21:47 -0000 1.9
+++ ProxyDirContext.java 24 Apr 2003 17:02:44 -0000 1.10
@@ -101,7 +101,6 @@
public static final String CONTEXT = "context";
public static final String HOST = "host";
- public static final int INCREMENT = 32;
// ----------------------------------------------------------- Constructors
@@ -117,11 +116,16 @@
// Initialize parameters based on the associated dir context, like
// the caching policy.
if (((BaseDirContext) dirContext).isCached()) {
+ try {
+ cache = (ResourceCache)
+ Class.forName(cacheClassName).newInstance();
+ } catch (Exception e) {
+ //FIXME
+ e.printStackTrace();
+ }
cacheTTL = ((BaseDirContext) dirContext).getCacheTTL();
cacheObjectMaxSize =
((BaseDirContext) dirContext).getCacheObjectMaxSize();
- cache = new CacheEntry[0];
- notFoundCache = new ThreadLocal();
}
}
hostName = (String) env.get(HOST);
@@ -198,22 +202,16 @@
/**
- * Cache.
- * Path -> Cache entry.
+ * Cache class.
*/
- protected CacheEntry[] cache = null;
+ protected String cacheClassName =
+ "org.apache.naming.resources.ResourceCache";
/**
- * Current cache size in KB.
- */
- protected int cacheSize = 0;
-
-
- /**
- * Thread local cache for not found resources.
+ * Cache.
*/
- protected ThreadLocal notFoundCache = null;
+ protected ResourceCache cache = null;
/**
@@ -225,44 +223,7 @@
/**
* Max size of resources which will have their content cached.
*/
- protected int cacheMaxSize = 10240; // 10 MB
-
-
- /**
- * Max size of resources which will have their content cached.
- */
- protected int cacheObjectMaxSize = cacheMaxSize / 20; // 512 KB
-
-
- /**
- * Max amount of removals during a make space.
- */
- protected int maxMakeSpaceIterations = 10;
-
-
- /**
- * Entry hit ratio at which an entry will never be removed from the cache.
- * Compared with entry.access / hitsCount
- */
- protected long desiredEntryAccessRatio = 3;
-
-
- /**
- * Spare amount of not found entries.
- */
- protected int spareNotFoundEntries = 10;
-
-
- /**
- * Number of accesses to the cache.
- */
- protected long accessCount = 0;
-
-
- /**
- * Number of cache hits.
- */
- protected long hitsCount = 0;
+ protected int cacheObjectMaxSize = 512; // 512 KB
/**
@@ -276,6 +237,14 @@
/**
+ * Get the cache used for this context.
+ */
+ public ResourceCache getCache() {
+ return cache;
+ }
+
+
+ /**
* Return the actual directory context we are wrapping.
*/
public DirContext getDirContext() {
@@ -310,34 +279,6 @@
}
- /**
- * Return the access count.
- * Note: Update is not synced, so the number may not be completely
- * accurate.
- */
- public long getAccessCount() {
- return accessCount;
- }
-
-
- /**
- * Return the number of cache hits.
- * Note: Update is not synced, so the number may not be completely
- * accurate.
- */
- public long getHitsCount() {
- return hitsCount;
- }
-
-
- /**
- * Return the current cache size in KB.
- */
- public int getCacheSize() {
- return cacheSize;
- }
-
-
// -------------------------------------------------------- Context Methods
@@ -783,7 +724,7 @@
public Name composeName(Name name, Name prefix)
throws NamingException {
prefix = (Name) name.clone();
- return prefix.addAll(name);
+ return prefix.addAll(name);
}
@@ -1486,20 +1427,7 @@
throws NamingException {
if (cache == null)
return (null);
- CacheEntry cacheEntry = null;
- accessCount++;
- int pos = find(cache, name);
- if ((pos != -1) && (name.equals(cache[pos].name))) {
- cacheEntry = cache[pos];
- }
- if (cacheEntry == null) {
- HashMap localCache = (HashMap) notFoundCache.get();
- if (localCache == null) {
- notFoundCache.set(new HashMap());
- }
- cacheEntry =
- (CacheEntry) ((HashMap) notFoundCache.get()).get(name);
- }
+ CacheEntry cacheEntry = cache.lookup(name);
if (cacheEntry == null) {
cacheEntry = new CacheEntry();
cacheEntry.name = name;
@@ -1516,7 +1444,6 @@
}
}
cacheEntry.accessCount++;
- hitsCount++;
}
if (!cacheEntry.exists) {
throw notFoundException;
@@ -1656,25 +1583,11 @@
entry.timestamp = System.currentTimeMillis() + cacheTTL;
// Add new entry to cache
- synchronized (this) {
+ synchronized (cache) {
// Check cache size, and remove elements if too big
- if (!makeSpace(entry.size)) {
- // Don't cache
- return;
+ if (cache.allocate(entry.size)) {
+ cache.load(entry);
}
- if (exists) {
- CacheEntry[] newCache = new CacheEntry[cache.length + 1];
- if (insertMap(cache, newCache, entry)) {
- cache = newCache;
- }
- } else {
- HashMap localCache = (HashMap) notFoundCache.get();
- if (localCache == null) {
- notFoundCache.set(new HashMap());
- }
- ((HashMap) notFoundCache.get()).put(name, entry);
- }
- cacheSize += entry.size;
}
}
@@ -1684,224 +1597,13 @@
* Remove entry from cache.
*/
protected boolean cacheUnload(String name) {
- if ((cache == null) || (cache.length==0)) {
- return false;
- }
- synchronized (this) {
- CacheEntry[] newCache = new CacheEntry[cache.length - 1];
- CacheEntry removedEntry = removeMap(cache, newCache, name);
- if (removedEntry != null) {
- cache = newCache;
- cacheSize -= removedEntry.size;
- return true;
- } else if (((HashMap) notFoundCache.get()).remove(name) != null) {
- cacheSize--;
- return true;
- }
- return false;
- }
- }
-
-
- /**
- * Make space for a new entry.
- */
- protected boolean makeSpace(int space) {
-
- int toFree = space - (cacheMaxSize - cacheSize);
-
- if (toFree < 0) {
- return true;
- }
-
- HashMap localNotFoundCache = (HashMap) notFoundCache.get();
- int size = localNotFoundCache.size();
- if (size > spareNotFoundEntries) {
- localNotFoundCache.clear();
- cacheSize -= size;
- toFree -= size;
- }
-
- if (toFree < 0) {
- return true;
- }
-
- int attempts = 0;
- long totalSpace = 0;
- int[] toRemove = new int[maxMakeSpaceIterations];
- while (toFree > 0) {
- if (attempts == maxMakeSpaceIterations) {
- // Give up, no changes are made to the current cache
- return false;
- }
- if (toFree > 0) {
- // Randomly select an entry in the array
- int entryPos = -1;
- while (true) {
- entryPos = (int) Math.round(Math.random()
- * (cache.length - 1));
- // Guarantee uniqueness
- for (int i = 0; i < attempts; i++) {
- if (toRemove[i] == entryPos) {
- continue;
- }
- }
- break;
- }
- long entryAccessRatio =
- ((cache[entryPos].accessCount * 100) / accessCount);
- if (entryAccessRatio < desiredEntryAccessRatio) {
- toRemove[attempts] = entryPos;
- totalSpace += cache[entryPos].size;
- toFree -= cache[entryPos].size;
- }
- }
- attempts++;
- }
-
- // Now remove the selected entries
- java.util.Arrays.sort(toRemove, 0, attempts);
- CacheEntry[] newCache = new CacheEntry[cache.length - attempts];
- int pos = 0;
- for (int i = 0; i < attempts; i++) {
- System.arraycopy(cache, pos, newCache, pos - i, toRemove[i] - pos);
- pos = toRemove[i] + 1;
- // Special case: last element
- if (pos == cache.length) {
- break;
- }
- }
- cache = newCache;
- cacheSize -= totalSpace;
-
- return true;
-
- }
-
-
- /**
- * Find a map elemnt given its name in a sorted array of map elements.
- * This will return the index for the closest inferior or equal item in the
- * given array.
- */
- private static final int find(CacheEntry[] map, String name) {
-
- int a = 0;
- int b = map.length - 1;
-
- // Special cases: -1 and 0
- if (b == -1) {
- return -1;
- }
- if (name.compareTo(map[0].name) < 0) {
- return -1;
- }
- if (b == 0) {
- return 0;
- }
-
- int i = 0;
- while (true) {
- i = (b + a) / 2;
- int result = name.compareTo(map[i].name);
- if (result > 0) {
- a = i;
- } else if (result == 0) {
- return i;
- } else {
- b = i;
- }
- if ((b - a) == 1) {
- int result2 = name.compareTo(map[b].name);
- if (result2 < 0) {
- return a;
- } else {
- return b;
- }
- }
- }
-
- }
-
-
- /**
- * Insert into the right place in a sorted MapElement array, and prevent
- * duplicates.
- */
- private static final boolean insertMap
- (CacheEntry[] oldMap, CacheEntry[] newMap, CacheEntry newElement) {
- int pos = find(oldMap, newElement.name);
- if ((pos != -1) && (newElement.name.equals(oldMap[pos].name))) {
+ if (cache == null)
return false;
+ synchronized (cache) {
+ return cache.unload(name);
}
- System.arraycopy(oldMap, 0, newMap, 0, pos + 1);
- newMap[pos + 1] = newElement;
- System.arraycopy
- (oldMap, pos + 1, newMap, pos + 2, oldMap.length - pos - 1);
- return true;
- }
-
-
- /**
- * Insert into the right place in a sorted MapElement array.
- */
- private static final CacheEntry removeMap
- (CacheEntry[] oldMap, CacheEntry[] newMap, String name) {
- int pos = find(oldMap, name);
- if ((pos != -1) && (name.equals(oldMap[pos].name))) {
- System.arraycopy(oldMap, 0, newMap, 0, pos);
- System.arraycopy(oldMap, pos + 1, newMap, pos,
- oldMap.length - pos - 1);
- return oldMap[pos];
- }
- return null;
- }
-
-
- // ------------------------------------------------- CacheEntry Inner Class
-
-
- protected class CacheEntry {
-
-
- // ------------------------------------------------- Instance Variables
-
-
- long timestamp = -1;
- String name = null;
- ResourceAttributes attributes = null;
- Resource resource = null;
- DirContext context = null;
- boolean exists = true;
- long accessCount = 0;
- int size = 1;
-
-
- // ----------------------------------------------------- Public Methods
-
-
- public void recycle() {
- timestamp = -1;
- name = null;
- attributes = null;
- resource = null;
- context = null;
- exists = true;
- accessCount = 0;
- size = 1;
- }
-
-
- public String toString() {
- return ("Cache entry: " + name + "\n"
- + "Exists: " + exists + "\n"
- + "Attributes: " + attributes + "\n"
- + "Resource: " + resource + "\n"
- + "Context: " + context);
- }
-
-
}
}
+
1.1 jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources/CacheEntry.java
Index: CacheEntry.java
===================================================================
/*
* $Header: /home/cvs/jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources/CacheEntry.java,v 1.1 2003/04/24 17:02:44 remm Exp $
* $Revision: 1.1 $
* $Date: 2003/04/24 17:02:44 $
*
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowlegement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowlegement may appear in the software itself,
* if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "The Jakarta Project", "Tomcat", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Group.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
* [Additional notices, if required by prior licensing conditions]
*
*/
package org.apache.naming.resources;
import javax.naming.directory.DirContext;
/**
* Implements a cache entry.
*
* @author <a href="mailto:remm@apache.org">Remy Maucherat</a>
* @version $Revision: 1.1 $
*/
public class CacheEntry {
// ------------------------------------------------- Instance Variables
public long timestamp = -1;
public String name = null;
public ResourceAttributes attributes = null;
public Resource resource = null;
public DirContext context = null;
public boolean exists = true;
public long accessCount = 0;
public int size = 1;
// ----------------------------------------------------- Public Methods
public void recycle() {
timestamp = -1;
name = null;
attributes = null;
resource = null;
context = null;
exists = true;
accessCount = 0;
size = 1;
}
public String toString() {
return ("Cache entry: " + name + "\n"
+ "Exists: " + exists + "\n"
+ "Attributes: " + attributes + "\n"
+ "Resource: " + resource + "\n"
+ "Context: " + context);
}
}
1.1 jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources/ResourceCache.java
Index: ResourceCache.java
===================================================================
/*
* $Header: /home/cvs/jakarta-tomcat-catalina/catalina/src/share/org/apache/naming/resources/ResourceCache.java,v 1.1 2003/04/24 17:02:45 remm Exp $
* $Revision: 1.1 $
* $Date: 2003/04/24 17:02:45 $
*
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowlegement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowlegement may appear in the software itself,
* if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "The Jakarta Project", "Tomcat", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Group.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
* [Additional notices, if required by prior licensing conditions]
*
*/
package org.apache.naming.resources;
import java.util.HashMap;
/**
* Implements a special purpose cache.
*
* @author <a href="mailto:remm@apache.org">Remy Maucherat</a>
* @version $Revision: 1.1 $
*/
public class ResourceCache {
// ----------------------------------------------------------- Constructors
public ResourceCache() {
}
// ----------------------------------------------------- Instance Variables
/**
* Cache.
* Path -> Cache entry.
*/
protected CacheEntry[] cache = new CacheEntry[0];
/**
* Not found cache.
*/
protected HashMap notFoundCache = new HashMap();
/**
* Max size of resources which will have their content cached.
*/
protected int cacheMaxSize = 10240; // 10 MB
/**
* Max amount of removals during a make space.
*/
protected int maxAllocateIterations = 10;
/**
* Entry hit ratio at which an entry will never be removed from the cache.
* Compared with entry.access / hitsCount
*/
protected long desiredEntryAccessRatio = 3;
/**
* Spare amount of not found entries.
*/
protected int spareNotFoundEntries = 500;
/**
* Current cache size in KB.
*/
protected int cacheSize = 0;
/**
* Number of accesses to the cache.
*/
protected long accessCount = 0;
/**
* Number of cache hits.
*/
protected long hitsCount = 0;
// ------------------------------------------------------------- Properties
/**
* Return the access count.
* Note: Update is not synced, so the number may not be completely
* accurate.
*/
public long getAccessCount() {
return accessCount;
}
/**
* Return the maximum size of the cache in KB.
*/
public int getCacheMaxSize() {
return cacheMaxSize;
}
/**
* Set the maximum size of the cache in KB.
*/
public void setCacheMaxSize(int cacheMaxSize) {
this.cacheMaxSize = cacheMaxSize;
}
/**
* Return the current cache size in KB.
*/
public int getCacheSize() {
return cacheSize;
}
/**
* Return desired entry access ratio.
*/
public long getDesiredEntryAccessRatio() {
return desiredEntryAccessRatio;
}
/**
* Set the desired entry access ratio.
*/
public void setDesiredEntryAccessRatio(long desiredEntryAccessRatio) {
this.desiredEntryAccessRatio = desiredEntryAccessRatio;
}
/**
* Return the number of cache hits.
* Note: Update is not synced, so the number may not be completely
* accurate.
*/
public long getHitsCount() {
return hitsCount;
}
/**
* Return the maximum amount of iterations during a space allocation.
*/
public int getMaxAllocateIterations() {
return maxAllocateIterations;
}
/**
* Set the maximum amount of iterations during a space allocation.
*/
public void setMaxAllocateIterations(int maxAllocateIterations) {
this.maxAllocateIterations = maxAllocateIterations;
}
/**
* Return the amount of spare not found entries.
*/
public int getSpareNotFoundEntries() {
return spareNotFoundEntries;
}
/**
* Set the amount of spare not found entries.
*/
public void setSpareNotFoundEntries(int spareNotFoundEntries) {
this.spareNotFoundEntries = spareNotFoundEntries;
}
// --------------------------------------------------------- Public Methods
public boolean allocate(int space) {
int toFree = space - (cacheMaxSize - cacheSize);
if (toFree < 0) {
return true;
}
int size = notFoundCache.size();
if (size > spareNotFoundEntries) {
notFoundCache.clear();
cacheSize -= size;
toFree -= size;
}
if (toFree < 0) {
return true;
}
int attempts = 0;
long totalSpace = 0;
int[] toRemove = new int[maxAllocateIterations];
while (toFree > 0) {
if (attempts == maxAllocateIterations) {
// Give up, no changes are made to the current cache
return false;
}
if (toFree > 0) {
// Randomly select an entry in the array
int entryPos = -1;
while (true) {
entryPos = (int) Math.round(Math.random()
* (cache.length - 1));
// Guarantee uniqueness
for (int i = 0; i < attempts; i++) {
if (toRemove[i] == entryPos) {
continue;
}
}
break;
}
long entryAccessRatio =
((cache[entryPos].accessCount * 100) / accessCount);
if (entryAccessRatio < desiredEntryAccessRatio) {
toRemove[attempts] = entryPos;
totalSpace += cache[entryPos].size;
toFree -= cache[entryPos].size;
}
}
attempts++;
}
// Now remove the selected entries
java.util.Arrays.sort(toRemove, 0, attempts);
CacheEntry[] newCache = new CacheEntry[cache.length - attempts];
int pos = 0;
for (int i = 0; i < attempts; i++) {
System.arraycopy(cache, pos, newCache, pos - i, toRemove[i] - pos);
pos = toRemove[i] + 1;
// Special case: last element
if (pos == cache.length) {
break;
}
}
cache = newCache;
cacheSize -= totalSpace;
return true;
}
public CacheEntry lookup(String name) {
CacheEntry cacheEntry = null;
accessCount++;
int pos = find(cache, name);
if ((pos != -1) && (name.equals(cache[pos].name))) {
cacheEntry = cache[pos];
}
if (cacheEntry == null) {
try {
cacheEntry = (CacheEntry) notFoundCache.get(name);
} catch (Exception e) {
// Ignore: the reliability of this lookup is not critical
}
}
if (cacheEntry != null) {
hitsCount++;
}
return cacheEntry;
}
public void load(CacheEntry entry) {
if (entry.exists) {
insertCache(entry);
} else {
notFoundCache.put(entry.name, entry);
}
cacheSize += entry.size;
}
public boolean unload(String name) {
CacheEntry removedEntry = removeCache(name);
if (removedEntry != null) {
cacheSize -= removedEntry.size;
return true;
} else if (notFoundCache.remove(name) != null) {
cacheSize--;
return true;
}
return false;
}
/**
* Find a map elemnt given its name in a sorted array of map elements.
* This will return the index for the closest inferior or equal item in the
* given array.
*/
private static final int find(CacheEntry[] map, String name) {
int a = 0;
int b = map.length - 1;
// Special cases: -1 and 0
if (b == -1) {
return -1;
}
if (name.compareTo(map[0].name) < 0) {
return -1;
}
if (b == 0) {
return 0;
}
int i = 0;
while (true) {
i = (b + a) / 2;
int result = name.compareTo(map[i].name);
if (result > 0) {
a = i;
} else if (result == 0) {
return i;
} else {
b = i;
}
if ((b - a) == 1) {
int result2 = name.compareTo(map[b].name);
if (result2 < 0) {
return a;
} else {
return b;
}
}
}
}
/**
* Insert into the right place in a sorted MapElement array, and prevent
* duplicates.
*/
private final boolean insertCache(CacheEntry newElement) {
CacheEntry[] oldCache = cache;
int pos = find(oldCache, newElement.name);
if ((pos != -1) && (newElement.name.equals(oldCache[pos].name))) {
return false;
}
CacheEntry[] newCache = new CacheEntry[cache.length + 1];
System.arraycopy(oldCache, 0, newCache, 0, pos + 1);
newCache[pos + 1] = newElement;
System.arraycopy
(oldCache, pos + 1, newCache, pos + 2, oldCache.length - pos - 1);
cache = newCache;
return true;
}
/**
* Insert into the right place in a sorted MapElement array.
*/
private final CacheEntry removeCache(String name) {
CacheEntry[] oldCache = cache;
int pos = find(oldCache, name);
if ((pos != -1) && (name.equals(oldCache[pos].name))) {
CacheEntry[] newCache = new CacheEntry[cache.length - 1];
System.arraycopy(oldCache, 0, newCache, 0, pos);
System.arraycopy(oldCache, pos + 1, newCache, pos,
oldCache.length - pos - 1);
cache = newCache;
return oldCache[pos];
}
return null;
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: tomcat-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: tomcat-dev-help@jakarta.apache.org