001: /*
002: (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP, all rights reserved.
003: [See end of file]
004: $Id: NodeCache.java,v 1.6 2008/01/02 12:06:55 andy_seaborne Exp $
005: */
006:
007: package com.hp.hpl.jena.graph;
008:
009: /**
010: A NodeCache caches nodes according to their labels, to reduce store turnover
011: at the expense of some additional computation. The cache is represented as an
012: array indexed by the reduced hashcode of the labels of the nodes it contains.
013: Only the most recent node with any given reduced hash is kept. This tactic
014: means that we don't need to have any explicit cache-clearing code in normal
015: oepration.
016:
017: @author kers
018: */
019: public class NodeCache {
020: /**
021: The defined size of the cache; 5000 is mostly guesswork. (It didn't *quite*
022: fill up when running the tests and had about an 85% hit-rate).
023: */
024: protected static final int SIZE = 5000;
025:
026: /**
027: The cache nodes, indexed by their label's reduced hash.
028: */
029: protected final Node[] nodes = new Node[SIZE];
030:
031: protected static final boolean counting = false;
032:
033: /**
034: Wipe the cache of all entries.
035: */
036: public void clear() {
037: for (int i = 0; i < SIZE; i += 1)
038: nodes[i] = null;
039: }
040:
041: public int size() {
042: return 0;
043: }
044:
045: private int hits = 0;
046: private int misses = 0;
047:
048: /**
049: Answer the number of used slots in the cache
050: */
051: private int count() {
052: int result = 0;
053: for (int i = 0; i < SIZE; i += 1)
054: if (nodes[i] != null)
055: result += 1;
056: return result;
057: }
058:
059: /**
060: Answer the node with the given <code>label</code> in the cache, or
061: <code>null</code> if there isn't one. Selects the slot in the cache by the
062: reduced hash of the label, and confirms that the Node is the right one using
063: .equals() on this label and that node's label.
064: */
065: public Node get(Object label) {
066: Node present = nodes[(label.hashCode() & 0x7fffffff) % SIZE];
067: if (counting) {
068: if (present == null || !label.equals(present.label))
069: misses += 1;
070: else
071: hits += 1;
072: if ((misses + hits) % 100 == 0)
073: System.err.println(">> hits: " + hits + ", misses: "
074: + misses + ", occ: " + count() + "/" + SIZE);
075: }
076: return present == null || !label.equals(present.label) ? null
077: : present;
078: }
079:
080: /**
081: Record in the cache the designated Node, using the given label (which must
082: be .equals() to the Node's label).
083: */
084: public void put(Object label, Node cached) {
085: nodes[(label.hashCode() & 0x7fffffff) % SIZE] = cached;
086: }
087: }
088:
089: /*
090: (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
091: All rights reserved.
092:
093: Redistribution and use in source and binary forms, with or without
094: modification, are permitted provided that the following conditions
095: are met:
096:
097: 1. Redistributions of source code must retain the above copyright
098: notice, this list of conditions and the following disclaimer.
099:
100: 2. Redistributions in binary form must reproduce the above copyright
101: notice, this list of conditions and the following disclaimer in the
102: documentation and/or other materials provided with the distribution.
103:
104: 3. The name of the author may not be used to endorse or promote products
105: derived from this software without specific prior written permission.
106:
107: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
108: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
109: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
110: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
111: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
112: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
113: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
114: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
115: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
116: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
117: */
|