1f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved. 2f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 3f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * This program and the accompanying materials are made available under 4f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * the terms of the Common Public License v1.0 which accompanies this distribution, 5f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * and is available at http://www.eclipse.org/legal/cpl-v10.html 6f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 7f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * $Id: IntIntMap.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $ 8f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 9f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Projectpackage com.vladium.util; 10f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 11f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project// ---------------------------------------------------------------------------- 12f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project/** 13f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 14f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * MT-safety: an instance of this class is <I>not</I> safe for access from 15f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * multiple concurrent threads [even if access is done by a single thread at a 16f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * time]. The caller is expected to synchronize externally on an instance [the 17f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * implementation does not do internal synchronization for the sake of efficiency]. 18f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * java.util.ConcurrentModificationException is not supported either. 19f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 20f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @author Vlad Roubtsov, (C) 2001 21f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 22f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Projectpublic 23f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Projectfinal class IntIntMap 24f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project{ 25f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // public: ................................................................ 26f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 27f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // TODO: optimize key comparisons using key.hash == entry.key.hash condition 28f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 29f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 30f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Equivalent to <CODE>IntObjectMap(11, 0.75F)</CODE>. 31f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 32f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public IntIntMap () 33f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 34f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project this (11, 0.75F); 35f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 36f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 37f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 38f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Equivalent to <CODE>IntObjectMap(capacity, 0.75F)</CODE>. 39f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 40f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public IntIntMap (final int initialCapacity) 41f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 42f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project this (initialCapacity, 0.75F); 43f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 44f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 45f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 46f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Constructs an IntObjectMap with specified initial capacity and load factor. 47f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 48f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param initialCapacity initial number of hash buckets in the table [may not be negative, 0 is equivalent to 1]. 49f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param loadFactor the load factor to use to determine rehashing points [must be in (0.0, 1.0] range]. 50f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 51f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public IntIntMap (int initialCapacity, final float loadFactor) 52f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 53f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (initialCapacity < 0) throw new IllegalArgumentException ("negative input: initialCapacity [" + initialCapacity + "]"); 54f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6)) 55f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project throw new IllegalArgumentException ("loadFactor not in (0.0, 1.0] range: " + loadFactor); 56f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 57f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (initialCapacity == 0) initialCapacity = 1; 58f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 59f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_loadFactor = loadFactor > 1.0 ? 1.0F : loadFactor; 60f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_sizeThreshold = (int) (initialCapacity * loadFactor); 61f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_buckets = new Entry [initialCapacity]; 62f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 63f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 64f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 65f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 66f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Overrides Object.toString() for debug purposes. 67f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 68f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public String toString () 69f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 70f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final StringBuffer s = new StringBuffer (); 71f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project debugDump (s); 72f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 73f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return s.toString (); 74f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 75f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 76f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 77f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Returns the number of key-value mappings in this map. 78f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 79f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public int size () 80f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 81f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return m_size; 82f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 83f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 84f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public boolean contains (final int key) 85f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 86f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // index into the corresponding hash bucket: 87f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry [] buckets = m_buckets; 88f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 89f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 90f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // traverse the singly-linked list of entries in the bucket: 91f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 92f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 93f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (key == entry.m_key) return true; 94f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 95f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 96f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return false; 97f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 98f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 99f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 100f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Returns the value that is mapped to a given 'key'. Returns 101f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * false if this key has never been mapped. 102f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 103f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param key mapping key 104f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param out holder for the found value [must be at least of size 1] 105f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 106f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @return 'true' if this key was mapped to an existing value 107f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 108f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public boolean get (final int key, final int [] out) 109f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 110f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // index into the corresponding hash bucket: 111f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry [] buckets = m_buckets; 112f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 113f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 114f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // traverse the singly-linked list of entries in the bucket: 115f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 116f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 117f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (key == entry.m_key) 118f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 119f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project out [0] = entry.m_value; 120f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return true; 121f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 122f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 123f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 124f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return false; 125f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 126f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 127f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public boolean get (final int key, final int [] out, final int index) 128f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 129f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // index into the corresponding hash bucket: 130f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry [] buckets = m_buckets; 131f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 132f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 133f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // traverse the singly-linked list of entries in the bucket: 134f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 135f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 136f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (key == entry.m_key) 137f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 138f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project out [index] = entry.m_value; 139f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return true; 140f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 141f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 142f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 143f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return false; 144f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 145f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 146f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public int [] keys () 147f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 148f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int [] result = new int [m_size]; 149f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project int scan = 0; 150f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 151f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (int b = 0; b < m_buckets.length; ++ b) 152f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 153f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next) 154f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 155f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project result [scan ++] = entry.m_key; 156f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 157f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 158f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 159f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project return result; 160f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 161f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 162f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 163f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten. 164f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 165f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param key mapping key 166f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param value mapping value 167f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 168f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public void put (final int key, final int value) 169f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 170f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project Entry currentKeyEntry = null; 171f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 172f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]: 173f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 174f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // index into the corresponding hash bucket: 175f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length; 176f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 177f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // traverse the singly-linked list of entries in the bucket: 178f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project Entry [] buckets = m_buckets; 179f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next) 180f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 181f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (key == entry.m_key) 182f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 183f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project currentKeyEntry = entry; 184f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project break; 185f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 186f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 187f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 188f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (currentKeyEntry != null) 189f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 190f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // replace the current value: 191f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 192f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project currentKeyEntry.m_value = value; 193f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 194f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project else 195f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 196f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // add a new entry: 197f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 198f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (m_size >= m_sizeThreshold) rehash (); 199f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 200f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project buckets = m_buckets; 201f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project bucketIndex = (key & 0x7FFFFFFF) % buckets.length; 202f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry bucketListHead = buckets [bucketIndex]; 203f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry newEntry = new Entry (key, value, bucketListHead); 204f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project buckets [bucketIndex] = newEntry; 205f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 206f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project ++ m_size; 207f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 208f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 209f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 210f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 211f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten. 212f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * 213f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * @param key mapping key 214f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 215f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project public void remove (final int key) 216f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 217f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // index into the corresponding hash bucket: 218f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length; 219f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 220f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // traverse the singly-linked list of entries in the bucket: 221f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project Entry [] buckets = m_buckets; 222f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = buckets [bucketIndex], prev = entry; entry != null; ) 223f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 224f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry next = entry.m_next; 225f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 226f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (key == entry.m_key) 227f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 228f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (prev == entry) 229f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project buckets [bucketIndex] = next; 230f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project else 231f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project prev.m_next = next; 232f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 233f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project -- m_size; 234f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project break; 235f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 236f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 237f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project prev = entry; 238f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project entry = next; 239f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 240f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 241f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 242f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 243f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // protected: ............................................................. 244f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 245f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // package: ............................................................... 246f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 247f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 248f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project void debugDump (final StringBuffer out) 249f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 250f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project if (out != null) 251f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 252f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project out.append (super.toString ()); out.append (EOL); 253f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL); 254f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project out.append ("size threshold = " + m_sizeThreshold + EOL); 255f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 256f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 257f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 258f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // private: ............................................................... 259f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 260f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 261f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 262f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * The structure used for chaining colliding keys. 263f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 264f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private static final class Entry 265f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 266f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project Entry (final int key, final int value, final Entry next) 267f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 268f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_key = key; 269f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_value = value; 270f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_next = next; 271f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 272f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 273f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project int m_key; 274f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project int m_value; 275f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 276f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project Entry m_next; // singly-linked list link 277f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 278f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } // end of nested class 279f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 280f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 281f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project /** 282f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project * Re-hashes the table into a new array of buckets. 283f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project */ 284f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private void rehash () 285f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 286f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount 287f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can 288f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // only grow in size 289f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 290f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry [] buckets = m_buckets; 291f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 292f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int newBucketCount = (m_buckets.length << 1) + 1; 293f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry [] newBuckets = new Entry [newBucketCount]; 294f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 295f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // rehash all entry chains in every bucket: 296f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (int b = 0; b < buckets.length; ++ b) 297f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 298f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project for (Entry entry = buckets [b]; entry != null; ) 299f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project { 300f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry 301f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int entryKeyHash = entry.m_key & 0x7FFFFFFF; 302f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 303f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project // index into the corresponding new hash bucket: 304f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final int newBucketIndex = entryKeyHash % newBucketCount; 305f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 306f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project final Entry bucketListHead = newBuckets [newBucketIndex]; 307f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project entry.m_next = bucketListHead; 308f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project newBuckets [newBucketIndex] = entry; 309f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 310f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project entry = next; 311f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 312f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 313f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 314f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 315f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_sizeThreshold = (int) (newBucketCount * m_loadFactor); 316f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project m_buckets = newBuckets; 317f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project } 318f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 319f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 320f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private final float m_loadFactor; // determines the setting of m_sizeThreshold 321f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 322f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private Entry [] m_buckets; // table of buckets 323f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private int m_size; // number of keys in the table, not cleared as of last check 324f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private int m_sizeThreshold; // size threshold for rehashing 325f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 326f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project private static final String EOL = System.getProperty ("line.separator", "\n"); 327f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 328f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project} // end of class 329f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project// ---------------------------------------------------------------------------- 330f6fe897e173f4e4bda72a7dddb091b667066764aThe Android Open Source Project 331