CacheTable.java revision 608:7e06bf1dcb09
1/* 2 * Copyright (c) 1999, 2003, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package com.sun.corba.se.impl.orbutil; 27import org.omg.CORBA.INTERNAL; 28import org.omg.CORBA.CompletionStatus; 29 30import com.sun.corba.se.spi.logging.CORBALogDomains; 31import com.sun.corba.se.spi.orb.ORB; 32 33import com.sun.corba.se.impl.logging.ORBUtilSystemException; 34 35public class CacheTable { 36 class Entry { 37 java.lang.Object key; 38 int val; 39 Entry next; // this chains the collision list of table "map" 40 Entry rnext; // this chains the collision list of table "rmap" 41 public Entry(java.lang.Object k, int v) { 42 key = k; 43 val = v; 44 next = null; 45 rnext = null; 46 } 47 } 48 private boolean noReverseMap; 49 // size must be power of 2 50 static final int INITIAL_SIZE = 16; 51 static final int MAX_SIZE = 1 << 30; 52 int size; 53 int entryCount; 54 private Entry [] map; 55 private Entry [] rmap; 56 57 private ORB orb; 58 private ORBUtilSystemException wrapper; 59 60 private CacheTable() {} 61 public CacheTable(ORB orb, boolean u) { 62 //System.out.println("using new cache table"); 63 this.orb = orb; 64 wrapper = ORBUtilSystemException.get(orb, 65 CORBALogDomains.RPC_ENCODING); 66 noReverseMap = u; 67 size = INITIAL_SIZE; 68 entryCount = 0; 69 initTables(); 70 } 71 private void initTables() { 72 map = new Entry[size]; 73 rmap = noReverseMap ? null : new Entry[size]; 74 } 75 private void grow() { 76 if (size == MAX_SIZE) 77 return; 78 Entry [] oldMap = map; 79 int oldSize = size; 80 size <<= 1; 81 initTables(); 82 // now rehash the entries into the new table 83 for (int i = 0; i < oldSize; i++) { 84 for (Entry e = oldMap[i]; e != null; e = e.next) 85 put_table(e.key, e.val); 86 } 87 } 88 private int moduloTableSize(int h) { 89 // these are the "supplemental hash function" copied from 90 // java.util.HashMap, supposed to be "critical" 91 h += ~(h << 9); 92 h ^= (h >>> 14); 93 h += (h << 4); 94 h ^= (h >>> 10); 95 return h & (size - 1); 96 } 97 private int hash(java.lang.Object key) { 98 return moduloTableSize(System.identityHashCode(key)); 99 } 100 private int hash(int val) { 101 return moduloTableSize(val); 102 } 103 public final void put(java.lang.Object key, int val) { 104 if (put_table(key, val)) { 105 entryCount++; 106 if (entryCount > size * 3 / 4) 107 grow(); 108 } 109 } 110 private boolean put_table(java.lang.Object key, int val) { 111 int index = hash(key); 112 for (Entry e = map[index]; e != null; e = e.next) { 113 if (e.key == key) { 114 if (e.val != val) { 115 throw wrapper.duplicateIndirectionOffset(); 116 } 117 // if we get here we are trying to put in the same key/val pair 118 // this is a no-op, so we just return 119 return false; 120 } 121 } 122 // this means the key is not present in our table 123 // then it shouldnt be present in our reverse table either 124 Entry newEntry = new Entry(key, val); 125 newEntry.next = map[index]; 126 map[index] = newEntry; 127 if (!noReverseMap) { 128 int rindex = hash(val); 129 newEntry.rnext = rmap[rindex]; 130 rmap[rindex] = newEntry; 131 } 132 return true; 133 } 134 public final boolean containsKey(java.lang.Object key) { 135 return (getVal(key) != -1); 136 } 137 public final int getVal(java.lang.Object key) { 138 int index = hash(key); 139 for (Entry e = map[index]; e != null; e = e.next) { 140 if (e.key == key) 141 return e.val; 142 } 143 return -1; 144 } 145 public final boolean containsVal(int val) { 146 return (getKey(val) != null); 147 } 148 public final boolean containsOrderedVal(int val) { 149 return containsVal(val); 150 } 151 public final java.lang.Object getKey(int val) { 152 int index = hash(val); 153 for (Entry e = rmap[index]; e != null; e = e.rnext) { 154 if (e.val == val) 155 return e.key; 156 } 157 return null; 158 } 159 public void done() { 160 map = null; 161 rmap = null; 162 } 163} 164