001: /*
002: (c) Copyright 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
003: All rights reserved - see end of file.
004: $Id: HashedBunchMap.java,v 1.14 2008/01/15 08:19:16 chris-dollin Exp $
005: */
006: package com.hp.hpl.jena.mem;
007:
008: import com.hp.hpl.jena.shared.BrokenException;
009:
010: /**
011: An implementation of BunchMap that does open-addressed hashing.
012: @author kers
013: */
014: public class HashedBunchMap extends HashCommon implements BunchMap {
015: protected TripleBunch[] values;
016:
017: public HashedBunchMap() {
018: super (10);
019: values = new TripleBunch[capacity];
020: }
021:
022: /**
023: Clear this map: all entries are removed. The keys <i>and value</i> array
024: elements are set to null (so the values may be garbage-collected).
025: */
026: public void clear() {
027: size = 0;
028: for (int i = 0; i < capacity; i += 1)
029: keys[i] = values[i] = null;
030: }
031:
032: public long size() {
033: return size;
034: }
035:
036: public TripleBunch get(Object key) {
037: int slot = findSlot(key);
038: return slot < 0 ? values[~slot] : null;
039: }
040:
041: public void put(Object key, TripleBunch value) {
042: int slot = findSlot(key);
043: if (slot < 0)
044: values[~slot] = value;
045: else {
046: keys[slot] = key;
047: values[slot] = value;
048: size += 1;
049: if (size == threshold)
050: grow();
051: }
052: }
053:
054: protected void grow() {
055: Object[] oldContents = keys;
056: TripleBunch[] oldValues = values;
057: final int oldCapacity = capacity;
058: growCapacityAndThreshold();
059: keys = new Object[capacity];
060: values = new TripleBunch[capacity];
061: for (int i = 0; i < oldCapacity; i += 1) {
062: Object key = oldContents[i];
063: if (key != null) {
064: int j = findSlot(key);
065: if (j < 0) {
066: throw new BrokenException(
067: "oh dear, already have a slot for " + key
068: + ", viz " + ~j);
069: }
070: keys[j] = key;
071: values[j] = oldValues[i];
072: }
073: }
074: }
075:
076: /**
077: Called by HashCommon when a key is removed: remove
078: associated element of the <code>values</code> array.
079: */
080: protected void removeAssociatedValues(int here) {
081: values[here] = null;
082: }
083:
084: /**
085: Called by HashCommon when a key is moved: move the
086: associated element of the <code>values</code> array.
087: */
088: protected void moveAssociatedValues(int here, int scan) {
089: values[here] = values[scan];
090: }
091: }
092:
093: /*
094: * (c) Copyright 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
095: * All rights reserved.
096: *
097: * Redistribution and use in source and binary forms, with or without
098: * modification, are permitted provided that the following conditions
099: * are met:
100: * 1. Redistributions of source code must retain the above copyright
101: * notice, this list of conditions and the following disclaimer.
102: * 2. Redistributions in binary form must reproduce the above copyright
103: * notice, this list of conditions and the following disclaimer in the
104: * documentation and/or other materials provided with the distribution.
105: * 3. The name of the author may not be used to endorse or promote products
106: * derived from this software without specific prior written permission.
107: *
108: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
109: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
110: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
111: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
112: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
113: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
114: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
115: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
116: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
117: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
118: */
|