001: /*
002: * The Apache Software License, Version 1.1
003: *
004: *
005: * Copyright (c) 1999,2000 The Apache Software Foundation. All rights
006: * reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Apache Software Foundation (http://www.apache.org/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Xerces" and "Apache Software Foundation" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact apache@apache.org.
031: *
032: * 5. Products derived from this software may not be called "Apache",
033: * nor may "Apache" appear in their name, without prior written
034: * permission of the Apache Software Foundation.
035: *
036: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
037: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
038: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
039: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
040: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
041: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
042: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
043: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
044: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
045: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
046: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
047: * SUCH DAMAGE.
048: * ====================================================================
049: *
050: * This software consists of voluntary contributions made by many
051: * individuals on behalf of the Apache Software Foundation and was
052: * originally based on software copyright (c) 1999, International
053: * Business Machines, Inc., http://www.apache.org. For more
054: * information on the Apache Software Foundation, please see
055: * <http://www.apache.org/>.
056: */
057:
058: package org.apache.xerces.utils;
059:
060: /**
061: * A light-weight hashtable class that takes 2 ints as key and 1 int as value
062: * @version
063: */
064:
065: public final class Hash2intTable {
066:
067: private static final int INITIAL_BUCKET_SIZE = 4;
068: private static final int HASHTABLE_SIZE = 256;
069: private int[][] fHashTable = new int[HASHTABLE_SIZE][];
070:
071: public void put(int key1, int key2, int key3, int value) {
072: int hash = (key1 + key2 + key3 + 2) % HASHTABLE_SIZE;
073: int[] bucket = fHashTable[hash];
074:
075: if (bucket == null) {
076: bucket = new int[1 + 4 * INITIAL_BUCKET_SIZE];
077: bucket[0] = 1;
078: bucket[1] = key1;
079: bucket[2] = key2;
080: bucket[3] = key3;
081: bucket[4] = value;
082: fHashTable[hash] = bucket;
083: } else {
084: int count = bucket[0];
085: int offset = 1 + 4 * count;
086: if (offset == bucket.length) {
087: int newSize = count + INITIAL_BUCKET_SIZE;
088: int[] newBucket = new int[1 + 4 * newSize];
089: System.arraycopy(bucket, 0, newBucket, 0, offset);
090: bucket = newBucket;
091: fHashTable[hash] = bucket;
092: }
093: boolean found = false;
094: int j = 1;
095: for (int i = 0; i < count; i++) {
096: if (bucket[j] == key1 && bucket[j + 1] == key2
097: && bucket[j + 2] == key3) {
098: bucket[j + 3] = value;
099: found = true;
100: break;
101: }
102: j += 4;
103: }
104: if (!found) {
105: bucket[offset++] = key1;
106: bucket[offset++] = key2;
107: bucket[offset++] = key3;
108: bucket[offset] = value;
109: bucket[0] = ++count;
110: }
111:
112: }
113: }
114:
115: public int get(int key1, int key2, int key3) {
116: int hash = (key1 + key2 + key3 + 2) % HASHTABLE_SIZE;
117: int[] bucket = fHashTable[hash];
118:
119: if (bucket == null) {
120: return -1;
121: }
122: int count = bucket[0];
123:
124: int j = 1;
125: for (int i = 0; i < count; i++) {
126: if (bucket[j] == key1 && bucket[j + 1] == key2
127: && bucket[j + 2] == key3) {
128: return bucket[j + 3];
129: }
130: j += 4;
131: }
132: return -1;
133: }
134:
135: } // class Hash2inTable
|