1: /**********************************************************************
    2: 
    3:   hash.c -
    4: 
    5:   $Author: matz $
    6:   $Date: 2007-11-30 14:26:59 +0900 (Fri, 30 Nov 2007) $
    7:   created at: Mon Nov 22 18:51:18 JST 1993
    8: 
    9:   Copyright (C) 1993-2007 Yukihiro Matsumoto
   10:   Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
   11:   Copyright (C) 2000  Information-technology Promotion Agency, Japan
   12: 
   13: **********************************************************************/
   14: 
   15: #include "ruby/ruby.h"
   16: #include "ruby/st.h"
   17: #include "ruby/util.h"
   18: #include "ruby/signal.h"
   19: 
   20: #ifdef __APPLE__
   21: #include <crt_externs.h>
   22: #endif
   23: 
   24: static VALUE rb_hash_s_try_convert(VALUE, VALUE);
   25: 
   26: #define HASH_DELETED  FL_USER1
   27: #define HASH_PROC_DEFAULT FL_USER2
   28: 
   29: VALUE
   30: rb_hash_freeze(VALUE hash)
   31: {
   32:     return rb_obj_freeze(hash);
   33: }
   34: 
   35: VALUE rb_cHash;
   36: 
   37: static VALUE envtbl;
   38: static ID id_hash, id_yield, id_default;
   39: 
   40: static VALUE
   41: eql(VALUE *args)
   42: {
   43:     return (VALUE)rb_eql(args[0], args[1]);
   44: }
   45: 
   46: static int
   47: rb_any_cmp(VALUE a, VALUE b)
   48: {
   49:     VALUE args[2];
   50: 
   51:     if (a == b) return 0;
   52:     if (FIXNUM_P(a) && FIXNUM_P(b)) {
   53:         return a != b;
   54:     }
   55:     if (TYPE(a) == T_STRING && RBASIC(a)->klass == rb_cString &&
   56:         TYPE(b) == T_STRING && RBASIC(b)->klass == rb_cString) {
   57:         return rb_str_cmp(a, b);
   58:     }
   59:     if (a == Qundef || b == Qundef) return -1;
   60:     if (SYMBOL_P(a) && SYMBOL_P(b)) {
   61:         return a != b;
   62:     }
   63: 
   64:     args[0] = a;
   65:     args[1] = b;
   66:     return !rb_with_disable_interrupt(eql, (VALUE)args);
   67: }
   68: 
   69: VALUE
   70: rb_hash(VALUE obj)
   71: {
   72:     return rb_funcall(obj, id_hash, 0);
   73: }
   74: 
   75: static int
   76: rb_any_hash(VALUE a)
   77: {
   78:     VALUE hval;
   79: 
   80:     switch (TYPE(a)) {
   81:       case T_FIXNUM:
   82:       case T_SYMBOL:
   83:         return (int)a;
   84:         break;
   85: 
   86:       case T_STRING:
   87:         return rb_str_hash(a);
   88:         break;
   89: 
   90:       default:
   91:         hval = rb_funcall(a, id_hash, 0);
   92:         if (!FIXNUM_P(hval)) {
   93:             hval = rb_funcall(hval, '%', 1, INT2FIX(536870923));
   94:         }
   95:         return (int)FIX2LONG(hval);
   96:     }
   97: }
   98: 
   99: static const struct st_hash_type objhash = {
  100:     rb_any_cmp,
  101:     rb_any_hash,
  102: };
  103: 
  104: typedef int st_foreach_func(st_data_t, st_data_t, st_data_t);
  105: 
  106: struct foreach_safe_arg {
  107:     st_table *tbl;
  108:     st_foreach_func *func;
  109:     st_data_t arg;
  110: };
  111: 
  112: static int
  113: foreach_safe_i(st_data_t key, st_data_t value, struct foreach_safe_arg *arg)
  114: {
  115:     int status;
  116: 
  117:     if (key == Qundef) return ST_CONTINUE;
  118:     status = (*arg->func)(key, value, arg->arg);
  119:     if (status == ST_CONTINUE) {
  120:         return ST_CHECK;
  121:     }
  122:     return status;
  123: }
  124: 
  125: void
  126: st_foreach_safe(st_table *table, int (*func)(ANYARGS), st_data_t a)
  127: {
  128:     struct foreach_safe_arg arg;
  129: 
  130:     arg.tbl = table;
  131:     arg.func = (st_foreach_func *)func;
  132:     arg.arg = a;
  133:     if (st_foreach(table, foreach_safe_i, (st_data_t)&arg)) {
  134:         rb_raise(rb_eRuntimeError, "hash modified during iteration");
  135:     }
  136: }
  137: 
  138: typedef int rb_foreach_func(VALUE, VALUE, VALUE);
  139: 
  140: struct hash_foreach_arg {
  141:     VALUE hash;
  142:     rb_foreach_func *func;
  143:     VALUE arg;
  144: };
  145: 
  146: static int
  147: hash_foreach_iter(VALUE key, VALUE value, struct hash_foreach_arg *arg)
  148: {
  149:     int status;
  150:     st_table *tbl;
  151: 
  152:     tbl = RHASH(arg->hash)->ntbl;
  153:     if (key == Qundef) return ST_CONTINUE;
  154:     status = (*arg->func)(key, value, arg->arg);
  155:     if (RHASH(arg->hash)->ntbl != tbl) {
  156:         rb_raise(rb_eRuntimeError, "rehash occurred during iteration");
  157:     }
  158:     switch (status) {
  159:       case ST_DELETE:
  160:         st_delete_safe(tbl, (st_data_t*)&key, 0, Qundef);
  161:         FL_SET(arg->hash, HASH_DELETED);
  162:       case ST_CONTINUE:
  163:         break;
  164:       case ST_STOP:
  165:         return ST_STOP;
  166:     }
  167:     return ST_CHECK;
  168: }
  169: 
  170: static VALUE
  171: hash_foreach_ensure(VALUE hash)
  172: {
  173:     RHASH(hash)->iter_lev--;
  174: 
  175:     if (RHASH(hash)->iter_lev == 0) {
  176:         if (FL_TEST(hash, HASH_DELETED)) {
  177:             st_cleanup_safe(RHASH(hash)->ntbl, Qundef);
  178:             FL_UNSET(hash, HASH_DELETED);
  179:         }
  180:     }
  181:     return 0;
  182: }
  183: 
  184: static VALUE
  185: hash_foreach_call(struct hash_foreach_arg *arg)
  186: {
  187:     if (st_foreach(RHASH(arg->hash)->ntbl, hash_foreach_iter, (st_data_t)arg)) {
  188:         rb_raise(rb_eRuntimeError, "hash modified during iteration");
  189:     }
  190:     return Qnil;
  191: }
  192: 
  193: void
  194: rb_hash_foreach(VALUE hash, int (*func)(ANYARGS), VALUE farg)
  195: {
  196:     struct hash_foreach_arg arg;
  197: 
  198:     if (!RHASH(hash)->ntbl)
  199:         return;
  200:     RHASH(hash)->iter_lev++;
  201:     arg.hash = hash;
  202:     arg.func = (rb_foreach_func *)func;
  203:     arg.arg  = farg;
  204:     rb_ensure(hash_foreach_call, (VALUE)&arg, hash_foreach_ensure, hash);
  205: }
  206: 
  207: static VALUE
  208: hash_alloc(VALUE klass)
  209: {
  210:     NEWOBJ(hash, struct RHash);
  211:     OBJSETUP(hash, klass, T_HASH);
  212: 
  213:     hash->ifnone = Qnil;
  214: 
  215:     return (VALUE)hash;
  216: }
  217: 
  218: VALUE
  219: rb_hash_new(void)
  220: {
  221:     return hash_alloc(rb_cHash);
  222: }
  223: 
  224: static void
  225: rb_hash_modify_check(VALUE hash)
  226: {
  227:     if (OBJ_FROZEN(hash)) rb_error_frozen("hash");
  228:     if (!OBJ_TAINTED(hash) && rb_safe_level() >= 4)
  229:         rb_raise(rb_eSecurityError, "Insecure: can't modify hash");
  230: }
  231: 
  232: struct st_table *
  233: rb_hash_tbl(VALUE hash)
  234: {
  235:     if (!RHASH(hash)->ntbl) {
  236:         RHASH(hash)->ntbl = st_init_table(&objhash);
  237:     }
  238:     return RHASH(hash)->ntbl;
  239: }
  240: 
  241: static void
  242: rb_hash_modify(VALUE hash)
  243: {
  244:     rb_hash_modify_check(hash);
  245:     rb_hash_tbl(hash);
  246: }
  247: 
  248: /*
  249:  *  call-seq:
  250:  *     Hash.new                          => hash
  251:  *     Hash.new(obj)                     => aHash
  252:  *     Hash.new {|hash, key| block }     => aHash
  253:  *
  254:  *  Returns a new, empty hash. If this hash is subsequently accessed by
  255:  *  a key that doesn't correspond to a hash entry, the value returned
  256:  *  depends on the style of <code>new</code> used to create the hash. In
  257:  *  the first form, the access returns <code>nil</code>. If
  258:  *  <i>obj</i> is specified, this single object will be used for
  259:  *  all <em>default values</em>. If a block is specified, it will be
  260:  *  called with the hash object and the key, and should return the
  261:  *  default value. It is the block's responsibility to store the value
  262:  *  in the hash if required.
  263:  *
  264:  *     h = Hash.new("Go Fish")
  265:  *     h["a"] = 100
  266:  *     h["b"] = 200
  267:  *     h["a"]           #=> 100
  268:  *     h["c"]           #=> "Go Fish"
  269:  *     # The following alters the single default object
  270:  *     h["c"].upcase!   #=> "GO FISH"
  271:  *     h["d"]           #=> "GO FISH"
  272:  *     h.keys           #=> ["a", "b"]
  273:  *
  274:  *     # While this creates a new default object each time
  275:  *     h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
  276:  *     h["c"]           #=> "Go Fish: c"
  277:  *     h["c"].upcase!   #=> "GO FISH: C"
  278:  *     h["d"]           #=> "Go Fish: d"
  279:  *     h.keys           #=> ["c", "d"]
  280:  *
  281:  */
  282: 
  283: static VALUE
  284: rb_hash_initialize(int argc, VALUE *argv, VALUE hash)
  285: {
  286:     VALUE ifnone;
  287: 
  288:     rb_hash_modify(hash);
  289:     if (rb_block_given_p()) {
  290:         if (argc > 0) {
  291:             rb_raise(rb_eArgError, "wrong number of arguments");
  292:         }
  293:         RHASH(hash)->ifnone = rb_block_proc();
  294:         FL_SET(hash, HASH_PROC_DEFAULT);
  295:     }
  296:     else {
  297:         rb_scan_args(argc, argv, "01", &ifnone);
  298:         RHASH(hash)->ifnone = ifnone;
  299:     }
  300: 
  301:     return hash;
  302: }
  303: 
  304: /*
  305:  *  call-seq:
  306:  *     Hash[ [key =>|, value]* ]   => hash
  307:  *
  308:  *  Creates a new hash populated with the given objects. Equivalent to
  309:  *  the literal <code>{ <i>key</i>, <i>value</i>, ... }</code>. Keys and
  310:  *  values occur in pairs, so there must be an even number of arguments.
  311:  *
  312:  *     Hash["a", 100, "b", 200]       #=> {"a"=>100, "b"=>200}
  313:  *     Hash["a" => 100, "b" => 200]   #=> {"a"=>100, "b"=>200}
  314:  *     { "a" => 100, "b" => 200 }     #=> {"a"=>100, "b"=>200}
  315:  */
  316: 
  317: static VALUE
  318: rb_hash_s_create(int argc, VALUE *argv, VALUE klass)
  319: {
  320:     VALUE hash, tmp;
  321:     int i;
  322: 
  323:     if (argc == 1) {
  324:         tmp = rb_hash_s_try_convert(Qnil, argv[0]);
  325:         if (!NIL_P(tmp)) {
  326:             hash = hash_alloc(klass);
  327:             if (RHASH(argv[0])->ntbl) {
  328:                 RHASH(hash)->ntbl = st_copy(RHASH(argv[0])->ntbl);
  329:             }
  330:             return hash;
  331:         }
  332: 
  333:         tmp = rb_check_array_type(argv[0]);
  334:         if (!NIL_P(tmp)) {
  335:             long i;
  336: 
  337:             hash = hash_alloc(klass);
  338:             for (i = 0; i < RARRAY_LEN(tmp); ++i) {
  339:                 VALUE v = rb_check_array_type(RARRAY_PTR(tmp)[i]);
  340:                 
  341:                 if (NIL_P(v)) continue;
  342:                 if (RARRAY_LEN(v) < 1 || 2 < RARRAY_LEN(v)) continue;
  343:                 rb_hash_aset(hash, RARRAY_PTR(v)[0], RARRAY_PTR(v)[1]);
  344:             }
  345:             return hash;
  346:         }
  347:     }
  348:     if (argc % 2 != 0) {
  349:         rb_raise(rb_eArgError, "odd number of arguments for Hash");
  350:     }
  351: 
  352:     hash = hash_alloc(klass);
  353:     for (i=0; i<argc; i+=2) {
  354:         rb_hash_aset(hash, argv[i], argv[i + 1]);
  355:     }
  356: 
  357:     return hash;
  358: }
  359: 
  360: static VALUE
  361: to_hash(VALUE hash)
  362: {
  363:     return rb_convert_type(hash, T_HASH, "Hash", "to_hash");
  364: }
  365: 
  366: /*
  367:  *  call-seq:
  368:  *     Hash.try_convert(obj) -> hash or nil
  369:  *
  370:  *  Try to convert <i>obj</i> into a hash, using to_hash method.
  371:  *  Returns converted hash or nil if <i>obj</i> cannot be converted
  372:  *  for any reason.
  373:  *
  374:  *     Hash.try_convert({1=>2})   # => {1=>2}
  375:  *     Hash.try_convert("1=>2")   # => nil
  376:  */
  377: static VALUE
  378: rb_hash_s_try_convert(VALUE dummy, VALUE hash)
  379: {
  380:     return rb_check_convert_type(hash, T_HASH, "Hash", "to_hash");
  381: }
  382: 
  383: static int
  384: rb_hash_rehash_i(VALUE key, VALUE value, st_table *tbl)
  385: {
  386:     if (key != Qundef) st_insert(tbl, key, value);
  387:     return ST_CONTINUE;
  388: }
  389: 
  390: /*
  391:  *  call-seq:
  392:  *     hsh.rehash -> hsh
  393:  *
  394:  *  Rebuilds the hash based on the current hash values for each key. If
  395:  *  values of key objects have changed since they were inserted, this
  396:  *  method will reindex <i>hsh</i>. If <code>Hash#rehash</code> is
  397:  *  called while an iterator is traversing the hash, an
  398:  *  <code>RuntimeError</code> will be raised in the iterator.
  399:  *
  400:  *     a = [ "a", "b" ]
  401:  *     c = [ "c", "d" ]
  402:  *     h = { a => 100, c => 300 }
  403:  *     h[a]       #=> 100
  404:  *     a[0] = "z"
  405:  *     h[a]       #=> nil
  406:  *     h.rehash   #=> {["z", "b"]=>100, ["c", "d"]=>300}
  407:  *     h[a]       #=> 100
  408:  */
  409: 
  410: static VALUE
  411: rb_hash_rehash(VALUE hash)
  412: {
  413:     st_table *tbl;
  414: 
  415:     if (RHASH(hash)->iter_lev > 0) {
  416:         rb_raise(rb_eRuntimeError, "rehash during iteration");
  417:     }
  418:     rb_hash_modify_check(hash);
  419:     if (!RHASH(hash)->ntbl)
  420:         return hash;
  421:     tbl = st_init_table_with_size(RHASH(hash)->ntbl->type, RHASH(hash)->ntbl->num_entries);
  422:     rb_hash_foreach(hash, rb_hash_rehash_i, (st_data_t)tbl);
  423:     st_free_table(RHASH(hash)->ntbl);
  424:     RHASH(hash)->ntbl = tbl;
  425: 
  426:     return hash;
  427: }
  428: 
  429: /*
  430:  *  call-seq:
  431:  *     hsh[key]    =>  value
  432:  *
  433:  *  Element Reference---Retrieves the <i>value</i> object corresponding
  434:  *  to the <i>key</i> object. If not found, returns the a default value (see
  435:  *  <code>Hash::new</code> for details).
  436:  *
  437:  *     h = { "a" => 100, "b" => 200 }
  438:  *     h["a"]   #=> 100
  439:  *     h["c"]   #=> nil
  440:  *
  441:  */
  442: 
  443: VALUE
  444: rb_hash_aref(VALUE hash, VALUE key)
  445: {
  446:     VALUE val;
  447: 
  448:     if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
  449:         return rb_funcall(hash, id_default, 1, key);
  450:     }
  451:     return val;
  452: }
  453: 
  454: VALUE
  455: rb_hash_lookup(VALUE hash, VALUE key)
  456: {
  457:     VALUE val;
  458: 
  459:     if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
  460:         return Qnil; /* without Hash#default */
  461:     }
  462:     return val;
  463: }
  464: 
  465: /*
  466:  *  call-seq:
  467:  *     hsh.fetch(key [, default] )       => obj
  468:  *     hsh.fetch(key) {| key | block }   => obj
  469:  *
  470:  *  Returns a value from the hash for the given key. If the key can't be
  471:  *  found, there are several options: With no other arguments, it will
  472:  *  raise an <code>KeyError</code> exception; if <i>default</i> is
  473:  *  given, then that will be returned; if the optional code block is
  474:  *  specified, then that will be run and its result returned.
  475:  *
  476:  *     h = { "a" => 100, "b" => 200 }
  477:  *     h.fetch("a")                            #=> 100
  478:  *     h.fetch("z", "go fish")                 #=> "go fish"
  479:  *     h.fetch("z") { |el| "go fish, #{el}"}   #=> "go fish, z"
  480:  *
  481:  *  The following example shows that an exception is raised if the key
  482:  *  is not found and a default value is not supplied.
  483:  *
  484:  *     h = { "a" => 100, "b" => 200 }
  485:  *     h.fetch("z")
  486:  *
  487:  *  <em>produces:</em>
  488:  *
  489:  *     prog.rb:2:in `fetch': key not found (KeyError)
  490:  *      from prog.rb:2
  491:  *
  492:  */
  493: 
  494: static VALUE
  495: rb_hash_fetch(int argc, VALUE *argv, VALUE hash)
  496: {
  497:     VALUE key, if_none;
  498:     VALUE val;
  499:     long block_given;
  500: 
  501:     rb_scan_args(argc, argv, "11", &key, &if_none);
  502: 
  503:     block_given = rb_block_given_p();
  504:     if (block_given && argc == 2) {
  505:         rb_warn("block supersedes default value argument");
  506:     }
  507:     if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
  508:         if (block_given) return rb_yield(key);
  509:         if (argc == 1) {
  510:             rb_raise(rb_eKeyError, "key not found");
  511:         }
  512:         return if_none;
  513:     }
  514:     return val;
  515: }
  516: 
  517: /*
  518:  *  call-seq:
  519:  *     hsh.default(key=nil)   => obj
  520:  *
  521:  *  Returns the default value, the value that would be returned by
  522:  *  <i>hsh</i>[<i>key</i>] if <i>key</i> did not exist in <i>hsh</i>.
  523:  *  See also <code>Hash::new</code> and <code>Hash#default=</code>.
  524:  *
  525:  *     h = Hash.new                            #=> {}
  526:  *     h.default                               #=> nil
  527:  *     h.default(2)                            #=> nil
  528:  *
  529:  *     h = Hash.new("cat")                     #=> {}
  530:  *     h.default                               #=> "cat"
  531:  *     h.default(2)                            #=> "cat"
  532:  *
  533:  *     h = Hash.new {|h,k| h[k] = k.to_i*10}   #=> {}
  534:  *     h.default                               #=> 0
  535:  *     h.default(2)                            #=> 20
  536:  */
  537: 
  538: static VALUE
  539: rb_hash_default(int argc, VALUE *argv, VALUE hash)
  540: {
  541:     VALUE key;
  542: 
  543:     rb_scan_args(argc, argv, "01", &key);
  544:     if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
  545:         if (argc == 0) return Qnil;
  546:         return rb_funcall(RHASH(hash)->ifnone, id_yield, 2, hash, key);
  547:     }
  548:     return RHASH(hash)->ifnone;
  549: }
  550: 
  551: /*
  552:  *  call-seq:
  553:  *     hsh.default = obj     => hsh
  554:  *
  555:  *  Sets the default value, the value returned for a key that does not
  556:  *  exist in the hash. It is not possible to set the a default to a
  557:  *  <code>Proc</code> that will be executed on each key lookup.
  558:  *
  559:  *     h = { "a" => 100, "b" => 200 }
  560:  *     h.default = "Go fish"
  561:  *     h["a"]     #=> 100
  562:  *     h["z"]     #=> "Go fish"
  563:  *     # This doesn't do what you might hope...
  564:  *     h.default = proc do |hash, key|
  565:  *       hash[key] = key + key
  566:  *     end
  567:  *     h[2]       #=> #<Proc:0x401b3948@-:6>
  568:  *     h["cat"]   #=> #<Proc:0x401b3948@-:6>
  569:  */
  570: 
  571: static VALUE
  572: rb_hash_set_default(VALUE hash, VALUE ifnone)
  573: {
  574:     rb_hash_modify(hash);
  575:     RHASH(hash)->ifnone = ifnone;
  576:     FL_UNSET(hash, HASH_PROC_DEFAULT);
  577:     return ifnone;
  578: }
  579: 
  580: /*
  581:  *  call-seq:
  582:  *     hsh.default_proc -> anObject
  583:  *
  584:  *  If <code>Hash::new</code> was invoked with a block, return that
  585:  *  block, otherwise return <code>nil</code>.
  586:  *
  587:  *     h = Hash.new {|h,k| h[k] = k*k }   #=> {}
  588:  *     p = h.default_proc                 #=> #<Proc:0x401b3d08@-:1>
  589:  *     a = []                             #=> []
  590:  *     p.call(a, 2)
  591:  *     a                                  #=> [nil, nil, 4]
  592:  */
  593: 
  594: 
  595: static VALUE
  596: rb_hash_default_proc(VALUE hash)
  597: {
  598:     if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
  599:         return RHASH(hash)->ifnone;
  600:     }
  601:     return Qnil;
  602: }
  603: 
  604: static int
  605: key_i(VALUE key, VALUE value, VALUE *args)
  606: {
  607:     if (rb_equal(value, args[0])) {
  608:         args[1] = key;
  609:         return ST_STOP;
  610:     }
  611:     return ST_CONTINUE;
  612: }
  613: 
  614: /*
  615:  *  call-seq:
  616:  *     hsh.key(value)    => key
  617:  *
  618:  *  Returns the key for a given value. If not found, returns <code>nil</code>.
  619:  *
  620:  *     h = { "a" => 100, "b" => 200 }
  621:  *     h.key(200)   #=> "b"
  622:  *     h.key(999)   #=> nil
  623:  *
  624:  */
  625: 
  626: static VALUE
  627: rb_hash_key(VALUE hash, VALUE value)
  628: {
  629:     VALUE args[2];
  630: 
  631:     args[0] = value;
  632:     args[1] = Qnil;
  633: 
  634:     rb_hash_foreach(hash, key_i, (st_data_t)args);
  635: 
  636:     return args[1];
  637: }
  638: 
  639: /* :nodoc: */
  640: static VALUE
  641: rb_hash_index(VALUE hash, VALUE value)
  642: {
  643:     rb_warn("Hash#index is deprecated; use Hash#key");
  644:     return rb_hash_key(hash, value);
  645: }
  646: 
  647: static VALUE
  648: rb_hash_delete_key(VALUE hash, VALUE key)
  649: {
  650:     st_data_t ktmp = (st_data_t)key, val;