uintmap.java

java中比较著名的js引擎当属mozilla开源的rhino

                if (entry == DELETED) { firstDeleted = index; }
                // 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; }
                    if (entry == DELETED && firstDeleted < 0) {
                        firstDeleted = index;
                    }
                } while (entry != EMPTY);
            }
        }
        // Inserting of new key
        if (check && keys != null && keys[index] != EMPTY)
            Kit.codeBug();
        if (firstDeleted >= 0) {
            index = firstDeleted;
        }
        else {
            // Need to consume empty entry: check occupation level
            if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
                // Too litle unused entries: rehash
                rehashTable(intType);
                keys = this.keys;
                return insertNewKey(key);
            }
            ++occupiedCount;
        }
        keys[index] = key;
        ++keyCount;
        return index;
    }

    private void writeObject(ObjectOutputStream out)
        throws IOException
    {
        out.defaultWriteObject();

        int count = keyCount;
        if (count != 0) {
            boolean hasIntValues = (ivaluesShift != 0);
            boolean hasObjectValues = (values != null);
            out.writeBoolean(hasIntValues);
            out.writeBoolean(hasObjectValues);

            for (int i = 0; count != 0; ++i) {
                int key = keys[i];
                if (key != EMPTY && key != DELETED) {
                    --count;
                    out.writeInt(key);
                    if (hasIntValues) {
                        out.writeInt(keys[ivaluesShift + i]);
                    }
                    if (hasObjectValues) {
                        out.writeObject(values[i]);
                    }
                }
            }
        }
    }

    private void readObject(ObjectInputStream in)
        throws IOException, ClassNotFoundException
    {
        in.defaultReadObject();

        int writtenKeyCount = keyCount;
        if (writtenKeyCount != 0) {
            keyCount = 0;
            boolean hasIntValues = in.readBoolean();
            boolean hasObjectValues = in.readBoolean();

            int N = 1 << power;
            if (hasIntValues) {
                keys = new int[2 * N];
                ivaluesShift = N;
            }else {
                keys = new int[N];
            }
            for (int i = 0; i != N; ++i) {
                keys[i] = EMPTY;
            }
            if (hasObjectValues) {
                values = new Object[N];
            }
            for (int i = 0; i != writtenKeyCount; ++i) {
                int key = in.readInt();
                int index = insertNewKey(key);
                if (hasIntValues) {
                    int ivalue = in.readInt();
                    keys[ivaluesShift + index] = ivalue;
                }
                if (hasObjectValues) {
                    values[index] = in.readObject();
                }
            }
        }
    }

// A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
// See Knuth etc.
    private static final int A = 0x9e3779b9;

    private static final int EMPTY = -1;
    private static final int DELETED = -2;

// Structure of kyes and values arrays (N == 1 << power):
// keys[0 <= i < N]: key value or EMPTY or DELETED mark
// values[0 <= i < N]: value of key at keys[i]
// keys[N <= i < 2N]: int values of keys at keys[i - N]

    private transient int[] keys;
    private transient Object[] values;

    private int power;
    private int keyCount;
    private transient int occupiedCount; // == keyCount + deleted_count

    // If ivaluesShift != 0, keys[ivaluesShift + index] contains integer
    // values associated with keys
    private transient int ivaluesShift;

// If true, enables consitency checks
    private static final boolean check = false;

