001: // Copyright (c) Corporation for National Research Initiatives
002: package org.python.core;
003:
004: /**
005: * A faster Dictionary where the keys have to be strings.
006: * <p>
007: * This is the default for all __dict__ instances.
008: */
009:
010: public class PyStringMap extends PyObject {
011: //Table of primes to cycle through
012: private static final int[] primes = { 7, 13, 31, 61, 127, 251, 509,
013: 1021, 2017, 4093, 5987, 9551, 15683, 19609, 31397, 65521,
014: 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593,
015: 16777213, 33554393, 67108859, 134217689, 268435399,
016: 536870909, 1073741789, };
017:
018: private transient String[] keys;
019: private transient PyObject[] values;
020: private int size;
021: private transient int filled;
022: private transient int prime;
023: private transient int popfinger;
024:
025: /* Override serialization behavior */
026: private void writeObject(java.io.ObjectOutputStream out)
027: throws java.io.IOException {
028: out.defaultWriteObject();
029:
030: String[] keyTable = keys;
031: PyObject[] valueTable = values;
032: int n = keyTable.length;
033:
034: for (int i = 0; i < n; i++) {
035: //String key = keyTable[i];
036: PyObject value = valueTable[i];
037: if (value == null)
038: continue;
039: out.writeUTF(keys[i]);
040: out.writeObject(values[i]);
041: }
042: }
043:
044: private void readObject(java.io.ObjectInputStream in)
045: throws java.io.IOException, ClassNotFoundException {
046: in.defaultReadObject();
047:
048: prime = 1;
049: keys = null;
050: values = null;
051: int n = size;
052:
053: resize(n);
054:
055: for (int i = 0; i < n; i++) {
056: String key = in.readUTF().intern();
057: insertkey(key, (PyObject) in.readObject());
058: }
059: }
060:
061: public PyStringMap(int capacity) {
062: prime = 0;
063: keys = null;
064: values = null;
065: resize(capacity);
066: }
067:
068: public PyStringMap() {
069: this (4);
070: }
071:
072: public PyStringMap(PyObject elements[]) {
073: this (elements.length);
074: for (int i = 0; i < elements.length; i += 2) {
075: __setitem__(elements[i], elements[i + 1]);
076: }
077: }
078:
079: public synchronized int __len__() {
080: return size;
081: }
082:
083: public synchronized boolean __nonzero__() {
084: return size != 0;
085: }
086:
087: public synchronized PyObject __finditem__(String key) {
088: String[] table = keys;
089: int maxindex = table.length;
090: int index = (System.identityHashCode(key) & 0x7fffffff)
091: % maxindex;
092:
093: // Fairly aribtrary choice for stepsize...
094: int stepsize = maxindex / 5;
095:
096: // Cycle through possible positions for the key;
097: //int collisions = 0;
098: while (true) {
099: String tkey = table[index];
100: if (tkey == key) {
101: //if (collisions > 0) {
102: // System.err.println("key: "+key+", "+collisions+", "+
103: // maxindex+", "+System.identityHashCode(key));
104: //}
105: return values[index];
106: }
107: if (tkey == null)
108: return values[index];
109:
110: //collisions++;
111: index = (index + stepsize) % maxindex;
112: }
113: }
114:
115: public PyObject __finditem__(PyObject key) {
116: //System.err.println("oops: "+key);
117: if (key instanceof PyString) {
118: return __finditem__(((PyString) key).internedString());
119: } else {
120: return null;
121: }
122: }
123:
124: public PyObject __iter__() {
125: return new PyStringMapIter(keys, values);
126: }
127:
128: private final void insertkey(String key, PyObject value) {
129: String[] table = keys;
130: int maxindex = table.length;
131: int index = (System.identityHashCode(key) & 0x7fffffff)
132: % maxindex;
133:
134: // Fairly aribtrary choice for stepsize...
135: int stepsize = maxindex / 5;
136:
137: int free_index = -1;
138:
139: // Cycle through possible positions for the key;
140: while (true) {
141: String tkey = table[index];
142: if (tkey == null) {
143: if (free_index == -1) {
144: filled++;
145: free_index = index;
146: }
147: break;
148: } else if (tkey == key) {
149: values[index] = value;
150: return;
151: } else if (tkey == "<deleted key>" && free_index == -1) {
152: free_index = index;
153: }
154: index = (index + stepsize) % maxindex;
155: }
156: table[free_index] = key;
157: values[free_index] = value;
158: size++;
159: return;
160: }
161:
162: private synchronized final void resize(int capacity) {
163: int p = prime;
164: for (; p < primes.length; p++) {
165: if (primes[p] >= capacity)
166: break;
167: }
168: if (primes[p] < capacity) {
169: throw Py.ValueError("can't make hashtable of size: "
170: + capacity);
171: }
172: //System.err.println("resize: "+(keys != null ? keys.length : -1)+
173: // ", "+primes[p]);
174: capacity = primes[p];
175: prime = p;
176:
177: String[] oldKeys = keys;
178: PyObject[] oldValues = values;
179:
180: keys = new String[capacity];
181: values = new PyObject[capacity];
182: size = 0;
183: filled = 0;
184:
185: if (oldValues != null) {
186: int n = oldValues.length;
187:
188: for (int i = 0; i < n; i++) {
189: PyObject value = oldValues[i];
190: if (value == null)
191: continue;
192: insertkey(oldKeys[i], value);
193: }
194: }
195: }
196:
197: public synchronized void __setitem__(String key, PyObject value) {
198: if (2 * filled > keys.length)
199: resize(keys.length + 1);
200: insertkey(key, value);
201: }
202:
203: public void __setitem__(PyObject key, PyObject value) {
204: if (key instanceof PyString) {
205: __setitem__(((PyString) key).internedString(), value);
206: } else {
207: throw Py.TypeError("keys in namespace must be strings");
208: }
209: }
210:
211: public synchronized void __delitem__(String key) {
212: String[] table = keys;
213: int maxindex = table.length;
214: int index = (System.identityHashCode(key) & 0x7fffffff)
215: % maxindex;
216:
217: // Fairly aribtrary choice for stepsize...
218: int stepsize = maxindex / 5;
219:
220: // Cycle through possible positions for the key;
221: while (true) {
222: String tkey = table[index];
223: if (tkey == null) {
224: throw Py.KeyError(key);
225: }
226: if (tkey == key) {
227: table[index] = "<deleted key>";
228: values[index] = null;
229: size--;
230: break;
231: }
232: index = (index + stepsize) % maxindex;
233: }
234: }
235:
236: public void __delitem__(PyObject key) {
237: if (key instanceof PyString) {
238: __delitem__(((PyString) key).internedString());
239: } else {
240: throw Py.KeyError(key.toString());
241: }
242: }
243:
244: /**
245: * Remove all items from the dictionary.
246: */
247: public synchronized void clear() {
248: for (int i = 0; i < keys.length; i++) {
249: keys[i] = null;
250: values[i] = null;
251: }
252: size = 0;
253: }
254:
255: public synchronized String toString() {
256: ThreadState ts = Py.getThreadState();
257: if (!ts.enterRepr(this )) {
258: return "{...}";
259: }
260:
261: String[] keyTable = keys;
262: PyObject[] valueTable = values;
263: int n = keyTable.length;
264:
265: StringBuffer buf = new StringBuffer("{");
266:
267: for (int i = 0; i < n; i++) {
268: //String key = keyTable[i];
269: PyObject value = valueTable[i];
270: if (value == null)
271: continue;
272: buf.append("'");
273: buf.append(keyTable[i]);
274: buf.append("': ");
275: buf.append(value.__repr__().toString());
276: buf.append(", ");
277: }
278:
279: // A hack to remove the final ", " from the string repr
280: int len = buf.length();
281: if (len > 4) {
282: buf.setLength(len - 2);
283: }
284:
285: buf.append("}");
286: ts.exitRepr(this );
287: return buf.toString();
288: }
289:
290: public synchronized int __cmp__(PyObject other) {
291: if (!(other instanceof PyStringMap || other instanceof PyDictionary)) {
292: return -2;
293: }
294: int an = __len__();
295: int bn = other.__len__();
296: if (an < bn)
297: return -1;
298: if (an > bn)
299: return 1;
300:
301: PyList akeys = keys();
302: PyList bkeys = null;
303: if (other instanceof PyStringMap) {
304: bkeys = ((PyStringMap) other).keys();
305: } else {
306: bkeys = ((PyDictionary) other).keys();
307: }
308: akeys.sort();
309: bkeys.sort();
310:
311: for (int i = 0; i < bn; i++) {
312: PyObject akey = akeys.pyget(i);
313: PyObject bkey = bkeys.pyget(i);
314: int c = akey._cmp(bkey);
315: if (c != 0)
316: return c;
317:
318: PyObject avalue = __finditem__(akey);
319: PyObject bvalue = other.__finditem__(bkey);
320: c = avalue._cmp(bvalue);
321: if (c != 0)
322: return c;
323: }
324: return 0;
325: }
326:
327: /**
328: * Return true if the key exist in the dictionary.
329: */
330: public boolean has_key(PyObject key) {
331: return __finditem__(key) != null;
332: }
333:
334: /**
335: * Return this[key] if the key exists in the mapping, default_object
336: * is returned otherwise.
337: *
338: * @param key the key to lookup in the mapping.
339: * @param default_object the value to return if the key does not
340: * exists in the mapping.
341: */
342: public PyObject get(PyObject key, PyObject default_object) {
343: PyObject o = __finditem__(key);
344: if (o == null)
345: return default_object;
346: else
347: return o;
348: }
349:
350: /**
351: * Return this[key] if the key exists in the mapping, None
352: * is returned otherwise.
353: *
354: * @param key the key to lookup in the mapping.
355: */
356: public PyObject get(PyObject key) {
357: return get(key, Py.None);
358: }
359:
360: /**
361: * Return a shallow copy of the dictionary.
362: */
363: public synchronized PyStringMap copy() {
364: int n = keys.length;
365:
366: PyStringMap map = new PyStringMap(n);
367: System.arraycopy(keys, 0, map.keys, 0, n);
368: System.arraycopy(values, 0, map.values, 0, n);
369:
370: map.filled = filled;
371: map.size = size;
372: map.prime = prime;
373:
374: return map;
375: }
376:
377: /**
378: * Insert all the key:value pairs from <code>map</code> into
379: * this mapping.
380: */
381: public synchronized void update(PyStringMap map) {
382: String[] keyTable = map.keys;
383: PyObject[] valueTable = map.values;
384: int n = keyTable.length;
385:
386: if (2 * filled + n > keys.length)
387: resize(2 * filled + n);
388:
389: for (int i = 0; i < n; i++) {
390: String key = keyTable[i];
391: if (key == null || key == "<deleted key>")
392: continue;
393: insertkey(key, valueTable[i]);
394: }
395: }
396:
397: /**
398: * Insert all the key:value pairs from <code>dict</code> into
399: * this mapping.
400: */
401: public void update(PyDictionary dict) {
402: java.util.Hashtable table = dict.table;
403:
404: java.util.Enumeration ek = table.keys();
405: java.util.Enumeration ev = table.elements();
406: int n = table.size();
407:
408: for (int i = 0; i < n; i++) {
409: __setitem__((PyObject) ek.nextElement(), (PyObject) ev
410: .nextElement());
411: }
412: }
413:
414: /**
415: * Return this[key] if the key exist, otherwise insert key with
416: * a None value and return None.
417: *
418: * @param key the key to lookup in the mapping.
419: */
420: public PyObject setdefault(PyObject key) {
421: return setdefault(key, Py.None);
422: }
423:
424: /**
425: * Return this[key] if the key exist, otherwise insert key with
426: * the value of failobj and return failobj
427: *
428: * @param key the key to lookup in the mapping.
429: * @param failobj the default value to insert in the mapping
430: * if key does not already exist.
431: */
432: public PyObject setdefault(PyObject key, PyObject failobj) {
433: PyObject o = __finditem__(key);
434: if (o == null)
435: __setitem__(key, o = failobj);
436: return o;
437: }
438:
439: /**
440: * Return a random (key, value) tuple pair and remove the pair
441: * from the mapping.
442: */
443: public synchronized PyObject popitem() {
444: if (size == 0)
445: throw Py.KeyError("popitem(): dictionary is empty");
446:
447: String[] table = keys;
448: int maxindex = table.length;
449: int index = popfinger;
450:
451: if (index >= maxindex || index < 0)
452: index = 1;
453: while (true) {
454: String tKey = table[index];
455: if (tKey != null && tKey != "<deleted key>")
456: break;
457: index++;
458: if (index >= maxindex)
459: index = 0;
460: }
461:
462: popfinger = index + 1;
463: PyObject key = Py.newString(table[index]);
464: PyObject val = (PyObject) values[index];
465:
466: table[index] = "<deleted key>";
467: values[index] = null;
468: size--;
469:
470: return new PyTuple(new PyObject[] { key, val });
471: }
472:
473: /**
474: * Return a copy of the mappings list of (key, value) tuple
475: * pairs.
476: */
477: public synchronized PyList items() {
478: String[] keyTable = keys;
479: PyObject[] valueTable = values;
480: int n = keyTable.length;
481:
482: PyList l = new PyList();
483: for (int i = 0; i < n; i++) {
484: String key = keyTable[i];
485: if (key == null || key == "<deleted key>"
486: || values[i] == null)
487: continue;
488: l.append(new PyTuple(new PyObject[] { new PyString(key),
489: valueTable[i] }));
490: }
491: return l;
492: }
493:
494: synchronized String[] jkeys() {
495: String[] keyTable = keys;
496: //PyObject[] valueTable = values;
497: int n = keyTable.length;
498:
499: String[] newKeys = new String[size];
500: int j = 0;
501:
502: for (int i = 0; i < n; i++) {
503: String key = keyTable[i];
504: if (key == null || key == "<deleted key>")
505: continue;
506: newKeys[j++] = key;
507: }
508: return newKeys;
509: }
510:
511: /**
512: * Return a copy of the mappings list of keys.
513: */
514: public synchronized PyList keys() {
515: String[] keyTable = keys;
516: //PyObject[] valueTable = values;
517: int n = keyTable.length;
518:
519: PyList l = new PyList();
520: for (int i = 0; i < n; i++) {
521: String key = keyTable[i];
522: if (key == null || key == "<deleted key>"
523: || values[i] == null)
524: continue;
525: l.append(new PyString(key));
526: }
527: return l;
528: }
529:
530: /**
531: * Return a copy of the mappings list of values.
532: */
533: public synchronized PyList values() {
534: PyObject[] valueTable = values;
535: int n = valueTable.length;
536:
537: PyList l = new PyList();
538: for (int i = 0; i < n; i++) {
539: PyObject value = valueTable[i];
540: if (value == null)
541: continue;
542: l.append(value);
543: }
544: return l;
545: }
546:
547: /**
548: * return an iterator over (key, value) pairs
549: */
550: public synchronized PyObject iteritems() {
551: return new PyStringMapIter(keys, values, PyStringMapIter.ITEMS);
552: }
553:
554: /**
555: * return an iterator over the keys
556: */
557: public synchronized PyObject iterkeys() {
558: return new PyStringMapIter(keys, values, PyStringMapIter.KEYS);
559: }
560:
561: /**
562: * return an iterator over the values
563: */
564: public synchronized PyObject itervalues() {
565: return new PyStringMapIter(keys, values, PyStringMapIter.VALUES);
566: }
567: }
568:
569: /* extended, based on PyDictionaryIter */
570: class PyStringMapIter extends PyIterator {
571: String[] keyTable;
572: PyObject[] valTable;
573: private int idx;
574: private int type;
575:
576: public static final int KEYS = 0;
577: public static final int VALUES = 1;
578: public static final int ITEMS = 2;
579:
580: public PyStringMapIter(String[] keys, PyObject[] values) {
581: this (keys, values, KEYS);
582: }
583:
584: public PyStringMapIter(String[] keys, PyObject[] values, int type) {
585: this .keyTable = keys;
586: this .valTable = values;
587: this .idx = 0;
588: this .type = type;
589: }
590:
591: public PyObject __iternext__() {
592: int n = keyTable.length;
593:
594: for (; idx < n; idx++) {
595: String key = keyTable[idx];
596: PyObject val = valTable[idx];
597: if (key == null || key == "<deleted key>" || val == null)
598: continue;
599: idx++;
600:
601: switch (type) {
602: case VALUES:
603: return val;
604: case ITEMS:
605: return new PyTuple(new PyObject[] { Py.newString(key),
606: val });
607: default: // KEYS
608: return Py.newString(key);
609: }
610: }
611: return null;
612: }
613: }
|