Source code: org/apache/xerces/utils/Hash2intTable.java
1 /*
2 * The Apache Software License, Version 1.1
3 *
4 *
5 * Copyright (c) 1999,2000 The Apache Software Foundation. All rights
6 * reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. The end-user documentation included with the redistribution,
21 * if any, must include the following acknowledgment:
22 * "This product includes software developed by the
23 * Apache Software Foundation (http://www.apache.org/)."
24 * Alternately, this acknowledgment may appear in the software itself,
25 * if and wherever such third-party acknowledgments normally appear.
26 *
27 * 4. The names "Xerces" and "Apache Software Foundation" must
28 * not be used to endorse or promote products derived from this
29 * software without prior written permission. For written
30 * permission, please contact apache@apache.org.
31 *
32 * 5. Products derived from this software may not be called "Apache",
33 * nor may "Apache" appear in their name, without prior written
34 * permission of the Apache Software Foundation.
35 *
36 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47 * SUCH DAMAGE.
48 * ====================================================================
49 *
50 * This software consists of voluntary contributions made by many
51 * individuals on behalf of the Apache Software Foundation and was
52 * originally based on software copyright (c) 1999, International
53 * Business Machines, Inc., http://www.apache.org. For more
54 * information on the Apache Software Foundation, please see
55 * <http://www.apache.org/>.
56 */
57
58 package org.apache.xerces.utils;
59
60 /**
61 * A light-weight hashtable class that takes 2 ints as key and 1 int as value
62 * @version
63 */
64
65 public final class Hash2intTable {
66
67
68 private static final int INITIAL_BUCKET_SIZE = 4;
69 private static final int HASHTABLE_SIZE = 256;
70 private int[][] fHashTable = new int[HASHTABLE_SIZE][];
71
72
73 public void put(int key1, int key2, int key3, int value) {
74 int hash = (key1+key2+key3+2) % HASHTABLE_SIZE;
75 int[] bucket = fHashTable[hash];
76
77 if (bucket == null) {
78 bucket = new int[1 + 4*INITIAL_BUCKET_SIZE];
79 bucket[0] = 1;
80 bucket[1] = key1;
81 bucket[2] = key2;
82 bucket[3] = key3;
83 bucket[4] = value;
84 fHashTable[hash] = bucket;
85 } else {
86 int count = bucket[0];
87 int offset = 1 + 4*count;
88 if (offset == bucket.length) {
89 int newSize = count + INITIAL_BUCKET_SIZE;
90 int[] newBucket = new int[1 + 4*newSize];
91 System.arraycopy(bucket, 0, newBucket, 0, offset);
92 bucket = newBucket;
93 fHashTable[hash] = bucket;
94 }
95 boolean found = false;
96 int j=1;
97 for (int i=0; i<count; i++){
98 if ( bucket[j] == key1 && bucket[j+1] == key2
99 && bucket[j+2] == key3 ) {
100 bucket[j+3] = value;
101 found = true;
102 break;
103 }
104 j += 4;
105 }
106 if (! found) {
107 bucket[offset++] = key1;
108 bucket[offset++] = key2;
109 bucket[offset++] = key3;
110 bucket[offset]= value;
111 bucket[0] = ++count;
112 }
113
114 }
115 }
116
117 public int get(int key1, int key2, int key3) {
118 int hash = (key1+key2+key3+2) % HASHTABLE_SIZE;
119 int[] bucket = fHashTable[hash];
120
121 if (bucket == null) {
122 return -1;
123 }
124 int count = bucket[0];
125
126 int j=1;
127 for (int i=0; i<count; i++){
128 if ( bucket[j] == key1 && bucket[j+1] == key2
129 && bucket[j+2] == key3) {
130 return bucket[j+3];
131 }
132 j += 4;
133 }
134 return -1;
135 }
136
137 } // class Hash2inTable
138
139
140
141
142
143
144
145
146
147
148
149
150
151