0001: /***** BEGIN LICENSE BLOCK *****
0002: * Version: CPL 1.0/GPL 2.0/LGPL 2.1
0003: *
0004: * The contents of this file are subject to the Common Public
0005: * License Version 1.0 (the "License"); you may not use this file
0006: * except in compliance with the License. You may obtain a copy of
0007: * the License at http://www.eclipse.org/legal/cpl-v10.html
0008: *
0009: * Software distributed under the License is distributed on an "AS
0010: * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
0011: * implied. See the License for the specific language governing
0012: * rights and limitations under the License.
0013: *
0014: * Copyright (C) 2001 Chad Fowler <chadfowler@chadfowler.com>
0015: * Copyright (C) 2001 Alan Moore <alan_moore@gmx.net>
0016: * Copyright (C) 2001-2002 Benoit Cerrina <b.cerrina@wanadoo.fr>
0017: * Copyright (C) 2001-2004 Jan Arne Petersen <jpetersen@uni-bonn.de>
0018: * Copyright (C) 2002-2004 Anders Bengtsson <ndrsbngtssn@yahoo.se>
0019: * Copyright (C) 2004-2006 Thomas E Enebo <enebo@acm.org>
0020: * Copyright (C) 2004 Stefan Matthias Aust <sma@3plus4.de>
0021: * Copyright (C) 2005 Charles O Nutter <headius@headius.com>
0022: * Copyright (C) 2006 Ola Bini <Ola.Bini@ki.se>
0023: * Copyright (C) 2006 Tim Azzopardi <tim@tigerfive.com>
0024: * Copyright (C) 2006 Miguel Covarrubias <mlcovarrubias@gmail.com>
0025: *
0026: * Alternatively, the contents of this file may be used under the terms of
0027: * either of the GNU General Public License Version 2 or later (the "GPL"),
0028: * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
0029: * in which case the provisions of the GPL or the LGPL are applicable instead
0030: * of those above. If you wish to allow use of your version of this file only
0031: * under the terms of either the GPL or the LGPL, and not to allow others to
0032: * use your version of this file under the terms of the CPL, indicate your
0033: * decision by deleting the provisions above and replace them with the notice
0034: * and other provisions required by the GPL or the LGPL. If you do not delete
0035: * the provisions above, a recipient may use your version of this file under
0036: * the terms of any one of the CPL, the GPL or the LGPL.
0037: ***** END LICENSE BLOCK *****/package org.jruby;
0038:
0039: import java.io.IOException;
0040: import java.util.AbstractCollection;
0041: import java.util.AbstractSet;
0042: import java.util.Collection;
0043: import java.util.Iterator;
0044: import java.util.Map;
0045: import java.util.NoSuchElementException;
0046: import java.util.Set;
0047: import org.jruby.javasupport.JavaUtil;
0048: import org.jruby.runtime.Arity;
0049: import org.jruby.runtime.Block;
0050: import org.jruby.runtime.CallbackFactory;
0051: import org.jruby.runtime.CallType;
0052: import org.jruby.runtime.ClassIndex;
0053: import org.jruby.runtime.MethodIndex;
0054: import org.jruby.runtime.ObjectAllocator;
0055: import org.jruby.runtime.ThreadContext;
0056: import org.jruby.runtime.builtin.IRubyObject;
0057: import org.jruby.runtime.marshal.MarshalStream;
0058: import org.jruby.runtime.marshal.UnmarshalStream;
0059:
0060: /** Implementation of the Hash class.
0061: *
0062: * @author jpetersen
0063: */
0064: public class RubyHash extends RubyObject implements Map {
0065:
0066: public static RubyClass createHashClass(Ruby runtime) {
0067: RubyClass hashc = runtime.defineClass("Hash", runtime
0068: .getObject(), HASH_ALLOCATOR);
0069: hashc.index = ClassIndex.HASH;
0070: CallbackFactory callbackFactory = runtime
0071: .callbackFactory(RubyHash.class);
0072:
0073: hashc.includeModule(runtime.getModule("Enumerable"));
0074: hashc.getMetaClass().defineMethod("[]",
0075: callbackFactory.getOptSingletonMethod("create"));
0076:
0077: hashc.defineMethod("initialize", callbackFactory
0078: .getOptMethod("initialize"));
0079: hashc.defineFastMethod("initialize_copy", callbackFactory
0080: .getFastMethod("replace", RubyKernel.IRUBY_OBJECT));
0081: hashc.defineFastMethod("rehash", callbackFactory
0082: .getFastMethod("rehash"));
0083:
0084: hashc.defineFastMethod("to_hash", callbackFactory
0085: .getFastMethod("to_hash"));
0086: hashc.defineFastMethod("to_a", callbackFactory
0087: .getFastMethod("to_a"));
0088: hashc.defineFastMethod("to_s", callbackFactory
0089: .getFastMethod("to_s"));
0090: hashc.defineFastMethod("inspect", callbackFactory
0091: .getFastMethod("inspect"));
0092:
0093: hashc.defineFastMethod("==", callbackFactory.getFastMethod(
0094: "equal", RubyKernel.IRUBY_OBJECT));
0095: hashc.defineFastMethod("[]", callbackFactory.getFastMethod(
0096: "aref", RubyKernel.IRUBY_OBJECT));
0097: hashc.defineMethod("fetch", callbackFactory
0098: .getOptMethod("fetch"));
0099: hashc.defineFastMethod("[]=", callbackFactory.getFastMethod(
0100: "aset", RubyKernel.IRUBY_OBJECT,
0101: RubyKernel.IRUBY_OBJECT));
0102: hashc.defineFastMethod("store", callbackFactory.getFastMethod(
0103: "aset", RubyKernel.IRUBY_OBJECT,
0104: RubyKernel.IRUBY_OBJECT));
0105: hashc.defineMethod("default", callbackFactory
0106: .getFastOptMethod("default_value_get"));
0107: hashc.defineFastMethod("default=", callbackFactory
0108: .getFastMethod("default_value_set",
0109: RubyKernel.IRUBY_OBJECT));
0110: hashc.defineMethod("default_proc", callbackFactory
0111: .getFastMethod("default_proc"));
0112: hashc.defineFastMethod("index", callbackFactory.getFastMethod(
0113: "index", RubyKernel.IRUBY_OBJECT));
0114: hashc.defineFastMethod("indexes", callbackFactory
0115: .getFastOptMethod("indices"));
0116: hashc.defineFastMethod("indices", callbackFactory
0117: .getFastOptMethod("indices"));
0118: hashc.defineFastMethod("size", callbackFactory
0119: .getFastMethod("rb_size"));
0120: hashc.defineFastMethod("length", callbackFactory
0121: .getFastMethod("rb_size"));
0122: hashc.defineFastMethod("empty?", callbackFactory
0123: .getFastMethod("empty_p"));
0124:
0125: hashc.defineMethod("each", callbackFactory.getMethod("each"));
0126: hashc.defineMethod("each_value", callbackFactory
0127: .getMethod("each_value"));
0128: hashc.defineMethod("each_key", callbackFactory
0129: .getMethod("each_key"));
0130: hashc.defineMethod("each_pair", callbackFactory
0131: .getMethod("each_pair"));
0132: hashc.defineMethod("sort", callbackFactory.getMethod("sort"));
0133:
0134: hashc.defineFastMethod("keys", callbackFactory
0135: .getFastMethod("keys"));
0136: hashc.defineFastMethod("values", callbackFactory
0137: .getFastMethod("rb_values"));
0138: hashc.defineFastMethod("values_at", callbackFactory
0139: .getFastOptMethod("values_at"));
0140:
0141: hashc.defineFastMethod("shift", callbackFactory
0142: .getFastMethod("shift"));
0143: hashc.defineMethod("delete", callbackFactory.getMethod(
0144: "delete", RubyKernel.IRUBY_OBJECT));
0145: hashc.defineMethod("delete_if", callbackFactory
0146: .getMethod("delete_if"));
0147: hashc.defineMethod("select", callbackFactory
0148: .getOptMethod("select"));
0149: hashc.defineMethod("reject", callbackFactory
0150: .getMethod("reject"));
0151: hashc.defineMethod("reject!", callbackFactory
0152: .getMethod("reject_bang"));
0153: hashc.defineFastMethod("clear", callbackFactory
0154: .getFastMethod("rb_clear"));
0155: hashc.defineFastMethod("invert", callbackFactory
0156: .getFastMethod("invert"));
0157: hashc.defineMethod("update", callbackFactory.getMethod(
0158: "update", RubyKernel.IRUBY_OBJECT));
0159: hashc.defineFastMethod("replace", callbackFactory
0160: .getFastMethod("replace", RubyKernel.IRUBY_OBJECT));
0161: hashc.defineMethod("merge!", callbackFactory.getMethod(
0162: "update", RubyKernel.IRUBY_OBJECT));
0163: hashc.defineMethod("merge", callbackFactory.getMethod("merge",
0164: RubyKernel.IRUBY_OBJECT));
0165:
0166: hashc.defineFastMethod("include?", callbackFactory
0167: .getFastMethod("has_key", RubyKernel.IRUBY_OBJECT));
0168: hashc.defineFastMethod("member?", callbackFactory
0169: .getFastMethod("has_key", RubyKernel.IRUBY_OBJECT));
0170: hashc.defineFastMethod("has_key?", callbackFactory
0171: .getFastMethod("has_key", RubyKernel.IRUBY_OBJECT));
0172: hashc.defineFastMethod("has_value?", callbackFactory
0173: .getFastMethod("has_value", RubyKernel.IRUBY_OBJECT));
0174: hashc.defineFastMethod("key?", callbackFactory.getFastMethod(
0175: "has_key", RubyKernel.IRUBY_OBJECT));
0176: hashc.defineFastMethod("value?", callbackFactory.getFastMethod(
0177: "has_value", RubyKernel.IRUBY_OBJECT));
0178:
0179: return hashc;
0180: }
0181:
0182: private final static ObjectAllocator HASH_ALLOCATOR = new ObjectAllocator() {
0183: public IRubyObject allocate(Ruby runtime, RubyClass klass) {
0184: return new RubyHash(runtime, klass);
0185: }
0186: };
0187:
0188: public int getNativeTypeIndex() {
0189: return ClassIndex.HASH;
0190: }
0191:
0192: public static final byte AREF_SWITCHVALUE = 1;
0193: public static final byte ASET_SWITCHVALUE = 2;
0194: public static final byte DEFAULT_SWITCHVALUE = 3;
0195: public static final byte NIL_P_SWITCHVALUE = 4;
0196: public static final byte EQUALEQUAL_SWITCHVALUE = 5;
0197: public static final byte EMPTY_P_SWITCHVALUE = 6;
0198: public static final byte TO_S_SWITCHVALUE = 7;
0199: public static final byte TO_A_SWITCHVALUE = 8;
0200: public static final byte HASH_SWITCHVALUE = 9;
0201: public static final byte LENGTH_SWITCHVALUE = 10;
0202: public static final byte TO_HASH_SWITCHVALUE = 11;
0203: public static final byte EQL_P_SWITCHVALUE = 12;
0204: public static final byte INSPECT_SWITCHVALUE = 13;
0205:
0206: public IRubyObject callMethod(ThreadContext context,
0207: RubyModule rubyclass, int methodIndex, String name,
0208: IRubyObject[] args, CallType callType, Block block) {
0209: // If tracing is on, don't do STI dispatch
0210: if (context.getRuntime().hasEventHooks())
0211: return super .callMethod(context, rubyclass, name, args,
0212: callType, block);
0213:
0214: switch (getRuntime().getSelectorTable().table[rubyclass.index][methodIndex]) {
0215: case AREF_SWITCHVALUE:
0216: if (args.length != 1)
0217: throw context.getRuntime().newArgumentError(
0218: "wrong number of arguments(" + args.length
0219: + " for " + 1 + ")");
0220: return aref(args[0]);
0221: case ASET_SWITCHVALUE:
0222: if (args.length != 2)
0223: throw context.getRuntime().newArgumentError(
0224: "wrong number of arguments(" + args.length
0225: + " for " + 2 + ")");
0226: return aset(args[0], args[1]);
0227: case DEFAULT_SWITCHVALUE:
0228: return default_value_get(args);
0229: case NIL_P_SWITCHVALUE:
0230: if (args.length != 0)
0231: throw context.getRuntime().newArgumentError(
0232: "wrong number of arguments(" + args.length
0233: + " for " + 0 + ")");
0234: return nil_p();
0235: case EQUALEQUAL_SWITCHVALUE:
0236: if (args.length != 1)
0237: throw context.getRuntime().newArgumentError(
0238: "wrong number of arguments(" + args.length
0239: + " for " + 1 + ")");
0240: return equal(args[0]);
0241: case EMPTY_P_SWITCHVALUE:
0242: if (args.length != 0)
0243: throw context.getRuntime().newArgumentError(
0244: "wrong number of arguments(" + args.length
0245: + " for " + 0 + ")");
0246: return empty_p();
0247: case TO_S_SWITCHVALUE:
0248: if (args.length != 0)
0249: throw context.getRuntime().newArgumentError(
0250: "wrong number of arguments(" + args.length
0251: + " for " + 0 + ")");
0252: return to_s();
0253: case TO_A_SWITCHVALUE:
0254: if (args.length != 0)
0255: throw context.getRuntime().newArgumentError(
0256: "wrong number of arguments(" + args.length
0257: + " for " + 0 + ")");
0258: return to_a();
0259: case HASH_SWITCHVALUE:
0260: if (args.length != 0)
0261: throw context.getRuntime().newArgumentError(
0262: "wrong number of arguments(" + args.length
0263: + " for " + 0 + ")");
0264: return hash();
0265: case LENGTH_SWITCHVALUE:
0266: if (args.length != 0)
0267: throw context.getRuntime().newArgumentError(
0268: "wrong number of arguments(" + args.length
0269: + " for " + 0 + ")");
0270: return rb_size();
0271: case TO_HASH_SWITCHVALUE:
0272: if (args.length != 0)
0273: throw context.getRuntime().newArgumentError(
0274: "wrong number of arguments(" + args.length
0275: + " for " + 0 + ")");
0276: return to_hash();
0277: case EQL_P_SWITCHVALUE:
0278: if (args.length != 1)
0279: throw context.getRuntime().newArgumentError(
0280: "wrong number of arguments(" + args.length
0281: + " for " + 1 + ")");
0282: return obj_equal(args[0]);
0283: case INSPECT_SWITCHVALUE:
0284: if (args.length != 0)
0285: throw context.getRuntime().newArgumentError(
0286: "wrong number of arguments(" + args.length
0287: + " for " + 0 + ")");
0288: return inspect();
0289: case 0:
0290: default:
0291: return super .callMethod(context, rubyclass, name, args,
0292: callType, block);
0293: }
0294: }
0295:
0296: /** rb_hash_s_create
0297: *
0298: */
0299: public static IRubyObject create(IRubyObject recv,
0300: IRubyObject[] args, Block block) {
0301: RubyClass klass = (RubyClass) recv;
0302: RubyHash hash;
0303:
0304: if (args.length == 1 && args[0] instanceof RubyHash) {
0305: RubyHash otherHash = (RubyHash) args[0];
0306: return new RubyHash(recv.getRuntime(), klass, otherHash
0307: .internalCopyTable(), otherHash.size); // hash_alloc0
0308: }
0309:
0310: if ((args.length & 1) != 0)
0311: throw recv.getRuntime().newArgumentError(
0312: "odd number of args for Hash");
0313:
0314: hash = (RubyHash) klass.allocate();
0315: for (int i = 0; i < args.length; i += 2)
0316: hash.aset(args[i], args[i + 1]);
0317:
0318: return hash;
0319: }
0320:
0321: /** rb_hash_new
0322: *
0323: */
0324: public static final RubyHash newHash(Ruby runtime) {
0325: return new RubyHash(runtime);
0326: }
0327:
0328: /** rb_hash_new
0329: *
0330: */
0331: public static final RubyHash newHash(Ruby runtime, Map valueMap,
0332: IRubyObject defaultValue) {
0333: assert defaultValue != null;
0334:
0335: return new RubyHash(runtime, valueMap, defaultValue);
0336: }
0337:
0338: private RubyHashEntry[] table;
0339: private int size = 0;
0340: private int threshold;
0341:
0342: private int iterLevel = 0;
0343: private boolean deleted = false;
0344:
0345: private boolean procDefault = false;
0346: private IRubyObject ifNone;
0347:
0348: private RubyHash(Ruby runtime, RubyClass klass,
0349: RubyHashEntry[] newTable, int newSize) {
0350: super (runtime, klass);
0351: this .ifNone = runtime.getNil();
0352: threshold = INITIAL_THRESHOLD;
0353: table = newTable;
0354: size = newSize;
0355: }
0356:
0357: public RubyHash(Ruby runtime, RubyClass klass) {
0358: super (runtime, klass);
0359: this .ifNone = runtime.getNil();
0360: alloc();
0361: }
0362:
0363: public RubyHash(Ruby runtime) {
0364: this (runtime, runtime.getNil());
0365: }
0366:
0367: public RubyHash(Ruby runtime, IRubyObject defaultValue) {
0368: super (runtime, runtime.getHash());
0369: this .ifNone = defaultValue;
0370: alloc();
0371: }
0372:
0373: // TODO should this be deprecated ? (to be efficient, internals should deal with RubyHash directly)
0374: public RubyHash(Ruby runtime, Map valueMap, IRubyObject defaultValue) {
0375: super (runtime, runtime.getHash());
0376: this .ifNone = runtime.getNil();
0377: alloc();
0378:
0379: for (Iterator iter = valueMap.entrySet().iterator(); iter
0380: .hasNext();) {
0381: Map.Entry e = (Map.Entry) iter.next();
0382: internalPut((IRubyObject) e.getKey(), (IRubyObject) e
0383: .getValue());
0384: }
0385: }
0386:
0387: private final void alloc() {
0388: threshold = INITIAL_THRESHOLD;
0389: table = new RubyHashEntry[MRI_HASH_RESIZE ? MRI_INITIAL_CAPACITY
0390: : JAVASOFT_INITIAL_CAPACITY];
0391: }
0392:
0393: /* ============================
0394: * Here are hash internals
0395: * (This could be extracted to a separate class but it's not too large though)
0396: * ============================
0397: */
0398:
0399: private static final int MRI_PRIMES[] = { 8 + 3, 16 + 3, 32 + 5,
0400: 64 + 3, 128 + 3, 256 + 27, 512 + 9, 1024 + 9, 2048 + 5,
0401: 4096 + 3, 8192 + 27, 16384 + 43, 32768 + 3, 65536 + 45,
0402: 131072 + 29, 262144 + 3, 524288 + 21, 1048576 + 7,
0403: 2097152 + 17, 4194304 + 15, 8388608 + 9, 16777216 + 43,
0404: 33554432 + 35, 67108864 + 15, 134217728 + 29,
0405: 268435456 + 3, 536870912 + 11, 1073741824 + 85, 0 };
0406:
0407: private static final int JAVASOFT_INITIAL_CAPACITY = 8; // 16 ?
0408: private static final int MRI_INITIAL_CAPACITY = MRI_PRIMES[0];
0409:
0410: private static final int INITIAL_THRESHOLD = JAVASOFT_INITIAL_CAPACITY
0411: - (JAVASOFT_INITIAL_CAPACITY >> 2);
0412: private static final int MAXIMUM_CAPACITY = 1 << 30;
0413:
0414: static final class RubyHashEntry implements Map.Entry {
0415: private IRubyObject key;
0416: private IRubyObject value;
0417: private RubyHashEntry next;
0418: private int hash;
0419:
0420: RubyHashEntry(int h, IRubyObject k, IRubyObject v,
0421: RubyHashEntry e) {
0422: key = k;
0423: value = v;
0424: next = e;
0425: hash = h;
0426: }
0427:
0428: public Object getKey() {
0429: return key;
0430: }
0431:
0432: public Object getJavaifiedKey() {
0433: return JavaUtil.convertRubyToJava(key);
0434: }
0435:
0436: public Object getValue() {
0437: return value;
0438: }
0439:
0440: public Object getJavaifiedValue() {
0441: return JavaUtil.convertRubyToJava(value);
0442: }
0443:
0444: public Object setValue(Object value) {
0445: IRubyObject oldValue = this .value;
0446: if (value instanceof IRubyObject) {
0447: this .value = (IRubyObject) value;
0448: } else {
0449: throw new UnsupportedOperationException(
0450: "directEntrySet() doesn't support setValue for non IRubyObject instance entries, convert them manually or use entrySet() instead");
0451: }
0452: return oldValue;
0453: }
0454:
0455: public boolean equals(Object other) {
0456: if (!(other instanceof RubyHashEntry))
0457: return false;
0458: RubyHashEntry otherEntry = (RubyHashEntry) other;
0459: if (key == otherEntry.key && key != NEVER
0460: && key.eql(otherEntry.key)) {
0461: if (value == otherEntry.value
0462: || value.equals(otherEntry.value))
0463: return true;
0464: }
0465: return false;
0466: }
0467:
0468: public int hashCode() {
0469: return key.hashCode() ^ value.hashCode();
0470: }
0471: }
0472:
0473: private static int JavaSoftHashValue(int h) {
0474: h ^= (h >>> 20) ^ (h >>> 12);
0475: return h ^ (h >>> 7) ^ (h >>> 4);
0476: }
0477:
0478: private static int JavaSoftBucketIndex(final int h, final int length) {
0479: return h & (length - 1);
0480: }
0481:
0482: private static int MRIHashValue(int h) {
0483: return h & HASH_SIGN_BIT_MASK;
0484: }
0485:
0486: private static final int HASH_SIGN_BIT_MASK = ~(1 << 31);
0487:
0488: private static int MRIBucketIndex(final int h, final int length) {
0489: return (h % length);
0490: }
0491:
0492: private final void resize(int newCapacity) {
0493: final RubyHashEntry[] oldTable = table;
0494: final RubyHashEntry[] newTable = new RubyHashEntry[newCapacity];
0495: for (int j = 0; j < oldTable.length; j++) {
0496: RubyHashEntry entry = oldTable[j];
0497: oldTable[j] = null;
0498: while (entry != null) {
0499: RubyHashEntry next = entry.next;
0500: int i = bucketIndex(entry.hash, newCapacity);
0501: entry.next = newTable[i];
0502: newTable[i] = entry;
0503: entry = next;
0504: }
0505: }
0506: table = newTable;
0507: }
0508:
0509: private final void JavaSoftCheckResize() {
0510: if (size > threshold) {
0511: int oldCapacity = table.length;
0512: if (oldCapacity == MAXIMUM_CAPACITY) {
0513: threshold = Integer.MAX_VALUE;
0514: return;
0515: }
0516: int newCapacity = table.length << 1;
0517: resize(newCapacity);
0518: threshold = newCapacity - (newCapacity >> 2);
0519: }
0520: }
0521:
0522: private static final int MIN_CAPA = 8;
0523: private static final int ST_DEFAULT_MAX_DENSITY = 5;
0524:
0525: private final void MRICheckResize() {
0526: if (size / table.length > ST_DEFAULT_MAX_DENSITY) {
0527: int forSize = table.length + 1; // size + 1;
0528: for (int i = 0, newCapacity = MIN_CAPA; i < MRI_PRIMES.length; i++, newCapacity <<= 1) {
0529: if (newCapacity > forSize) {
0530: resize(MRI_PRIMES[i]);
0531: return;
0532: }
0533: }
0534: return; // suboptimal for large hashes (> 1073741824 + 85 entries) not very likely to happen
0535: }
0536: }
0537:
0538: // ------------------------------
0539: private static boolean MRI_HASH = true;
0540: private static boolean MRI_HASH_RESIZE = true;
0541:
0542: private static int hashValue(final int h) {
0543: return MRI_HASH ? MRIHashValue(h) : JavaSoftHashValue(h);
0544: }
0545:
0546: private static int bucketIndex(final int h, final int length) {
0547: return MRI_HASH ? MRIBucketIndex(h, length)
0548: : JavaSoftBucketIndex(h, length);
0549: }
0550:
0551: private void checkResize() {
0552: if (MRI_HASH_RESIZE)
0553: MRICheckResize();
0554: else
0555: JavaSoftCheckResize();
0556: }
0557:
0558: // ------------------------------
0559: public static long collisions = 0;
0560:
0561: private final void internalPut(final IRubyObject key,
0562: final IRubyObject value) {
0563: checkResize();
0564: final int hash = hashValue(key.hashCode());
0565: final int i = bucketIndex(hash, table.length);
0566:
0567: // if (table[i] != null) collisions++;
0568:
0569: for (RubyHashEntry entry = table[i]; entry != null; entry = entry.next) {
0570: IRubyObject k;
0571: if (entry.hash == hash
0572: && ((k = entry.key) == key || key.eql(k))) {
0573: entry.value = value;
0574: return;
0575: }
0576: }
0577:
0578: table[i] = new RubyHashEntry(hash, key, value, table[i]);
0579: size++;
0580: }
0581:
0582: private final void internalPutDirect(final IRubyObject key,
0583: final IRubyObject value) {
0584: checkResize();
0585: final int hash = hashValue(key.hashCode());
0586: final int i = bucketIndex(hash, table.length);
0587: table[i] = new RubyHashEntry(hash, key, value, table[i]);
0588: size++;
0589: }
0590:
0591: private final IRubyObject internalGet(IRubyObject key) { // specialized for value
0592: final int hash = hashValue(key.hashCode());
0593: for (RubyHashEntry entry = table[bucketIndex(hash, table.length)]; entry != null; entry = entry.next) {
0594: IRubyObject k;
0595: if (entry.hash == hash
0596: && ((k = entry.key) == key || key.eql(k)))
0597: return entry.value;
0598: }
0599: return null;
0600: }
0601:
0602: private final RubyHashEntry internalGetEntry(IRubyObject key) {
0603: final int hash = hashValue(key.hashCode());
0604: for (RubyHashEntry entry = table[bucketIndex(hash, table.length)]; entry != null; entry = entry.next) {
0605: IRubyObject k;
0606: if (entry.hash == hash
0607: && ((k = entry.key) == key || key.eql(k)))
0608: return entry;
0609: }
0610: return null;
0611: }
0612:
0613: private final RubyHashEntry internalDelete(IRubyObject key) {
0614: final int hash = hashValue(key.hashCode());
0615: final int i = bucketIndex(hash, table.length);
0616: RubyHashEntry entry = table[i];
0617:
0618: if (entry == null)
0619: return null;
0620:
0621: IRubyObject k;
0622: if (entry.hash == hash
0623: && ((k = entry.key) == key || key.eql(k))) {
0624: table[i] = entry.next;
0625: size--;
0626: return entry;
0627: }
0628: for (; entry.next != null; entry = entry.next) {
0629: RubyHashEntry tmp = entry.next;
0630: if (tmp.hash == hash
0631: && ((k = tmp.key) == key || key.eql(k))) {
0632: entry.next = entry.next.next;
0633: size--;
0634: return tmp;
0635: }
0636: }
0637: return null;
0638: }
0639:
0640: private final RubyHashEntry internalDeleteSafe(IRubyObject key) {
0641: final int hash = hashValue(key.hashCode());
0642: RubyHashEntry entry = table[bucketIndex(hash, table.length)];
0643:
0644: if (entry == null)
0645: return null;
0646: IRubyObject k;
0647:
0648: for (; entry != null; entry = entry.next) {
0649: if (entry.key != NEVER && entry.hash == hash
0650: && ((k = entry.key) == key || key.eql(k))) {
0651: entry.key = NEVER; // make it a skip node
0652: size--;
0653: return entry;
0654: }
0655: }
0656: return null;
0657: }
0658:
0659: private final RubyHashEntry internalDeleteEntry(RubyHashEntry entry) {
0660: final int hash = hashValue(entry.key.hashCode());
0661: final int i = bucketIndex(hash, table.length);
0662: RubyHashEntry prev = table[i];
0663: RubyHashEntry e = prev;
0664: while (e != null) {
0665: RubyHashEntry next = e.next;
0666: if (e.hash == hash && e.equals(entry)) {
0667: size--;
0668: if (iterLevel > 0) {
0669: if (prev == e)
0670: table[i] = next;
0671: else
0672: prev.next = next;
0673: } else {
0674: e.key = NEVER;
0675: }
0676: return e;
0677: }
0678: prev = e;
0679: e = next;
0680: }
0681: return e;
0682: }
0683:
0684: private final void internalCleanupSafe() { // synchronized ?
0685: for (int i = 0; i < table.length; i++) {
0686: RubyHashEntry entry = table[i];
0687: while (entry != null && entry.key == NEVER)
0688: table[i] = entry = entry.next;
0689: if (entry != null) {
0690: RubyHashEntry prev = entry;
0691: entry = entry.next;
0692: while (entry != null) {
0693: if (entry.key == NEVER) {
0694: prev.next = entry.next;
0695: } else {
0696: prev = prev.next;
0697: }
0698: entry = prev.next;
0699: }
0700: }
0701: }
0702: }
0703:
0704: private final RubyHashEntry[] internalCopyTable() {
0705: RubyHashEntry[] newTable = new RubyHashEntry[table.length];
0706:
0707: for (int i = 0; i < table.length; i++) {
0708: for (RubyHashEntry entry = table[i]; entry != null; entry = entry.next) {
0709: if (entry.key != NEVER)
0710: newTable[i] = new RubyHashEntry(entry.hash,
0711: entry.key, entry.value, newTable[i]);
0712: }
0713: }
0714: return newTable;
0715: }
0716:
0717: // flags for callback based interation
0718: public static final int ST_CONTINUE = 0;
0719: public static final int ST_STOP = 1;
0720: public static final int ST_DELETE = 2;
0721: public static final int ST_CHECK = 3;
0722:
0723: private void rehashOccured() {
0724: throw getRuntime().newRuntimeError(
0725: "rehash occurred during iteration");
0726: }
0727:
0728: public static abstract class Callback { // a class to prevent invokeinterface
0729: public abstract int call(RubyHash hash, RubyHashEntry entry);
0730: }
0731:
0732: private final int hashForEachEntry(final RubyHashEntry entry,
0733: final Callback callback) {
0734: if (entry.key == NEVER)
0735: return ST_CONTINUE;
0736: RubyHashEntry[] ltable = table;
0737:
0738: int status = callback.call(this , entry);
0739:
0740: if (ltable != table)
0741: rehashOccured();
0742:
0743: switch (status) {
0744: case ST_DELETE:
0745: internalDeleteSafe(entry.key);
0746: deleted = true;
0747: case ST_CONTINUE:
0748: break;
0749: case ST_STOP:
0750: return ST_STOP;
0751: }
0752: return ST_CHECK;
0753: }
0754:
0755: private final boolean internalForEach(final Callback callback) {
0756: RubyHashEntry entry, last, tmp;
0757: int length = table.length;
0758: for (int i = 0; i < length; i++) {
0759: last = null;
0760: for (entry = table[i]; entry != null;) {
0761: switch (hashForEachEntry(entry, callback)) {
0762: case ST_CHECK:
0763: tmp = null;
0764: if (i < length)
0765: for (tmp = table[i]; tmp != null
0766: && tmp != entry; tmp = tmp.next)
0767: ;
0768: if (tmp == null)
0769: return true;
0770: case ST_CONTINUE:
0771: last = entry;
0772: entry = entry.next;
0773: break;
0774: case ST_STOP:
0775: return false;
0776: case ST_DELETE:
0777: tmp = entry;
0778: if (last == null)
0779: table[i] = entry.next;
0780: else
0781: last.next = entry.next;
0782: entry = entry.next;
0783: size--;
0784: }
0785: }
0786: }
0787: return false;
0788: }
0789:
0790: public final void forEach(final Callback callback) {
0791: try {
0792: preIter();
0793: if (internalForEach(callback))
0794: rehashOccured();
0795: } finally {
0796: postIter();
0797: }
0798: }
0799:
0800: private final void preIter() {
0801: iterLevel++;
0802: }
0803:
0804: private final void postIter() {
0805: iterLevel--;
0806: if (deleted) {
0807: internalCleanupSafe();
0808: deleted = false;
0809: }
0810: }
0811:
0812: private final RubyHashEntry checkIter(RubyHashEntry[] ltable,
0813: RubyHashEntry node) {
0814: while (node != null && node.key == NEVER)
0815: node = node.next;
0816: if (ltable != table)
0817: rehashOccured();
0818: return node;
0819: }
0820:
0821: /* ============================
0822: * End of hash internals
0823: * ============================
0824: */
0825:
0826: /* ================
0827: * Instance Methods
0828: * ================
0829: */
0830:
0831: /** rb_hash_initialize
0832: *
0833: */
0834: public IRubyObject initialize(IRubyObject[] args, final Block block) {
0835: modify();
0836:
0837: if (block.isGiven()) {
0838: if (args.length > 0)
0839: throw getRuntime().newArgumentError(
0840: "wrong number of arguments");
0841: ifNone = getRuntime().newProc(false, block);
0842: procDefault = true;
0843: } else {
0844: Arity.checkArgumentCount(getRuntime(), args, 0, 1);
0845: if (args.length == 1)
0846: ifNone = args[0];
0847: }
0848: return this ;
0849: }
0850:
0851: /** rb_hash_default
0852: *
0853: */
0854: public IRubyObject default_value_get(IRubyObject[] args) {
0855: Arity.checkArgumentCount(getRuntime(), args, 0, 1);
0856:
0857: if (procDefault) {
0858: if (args.length == 0)
0859: return getRuntime().getNil();
0860: return ifNone.callMethod(getRuntime().getCurrentContext(),
0861: "call", new IRubyObject[] { this , args[0] });
0862: }
0863: return ifNone;
0864: }
0865:
0866: /** rb_hash_set_default
0867: *
0868: */
0869: public IRubyObject default_value_set(final IRubyObject defaultValue) {
0870: modify();
0871:
0872: ifNone = defaultValue;
0873: procDefault = false;
0874:
0875: return ifNone;
0876: }
0877:
0878: /** rb_hash_default_proc
0879: *
0880: */
0881: public IRubyObject default_proc() {
0882: return procDefault ? ifNone : getRuntime().getNil();
0883: }
0884:
0885: /** rb_hash_modify
0886: *
0887: */
0888: public void modify() {
0889: testFrozen("hash");
0890: if (isTaint() && getRuntime().getSafeLevel() >= 4) {
0891: throw getRuntime().newSecurityError(
0892: "Insecure: can't modify hash");
0893: }
0894: }
0895:
0896: /** rb_hash_inspect
0897: *
0898: */
0899: public IRubyObject inspect() {
0900: Ruby runtime = getRuntime();
0901: if (!runtime.registerInspecting(this )) {
0902: return runtime.newString("{...}");
0903: }
0904:
0905: try {
0906: final String sep = ", ";
0907: final String arrow = "=>";
0908: final StringBuffer sb = new StringBuffer("{");
0909: boolean firstEntry = true;
0910:
0911: ThreadContext context = runtime.getCurrentContext();
0912: preIter();
0913: RubyHashEntry[] ltable = table;
0914: for (int i = 0; i < ltable.length; i++) {
0915: for (RubyHashEntry entry = ltable[i]; entry != null
0916: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
0917: if (!firstEntry)
0918: sb.append(sep);
0919: sb.append(entry.key.callMethod(context, "inspect"))
0920: .append(arrow);
0921: sb.append(entry.value
0922: .callMethod(context, "inspect"));
0923: firstEntry = false;
0924: }
0925: }
0926: sb.append("}");
0927: return runtime.newString(sb.toString());
0928: } finally {
0929: postIter();
0930: runtime.unregisterInspecting(this );
0931: }
0932: }
0933:
0934: /** rb_hash_size
0935: *
0936: */
0937: public RubyFixnum rb_size() {
0938: return getRuntime().newFixnum(size);
0939: }
0940:
0941: /** rb_hash_empty_p
0942: *
0943: */
0944: public RubyBoolean empty_p() {
0945: return size == 0 ? getRuntime().getTrue() : getRuntime()
0946: .getFalse();
0947: }
0948:
0949: /** rb_hash_to_a
0950: *
0951: */
0952: public RubyArray to_a() {
0953: Ruby runtime = getRuntime();
0954: RubyArray result = RubyArray.newArray(runtime, size);
0955:
0956: try {
0957: preIter();
0958: RubyHashEntry[] ltable = table;
0959: for (int i = 0; i < ltable.length; i++) {
0960: for (RubyHashEntry entry = ltable[i]; entry != null
0961: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
0962: result.append(RubyArray.newArray(runtime,
0963: entry.key, entry.value));
0964: }
0965: }
0966: } finally {
0967: postIter();
0968: }
0969:
0970: result.setTaint(isTaint());
0971: return result;
0972: }
0973:
0974: /** rb_hash_to_s
0975: *
0976: */
0977: public IRubyObject to_s() {
0978: if (!getRuntime().registerInspecting(this )) {
0979: return getRuntime().newString("{...}");
0980: }
0981: try {
0982: return to_a().to_s();
0983: } finally {
0984: getRuntime().unregisterInspecting(this );
0985: }
0986: }
0987:
0988: /** rb_hash_rehash
0989: *
0990: */
0991: public RubyHash rehash() {
0992: modify();
0993: final RubyHashEntry[] oldTable = table;
0994: final RubyHashEntry[] newTable = new RubyHashEntry[oldTable.length];
0995: for (int j = 0; j < oldTable.length; j++) {
0996: RubyHashEntry entry = oldTable[j];
0997: oldTable[j] = null;
0998: while (entry != null) {
0999: RubyHashEntry next = entry.next;
1000: if (entry.key != NEVER) {
1001: entry.hash = entry.key.hashCode(); // update the hash value
1002: int i = bucketIndex(entry.hash, newTable.length);
1003: entry.next = newTable[i];
1004: newTable[i] = entry;
1005: }
1006: entry = next;
1007: }
1008: }
1009: table = newTable;
1010: return this ;
1011: }
1012:
1013: /** rb_hash_to_hash
1014: *
1015: */
1016: public RubyHash to_hash() {
1017: return this ;
1018: }
1019:
1020: public RubyHash convertToHash() {
1021: return this ;
1022: }
1023:
1024: public final void fastASet(IRubyObject key, IRubyObject value) {
1025: internalPut(key, value);
1026: }
1027:
1028: /** rb_hash_aset
1029: *
1030: */
1031: public IRubyObject aset(IRubyObject key, IRubyObject value) {
1032: modify();
1033:
1034: if (!(key instanceof RubyString)) {
1035: internalPut(key, value);
1036: return value;
1037: }
1038:
1039: RubyHashEntry entry = null;
1040: if ((entry = internalGetEntry(key)) != null) {
1041: entry.value = value;
1042: } else {
1043: IRubyObject realKey = ((RubyString) key).strDup();
1044: realKey.setFrozen(true);
1045: internalPutDirect(realKey, value);
1046: }
1047:
1048: return value;
1049: }
1050:
1051: public final IRubyObject fastARef(IRubyObject key) { // retuns null when not found to avoid unnecessary getRuntime().getNil() call
1052: return internalGet(key);
1053: }
1054:
1055: /** rb_hash_aref
1056: *
1057: */
1058: public IRubyObject aref(IRubyObject key) {
1059: IRubyObject value;
1060: return ((value = internalGet(key)) == null) ? callMethod(
1061: getRuntime().getCurrentContext(), MethodIndex.DEFAULT,
1062: "default", key) : value;
1063: }
1064:
1065: /** rb_hash_fetch
1066: *
1067: */
1068: public IRubyObject fetch(IRubyObject[] args, Block block) {
1069: if (Arity.checkArgumentCount(getRuntime(), args, 1, 2) == 2
1070: && block.isGiven()) {
1071: getRuntime().getWarnings().warn(
1072: "block supersedes default value argument");
1073: }
1074:
1075: IRubyObject value;
1076: if ((value = internalGet(args[0])) == null) {
1077: if (block.isGiven())
1078: return block.yield(getRuntime().getCurrentContext(),
1079: args[0]);
1080: if (args.length == 1)
1081: throw getRuntime().newIndexError("key not found");
1082: return args[1];
1083: }
1084: return value;
1085: }
1086:
1087: /** rb_hash_has_key
1088: *
1089: */
1090: public RubyBoolean has_key(IRubyObject key) {
1091: return internalGetEntry(key) == null ? getRuntime().getFalse()
1092: : getRuntime().getTrue();
1093: }
1094:
1095: /** rb_hash_has_value
1096: *
1097: */
1098: public RubyBoolean has_value(IRubyObject value) {
1099: Ruby runtime = getRuntime();
1100: ThreadContext context = runtime.getCurrentContext();
1101:
1102: try {
1103: preIter();
1104: RubyHashEntry[] ltable = table;
1105: for (int i = 0; i < ltable.length; i++) {
1106: for (RubyHashEntry entry = ltable[i]; entry != null
1107: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1108: if (entry.value.equalInternal(context, value)
1109: .isTrue())
1110: return runtime.getTrue();
1111: }
1112: }
1113: } finally {
1114: postIter();
1115: }
1116: return runtime.getFalse();
1117: }
1118:
1119: /** rb_hash_each
1120: *
1121: */
1122: public RubyHash each(Block block) {
1123: Ruby runtime = getRuntime();
1124: ThreadContext context = runtime.getCurrentContext();
1125:
1126: try {
1127: preIter();
1128: RubyHashEntry[] ltable = table;
1129: for (int i = 0; i < ltable.length; i++) {
1130: for (RubyHashEntry entry = ltable[i]; entry != null
1131: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1132: // rb_assoc_new equivalent
1133: block.yield(context, RubyArray.newArray(runtime,
1134: entry.key, entry.value), null, null, false);
1135: }
1136: }
1137: } finally {
1138: postIter();
1139: }
1140:
1141: return this ;
1142: }
1143:
1144: /** rb_hash_each_pair
1145: *
1146: */
1147: public RubyHash each_pair(Block block) {
1148: Ruby runtime = getRuntime();
1149: ThreadContext context = runtime.getCurrentContext();
1150:
1151: try {
1152: preIter();
1153: RubyHashEntry[] ltable = table;
1154: for (int i = 0; i < ltable.length; i++) {
1155: for (RubyHashEntry entry = ltable[i]; entry != null
1156: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1157: // rb_yield_values(2,...) equivalent
1158: block.yield(context, RubyArray.newArray(runtime,
1159: entry.key, entry.value), null, null, true);
1160: }
1161: }
1162: } finally {
1163: postIter();
1164: }
1165:
1166: return this ;
1167: }
1168:
1169: /** rb_hash_each_value
1170: *
1171: */
1172: public RubyHash each_value(Block block) {
1173: Ruby runtime = getRuntime();
1174: ThreadContext context = runtime.getCurrentContext();
1175:
1176: try {
1177: preIter();
1178: RubyHashEntry[] ltable = table;
1179: for (int i = 0; i < ltable.length; i++) {
1180: for (RubyHashEntry entry = ltable[i]; entry != null
1181: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1182: block.yield(context, entry.value);
1183: }
1184: }
1185: } finally {
1186: postIter();
1187: }
1188:
1189: return this ;
1190: }
1191:
1192: /** rb_hash_each_key
1193: *
1194: */
1195: public RubyHash each_key(Block block) {
1196: Ruby runtime = getRuntime();
1197: ThreadContext context = runtime.getCurrentContext();
1198:
1199: try {
1200: preIter();
1201: RubyHashEntry[] ltable = table;
1202: for (int i = 0; i < ltable.length; i++) {
1203: for (RubyHashEntry entry = ltable[i]; entry != null
1204: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1205: block.yield(context, entry.key);
1206: }
1207: }
1208: } finally {
1209: postIter();
1210: }
1211:
1212: return this ;
1213: }
1214:
1215: /** rb_hash_sort
1216: *
1217: */
1218: public RubyArray sort(Block block) {
1219: return to_a().sort_bang(block);
1220: }
1221:
1222: /** rb_hash_index
1223: *
1224: */
1225: public IRubyObject index(IRubyObject value) {
1226: Ruby runtime = getRuntime();
1227: ThreadContext context = runtime.getCurrentContext();
1228:
1229: try {
1230: preIter();
1231: RubyHashEntry[] ltable = table;
1232: for (int i = 0; i < ltable.length; i++) {
1233: for (RubyHashEntry entry = ltable[i]; entry != null
1234: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1235: if (entry.value.equalInternal(context, value)
1236: .isTrue())
1237: return entry.key;
1238: }
1239: }
1240: } finally {
1241: postIter();
1242: }
1243:
1244: return getRuntime().getNil();
1245: }
1246:
1247: /** rb_hash_indexes
1248: *
1249: */
1250: public RubyArray indices(IRubyObject[] indices) {
1251: RubyArray values = RubyArray.newArray(getRuntime(),
1252: indices.length);
1253:
1254: for (int i = 0; i < indices.length; i++) {
1255: values.append(aref(indices[i]));
1256: }
1257:
1258: return values;
1259: }
1260:
1261: /** rb_hash_keys
1262: *
1263: */
1264: public RubyArray keys() {
1265: Ruby runtime = getRuntime();
1266: RubyArray keys = RubyArray.newArray(runtime, size);
1267:
1268: try {
1269: preIter();
1270: RubyHashEntry[] ltable = table;
1271: for (int i = 0; i < ltable.length; i++) {
1272: for (RubyHashEntry entry = ltable[i]; entry != null
1273: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1274: keys.append(entry.key);
1275: }
1276: }
1277: } finally {
1278: postIter();
1279: }
1280:
1281: return keys;
1282: }
1283:
1284: /** rb_hash_values
1285: *
1286: */
1287: public RubyArray rb_values() {
1288: RubyArray values = RubyArray.newArray(getRuntime(), size);
1289:
1290: try {
1291: preIter();
1292: RubyHashEntry[] ltable = table;
1293: for (int i = 0; i < ltable.length; i++) {
1294: for (RubyHashEntry entry = ltable[i]; entry != null
1295: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1296: values.append(entry.value);
1297: }
1298: }
1299: } finally {
1300: postIter();
1301: }
1302:
1303: return values;
1304: }
1305:
1306: /** rb_hash_equal
1307: *
1308: */
1309:
1310: private static final boolean EQUAL_CHECK_DEFAULT_VALUE = false;
1311:
1312: public IRubyObject equal(IRubyObject other) {
1313: if (this == other)
1314: return getRuntime().getTrue();
1315: if (!(other instanceof RubyHash)) {
1316: if (!other.respondsTo("to_hash"))
1317: return getRuntime().getFalse();
1318: return other.equalInternal(
1319: getRuntime().getCurrentContext(), this );
1320: }
1321:
1322: RubyHash otherHash = (RubyHash) other;
1323: if (size != otherHash.size)
1324: return getRuntime().getFalse();
1325:
1326: Ruby runtime = getRuntime();
1327: ThreadContext context = runtime.getCurrentContext();
1328:
1329: if (EQUAL_CHECK_DEFAULT_VALUE) {
1330: if (!ifNone.equalInternal(context, otherHash.ifNone)
1331: .isTrue()
1332: && procDefault != otherHash.procDefault)
1333: return runtime.getFalse();
1334: }
1335:
1336: try {
1337: preIter();
1338: RubyHashEntry[] ltable = table;
1339: for (int i = 0; i < ltable.length; i++) {
1340: for (RubyHashEntry entry = ltable[i]; entry != null
1341: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1342: IRubyObject value = otherHash
1343: .internalGet(entry.key);
1344: if (value == null)
1345: return runtime.getFalse();
1346: if (!entry.value.equalInternal(context, value)
1347: .isTrue())
1348: return runtime.getFalse();
1349: }
1350: }
1351: } finally {
1352: postIter();
1353: }
1354:
1355: return runtime.getTrue();
1356: }
1357:
1358: /** rb_hash_shift
1359: *
1360: */
1361: public IRubyObject shift() {
1362: modify();
1363:
1364: try {
1365: preIter();
1366: RubyHashEntry[] ltable = table;
1367: for (int i = 0; i < ltable.length; i++) {
1368: for (RubyHashEntry entry = ltable[i]; entry != null
1369: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1370: RubyArray result = RubyArray.newArray(getRuntime(),
1371: entry.key, entry.value);
1372: internalDeleteSafe(entry.key);
1373: deleted = true;
1374: return result;
1375: }
1376: }
1377: } finally {
1378: postIter();
1379: }
1380:
1381: if (procDefault)
1382: return ifNone.callMethod(getRuntime().getCurrentContext(),
1383: "call", new IRubyObject[] { this ,
1384: getRuntime().getNil() });
1385: return ifNone;
1386: }
1387:
1388: /** rb_hash_delete
1389: *
1390: */
1391: public IRubyObject delete(IRubyObject key, Block block) {
1392: modify();
1393:
1394: RubyHashEntry entry;
1395: if (iterLevel > 0) {
1396: if ((entry = internalDeleteSafe(key)) != null) {
1397: deleted = true;
1398: return entry.value;
1399: }
1400: } else if ((entry = internalDelete(key)) != null)
1401: return entry.value;
1402:
1403: if (block.isGiven())
1404: return block.yield(getRuntime().getCurrentContext(), key);
1405: return getRuntime().getNil();
1406: }
1407:
1408: /** rb_hash_select
1409: *
1410: */
1411: public IRubyObject select(IRubyObject[] args, Block block) {
1412: if (args.length > 0)
1413: throw getRuntime().newArgumentError(
1414: "wrong number of arguments (" + args.length
1415: + " for 0)");
1416: RubyArray result = getRuntime().newArray();
1417:
1418: Ruby runtime = getRuntime();
1419: ThreadContext context = runtime.getCurrentContext();
1420:
1421: try {
1422: preIter();
1423: RubyHashEntry[] ltable = table;
1424: for (int i = 0; i < ltable.length; i++) {
1425: for (RubyHashEntry entry = ltable[i]; entry != null
1426: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1427: if (block.yield(context,
1428: runtime.newArray(entry.key, entry.value),
1429: null, null, true).isTrue()) {
1430: result.append(runtime.newArray(entry.key,
1431: entry.value));
1432: }
1433: }
1434: }
1435: } finally {
1436: postIter();
1437: }
1438: return result;
1439: }
1440:
1441: /** rb_hash_delete_if
1442: *
1443: */
1444: public RubyHash delete_if(Block block) {
1445: modify();
1446:
1447: Ruby runtime = getRuntime();
1448: ThreadContext context = runtime.getCurrentContext();
1449:
1450: try {
1451: preIter();
1452: RubyHashEntry[] ltable = table;
1453: for (int i = 0; i < ltable.length; i++) {
1454: for (RubyHashEntry entry = ltable[i]; entry != null
1455: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1456: if (block.yield(
1457: context,
1458: RubyArray.newArray(runtime, entry.key,
1459: entry.value), null, null, true)
1460: .isTrue())
1461: delete(entry.key, block);
1462: }
1463: }
1464: } finally {
1465: postIter();
1466: }
1467:
1468: return this ;
1469: }
1470:
1471: /** rb_hash_reject
1472: *
1473: */
1474: public RubyHash reject(Block block) {
1475: return ((RubyHash) dup()).delete_if(block);
1476: }
1477:
1478: /** rb_hash_reject_bang
1479: *
1480: */
1481: public IRubyObject reject_bang(Block block) {
1482: int n = size;
1483: delete_if(block);
1484: if (n == size)
1485: return getRuntime().getNil();
1486: return this ;
1487: }
1488:
1489: /** rb_hash_clear
1490: *
1491: */
1492: public RubyHash rb_clear() {
1493: modify();
1494:
1495: if (size > 0) {
1496: alloc();
1497: size = 0;
1498: deleted = false;
1499: }
1500:
1501: return this ;
1502: }
1503:
1504: /** rb_hash_invert
1505: *
1506: */
1507: public RubyHash invert() {
1508: RubyHash result = newHash(getRuntime());
1509:
1510: try {
1511: preIter();
1512: RubyHashEntry[] ltable = table;
1513: for (int i = 0; i < ltable.length; i++) {
1514: for (RubyHashEntry entry = ltable[i]; entry != null
1515: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1516: result.aset(entry.value, entry.key);
1517: }
1518: }
1519: } finally {
1520: postIter();
1521: }
1522:
1523: return result;
1524: }
1525:
1526: /** rb_hash_update
1527: *
1528: */
1529: public RubyHash update(IRubyObject other, Block block) {
1530: modify();
1531:
1532: RubyHash otherHash = other.convertToHash();
1533:
1534: try {
1535: otherHash.preIter();
1536: RubyHashEntry[] ltable = otherHash.table;
1537: if (block.isGiven()) {
1538: Ruby runtime = getRuntime();
1539: ThreadContext context = runtime.getCurrentContext();
1540:
1541: for (int i = 0; i < ltable.length; i++) {
1542: for (RubyHashEntry entry = ltable[i]; entry != null
1543: && (entry = otherHash.checkIter(ltable,
1544: entry)) != null; entry = entry.next) {
1545: IRubyObject value;
1546: if (internalGet(entry.key) != null)
1547: value = block.yield(context, RubyArray
1548: .newArrayNoCopy(runtime,
1549: new IRubyObject[] {
1550: entry.key,
1551: aref(entry.key),
1552: entry.value }));
1553: else
1554: value = entry.value;
1555: aset(entry.key, value);
1556: }
1557: }
1558: } else {
1559: for (int i = 0; i < ltable.length; i++) {
1560: for (RubyHashEntry entry = ltable[i]; entry != null
1561: && (entry = otherHash.checkIter(ltable,
1562: entry)) != null; entry = entry.next) {
1563: aset(entry.key, entry.value);
1564: }
1565: }
1566: }
1567: } finally {
1568: otherHash.postIter();
1569: }
1570:
1571: return this ;
1572: }
1573:
1574: /** rb_hash_merge
1575: *
1576: */
1577: public RubyHash merge(IRubyObject other, Block block) {
1578: return ((RubyHash) dup()).update(other, block);
1579: }
1580:
1581: /** rb_hash_replace
1582: *
1583: */
1584: public RubyHash replace(IRubyObject other) {
1585: RubyHash otherHash = other.convertToHash();
1586:
1587: if (this == otherHash)
1588: return this ;
1589:
1590: rb_clear();
1591:
1592: try {
1593: otherHash.preIter();
1594: RubyHashEntry[] ltable = otherHash.table;
1595: for (int i = 0; i < ltable.length; i++) {
1596: for (RubyHashEntry entry = ltable[i]; entry != null
1597: && (entry = otherHash.checkIter(ltable, entry)) != null; entry = entry.next) {
1598: aset(entry.key, entry.value);
1599: }
1600: }
1601: } finally {
1602: otherHash.postIter();
1603: }
1604:
1605: ifNone = otherHash.ifNone;
1606: procDefault = otherHash.procDefault;
1607:
1608: return this ;
1609: }
1610:
1611: /** rb_hash_values_at
1612: *
1613: */
1614: public RubyArray values_at(IRubyObject[] args) {
1615: RubyArray result = RubyArray
1616: .newArray(getRuntime(), args.length);
1617: for (int i = 0; i < args.length; i++) {
1618: result.append(aref(args[i]));
1619: }
1620: return result;
1621: }
1622:
1623: public boolean hasDefaultProc() {
1624: return procDefault;
1625: }
1626:
1627: public IRubyObject getIfNone() {
1628: return ifNone;
1629: }
1630:
1631: // FIXME: Total hack to get flash in Rails marshalling/unmarshalling in session ok...We need
1632: // to totally change marshalling to work with overridden core classes.
1633: public static void marshalTo(RubyHash hash, MarshalStream output)
1634: throws IOException {
1635: output.writeInt(hash.size);
1636: try {
1637: hash.preIter();
1638: RubyHashEntry[] ltable = hash.table;
1639: for (int i = 0; i < ltable.length; i++) {
1640: for (RubyHashEntry entry = ltable[i]; entry != null
1641: && (entry = hash.checkIter(ltable, entry)) != null; entry = entry.next) {
1642: output.dumpObject(entry.key);
1643: output.dumpObject(entry.value);
1644: }
1645: }
1646: } finally {
1647: hash.postIter();
1648: }
1649:
1650: if (!hash.ifNone.isNil())
1651: output.dumpObject(hash.ifNone);
1652: }
1653:
1654: public static RubyHash unmarshalFrom(UnmarshalStream input,
1655: boolean defaultValue) throws IOException {
1656: RubyHash result = newHash(input.getRuntime());
1657: input.registerLinkTarget(result);
1658: int size = input.unmarshalInt();
1659: for (int i = 0; i < size; i++) {
1660: result.aset(input.unmarshalObject(), input
1661: .unmarshalObject());
1662: }
1663: if (defaultValue)
1664: result.default_value_set(input.unmarshalObject());
1665: return result;
1666: }
1667:
1668: public Class getJavaClass() {
1669: return Map.class;
1670: }
1671:
1672: // Satisfy java.util.Set interface (for Java integration)
1673:
1674: public int size() {
1675: return size;
1676: }
1677:
1678: public boolean isEmpty() {
1679: return size == 0;
1680: }
1681:
1682: public boolean containsKey(Object key) {
1683: return internalGet(JavaUtil
1684: .convertJavaToRuby(getRuntime(), key)) != null;
1685: }
1686:
1687: public boolean containsValue(Object value) {
1688: Ruby runtime = getRuntime();
1689: ThreadContext context = runtime.getCurrentContext();
1690: IRubyObject element = JavaUtil
1691: .convertJavaToRuby(runtime, value);
1692:
1693: try {
1694: preIter();
1695: RubyHashEntry[] ltable = table;
1696: for (int i = 0; i < ltable.length; i++) {
1697: for (RubyHashEntry entry = ltable[i]; entry != null
1698: && (entry = checkIter(ltable, entry)) != null; entry = entry.next) {
1699: if (entry.value.equalInternal(context, element)
1700: .isTrue())
1701: return true;
1702: }
1703: }
1704: } finally {
1705: postIter();
1706: }
1707:
1708: return false;
1709: }
1710:
1711: public Object get(Object key) {
1712: return JavaUtil.convertRubyToJava(internalGet(JavaUtil
1713: .convertJavaToRuby(getRuntime(), key)));
1714: }
1715:
1716: public Object put(Object key, Object value) {
1717: internalPut(JavaUtil.convertJavaToRuby(getRuntime(), key),
1718: JavaUtil.convertJavaToRuby(getRuntime(), value));
1719: return value;
1720: }
1721:
1722: public Object remove(Object key) {
1723: IRubyObject rubyKey = JavaUtil.convertJavaToRuby(getRuntime(),
1724: key);
1725: RubyHashEntry entry;
1726: if (iterLevel > 0) {
1727: entry = internalDeleteSafe(rubyKey);
1728: deleted = true;
1729: } else {
1730: entry = internalDelete(rubyKey);
1731: }
1732:
1733: return entry != null ? entry.value : null;
1734: }
1735:
1736: public void putAll(Map map) {
1737: Ruby runtime = getRuntime();
1738: for (Iterator iter = map.keySet().iterator(); iter.hasNext();) {
1739: Object key = iter.next();
1740: internalPut(JavaUtil.convertJavaToRuby(runtime, key),
1741: JavaUtil.convertJavaToRuby(runtime, map.get(key)));
1742: }
1743: }
1744:
1745: public void clear() {
1746: rb_clear();
1747: }
1748:
1749: private abstract class RubyHashIterator implements Iterator {
1750: RubyHashEntry entry, current;
1751: int index;
1752: RubyHashEntry[] iterTable;
1753: Ruby runtime = getRuntime();
1754:
1755: public RubyHashIterator() {
1756: iterTable = table;
1757: if (size > 0)
1758: seekNextValidEntry();
1759: }
1760:
1761: private final void seekNextValidEntry() {
1762: do {
1763: while (index < iterTable.length
1764: && (entry = iterTable[index++]) == null)
1765: ;
1766: while (entry != null && entry.key == NEVER)
1767: entry = entry.next;
1768: } while (entry == null && index < iterTable.length);
1769: }
1770:
1771: public boolean hasNext() {
1772: return entry != null;
1773: }
1774:
1775: public final RubyHashEntry nextEntry() {
1776: if (entry == null)
1777: throw new NoSuchElementException();
1778: RubyHashEntry e = current = entry;
1779: if ((entry = checkIter(iterTable, entry.next)) == null)
1780: seekNextValidEntry();
1781: return e;
1782: }
1783:
1784: public void remove() {
1785: if (current == null)
1786: throw new IllegalStateException();
1787: internalDeleteSafe(current.key);
1788: deleted = true;
1789: }
1790:
1791: }
1792:
1793: private final class KeyIterator extends RubyHashIterator {
1794: public Object next() {
1795: return JavaUtil.convertRubyToJava(nextEntry().key);
1796: }
1797: }
1798:
1799: private class KeySet extends AbstractSet {
1800: public Iterator iterator() {
1801: return new KeyIterator();
1802: }
1803:
1804: public int size() {
1805: return size;
1806: }
1807:
1808: public boolean contains(Object o) {
1809: return containsKey(o);
1810: }
1811:
1812: public boolean remove(Object o) {
1813: return RubyHash.this .remove(o) != null;
1814: }
1815:
1816: public void clear() {
1817: RubyHash.this .clear();
1818: }
1819: }
1820:
1821: public Set keySet() {
1822: return new KeySet();
1823: }
1824:
1825: private final class DirectKeyIterator extends RubyHashIterator {
1826: public Object next() {
1827: return nextEntry().key;
1828: }
1829: }
1830:
1831: private final class DirectKeySet extends KeySet {
1832: public Iterator iterator() {
1833: return new DirectKeyIterator();
1834: }
1835: }
1836:
1837: public Set directKeySet() {
1838: return new DirectKeySet();
1839: }
1840:
1841: private final class ValueIterator extends RubyHashIterator {
1842: public Object next() {
1843: return JavaUtil.convertRubyToJava(nextEntry().value);
1844: }
1845: }
1846:
1847: private class Values extends AbstractCollection {
1848: public Iterator iterator() {
1849: return new ValueIterator();
1850: }
1851:
1852: public int size() {
1853: return size;
1854: }
1855:
1856: public boolean contains(Object o) {
1857: return containsValue(o);
1858: }
1859:
1860: public void clear() {
1861: RubyHash.this .clear();
1862: }
1863: }
1864:
1865: public Collection values() {
1866: return new Values();
1867: }
1868:
1869: private final class DirectValueIterator extends RubyHashIterator {
1870: public Object next() {
1871: return nextEntry().value;
1872: }
1873: }
1874:
1875: private final class DirectValues extends Values {
1876: public Iterator iterator() {
1877: return new DirectValueIterator();
1878: }
1879: }
1880:
1881: public Collection directValues() {
1882: return new DirectValues();
1883: }
1884:
1885: static final class ConversionMapEntry implements Map.Entry {
1886: private final RubyHashEntry entry;
1887: private final Ruby runtime;
1888:
1889: public ConversionMapEntry(Ruby runtime, RubyHashEntry entry) {
1890: this .entry = entry;
1891: this .runtime = runtime;
1892: }
1893:
1894: public Object getKey() {
1895: return JavaUtil.convertRubyToJava(entry.key, Object.class);
1896: }
1897:
1898: public Object getValue() {
1899: return JavaUtil
1900: .convertRubyToJava(entry.value, Object.class);
1901: }
1902:
1903: public Object setValue(Object value) {
1904: return entry.value = JavaUtil.convertJavaToRuby(runtime,
1905: value);
1906: }
1907:
1908: public boolean equals(Object other) {
1909: if (!(other instanceof RubyHashEntry))
1910: return false;
1911: RubyHashEntry otherEntry = (RubyHashEntry) other;
1912: if (entry.key != NEVER && entry.key == otherEntry.key
1913: && entry.key.eql(otherEntry.key)) {
1914: if (entry.value == otherEntry.value
1915: || entry.value.equals(otherEntry.value))
1916: return true;
1917: }
1918: return false;
1919: }
1920:
1921: public int hashCode() {
1922: return entry.hashCode();
1923: }
1924: }
1925:
1926: private final class EntryIterator extends RubyHashIterator {
1927: public Object next() {
1928: return new ConversionMapEntry(runtime, nextEntry());
1929: }
1930: }
1931:
1932: private final class EntrySet extends AbstractSet {
1933: public Iterator iterator() {
1934: return new EntryIterator();
1935: }
1936:
1937: public boolean contains(Object o) {
1938: if (!(o instanceof ConversionMapEntry))
1939: return false;
1940: ConversionMapEntry entry = (ConversionMapEntry) o;
1941: if (entry.entry.key == NEVER)
1942: return false;
1943: RubyHashEntry candidate = internalGetEntry(entry.entry.key);
1944: return candidate != null && candidate.equals(entry.entry);
1945: }
1946:
1947: public boolean remove(Object o) {
1948: if (!(o instanceof ConversionMapEntry))
1949: return false;
1950: return internalDeleteEntry(((ConversionMapEntry) o).entry) != null;
1951: }
1952:
1953: public int size() {
1954: return size;
1955: }
1956:
1957: public void clear() {
1958: RubyHash.this .clear();
1959: }
1960: }
1961:
1962: public Set entrySet() {
1963: return new EntrySet();
1964: }
1965:
1966: private final class DirectEntryIterator extends RubyHashIterator {
1967: public Object next() {
1968: return nextEntry();
1969: }
1970: }
1971:
1972: private final class DirectEntrySet extends AbstractSet {
1973: public Iterator iterator() {
1974: return new DirectEntryIterator();
1975: }
1976:
1977: public boolean contains(Object o) {
1978: if (!(o instanceof RubyHashEntry))
1979: return false;
1980: RubyHashEntry entry = (RubyHashEntry) o;
1981: if (entry.key == NEVER)
1982: return false;
1983: RubyHashEntry candidate = internalGetEntry(entry.key);
1984: return candidate != null && candidate.equals(entry);
1985: }
1986:
1987: public boolean remove(Object o) {
1988: if (!(o instanceof RubyHashEntry))
1989: return false;
1990: return internalDeleteEntry((RubyHashEntry) o) != null;
1991: }
1992:
1993: public int size() {
1994: return size;
1995: }
1996:
1997: public void clear() {
1998: RubyHash.this .clear();
1999: }
2000: }
2001:
2002: /** return an entry set who's entries do not convert their values, faster
2003: *
2004: */
2005: public Set directEntrySet() {
2006: return new DirectEntrySet();
2007: }
2008:
2009: public boolean equals(Object other) {
2010: if (!(other instanceof RubyHash))
2011: return false;
2012: if (this == other)
2013: return true;
2014: return equal((RubyHash) other).isTrue() ? true : false;
2015: }
2016: }
|