1 /* 2 * Copyright 2002-2004 The Apache Software Foundation. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the 5 * License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" 10 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language 11 * governing permissions and limitations under the License. 12 */ 13 package org.lwjgl.opengl; 14 15 import java.util.Iterator; 16 17 /** 18 * A hash map using primitive ints as keys rather than objects. 19 * 20 * @author Justin Couch 21 * @author Alex Chaffee (alex@apache.org) 22 * @author Stephen Colebourne 23 * @author Nathan Sweet 24 */ 25 final class FastIntMap<V> implements Iterable<FastIntMap.Entry<V>> { 26 27 private Entry[] table; 28 private int size, mask, capacity, threshold; 29 30 /** Same as: FastIntMap(16, 0.75f); */ FastIntMap()31 FastIntMap() { 32 this(16, 0.75f); 33 } 34 35 /** Same as: FastIntMap(initialCapacity, 0.75f); */ FastIntMap(int initialCapacity)36 FastIntMap(int initialCapacity) { 37 this(initialCapacity, 0.75f); 38 } 39 FastIntMap(int initialCapacity, float loadFactor)40 FastIntMap(int initialCapacity, float loadFactor) { 41 if ( initialCapacity > 1 << 30 ) throw new IllegalArgumentException("initialCapacity is too large."); 42 if ( initialCapacity < 0 ) throw new IllegalArgumentException("initialCapacity must be greater than zero."); 43 if ( loadFactor <= 0 ) throw new IllegalArgumentException("initialCapacity must be greater than zero."); 44 capacity = 1; 45 while ( capacity < initialCapacity ) 46 capacity <<= 1; 47 this.threshold = (int)(capacity * loadFactor); 48 this.table = new Entry[capacity]; 49 this.mask = capacity - 1; 50 } 51 index(final int key)52 private int index(final int key) { 53 return index(key, mask); 54 } 55 index(final int key, final int mask)56 private static int index(final int key, final int mask) { 57 return key & mask; 58 } 59 put(int key, V value)60 public V put(int key, V value) { 61 final Entry<V>[] table = this.table; 62 int index = index(key); 63 64 // Check if key already exists. 65 for ( Entry<V> e = table[index]; e != null; e = e.next ) { 66 if ( e.key != key ) continue; 67 V oldValue = e.value; 68 e.value = value; 69 return oldValue; 70 } 71 72 table[index] = new Entry<V>(key, value, table[index]); 73 74 if ( size++ >= threshold ) 75 rehash(table); 76 77 return null; 78 } 79 rehash(final Entry<V>[] table)80 private void rehash(final Entry<V>[] table) { 81 final int newCapacity = 2 * capacity; 82 final int newMask = newCapacity - 1; 83 84 final Entry<V>[] newTable = new Entry[newCapacity]; 85 86 for ( int i = 0, index; i < table.length; i++ ) { 87 Entry<V> e = table[i]; 88 if ( e == null ) continue; 89 do { 90 final Entry<V> next = e.next; 91 index = index(e.key, newMask); 92 e.next = newTable[index]; 93 newTable[index] = e; 94 e = next; 95 } while ( e != null ); 96 } 97 98 this.table = newTable; 99 capacity = newCapacity; 100 mask = newMask; 101 threshold *= 2; 102 } 103 get(int key)104 public V get(int key) { 105 final int index = index(key); 106 for ( Entry<V> e = table[index]; e != null; e = e.next ) 107 if ( e.key == key ) return e.value; 108 return null; 109 } 110 containsValue(Object value)111 public boolean containsValue(Object value) { 112 final Entry<V>[] table = this.table; 113 for ( int i = table.length - 1; i >= 0; i-- ) 114 for ( Entry<V> e = table[i]; e != null; e = e.next ) 115 if ( e.value.equals(value) ) return true; 116 return false; 117 } 118 containsKey(int key)119 public boolean containsKey(int key) { 120 final int index = index(key); 121 for ( Entry<V> e = table[index]; e != null; e = e.next ) 122 if ( e.key == key ) return true; 123 return false; 124 } 125 remove(int key)126 public V remove(int key) { 127 final int index = index(key); 128 129 Entry<V> prev = table[index]; 130 Entry<V> e = prev; 131 while ( e != null ) { 132 Entry<V> next = e.next; 133 if ( e.key == key ) { 134 size--; 135 if ( prev == e ) 136 table[index] = next; 137 else 138 prev.next = next; 139 return e.value; 140 } 141 prev = e; 142 e = next; 143 } 144 return null; 145 } 146 size()147 public int size() { 148 return size; 149 } 150 isEmpty()151 public boolean isEmpty() { 152 return size == 0; 153 } 154 clear()155 public void clear() { 156 final Entry<V>[] table = this.table; 157 for ( int index = table.length - 1; index >= 0; index-- ) 158 table[index] = null; 159 size = 0; 160 } 161 iterator()162 public EntryIterator iterator() { 163 return new EntryIterator(); 164 } 165 166 public class EntryIterator implements Iterator<Entry<V>> { 167 168 private int nextIndex; 169 private Entry<V> current; 170 EntryIterator()171 EntryIterator() { 172 reset(); 173 } 174 reset()175 public void reset() { 176 current = null; 177 // Find first bucket. 178 final Entry<V>[] table = FastIntMap.this.table; 179 int i; 180 for ( i = table.length - 1; i >= 0; i-- ) 181 if ( table[i] != null ) break; 182 nextIndex = i; 183 } 184 hasNext()185 public boolean hasNext() { 186 if ( nextIndex >= 0 ) return true; 187 Entry e = current; 188 return e != null && e.next != null; 189 } 190 next()191 public Entry<V> next() { 192 // Next entry in current bucket. 193 Entry<V> e = current; 194 if ( e != null ) { 195 e = e.next; 196 if ( e != null ) { 197 current = e; 198 return e; 199 } 200 } 201 // Use the bucket at nextIndex and find the next nextIndex. 202 final Entry<V>[] table = FastIntMap.this.table; 203 int i = nextIndex; 204 e = current = table[i]; 205 while ( --i >= 0 ) 206 if ( table[i] != null ) break; 207 nextIndex = i; 208 return e; 209 } 210 remove()211 public void remove() { 212 FastIntMap.this.remove(current.key); 213 } 214 } 215 216 static final class Entry<T> { 217 218 final int key; 219 T value; 220 Entry<T> next; 221 Entry(int key, T value, Entry<T> next)222 Entry(int key, T value, Entry<T> next) { 223 this.key = key; 224 this.value = value; 225 this.next = next; 226 } 227 getKey()228 public int getKey() { 229 return key; 230 } 231 getValue()232 public T getValue() { 233 return value; 234 } 235 236 } 237 238 }