| /* |
| * Copyright 2002-2004 The Apache Software Foundation. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the |
| * License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" |
| * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language |
| * governing permissions and limitations under the License. |
| */ |
| package org.apache.directmemory.lightning.internal.util; |
| |
| import java.util.Iterator; |
| |
| /* |
| * Taken from lwjgl project |
| */ |
| |
| /** |
| * A hash map using primitive longs as keys rather than objects. |
| * |
| * @author Justin Couch |
| * @author Alex Chaffee (alex@apache.org) |
| * @author Stephen Colebourne |
| * @author Nathan Sweet |
| */ |
| public final class FastLongMap<V> |
| implements Iterable<FastLongMap.Entry<V>> |
| { |
| |
| private Entry[] table; |
| |
| private int size, mask, capacity, threshold; |
| |
| /** Same as: FastLongMap(16, 0.75f); */ |
| public FastLongMap() |
| { |
| this( 16, 0.75f ); |
| } |
| |
| /** Same as: FastLongMap(initialCapacity, 0.75f); */ |
| public FastLongMap( int initialCapacity ) |
| { |
| this( initialCapacity, 0.75f ); |
| } |
| |
| public FastLongMap( int initialCapacity, float loadFactor ) |
| { |
| if ( initialCapacity > 1 << 30 ) |
| throw new IllegalArgumentException( "initialCapacity is too large." ); |
| if ( initialCapacity < 0 ) |
| throw new IllegalArgumentException( "initialCapacity must be greater than zero." ); |
| if ( loadFactor <= 0 ) |
| throw new IllegalArgumentException( "initialCapacity must be greater than zero." ); |
| capacity = 1; |
| while ( capacity < initialCapacity ) |
| capacity <<= 1; |
| this.threshold = (int) ( capacity * loadFactor ); |
| this.table = new Entry[capacity]; |
| this.mask = capacity - 1; |
| } |
| |
| private int index( final long key ) |
| { |
| return index( key, mask ); |
| } |
| |
| private static int index( final long key, final int mask ) |
| { |
| final int hash = (int) ( key ^ ( key >>> 32 ) ); |
| return hash & mask; |
| } |
| |
| public V put( long key, V value ) |
| { |
| final Entry<V>[] table = this.table; |
| int index = index( key ); |
| |
| // Check if key already exists. |
| for ( Entry<V> e = table[index]; e != null; e = e.next ) |
| { |
| if ( e.key != key ) |
| continue; |
| V oldValue = e.value; |
| e.value = value; |
| return oldValue; |
| } |
| |
| table[index] = new Entry<V>( key, value, table[index] ); |
| |
| if ( size++ >= threshold ) |
| rehash( table ); |
| |
| return null; |
| } |
| |
| private void rehash( final Entry<V>[] table ) |
| { |
| final int newCapacity = 2 * capacity; |
| final int newMask = newCapacity - 1; |
| |
| final Entry<V>[] newTable = new Entry[newCapacity]; |
| |
| for ( int i = 0, index; i < table.length; i++ ) |
| { |
| Entry<V> e = table[i]; |
| if ( e == null ) |
| continue; |
| do |
| { |
| final Entry<V> next = e.next; |
| index = index( e.key, newMask ); |
| e.next = newTable[index]; |
| newTable[index] = e; |
| e = next; |
| } |
| while ( e != null ); |
| } |
| |
| this.table = newTable; |
| capacity = newCapacity; |
| mask = newMask; |
| threshold *= 2; |
| } |
| |
| public V get( long key ) |
| { |
| final int index = index( key ); |
| for ( Entry<V> e = table[index]; e != null; e = e.next ) |
| if ( e.key == key ) |
| return e.value; |
| return null; |
| } |
| |
| public boolean containsValue( Object value ) |
| { |
| final Entry<V>[] table = this.table; |
| for ( int i = table.length - 1; i >= 0; i-- ) |
| for ( Entry<V> e = table[i]; e != null; e = e.next ) |
| if ( e.value.equals( value ) ) |
| return true; |
| return false; |
| } |
| |
| public boolean containsKey( long key ) |
| { |
| final int index = index( key ); |
| for ( Entry<V> e = table[index]; e != null; e = e.next ) |
| if ( e.key == key ) |
| return true; |
| return false; |
| } |
| |
| public V remove( long key ) |
| { |
| final int index = index( key ); |
| |
| Entry<V> prev = table[index]; |
| Entry<V> e = prev; |
| while ( e != null ) |
| { |
| Entry<V> next = e.next; |
| if ( e.key == key ) |
| { |
| size--; |
| if ( prev == e ) |
| table[index] = next; |
| else |
| prev.next = next; |
| return e.value; |
| } |
| prev = e; |
| e = next; |
| } |
| return null; |
| } |
| |
| public int size() |
| { |
| return size; |
| } |
| |
| public boolean isEmpty() |
| { |
| return size == 0; |
| } |
| |
| public void clear() |
| { |
| final Entry<V>[] table = this.table; |
| for ( int index = table.length - 1; index >= 0; index-- ) |
| table[index] = null; |
| size = 0; |
| } |
| |
| public EntryIterator iterator() |
| { |
| return new EntryIterator(); |
| } |
| |
| public class EntryIterator |
| implements Iterator<Entry<V>> |
| { |
| |
| private int nextIndex; |
| |
| private Entry<V> current; |
| |
| EntryIterator() |
| { |
| reset(); |
| } |
| |
| public void reset() |
| { |
| current = null; |
| // Find first bucket. |
| final Entry<V>[] table = FastLongMap.this.table; |
| int i; |
| for ( i = table.length - 1; i >= 0; i-- ) |
| if ( table[i] != null ) |
| break; |
| nextIndex = i; |
| } |
| |
| public boolean hasNext() |
| { |
| if ( nextIndex >= 0 ) |
| return true; |
| Entry e = current; |
| return e != null && e.next != null; |
| } |
| |
| public Entry<V> next() |
| { |
| // Next entry in current bucket. |
| Entry<V> e = current; |
| if ( e != null ) |
| { |
| e = e.next; |
| if ( e != null ) |
| { |
| current = e; |
| return e; |
| } |
| } |
| // Use the bucket at nextIndex and find the next nextIndex. |
| final Entry<V>[] table = FastLongMap.this.table; |
| int i = nextIndex; |
| e = current = table[i]; |
| while ( --i >= 0 ) |
| if ( table[i] != null ) |
| break; |
| nextIndex = i; |
| return e; |
| } |
| |
| public void remove() |
| { |
| FastLongMap.this.remove( current.key ); |
| } |
| } |
| |
| static final class Entry<T> |
| { |
| |
| final long key; |
| |
| T value; |
| |
| Entry<T> next; |
| |
| Entry( long key, T value, Entry<T> next ) |
| { |
| this.key = key; |
| this.value = value; |
| this.next = next; |
| } |
| |
| public long getKey() |
| { |
| return key; |
| } |
| |
| public T getValue() |
| { |
| return value; |
| } |
| |
| } |
| |
| } |