/* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- * * The contents of this file are subject to the Netscape Public * License Version 1.1 (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.mozilla.org/NPL/ * * Software distributed under the License is distributed on an "AS * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or * implied. See the License for the specific language governing * rights and limitations under the License. * * The Original Code is Rhino code, released * May 6, 1999. * * The Initial Developer of the Original Code is Netscape * Communications Corporation.  Portions created by Netscape are * Copyright (C) 1997-2000 Netscape Communications Corporation. All * Rights Reserved. * * Contributor(s): * Igor Bukanov * * Alternatively, the contents of this file may be used under the * terms of the GNU Public License (the "GPL"), in which case the * provisions of the GPL are applicable instead of those above. * If you wish to allow use of your version of this file only * under the terms of the GPL and not to allow others to use your * version of this file under the NPL, indicate your decision by * deleting the provisions above and replace them with the notice * and other provisions required by the GPL.  If you do not delete * the provisions above, a recipient may use your version of this * file under either the NPL or the GPL. */package org.mozilla.javascript;import java.io.Serializable;import java.io.IOException;import java.io.ObjectInputStream;import java.io.ObjectOutputStream;/** * Map to associate non-negative integers to objects or integers. * The map does not synchronize any of its operation, so either use * it from a single thread or do own synchronization or perform all mutation * operations on one thread before passing the map to others. * * @author Igor Bukanov * */public class UintMap implements Serializable{    static final long serialVersionUID = 4242698212885848444L;// Map implementation via hashtable,// follows "The Art of Computer Programming" by Donald E. Knuth    public UintMap() {        this(4);    }    public UintMap(int initialCapacity) {        if (initialCapacity < 0) Kit.codeBug();        // Table grow when number of stored keys >= 3/4 of max capacity        int minimalCapacity = initialCapacity * 4 / 3;        int i;        for (i = 2; (1 << i) < minimalCapacity; ++i) { }        power = i;        if (check && power < 2) Kit.codeBug();    }    public boolean isEmpty() {        return keyCount == 0;    }    public int size() {        return keyCount;    }    public boolean has(int key) {        if (key < 0) Kit.codeBug();        return 0 <= findIndex(key);    }    /**     * Get object value assigned with key.     * @return key object value or null if key is absent     */    public Object getObject(int key) {        if (key < 0) Kit.codeBug();        if (values != null) {            int index = findIndex(key);            if (0 <= index) {                return values[index];            }        }        return null;    }    /**     * Get integer value assigned with key.     * @return key integer value or defaultValue if key is absent     */    public int getInt(int key, int defaultValue) {        if (key < 0) Kit.codeBug();        int index = findIndex(key);        if (0 <= index) {            if (ivaluesShift != 0) {                return keys[ivaluesShift + index];            }            return 0;        }        return defaultValue;    }    /**     * Get integer value assigned with key.     * @return key integer value or defaultValue if key does not exist or does     * not have int value     * @throws RuntimeException if key does not exist     */    public int getExistingInt(int key) {        if (key < 0) Kit.codeBug();        int index = findIndex(key);        if (0 <= index) {            if (ivaluesShift != 0) {                return keys[ivaluesShift + index];            }            return 0;        }        // Key must exist        Kit.codeBug();        return 0;    }    /**     * Set object value of the key.     * If key does not exist, also set its int value to 0.     */    public void put(int key, Object value) {        if (key < 0) Kit.codeBug();        int index = ensureIndex(key, false);        if (values == null) {            values = new Object[1 << power];        }        values[index] = value;    }    /**     * Set int value of the key.     * If key does not exist, also set its object value to null.     */    public void put(int key, int value) {        if (key < 0) Kit.codeBug();        int index = ensureIndex(key, true);        if (ivaluesShift == 0) {            int N = 1 << power;            // keys.length can be N * 2 after clear which set ivaluesShift to 0            if (keys.length != N * 2) {                int[] tmp = new int[N * 2];                System.arraycopy(keys, 0, tmp, 0, N);                keys = tmp;            }            ivaluesShift = N;        }        keys[ivaluesShift + index] = value;    }    public void remove(int key) {        if (key < 0) Kit.codeBug();        int index = findIndex(key);        if (0 <= index) {            keys[index] = DELETED;            --keyCount;            // Allow to GC value and make sure that new key with the deleted            // slot shall get proper default values            if (values != null) { values[index] = null; }            if (ivaluesShift != 0) { keys[ivaluesShift + index] = 0; }        }    }    public void clear() {        int N = 1 << power;        if (keys != null) {            for (int i = 0; i != N; ++i) {                keys[i] = EMPTY;            }            if (values != null) {                for (int i = 0; i != N; ++i) {                    values[i] = null;                }            }        }        ivaluesShift = 0;        keyCount = 0;        occupiedCount = 0;    }    /** Return array of present keys */    public int[] getKeys() {        int[] keys = this.keys;        int n = keyCount;        int[] result = new int[n];        for (int i = 0; n != 0; ++i) {            int entry = keys[i];            if (entry != EMPTY && entry != DELETED) {                result[--n] = entry;            }        }        return result;    }    private static int tableLookupStep(int fraction, int mask, int power) {        int shift = 32 - 2 * power;        if (shift >= 0) {            return ((fraction >>> shift) & mask) | 1;        }        else {            return (fraction & (mask >>> -shift)) | 1;        }    }    private int findIndex(int key) {        int[] keys = this.keys;        if (keys != null) {            int fraction = key * A;            int index = fraction >>> (32 - power);            int entry = keys[index];            if (entry == key) { return index; }            if (entry != EMPTY) {                // Search in table after first failed attempt                int mask = (1 << power) - 1;                int step = tableLookupStep(fraction, mask, power);                int n = 0;                do {                    if (check) {                        if (n >= occupiedCount) Kit.codeBug();                        ++n;                    }                    index = (index + step) & mask;                    entry = keys[index];                    if (entry == key) { return index; }                } while (entry != EMPTY);            }        }        return -1;    }// Insert key that is not present to table without deleted entries// and enough free space    private int insertNewKey(int key) {        if (check && occupiedCount != keyCount) Kit.codeBug();        if (check && keyCount == 1 << power) Kit.codeBug();        int[] keys = this.keys;        int fraction = key * A;        int index = fraction >>> (32 - power);        if (keys[index] != EMPTY) {            int mask = (1 << power) - 1;            int step = tableLookupStep(fraction, mask, power);            int firstIndex = index;            do {                if (check && keys[index] == DELETED) Kit.codeBug();                index = (index + step) & mask;                if (check && firstIndex == index) Kit.codeBug();            } while (keys[index] != EMPTY);        }        keys[index] = key;        ++occupiedCount;        ++keyCount;        return index;    }    private void rehashTable(boolean ensureIntSpace) {        if (keys != null) {            // Check if removing deleted entries would free enough space            if (keyCount * 2 >= occupiedCount) {                // Need to grow: less then half of deleted entries                ++power;            }        }        int N = 1 << power;        int[] old = keys;        int oldShift = ivaluesShift;        if (oldShift == 0 && !ensureIntSpace) {            keys = new int[N];        }        else {            ivaluesShift = N; keys = new int[N * 2];        }        for (int i = 0; i != N; ++i) { keys[i] = EMPTY; }        Object[] oldValues = values;        if (oldValues != null) { values = new Object[N]; }        int oldCount = keyCount;        occupiedCount = 0;        if (oldCount != 0) {            keyCount = 0;            for (int i = 0, remaining = oldCount; remaining != 0; ++i) {                int key = old[i];                if (key != EMPTY && key != DELETED) {                    int index = insertNewKey(key);                    if (oldValues != null) {                        values[index] = oldValues[i];                    }                    if (oldShift != 0) {                        keys[ivaluesShift + index] = old[oldShift + i];                    }                    --remaining;                }            }        }    }// Ensure key index creating one if necessary    private int ensureIndex(int key, boolean intType) {        int index = -1;        int firstDeleted = -1;        int[] keys = this.keys;        if (keys != null) {            int fraction = key * A;            index = fraction >>> (32 - power);            int entry = keys[index];            if (entry == key) { return index; }            if (entry != EMPTY) {                if (entry == DELETED) { firstDeleted = index; }                // Search in table after first failed attempt