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: */
017: package org.apache.cocoon.util;
018:
019: import java.util.Set;
020: import java.util.HashSet;
021: import java.util.NoSuchElementException;
022: import java.util.Map;
023: import java.util.Collection;
024: import java.util.Iterator;
025:
026: /**
027: * A MRUBucketMap is an efficient ThreadSafe implementation of a Map with
028: * addition of the removeLast method implementing LRU removal policy.
029: * <br />
030: * MRUBucketMap is based on the Avalon's BucketMap.
031: *
032: * @author <a href="mailto:vgritsenko@apache.org">Vadim Gritsenko</a>
033: * @deprecated Will be removed in Cocoon 2.2
034: * @version CVS $Id: MRUBucketMap.java 433543 2006-08-22 06:22:54Z crossley $
035: */
036: public final class MRUBucketMap implements Map {
037: private static final int DEFAULT_BUCKETS = 255;
038: private final Node[] m_buckets;
039: private final Object[] m_locks;
040: private final Node m_header = new Node();
041: private int m_size = 0;
042:
043: /**
044: * Creates map with default number of buckets.
045: */
046: public MRUBucketMap() {
047: this (DEFAULT_BUCKETS);
048: }
049:
050: /**
051: * Creates map with specified number of buckets.
052: */
053: public MRUBucketMap(int numBuckets) {
054: int size = Math.max(17, numBuckets);
055:
056: // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
057: if (size % 2 == 0) {
058: size--;
059: }
060:
061: m_buckets = new Node[size];
062: m_locks = new Object[size];
063:
064: for (int i = 0; i < size; i++) {
065: m_locks[i] = new Object();
066: }
067:
068: m_header.mru_next = m_header.mru_previous = m_header;
069: }
070:
071: private final int getHash(Object key) {
072: final int hash = key.hashCode() % m_buckets.length;
073: return (hash < 0) ? hash * -1 : hash;
074: }
075:
076: public Set keySet() {
077: Set keySet = new HashSet();
078:
079: for (int i = 0; i < m_buckets.length; i++) {
080: synchronized (m_locks[i]) {
081: Node n = m_buckets[i];
082:
083: while (n != null) {
084: keySet.add(n.key);
085: n = n.next;
086: }
087: }
088: }
089:
090: return keySet;
091: }
092:
093: /**
094: * Returns the current number of key, value pairs.
095: */
096: public int size() {
097: return m_size;
098: }
099:
100: /**
101: * Put a reference in the Map.
102: */
103: public Object put(final Object key, final Object value) {
104: if (null == key || null == value) {
105: return null;
106: }
107:
108: int isNew = 0;
109: Node node;
110: Object oldValue = null;
111:
112: int hash = getHash(key);
113:
114: synchronized (m_locks[hash]) {
115: Node n = m_buckets[hash];
116: if (n == null) {
117: node = new Node();
118: node.key = key;
119: node.value = value;
120: m_buckets[hash] = node;
121: isNew = 1;
122: } else {
123: // Set n to the last node in the linked list. Check each key along the way
124: // If the key is found, then change the value of that node and return
125: // the old value.
126: for (Node next = n; next != null; next = next.next) {
127: n = next;
128:
129: if (n.key.equals(key)) {
130: oldValue = n.value;
131: n.value = value;
132: break;
133: }
134: }
135:
136: if (oldValue == null) {
137: // The key was not found in the current list of nodes,
138: // add it to the end in a new node.
139: node = new Node();
140: node.key = key;
141: node.value = value;
142: n.next = node;
143: isNew = 1;
144: } else {
145: // The key was found in the list. Move it to the head.
146: node = n;
147: }
148: }
149: }
150:
151: synchronized (m_header) {
152: if (isNew == 0) {
153: // Remove
154: node.mru_previous.mru_next = node.mru_next;
155: node.mru_next.mru_previous = node.mru_previous;
156: }
157: // Move node to the head.
158: node.mru_previous = m_header;
159: node.mru_next = m_header.mru_next;
160: node.mru_previous.mru_next = node;
161: node.mru_next.mru_previous = node;
162: m_size += isNew;
163: }
164:
165: return oldValue;
166: }
167:
168: public Object get(final Object key) {
169: if (null == key) {
170: return null;
171: }
172:
173: Node n;
174:
175: int hash = getHash(key);
176:
177: synchronized (m_locks[hash]) {
178: n = m_buckets[hash];
179:
180: while (n != null) {
181: if (n.key.equals(key)) {
182: break;
183: }
184:
185: n = n.next;
186: }
187: }
188:
189: if (n != null) {
190: synchronized (m_header) {
191: // Remove
192: n.mru_previous.mru_next = n.mru_next;
193: n.mru_next.mru_previous = n.mru_previous;
194: // Add first
195: n.mru_previous = m_header;
196: n.mru_next = m_header.mru_next;
197: n.mru_previous.mru_next = n;
198: n.mru_next.mru_previous = n;
199: }
200: return n.value;
201: }
202:
203: return null;
204: }
205:
206: public boolean containsKey(final Object key) {
207: if (null == key) {
208: return false;
209: }
210:
211: int hash = getHash(key);
212:
213: synchronized (m_locks[hash]) {
214: Node n = m_buckets[hash];
215:
216: while (n != null) {
217: if (n.key.equals(key)) {
218: return true;
219: }
220:
221: n = n.next;
222: }
223: }
224:
225: return false;
226: }
227:
228: public boolean containsValue(final Object value) {
229: if (null == value) {
230: return false;
231: }
232:
233: synchronized (m_header) {
234: for (Node n = m_header.mru_next; n != m_header; n = n.mru_next) {
235: if (n.value.equals(value)) {
236: return true;
237: }
238: }
239: }
240:
241: return false;
242: }
243:
244: public Collection values() {
245: Set valueSet = new HashSet();
246:
247: synchronized (m_header) {
248: for (Node n = m_header.mru_next; n != m_header; n = n.mru_next) {
249: valueSet.add(n.value);
250: }
251: }
252:
253: return valueSet;
254: }
255:
256: public Set entrySet() {
257: Set entrySet = new HashSet();
258:
259: synchronized (m_header) {
260: for (Node n = m_header.mru_next; n != m_header; n = n.mru_next) {
261: entrySet.add(n);
262: }
263: }
264:
265: return entrySet;
266: }
267:
268: /**
269: * Add all the contents of one Map into this one.
270: */
271: public void putAll(Map other) {
272: for (Iterator i = other.entrySet().iterator(); i.hasNext();) {
273: Map.Entry me = (Map.Entry) i.next();
274: put(me.getKey(), me.getValue());
275: }
276: }
277:
278: public Object remove(Object key) {
279: if (null == key) {
280: return null;
281: }
282:
283: Node n;
284:
285: int hash = getHash(key);
286:
287: synchronized (m_locks[hash]) {
288: n = m_buckets[hash];
289: Node prev = null;
290:
291: while (n != null) {
292: if (n.key.equals(key)) {
293: // Remove this node from the linked list of nodes.
294: if (null == prev) {
295: // This node was the head, set the next node to be the new head.
296: m_buckets[hash] = n.next;
297: } else {
298: // Set the next node of the previous node to be the node after this one.
299: prev.next = n.next;
300: }
301:
302: break;
303: }
304:
305: prev = n;
306: n = n.next;
307: }
308: }
309:
310: if (n != null) {
311: synchronized (m_header) {
312: // Remove
313: n.mru_previous.mru_next = n.mru_next;
314: n.mru_next.mru_previous = n.mru_previous;
315: m_size--;
316: }
317:
318: return n.value;
319: }
320:
321: return null;
322: }
323:
324: public final boolean isEmpty() {
325: return m_size == 0;
326: }
327:
328: public final void clear() {
329: synchronized (m_header) {
330: for (int i = 0; i < m_buckets.length; i++) {
331: m_buckets[i] = null;
332: }
333:
334: m_header.mru_next = m_header.mru_previous = m_header;
335: m_size = 0;
336: }
337: }
338:
339: public Map.Entry removeLast() {
340: Node node = m_header.mru_previous;
341: if (node == m_header) {
342: throw new NoSuchElementException("MRUBucketMap is empty");
343: }
344:
345: remove(node.key);
346: node.mru_next = null;
347: node.mru_previous = null;
348: return node;
349: }
350:
351: private static final class Node implements Map.Entry {
352: protected Object key;
353: protected Object value;
354: protected Node next;
355:
356: protected Node mru_previous;
357: protected Node mru_next;
358:
359: public Object getKey() {
360: return key;
361: }
362:
363: public Object getValue() {
364: return value;
365: }
366:
367: public Object setValue(Object val) {
368: Object retVal = value;
369: value = val;
370: return retVal;
371: }
372: }
373:
374: static class X {
375: String x;
376:
377: public X(String s) {
378: x = s;
379: }
380:
381: public int hashCode() {
382: return 1;
383: }
384:
385: public boolean equals(Object obj) {
386: return this == obj;
387: }
388:
389: public String toString() {
390: return x;
391: }
392: }
393: }
|