pystringmap.java

无线通信的主要编程软件,是无线通信工作人员的必备工具,关天相关教程我会在后续传上.

// Copyright (c) Corporation for National Research Initiatives

// Modified for tinyos by Michael Demmer ([e-mail]) to
// use java.lang.String hashCode() and equals() methods, not to use
// System.identityHashCode() and the == operator.

package org.python.core;

/**
 * A faster Dictionary where the keys have to be strings.
 * <p>
 * This is the default for all __dict__ instances.
 */

public class PyStringMap extends PyObject
{
    //Table of primes to cycle through
    private static final int[] primes = {
        7, 13, 31, 61, 127, 251, 509, 1021, 2017, 4093,
        5987, 9551, 15683, 19609, 31397,
        65521, 131071, 262139, 524287, 1048573, 2097143,
        4194301, 8388593, 16777213, 33554393, 67108859,
        134217689, 268435399, 536870909, 1073741789,};

    private transient String[] keys;
    private transient PyObject[] values;
    private int size;
    private transient int filled;
    private transient int prime;
    private transient int popfinger;

    /* Override serialization behavior */
    private void writeObject(java.io.ObjectOutputStream out)
        throws java.io.IOException
    {
        out.defaultWriteObject();

        String[] keyTable = keys;
        PyObject[] valueTable = values;
        int n = keyTable.length;

        for (int i=0; i<n; i++) {
            //String key = keyTable[i];
            PyObject value = valueTable[i];
            if (value == null)
                continue;
            out.writeUTF(keys[i]);
            out.writeObject(values[i]);
        }
    }

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

        prime = 1;
        keys = null;
        values = null;
        int n = size;

        resize(n);

        for (int i=0; i<n; i++) {
            String key = in.readUTF().intern();
            insertkey(key, (PyObject)in.readObject());
        }
    }

    public static PyClass __class__;

    public PyStringMap(int capacity) {
        super(__class__);
        prime = 0;
        keys = null;
        values = null;
        resize(capacity);
    }

    public PyStringMap() {
        this(4);
    }

    public PyStringMap(PyObject elements[]) {
        this(elements.length);
        for (int i=0; i<elements.length; i+=2) {
            __setitem__(elements[i], elements[i+1]);
        }
    }

    public synchronized int __len__() {
        return size;
    }

    public synchronized boolean __nonzero__() {
        return size != 0;
    }

    private final int myHashCode(String key) {
        if (key == null) return 0;
        return key.hashCode();
    }

    public synchronized PyObject __finditem__(String key) {
        String[] table = keys;
        int maxindex = table.length;
        int index = (myHashCode(key) & 0x7fffffff) % maxindex;

        // Fairly aribtrary choice for stepsize...
        int stepsize = maxindex / 5;

        // Cycle through possible positions for the key;
        //int collisions = 0;
        while (true) {
            String tkey = table[index];

            if (tkey == null)
                return values[index];
            
            if (tkey.equals(key)) {
                //if (collisions > 0) {
                //    System.err.println("key: "+key+", "+collisions+", "+
                //               maxindex+", "+System.identityHashCode(key));
                //}
                return values[index];
            }

            //collisions++;
            index = (index+stepsize) % maxindex;
        }
    }

    public PyObject __finditem__(PyObject key) {
        //System.err.println("oops: "+key);
        if (key instanceof PyString) {
            return __finditem__(((PyString)key).internedString());
        } else {
            return null;
        }
    }

    public PyObject __iter__() {
        return new PyStringMapIter(keys, values);
    }

    private final void insertkey(String key, PyObject value) {
        String[] table = keys;
        int maxindex = table.length;
        int index = (myHashCode(key) & 0x7fffffff) % maxindex;
        int orig = index;

        // Fairly aribtrary choice for stepsize...
        int stepsize = maxindex / 5;
 
        int free_index = -1;

        // Cycle through possible positions for the key;
        while (true) {
            String tkey = table[index];
            if (tkey == null) {
                if (free_index == -1 ) {
                    filled++;
                    free_index = index;
                }
                break;
            } else if (tkey.equals(key)) {
                values[index] = value;
                return;
            } else if (tkey == "<deleted key>" && free_index == -1) {
                free_index = index;
            }
            index = (index+stepsize) % maxindex;
        }
        table[free_index] = key;
        values[free_index] = value;
        size++;
        return;        
    }

    private synchronized final void resize(int capacity) {
        int p = prime;
        for (; p<primes.length; p++) {
            if (primes[p] >= capacity)
                break;
        }
        if (primes[p] < capacity) {
            throw Py.ValueError("can't make hashtable of size: "+capacity);
        }
        //System.err.println("resize: "+(keys != null ? keys.length : -1)+
        //                   ", "+primes[p]);
        capacity = primes[p];
        prime = p;

        String[] oldKeys = keys;
        PyObject[] oldValues = values;

        keys = new String[capacity];
        values = new PyObject[capacity];
        size = 0;
        filled = 0;

        if (oldValues != null) {
            int n = oldValues.length;

            for (int i=0; i<n; i++) {
                PyObject value = oldValues[i];
                if (value == null)
                    continue;
                insertkey(oldKeys[i], value);
            }
        }
    }

    public synchronized void __setitem__(String key, PyObject value) {
        if (2*filled > keys.length)
            resize(keys.length+1);
        insertkey(key, value);
    }

    public void __setitem__(PyObject key, PyObject value) {
        if (key instanceof PyString) {
            __setitem__(((PyString)key).internedString(), value);
        } else {
            throw Py.TypeError("keys in namespace must be strings");
        }
    }

    public synchronized void __delitem__(String key) {
        String[] table = keys;
        int maxindex = table.length;
        int index = (myHashCode(key) & 0x7fffffff) % maxindex;

        // Fairly aribtrary choice for stepsize...
        int stepsize = maxindex / 5;

        // Cycle through possible positions for the key;
        while (true) {
            String tkey = table[index];
            if (tkey == null) {
                throw Py.KeyError(key);
            }
            if (tkey.equals(key)) {
                table[index] = "<deleted key>";
                values[index] = null;
                size--;
                break;
            }
            index = (index+stepsize) % maxindex;
        }
    }

    public void __delitem__(PyObject key) {
        if (key instanceof PyString) {
            __delitem__(((PyString)key).internedString());
        } else {
            throw Py.KeyError(key.toString());
        }
    }

    /**
     * Remove all items from the dictionary.
     */
    public synchronized void clear() {
        for (int i=0; i<keys.length; i++) {
            keys[i] = null;
            values[i] = null;
        }
        size = 0;
    }


    public synchronized String toString() {
        ThreadState ts = Py.getThreadState();
        if (!ts.enterRepr(this)) {
            return "{...}";
        }

        String[] keyTable = keys;
        PyObject[] valueTable = values;
        int n = keyTable.length;

        StringBuffer buf = new StringBuffer("{");

        for (int i=0; i<n; i++) {
            //String key = keyTable[i];
            PyObject value = valueTable[i];
            if (value == null)
                continue;
            buf.append("'");
            buf.append(keyTable[i]);
            buf.append("': ");
            buf.append(value.__repr__().toString());
            buf.append(", ");
        }

        // A hack to remove the final ", " from the string repr
        int len = buf.length();
        if (len > 4) {