/* TEST START

    public static void main(String[] args) {
        if (!check) {
            System.err.println("Set check to true and re-run");
            throw new RuntimeException("Set check to true and re-run");
        }

        UintMap map;
        map = new UintMap();
        testHash(map, 2);
        map = new UintMap();
        testHash(map, 10 * 1000);
        map = new UintMap(30 * 1000);
        testHash(map, 10 * 100);
        map.clear();
        testHash(map, 4);
        map = new UintMap(0);
        testHash(map, 10 * 100);
    }

    private static void testHash(UintMap map, int N) {
        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            map.put(i, i);
            check(i == map.getInt(i, -1));
        }

        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            map.put(i, i);
            check(i == map.getInt(i, -1));
        }

        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            map.put(i, new Integer(i));
            check(-1 == map.getInt(i, -1));
            Integer obj = (Integer)map.getObject(i);
            check(obj != null && i == obj.intValue());
        }

        check(map.size() == N);

        System.out.print("."); System.out.flush();
        int[] keys = map.getKeys();
        check(keys.length == N);
        for (int i = 0; i != N; ++i) {
            int key = keys[i];
            check(map.has(key));
            check(!map.isIntType(key));
            check(map.isObjectType(key));
            Integer obj = (Integer) map.getObject(key);
            check(obj != null && key == obj.intValue());
        }


        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            check(-1 == map.getInt(i, -1));
        }

        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            map.put(i * i, i);
            check(i == map.getInt(i * i, -1));
        }

        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            check(i == map.getInt(i * i, -1));
        }

        System.out.print("."); System.out.flush();
        for (int i = 0; i != N; ++i) {
            map.put(i * i, new Integer(i));
            check(-1 == map.getInt(i * i, -1));
            map.remove(i * i);
            check(!map.has(i * i));
            map.put(i * i, i);
            check(map.isIntType(i * i));
            check(null == map.getObject(i * i));
            map.remove(i * i);
            check(!map.isObjectType(i * i));
            check(!map.isIntType(i * i));
        }

        int old_size = map.size();
        for (int i = 0; i != N; ++i) {
            map.remove(i * i);
            check(map.size() == old_size);
        }

        System.out.print("."); System.out.flush();
        map.clear();
        check(map.size() == 0);
        for (int i = 0; i != N; ++i) {
            map.put(i * i, i);
            map.put(i * i + 1, new Double(i+0.5));
        }
        checkSameMaps(map, (UintMap)writeAndRead(map));

        System.out.print("."); System.out.flush();
        map = new UintMap(0);
        checkSameMaps(map, (UintMap)writeAndRead(map));
        map = new UintMap(1);
        checkSameMaps(map, (UintMap)writeAndRead(map));
        map = new UintMap(1000);
        checkSameMaps(map, (UintMap)writeAndRead(map));

        System.out.print("."); System.out.flush();
        map = new UintMap(N / 10);
        for (int i = 0; i != N; ++i) {
            map.put(2*i+1, i);
        }
        checkSameMaps(map, (UintMap)writeAndRead(map));

        System.out.print("."); System.out.flush();
        map = new UintMap(N / 10);
        for (int i = 0; i != N; ++i) {
            map.put(2*i+1, i);
        }
        for (int i = 0; i != N / 2; ++i) {
            map.remove(2*i+1);
        }
        checkSameMaps(map, (UintMap)writeAndRead(map));

        System.out.print("."); System.out.flush();
        map = new UintMap();
        for (int i = 0; i != N; ++i) {
            map.put(2*i+1, new Double(i + 10));
        }
        for (int i = 0; i != N / 2; ++i) {
            map.remove(2*i+1);
        }
        checkSameMaps(map, (UintMap)writeAndRead(map));

        System.out.println(); System.out.flush();

    }

    private static void checkSameMaps(UintMap map1, UintMap map2) {
        check(map1.size() == map2.size());
        int[] keys = map1.getKeys();
        check(keys.length == map1.size());
        for (int i = 0; i != keys.length; ++i) {
            int key = keys[i];
            check(map2.has(key));
            check(map1.isObjectType(key) == map2.isObjectType(key));
            check(map1.isIntType(key) == map2.isIntType(key));
            Object o1 = map1.getObject(key);
            Object o2 = map2.getObject(key);
            if (map1.isObjectType(key)) {
                check(o1.equals(o2));
            }else {
                check(map1.getObject(key) == null);
                check(map2.getObject(key) == null);
            }
            if (map1.isIntType(key)) {
                check(map1.getExistingInt(key) == map2.getExistingInt(key));
            }else {
                check(map1.getInt(key, -10) == -10);
                check(map1.getInt(key, -11) == -11);
                check(map2.getInt(key, -10) == -10);
                check(map2.getInt(key, -11) == -11);
            }
        }
    }

    private static void check(boolean condition) {
        if (!condition) Kit.codeBug();
    }

    private static Object writeAndRead(Object obj) {
        try {
            java.io.ByteArrayOutputStream
                bos = new java.io.ByteArrayOutputStream();
            java.io.ObjectOutputStream
                out = new java.io.ObjectOutputStream(bos);
            out.writeObject(obj);
            out.close();
            byte[] data = bos.toByteArray();
            java.io.ByteArrayInputStream
                bis = new java.io.ByteArrayInputStream(data);
            java.io.ObjectInputStream
                in = new java.io.ObjectInputStream(bis);
            Object result = in.readObject();
            in.close();
            return result;
        }catch (Exception ex) {
            ex.printStackTrace();
            throw new RuntimeException("Unexpected");
        }
    }

// TEST END */
}