hash.c

   1 /**********************************************************************
   2
   3   hash.c -
   4
   5   $Author$
   6   created at: Mon Nov 22 18:51:18 JST 1993
   7
   8   Copyright (C) 1993-2007 Yukihiro Matsumoto
   9   Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  10   Copyright (C) 2000  Information-technology Promotion Agency, Japan
  11
  12 **********************************************************************/
  13
  14 #include "eval_intern.h"
  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_hash_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     int hnum;
  80
  81     switch (TYPE(a)) {
  82       case T_FIXNUM:
  83       case T_SYMBOL:
  84         hnum = (int)a;
  85         break;
  86
  87       case T_STRING:
  88         hnum = rb_str_hash(a);
  89         break;
  90
  91       default:
  92         hval = rb_funcall(a, id_hash, 0);
  93         if (!FIXNUM_P(hval)) {
  94             hval = rb_funcall(hval, '%', 1, INT2FIX(536870923));
  95         }
  96         hnum = (int)FIX2LONG(hval);
  97     }
  98     hnum <<= 1;
  99     return RSHIFT(hnum, 1);
 100 }
 101
 102 static const struct st_hash_type objhash = {
 103     rb_any_cmp,
 104     rb_any_hash,
 105 };
 106
 107 static const struct st_hash_type identhash = {
 108     st_numcmp,
 109     st_numhash,
 110 };
 111
 112 typedef int st_foreach_func(st_data_t, st_data_t, st_data_t);
 113
 114 struct foreach_safe_arg {
 115     st_table *tbl;
 116     st_foreach_func *func;
 117     st_data_t arg;
 118 };
 119
 120 static int
 121 foreach_safe_i(st_data_t key, st_data_t value, struct foreach_safe_arg *arg)
 122 {
 123     int status;
 124
 125     if (key == Qundef) return ST_CONTINUE;
 126     status = (*arg->func)(key, value, arg->arg);
 127     if (status == ST_CONTINUE) {
 128         return ST_CHECK;
 129     }
 130     return status;
 131 }
 132
 133 void
 134 st_foreach_safe(st_table *table, int (*func)(ANYARGS), st_data_t a)
 135 {
 136     struct foreach_safe_arg arg;
 137
 138     arg.tbl = table;
 139     arg.func = (st_foreach_func *)func;
 140     arg.arg = a;
 141     if (st_foreach(table, foreach_safe_i, (st_data_t)&arg)) {
 142         rb_raise(rb_eRuntimeError, "hash modified during iteration");
 143     }
 144 }
 145
 146 typedef int rb_foreach_func(VALUE, VALUE, VALUE);
 147
 148 struct hash_foreach_arg {
 149     VALUE hash;
 150     rb_foreach_func *func;
 151     VALUE arg;
 152 };
 153
 154 static int
 155 hash_foreach_iter(VALUE key, VALUE value, struct hash_foreach_arg *arg)
 156 {
 157     int status;
 158     st_table *tbl;
 159
 160     tbl = RHASH(arg->hash)->ntbl;
 161     if (key == Qundef) return ST_CONTINUE;
 162     status = (*arg->func)(key, value, arg->arg);
 163     if (RHASH(arg->hash)->ntbl != tbl) {
 164         rb_raise(rb_eRuntimeError, "rehash occurred during iteration");
 165     }
 166     switch (status) {
 167       case ST_DELETE:
 168         st_delete_safe(tbl, (st_data_t*)&key, 0, Qundef);
 169         FL_SET(arg->hash, HASH_DELETED);
 170       case ST_CONTINUE:
 171         break;
 172       case ST_STOP:
 173         return ST_STOP;
 174     }
 175     return ST_CHECK;
 176 }
 177
 178 static VALUE
 179 hash_foreach_ensure(VALUE hash)
 180 {
 181     RHASH(hash)->iter_lev--;
 182
 183     if (RHASH(hash)->iter_lev == 0) {
 184         if (FL_TEST(hash, HASH_DELETED)) {
 185             st_cleanup_safe(RHASH(hash)->ntbl, Qundef);
 186             FL_UNSET(hash, HASH_DELETED);
 187         }
 188     }
 189     return 0;
 190 }
 191
 192 static VALUE
 193 hash_foreach_call(struct hash_foreach_arg *arg)
 194 {
 195     if (st_foreach(RHASH(arg->hash)->ntbl, hash_foreach_iter, (st_data_t)arg)) {
 196         rb_raise(rb_eRuntimeError, "hash modified during iteration");
 197     }
 198     return Qnil;
 199 }
 200
 201 void
 202 rb_hash_foreach(VALUE hash, int (*func)(ANYARGS), VALUE farg)
 203 {
 204     struct hash_foreach_arg arg;
 205
 206     if (!RHASH(hash)->ntbl)
 207         return;
 208     RHASH(hash)->iter_lev++;
 209     arg.hash = hash;
 210     arg.func = (rb_foreach_func *)func;
 211     arg.arg  = farg;
 212     rb_ensure(hash_foreach_call, (VALUE)&arg, hash_foreach_ensure, hash);
 213 }
 214
 215 static VALUE
 216 hash_alloc(VALUE klass)
 217 {
 218     NEWOBJ(hash, struct RHash);
 219     OBJSETUP(hash, klass, T_HASH);
 220
 221     hash->ifnone = Qnil;
 222
 223     return (VALUE)hash;
 224 }
 225
 226 VALUE
 227 rb_hash_new(void)
 228 {
 229     return hash_alloc(rb_cHash);
 230 }
 231
 232 VALUE
 233 rb_hash_dup(VALUE hash)
 234 {
 235     NEWOBJ(ret, struct RHash);
 236     DUPSETUP(ret, hash);
 237
 238     if (!RHASH_EMPTY_P(hash))
 239         ret->ntbl = st_copy(RHASH(hash)->ntbl);
 240     if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
 241         FL_SET(ret, HASH_PROC_DEFAULT);
 242     }
 243     ret->ifnone = RHASH(hash)->ifnone;
 244     return (VALUE)ret;
 245 }
 246
 247 static void
 248 rb_hash_modify_check(VALUE hash)
 249 {
 250     if (OBJ_FROZEN(hash)) rb_error_frozen("hash");
 251     if (!OBJ_UNTRUSTED(hash) && rb_safe_level() >= 4)
 252         rb_raise(rb_eSecurityError, "Insecure: can't modify hash");
 253 }
 254
 255 struct st_table *
 256 rb_hash_tbl(VALUE hash)
 257 {
 258     if (!RHASH(hash)->ntbl) {
 259         RHASH(hash)->ntbl = st_init_table(&objhash);
 260     }
 261     return RHASH(hash)->ntbl;
 262 }
 263
 264 static void
 265 rb_hash_modify(VALUE hash)
 266 {
 267     rb_hash_modify_check(hash);
 268     rb_hash_tbl(hash);
 269 }
 270
 271 /*
 272  *  call-seq:
 273  *     Hash.new                          => hash
 274  *     Hash.new(obj)                     => aHash
 275  *     Hash.new {|hash, key| block }     => aHash
 276  *
 277  *  Returns a new, empty hash. If this hash is subsequently accessed by
 278  *  a key that doesn't correspond to a hash entry, the value returned
 279  *  depends on the style of <code>new</code> used to create the hash. In
 280  *  the first form, the access returns <code>nil</code>. If
 281  *  <i>obj</i> is specified, this single object will be used for
 282  *  all <em>default values</em>. If a block is specified, it will be
 283  *  called with the hash object and the key, and should return the
 284  *  default value. It is the block's responsibility to store the value
 285  *  in the hash if required.
 286  *
 287  *     h = Hash.new("Go Fish")
 288  *     h["a"] = 100
 289  *     h["b"] = 200
 290  *     h["a"]           #=> 100
 291  *     h["c"]           #=> "Go Fish"
 292  *     # The following alters the single default object
 293  *     h["c"].upcase!   #=> "GO FISH"
 294  *     h["d"]           #=> "GO FISH"
 295  *     h.keys           #=> ["a", "b"]
 296  *
 297  *     # While this creates a new default object each time
 298  *     h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
 299  *     h["c"]           #=> "Go Fish: c"
 300  *     h["c"].upcase!   #=> "GO FISH: C"
 301  *     h["d"]           #=> "Go Fish: d"
 302  *     h.keys           #=> ["c", "d"]
 303  *
 304  */
 305
 306 static VALUE
 307 rb_hash_initialize(int argc, VALUE *argv, VALUE hash)
 308 {
 309     VALUE ifnone;
 310
 311     rb_hash_modify(hash);
 312     if (rb_block_given_p()) {
 313         if (argc > 0) {
 314             rb_raise(rb_eArgError, "wrong number of arguments");
 315         }
 316         RHASH(hash)->ifnone = rb_block_proc();
 317         FL_SET(hash, HASH_PROC_DEFAULT);
 318     }
 319     else {
 320         rb_scan_args(argc, argv, "01", &ifnone);
 321         RHASH(hash)->ifnone = ifnone;
 322     }
 323
 324     return hash;
 325 }
 326
 327 /*
 328  *  call-seq:
 329  *     Hash[ [key =>|, value]* ]   => hash
 330  *
 331  *  Creates a new hash populated with the given objects. Equivalent to
 332  *  the literal <code>{ <i>key</i>, <i>value</i>, ... }</code>. Keys and
 333  *  values occur in pairs, so there must be an even number of arguments.
 334  *
 335  *     Hash["a", 100, "b", 200]       #=> {"a"=>100, "b"=>200}
 336  *     Hash["a" => 100, "b" => 200]   #=> {"a"=>100, "b"=>200}
 337  *     { "a" => 100, "b" => 200 }     #=> {"a"=>100, "b"=>200}
 338  */
 339
 340 static VALUE
 341 rb_hash_s_create(int argc, VALUE *argv, VALUE klass)
 342 {
 343     VALUE hash, tmp;
 344     int i;
 345
 346     if (argc == 1) {
 347         tmp = rb_hash_s_try_convert(Qnil, argv[0]);
 348         if (!NIL_P(tmp)) {
 349             hash = hash_alloc(klass);
 350             if (RHASH(tmp)->ntbl) {
 351                 RHASH(hash)->ntbl = st_copy(RHASH(tmp)->ntbl);
 352             }
 353             return hash;
 354         }
 355
 356         tmp = rb_check_array_type(argv[0]);
 357         if (!NIL_P(tmp)) {
 358             long i;
 359
 360             hash = hash_alloc(klass);
 361             for (i = 0; i < RARRAY_LEN(tmp); ++i) {
 362                 VALUE v = rb_check_array_type(RARRAY_PTR(tmp)[i]);
 363
 364                 if (NIL_P(v)) continue;
 365                 if (RARRAY_LEN(v) < 1 || 2 < RARRAY_LEN(v)) continue;
 366                 rb_hash_aset(hash, RARRAY_PTR(v)[0], RARRAY_PTR(v)[1]);
 367             }
 368             return hash;
 369         }
 370     }
 371     if (argc % 2 != 0) {
 372         rb_raise(rb_eArgError, "odd number of arguments for Hash");
 373     }
 374
 375     hash = hash_alloc(klass);
 376     for (i=0; i<argc; i+=2) {
 377         rb_hash_aset(hash, argv[i], argv[i + 1]);
 378     }
 379
 380     return hash;
 381 }
 382
 383 static VALUE
 384 to_hash(VALUE hash)
 385 {
 386     return rb_convert_type(hash, T_HASH, "Hash", "to_hash");
 387 }
 388
 389 /*
 390  *  call-seq:
 391  *     Hash.try_convert(obj) -> hash or nil
 392  *
 393  *  Try to convert <i>obj</i> into a hash, using to_hash method.
 394  *  Returns converted hash or nil if <i>obj</i> cannot be converted
 395  *  for any reason.
 396  *
 397  *     Hash.try_convert({1=>2})   # => {1=>2}
 398  *     Hash.try_convert("1=>2")   # => nil
 399  */
 400 static VALUE
 401 rb_hash_s_try_convert(VALUE dummy, VALUE hash)
 402 {
 403     return rb_check_convert_type(hash, T_HASH, "Hash", "to_hash");
 404 }
 405
 406 static int
 407 rb_hash_rehash_i(VALUE key, VALUE value, st_table *tbl)
 408 {
 409     if (key != Qundef) st_insert(tbl, key, value);
 410     return ST_CONTINUE;
 411 }
 412
 413 /*
 414  *  call-seq:
 415  *     hsh.rehash -> hsh
 416  *
 417  *  Rebuilds the hash based on the current hash values for each key. If
 418  *  values of key objects have changed since they were inserted, this
 419  *  method will reindex <i>hsh</i>. If <code>Hash#rehash</code> is
 420  *  called while an iterator is traversing the hash, an
 421  *  <code>RuntimeError</code> will be raised in the iterator.
 422  *
 423  *     a = [ "a", "b" ]
 424  *     c = [ "c", "d" ]
 425  *     h = { a => 100, c => 300 }
 426  *     h[a]       #=> 100
 427  *     a[0] = "z"
 428  *     h[a]       #=> nil
 429  *     h.rehash   #=> {["z", "b"]=>100, ["c", "d"]=>300}
 430  *     h[a]       #=> 100
 431  */
 432
 433 static VALUE
 434 rb_hash_rehash(VALUE hash)
 435 {
 436     st_table *tbl;
 437
 438     if (RHASH(hash)->iter_lev > 0) {
 439         rb_raise(rb_eRuntimeError, "rehash during iteration");
 440     }
 441     rb_hash_modify_check(hash);
 442     if (!RHASH(hash)->ntbl)
 443         return hash;
 444     tbl = st_init_table_with_size(RHASH(hash)->ntbl->type, RHASH(hash)->ntbl->num_entries);
 445     rb_hash_foreach(hash, rb_hash_rehash_i, (st_data_t)tbl);
 446     st_free_table(RHASH(hash)->ntbl);
 447     RHASH(hash)->ntbl = tbl;
 448
 449     return hash;
 450 }
 451
 452 /*
 453  *  call-seq:
 454  *     hsh[key]    =>  value
 455  *
 456  *  Element Reference---Retrieves the <i>value</i> object corresponding
 457  *  to the <i>key</i> object. If not found, returns the a default value (see
 458  *  <code>Hash::new</code> for details).
 459  *
 460  *     h = { "a" => 100, "b" => 200 }
 461  *     h["a"]   #=> 100
 462  *     h["c"]   #=> nil
 463  *
 464  */
 465
 466 VALUE
 467 rb_hash_aref(VALUE hash, VALUE key)
 468 {
 469     VALUE val;
 470
 471     if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
 472         return rb_funcall(hash, id_default, 1, key);
 473     }
 474     return val;
 475 }
 476
 477 VALUE
 478 rb_hash_lookup(VALUE hash, VALUE key)
 479 {
 480     VALUE val;
 481
 482     if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
 483         return Qnil; /* without Hash#default */
 484     }
 485     return val;
 486 }
 487
 488 /*
 489  *  call-seq:
 490  *     hsh.fetch(key [, default] )       => obj
 491  *     hsh.fetch(key) {| key | block }   => obj
 492  *
 493  *  Returns a value from the hash for the given key. If the key can't be
 494  *  found, there are several options: With no other arguments, it will
 495  *  raise an <code>KeyError</code> exception; if <i>default</i> is
 496  *  given, then that will be returned; if the optional code block is
 497  *  specified, then that will be run and its result returned.
 498  *
 499  *     h = { "a" => 100, "b" => 200 }
 500  *     h.fetch("a")                            #=> 100
 501  *     h.fetch("z", "go fish")                 #=> "go fish"
 502  *     h.fetch("z") { |el| "go fish, #{el}"}   #=> "go fish, z"
 503  *
 504  *  The following example shows that an exception is raised if the key
 505  *  is not found and a default value is not supplied.
 506  *
 507  *     h = { "a" => 100, "b" => 200 }
 508  *     h.fetch("z")
 509  *
 510  *  <em>produces:</em>
 511  *
 512  *     prog.rb:2:in `fetch': key not found (KeyError)
 513  *      from prog.rb:2
 514  *
 515  */
 516
 517 static VALUE
 518 rb_hash_fetch(int argc, VALUE *argv, VALUE hash)
 519 {
 520     VALUE key, if_none;
 521     VALUE val;
 522     long block_given;
 523
 524     rb_scan_args(argc, argv, "11", &key, &if_none);
 525
 526     block_given = rb_block_given_p();
 527     if (block_given && argc == 2) {
 528         rb_warn("block supersedes default value argument");
 529     }
 530     if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
 531         if (block_given) return rb_yield(key);
 532         if (argc == 1) {
 533             rb_raise(rb_eKeyError, "key not found");
 534         }
 535         return if_none;
 536     }
 537     return val;
 538 }
 539
 540 /*
 541  *  call-seq:
 542  *     hsh.default(key=nil)   => obj
 543  *
 544  *  Returns the default value, the value that would be returned by
 545  *  <i>hsh</i>[<i>key</i>] if <i>key</i> did not exist in <i>hsh</i>.
 546  *  See also <code>Hash::new</code> and <code>Hash#default=</code>.
 547  *
 548  *     h = Hash.new                            #=> {}
 549  *     h.default                               #=> nil
 550  *     h.default(2)                            #=> nil
 551  *
 552  *     h = Hash.new("cat")                     #=> {}
 553  *     h.default                               #=> "cat"
 554  *     h.default(2)                            #=> "cat"
 555  *
 556  *     h = Hash.new {|h,k| h[k] = k.to_i*10}   #=> {}
 557  *     h.default                               #=> nil
 558  *     h.default(2)                            #=> 20
 559  */
 560
 561 static VALUE
 562 rb_hash_default(int argc, VALUE *argv, VALUE hash)
 563 {
 564     VALUE key;
 565
 566     rb_scan_args(argc, argv, "01", &key);
 567     if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
 568         if (argc == 0) return Qnil;
 569         return rb_funcall(RHASH(hash)->ifnone, id_yield, 2, hash, key);
 570     }
 571     return RHASH(hash)->ifnone;
 572 }
 573
 574 /*
 575  *  call-seq:
 576  *     hsh.default = obj     => obj
 577  *
 578  *  Sets the default value, the value returned for a key that does not
 579  *  exist in the hash. It is not possible to set the a default to a
 580  *  <code>Proc</code> that will be executed on each key lookup.
 581  *
 582  *     h = { "a" => 100, "b" => 200 }
 583  *     h.default = "Go fish"
 584  *     h["a"]     #=> 100
 585  *     h["z"]     #=> "Go fish"
 586  *     # This doesn't do what you might hope...
 587  *     h.default = proc do |hash, key|
 588  *       hash[key] = key + key
 589  *     end
 590  *     h[2]       #=> #<Proc:0x401b3948@-:6>
 591  *     h["cat"]   #=> #<Proc:0x401b3948@-:6>
 592  */
 593
 594 static VALUE
 595 rb_hash_set_default(VALUE hash, VALUE ifnone)
 596 {
 597     rb_hash_modify(hash);
 598     RHASH(hash)->ifnone = ifnone;
 599     FL_UNSET(hash, HASH_PROC_DEFAULT);
 600     return ifnone;
 601 }
 602
 603 /*
 604  *  call-seq:
 605  *     hsh.default_proc -> anObject
 606  *
 607  *  If <code>Hash::new</code> was invoked with a block, return that
 608  *  block, otherwise return <code>nil</code>.
 609  *
 610  *     h = Hash.new {|h,k| h[k] = k*k }   #=> {}
 611  *     p = h.default_proc                 #=> #<Proc:0x401b3d08@-:1>
 612  *     a = []                             #=> []
 613  *     p.call(a, 2)
 614  *     a                                  #=> [nil, nil, 4]
 615  */
 616
 617
 618 static VALUE
 619 rb_hash_default_proc(VALUE hash)
 620 {
 621     if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
 622         return RHASH(hash)->ifnone;
 623     }
 624     return Qnil;
 625 }
 626
 627 /*
 628  *  call-seq:
 629  *     hsh.default_proc = proc_obj     => proc_obj
 630  *
 631  *  Sets the default proc to be executed on each key lookup.
 632  *
 633  *     h.default_proc = proc do |hash, key|
 634  *       hash[key] = key + key
 635  *     end
 636  *     h[2]       #=> 4
 637  *     h["cat"]   #=> "catcat"
 638  */
 639
 640 static VALUE
 641 rb_hash_set_default_proc(VALUE hash, VALUE proc)
 642 {
 643     VALUE b;
 644
 645     rb_hash_modify(hash);
 646     b = rb_check_convert_type(proc, T_DATA, "Proc", "to_proc");
 647     if (NIL_P(b) || !rb_obj_is_proc(b)) {
 648         rb_raise(rb_eTypeError,
 649                  "wrong default_proc type %s (expected Proc)",
 650                  rb_obj_classname(proc));
 651     }
 652     proc = b;
 653     RHASH(hash)->ifnone = proc;
 654     FL_SET(hash, HASH_PROC_DEFAULT);
 655     return proc;
 656 }
 657
 658 static int
 659 key_i(VALUE key, VALUE value, VALUE *args)
 660 {
 661     if (rb_equal(value, args[0])) {
 662         args[1] = key;
 663         return ST_STOP;
 664     }
 665     return ST_CONTINUE;
 666 }
 667
 668 /*
 669  *  call-seq:
 670  *     hsh.key(value)    => key
 671  *
 672  *  Returns the key for a given value. If not found, returns <code>nil</code>.
 673  *
 674  *     h = { "a" => 100, "b" => 200 }
 675  *     h.key(200)   #=> "b"
 676  *     h.key(999)   #=> nil
 677  *
 678  */
 679
 680 static VALUE
 681 rb_hash_key(VALUE hash, VALUE value)
 682 {
 683     VALUE args[2];
 684
 685     args[0] = value;
 686     args[1] = Qnil;
 687
 688     rb_hash_foreach(hash, key_i, (st_data_t)args);
 689
 690     return args[1];
 691 }
 692
 693 /* :nodoc: */
 694 static VALUE
 695 rb_hash_index(VALUE hash, VALUE value)
 696 {
 697     rb_warn("Hash#index is deprecated; use Hash#key");
 698     return rb_hash_key(hash, value);
 699 }
 700
 701 static VALUE
 702 rb_hash_delete_key(VALUE hash, VALUE key)
 703 {
 704     st_data_t ktmp = (st_data_t)key, val;
 705
 706     if (!RHASH(hash)->ntbl)
 707         return Qundef;
 708     if (RHASH(hash)->iter_lev > 0) {
 709         if (st_delete_safe(RHASH(hash)->ntbl, &ktmp, &val, Qundef)) {
 710             FL_SET(hash, HASH_DELETED);
 711             return (VALUE)val;
 712         }
 713     }
 714     else if (st_delete(RHASH(hash)->ntbl, &ktmp, &val))
 715         return (VALUE)val;
 716     return Qundef;
 717 }
 718
 719 /*
 720  *  call-seq:
 721  *     hsh.delete(key)                   => value
 722  *     hsh.delete(key) {| key | block }  => value
 723  *
 724  *  Deletes and returns a key-value pair from <i>hsh</i> whose key is
 725  *  equal to <i>key</i>. If the key is not found, returns the
 726  *  <em>default value</em>. If the optional code block is given and the
 727  *  key is not found, pass in the key and return the result of
 728  *  <i>block</i>.
 729  *
 730  *     h = { "a" => 100, "b" => 200 }
 731  *     h.delete("a")                              #=> 100
 732  *     h.delete("z")                              #=> nil
 733  *     h.delete("z") { |el| "#{el} not found" }   #=> "z not found"
 734  *
 735  */
 736
 737 VALUE
 738 rb_hash_delete(VALUE hash, VALUE key)
 739 {
 740     VALUE val;
 741
 742     rb_hash_modify(hash);
 743     val = rb_hash_delete_key(hash, key);
 744     if (val != Qundef) return val;
 745     if (rb_block_given_p()) {
 746         return rb_yield(key);
 747     }
 748     return Qnil;
 749 }
 750
 751 struct shift_var {
 752     VALUE key;
 753     VALUE val;
 754 };
 755
 756 static int
 757 shift_i(VALUE key, VALUE value, struct shift_var *var)
 758 {
 759     if (key == Qundef) return ST_CONTINUE;
 760     if (var->key != Qundef) return ST_STOP;
 761     var->key = key;
 762     var->val = value;
 763     return ST_DELETE;
 764 }
 765
 766 static int
 767 shift_i_safe(VALUE key, VALUE value, struct shift_var *var)
 768 {
 769     if (key == Qundef) return ST_CONTINUE;
 770     var->key = key;
 771     var->val = value;
 772     return ST_STOP;
 773 }
 774
 775 /*
 776  *  call-seq:
 777  *     hsh.shift -> anArray or obj
 778  *
 779  *  Removes a key-value pair from <i>hsh</i> and returns it as the
 780  *  two-item array <code>[</code> <i>key, value</i> <code>]</code>, or
 781  *  the hash's default value if the hash is empty.
 782  *
 783  *     h = { 1 => "a", 2 => "b", 3 => "c" }
 784  *     h.shift   #=> [1, "a"]
 785  *     h         #=> {2=>"b", 3=>"c"}
 786  */
 787
 788 static VALUE
 789 rb_hash_shift(VALUE hash)
 790 {
 791     struct shift_var var;
 792
 793     rb_hash_modify(hash);
 794     var.key = Qundef;
 795     rb_hash_foreach(hash, RHASH(hash)->iter_lev > 0 ? shift_i_safe : shift_i,
 796                     (st_data_t)&var);
 797
 798     if (var.key != Qundef) {
 799         if (RHASH(hash)->iter_lev > 0) {
 800             rb_hash_delete_key(hash, var.key);
 801         }
 802         return rb_assoc_new(var.key, var.val);
 803     }
 804     else if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
 805         return rb_funcall(RHASH(hash)->ifnone, id_yield, 2, hash, Qnil);
 806     }
 807     else {
 808         return RHASH(hash)->ifnone;
 809     }
 810 }
 811
 812 static int
 813 delete_if_i(VALUE key, VALUE value, VALUE hash)
 814 {
 815     if (key == Qundef) return ST_CONTINUE;
 816     if (RTEST(rb_yield_values(2, key, value))) {
 817         rb_hash_delete_key(hash, key);
 818     }
 819     return ST_CONTINUE;
 820 }
 821
 822 /*
 823  *  call-seq:
 824  *     hsh.delete_if {| key, value | block }  -> hsh
 825  *
 826  *  Deletes every key-value pair from <i>hsh</i> for which <i>block</i>
 827  *  evaluates to <code>true</code>.
 828  *
 829  *     h = { "a" => 100, "b" => 200, "c" => 300 }
 830  *     h.delete_if {|key, value| key >= "b" }   #=> {"a"=>100}
 831  *
 832  */
 833
 834 VALUE
 835 rb_hash_delete_if(VALUE hash)
 836 {
 837     RETURN_ENUMERATOR(hash, 0, 0);
 838     rb_hash_modify(hash);
 839     rb_hash_foreach(hash, delete_if_i, hash);
 840     return hash;
 841 }
 842
 843 /*
 844  *  call-seq:
 845  *     hsh.reject! {| key, value | block }  -> hsh or nil
 846  *
 847  *  Equivalent to <code>Hash#delete_if</code>, but returns
 848  *  <code>nil</code> if no changes were made.
 849  */
 850
 851 VALUE
 852 rb_hash_reject_bang(VALUE hash)
 853 {
 854     int n;
 855
 856     RETURN_ENUMERATOR(hash, 0, 0);
 857     if (!RHASH(hash)->ntbl)
 858         return Qnil;
 859     n = RHASH(hash)->ntbl->num_entries;
 860     rb_hash_delete_if(hash);
 861     if (n == RHASH(hash)->ntbl->num_entries) return Qnil;
 862     return hash;
 863 }
 864
 865 /*
 866  *  call-seq:
 867  *     hsh.reject {| key, value | block }  -> a_hash
 868  *
 869  *  Same as <code>Hash#delete_if</code>, but works on (and returns) a
 870  *  copy of the <i>hsh</i>. Equivalent to
 871  *  <code><i>hsh</i>.dup.delete_if</code>.
 872  *
 873  */
 874
 875 static VALUE
 876 rb_hash_reject(VALUE hash)
 877 {
 878     return rb_hash_delete_if(rb_obj_dup(hash));
 879 }
 880
 881 /*
 882  * call-seq:
 883  *   hsh.values_at(key, ...)   => array
 884  *
 885  * Return an array containing the values associated with the given keys.
 886  * Also see <code>Hash.select</code>.
 887  *
 888  *   h = { "cat" => "feline", "dog" => "canine", "cow" => "bovine" }
 889  *   h.values_at("cow", "cat")  #=> ["bovine", "feline"]
 890  */
 891
 892 VALUE
 893 rb_hash_values_at(int argc, VALUE *argv, VALUE hash)
 894 {
 895     VALUE result = rb_ary_new2(argc);
 896     long i;
 897
 898     for (i=0; i<argc; i++) {
 899         rb_ary_push(result, rb_hash_aref(hash, argv[i]));
 900     }
 901     return result;
 902 }
 903
 904 static int
 905 select_i(VALUE key, VALUE value, VALUE result)
 906 {
 907     if (key == Qundef) return ST_CONTINUE;
 908     if (RTEST(rb_yield_values(2, key, value)))
 909         rb_hash_aset(result, key, value);
 910     return ST_CONTINUE;
 911 }
 912
 913 /*
 914  *  call-seq:
 915  *     hsh.select {|key, value| block}   => a_hash
 916  *
 917  *  Returns a new hash consisting of entries which the block returns true.
 918  *
 919  *     h = { "a" => 100, "b" => 200, "c" => 300 }
 920  *     h.select {|k,v| k > "a"}  #=> {"b" => 200, "c" => 300}
 921  *     h.select {|k,v| v < 200}  #=> {"a" => 100}
 922  */
 923
 924 VALUE
 925 rb_hash_select(VALUE hash)
 926 {
 927     VALUE result;
 928
 929     RETURN_ENUMERATOR(hash, 0, 0);
 930     result = rb_hash_new();
 931     rb_hash_foreach(hash, select_i, result);
 932     return result;
 933 }
 934
 935 static int
 936 clear_i(VALUE key, VALUE value, VALUE dummy)
 937 {
 938     return ST_DELETE;
 939 }
 940
 941 /*
 942  *  call-seq:
 943  *     hsh.clear -> hsh
 944  *
 945  *  Removes all key-value pairs from <i>hsh</i>.
 946  *
 947  *     h = { "a" => 100, "b" => 200 }   #=> {"a"=>100, "b"=>200}
 948  *     h.clear                          #=> {}
 949  *
 950  */
 951
 952 static VALUE
 953 rb_hash_clear(VALUE hash)
 954 {
 955     rb_hash_modify_check(hash);
 956     if (!RHASH(hash)->ntbl)
 957         return hash;
 958     if (RHASH(hash)->ntbl->num_entries > 0) {
 959         if (RHASH(hash)->iter_lev > 0)
 960             rb_hash_foreach(hash, clear_i, 0);
 961         else
 962             st_clear(RHASH(hash)->ntbl);
 963     }
 964
 965     return hash;
 966 }
 967
 968 /*
 969  *  call-seq:
 970  *     hsh[key] = value        => value
 971  *     hsh.store(key, value)   => value
 972  *
 973  *  Element Assignment---Associates the value given by
 974  *  <i>value</i> with the key given by <i>key</i>.
 975  *  <i>key</i> should not have its value changed while it is in
 976  *  use as a key (a <code>String</code> passed as a key will be
 977  *  duplicated and frozen).
 978  *
 979  *     h = { "a" => 100, "b" => 200 }
 980  *     h["a"] = 9
 981  *     h["c"] = 4
 982  *     h   #=> {"a"=>9, "b"=>200, "c"=>4}
 983  *
 984  */
 985
 986 VALUE
 987 rb_hash_aset(VALUE hash, VALUE key, VALUE val)
 988 {
 989     rb_hash_modify(hash);
 990     if (RHASH(hash)->ntbl->type == &identhash ||
 991         TYPE(key) != T_STRING || st_lookup(RHASH(hash)->ntbl, key, 0)) {
 992         st_insert(RHASH(hash)->ntbl, key, val);
 993     }
 994     else {
 995         st_add_direct(RHASH(hash)->ntbl, rb_str_new4(key), val);
 996     }
 997     return val;
 998 }
 999
1000 static int
1001 replace_i(VALUE key, VALUE val, VALUE hash)
1002 {
1003     if (key != Qundef) {
1004         rb_hash_aset(hash, key, val);
1005     }
1006
1007     return ST_CONTINUE;
1008 }
1009
1010 /*
1011  *  call-seq:
1012  *     hsh.replace(other_hash) -> hsh
1013  *
1014  *  Replaces the contents of <i>hsh</i> with the contents of
1015  *  <i>other_hash</i>.
1016  *
1017  *     h = { "a" => 100, "b" => 200 }
1018  *     h.replace({ "c" => 300, "d" => 400 })   #=> {"c"=>300, "d"=>400}
1019  *
1020  */
1021
1022 static VALUE
1023 rb_hash_replace(VALUE hash, VALUE hash2)
1024 {
1025     hash2 = to_hash(hash2);
1026     if (hash == hash2) return hash;
1027     rb_hash_clear(hash);
1028     rb_hash_foreach(hash2, replace_i, hash);
1029     RHASH(hash)->ifnone = RHASH(hash2)->ifnone;
1030     if (FL_TEST(hash2, HASH_PROC_DEFAULT)) {
1031         FL_SET(hash, HASH_PROC_DEFAULT);
1032     }
1033     else {
1034         FL_UNSET(hash, HASH_PROC_DEFAULT);
1035     }
1036
1037     return hash;
1038 }
1039
1040 /*
1041  *  call-seq:
1042  *     hsh.length    =>  fixnum
1043  *     hsh.size      =>  fixnum
1044  *
1045  *  Returns the number of key-value pairs in the hash.
1046  *
1047  *     h = { "d" => 100, "a" => 200, "v" => 300, "e" => 400 }
1048  *     h.length        #=> 4
1049  *     h.delete("a")   #=> 200
1050  *     h.length        #=> 3
1051  */
1052
1053 static VALUE
1054 rb_hash_size(VALUE hash)
1055 {
1056     if (!RHASH(hash)->ntbl)
1057         return INT2FIX(0);
1058     return INT2FIX(RHASH(hash)->ntbl->num_entries);
1059 }
1060
1061
1062 /*
1063  *  call-seq:
1064  *     hsh.empty?    => true or false
1065  *
1066  *  Returns <code>true</code> if <i>hsh</i> contains no key-value pairs.
1067  *
1068  *     {}.empty?   #=> true
1069  *
1070  */
1071
1072 static VALUE
1073 rb_hash_empty_p(VALUE hash)
1074 {
1075     return RHASH_EMPTY_P(hash) ? Qtrue : Qfalse;
1076 }
1077
1078 static int
1079 each_value_i(VALUE key, VALUE value)
1080 {
1081     if (key == Qundef) return ST_CONTINUE;
1082     rb_yield(value);
1083     return ST_CONTINUE;
1084 }
1085
1086 /*
1087  *  call-seq:
1088  *     hsh.each_value {| value | block } -> hsh
1089  *
1090  *  Calls <i>block</i> once for each key in <i>hsh</i>, passing the
1091  *  value as a parameter.
1092  *
1093  *     h = { "a" => 100, "b" => 200 }
1094  *     h.each_value {|value| puts value }
1095  *
1096  *  <em>produces:</em>
1097  *
1098  *     100
1099  *     200
1100  */
1101
1102 static VALUE
1103 rb_hash_each_value(VALUE hash)
1104 {
1105     RETURN_ENUMERATOR(hash, 0, 0);
1106     rb_hash_foreach(hash, each_value_i, 0);
1107     return hash;
1108 }
1109
1110 static int
1111 each_key_i(VALUE key, VALUE value)
1112 {
1113     if (key == Qundef) return ST_CONTINUE;
1114     rb_yield(key);
1115     return ST_CONTINUE;
1116 }
1117
1118 /*
1119  *  call-seq:
1120  *     hsh.each_key {| key | block } -> hsh
1121  *
1122  *  Calls <i>block</i> once for each key in <i>hsh</i>, passing the key
1123  *  as a parameter.
1124  *
1125  *     h = { "a" => 100, "b" => 200 }
1126  *     h.each_key {|key| puts key }
1127  *
1128  *  <em>produces:</em>
1129  *
1130  *     a
1131  *     b
1132  */
1133 static VALUE
1134 rb_hash_each_key(VALUE hash)
1135 {
1136     RETURN_ENUMERATOR(hash, 0, 0);
1137     rb_hash_foreach(hash, each_key_i, 0);
1138     return hash;
1139 }
1140
1141 static int
1142 each_pair_i(VALUE key, VALUE value)
1143 {
1144     if (key == Qundef) return ST_CONTINUE;
1145     rb_yield(rb_assoc_new(key, value));
1146     return ST_CONTINUE;
1147 }
1148
1149 /*
1150  *  call-seq:
1151  *     hsh.each {| key, value | block } -> hsh
1152  *     hsh.each_pair {| key, value | block } -> hsh
1153  *
1154  *  Calls <i>block</i> once for each key in <i>hsh</i>, passing the key-value
1155  *  pair as parameters.
1156  *
1157  *     h = { "a" => 100, "b" => 200 }
1158  *     h.each {|key, value| puts "#{key} is #{value}" }
1159  *
1160  *  <em>produces:</em>
1161  *
1162  *     a is 100
1163  *     b is 200
1164  *
1165  */
1166
1167 static VALUE
1168 rb_hash_each_pair(VALUE hash)
1169 {
1170     RETURN_ENUMERATOR(hash, 0, 0);
1171     rb_hash_foreach(hash, each_pair_i, 0);
1172     return hash;
1173 }
1174
1175 static int
1176 to_a_i(VALUE key, VALUE value, VALUE ary)
1177 {
1178     if (key == Qundef) return ST_CONTINUE;
1179     rb_ary_push(ary, rb_assoc_new(key, value));
1180     return ST_CONTINUE;
1181 }
1182
1183 /*
1184  *  call-seq:
1185  *     hsh.to_a -> array
1186  *
1187  *  Converts <i>hsh</i> to a nested array of <code>[</code> <i>key,
1188  *  value</i> <code>]</code> arrays.
1189  *
1190  *     h = { "c" => 300, "a" => 100, "d" => 400, "c" => 300  }
1191  *     h.to_a   #=> [["c", 300], ["a", 100], ["d", 400]]
1192  */
1193
1194 static VALUE
1195 rb_hash_to_a(VALUE hash)
1196 {
1197     VALUE ary;
1198
1199     ary = rb_ary_new();
1200     rb_hash_foreach(hash, to_a_i, ary);
1201     OBJ_INFECT(ary, hash);
1202
1203     return ary;
1204 }
1205
1206 static int
1207 inspect_i(VALUE key, VALUE value, VALUE str)
1208 {
1209     VALUE str2;
1210
1211     if (key == Qundef) return ST_CONTINUE;
1212     if (RSTRING_LEN(str) > 1) {
1213         rb_str_cat2(str, ", ");
1214     }
1215     str2 = rb_inspect(key);
1216     rb_str_buf_append(str, str2);
1217     OBJ_INFECT(str, str2);
1218     rb_str_buf_cat2(str, "=>");
1219     str2 = rb_inspect(value);
1220     rb_str_buf_append(str, str2);
1221     OBJ_INFECT(str, str2);
1222
1223     return ST_CONTINUE;
1224 }
1225
1226 static VALUE
1227 inspect_hash(VALUE hash, VALUE dummy, int recur)
1228 {
1229     VALUE str;
1230
1231     if (recur) return rb_usascii_str_new2("{...}");
1232     str = rb_str_buf_new2("{");
1233     rb_hash_foreach(hash, inspect_i, str);
1234     rb_str_buf_cat2(str, "}");
1235     OBJ_INFECT(str, hash);
1236
1237     return str;
1238 }
1239
1240 /*
1241  * call-seq:
1242  *   hsh.to_s   => string
1243  *   hsh.inspect  => string
1244  *
1245  * Return the contents of this hash as a string.
1246  *
1247  *     h = { "c" => 300, "a" => 100, "d" => 400, "c" => 300  }
1248  *     h.to_s   #=> "{\"c\"=>300, \"a\"=>100, \"d\"=>400}"
1249  */
1250
1251 static VALUE
1252 rb_hash_inspect(VALUE hash)
1253 {
1254     if (RHASH_EMPTY_P(hash))
1255         return rb_usascii_str_new2("{}");
1256     return rb_exec_recursive(inspect_hash, hash, 0);
1257 }
1258
1259 /*
1260  * call-seq:
1261  *    hsh.to_hash   => hsh
1262  *
1263  * Returns <i>self</i>.
1264  */
1265
1266 static VALUE
1267 rb_hash_to_hash(VALUE hash)
1268 {
1269     return hash;
1270 }
1271
1272 static int
1273 keys_i(VALUE key, VALUE value, VALUE ary)
1274 {
1275     if (key == Qundef) return ST_CONTINUE;
1276     rb_ary_push(ary, key);
1277     return ST_CONTINUE;
1278 }
1279
1280 /*
1281  *  call-seq:
1282  *     hsh.keys    => array
1283  *
1284  *  Returns a new array populated with the keys from this hash. See also
1285  *  <code>Hash#values</code>.
1286  *
1287  *     h = { "a" => 100, "b" => 200, "c" => 300, "d" => 400 }
1288  *     h.keys   #=> ["a", "b", "c", "d"]
1289  *
1290  */
1291
1292 static VALUE
1293 rb_hash_keys(VALUE hash)
1294 {
1295     VALUE ary;
1296
1297     ary = rb_ary_new();
1298     rb_hash_foreach(hash, keys_i, ary);
1299
1300     return ary;
1301 }
1302
1303 static int
1304 values_i(VALUE key, VALUE value, VALUE ary)
1305 {
1306     if (key == Qundef) return ST_CONTINUE;
1307     rb_ary_push(ary, value);
1308     return ST_CONTINUE;
1309 }
1310
1311 /*
1312  *  call-seq:
1313  *     hsh.values    => array
1314  *
1315  *  Returns a new array populated with the values from <i>hsh</i>. See
1316  *  also <code>Hash#keys</code>.
1317  *
1318  *     h = { "a" => 100, "b" => 200, "c" => 300 }
1319  *     h.values   #=> [100, 200, 300]
1320  *
1321  */
1322
1323 static VALUE
1324 rb_hash_values(VALUE hash)
1325 {
1326     VALUE ary;
1327
1328     ary = rb_ary_new();
1329     rb_hash_foreach(hash, values_i, ary);
1330
1331     return ary;
1332 }
1333
1334 /*
1335  *  call-seq:
1336  *     hsh.has_key?(key)    => true or false
1337  *     hsh.include?(key)    => true or false
1338  *     hsh.key?(key)        => true or false
1339  *     hsh.member?(key)     => true or false
1340  *
1341  *  Returns <code>true</code> if the given key is present in <i>hsh</i>.
1342  *
1343  *     h = { "a" => 100, "b" => 200 }
1344  *     h.has_key?("a")   #=> true
1345  *     h.has_key?("z")   #=> false
1346  *
1347  */
1348
1349 static VALUE
1350 rb_hash_has_key(VALUE hash, VALUE key)
1351 {
1352     if (!RHASH(hash)->ntbl)
1353         return Qfalse;
1354     if (st_lookup(RHASH(hash)->ntbl, key, 0)) {
1355         return Qtrue;
1356     }
1357     return Qfalse;
1358 }
1359
1360 static int
1361 rb_hash_search_value(VALUE key, VALUE value, VALUE *data)
1362 {
1363     if (key == Qundef) return ST_CONTINUE;
1364     if (rb_equal(value, data[1])) {
1365         data[0] = Qtrue;
1366         return ST_STOP;
1367     }
1368     return ST_CONTINUE;
1369 }
1370
1371 /*
1372  *  call-seq:
1373  *     hsh.has_value?(value)    => true or false
1374  *     hsh.value?(value)        => true or false
1375  *
1376  *  Returns <code>true</code> if the given value is present for some key
1377  *  in <i>hsh</i>.
1378  *
1379  *     h = { "a" => 100, "b" => 200 }
1380  *     h.has_value?(100)   #=> true
1381  *     h.has_value?(999)   #=> false
1382  */
1383
1384 static VALUE
1385 rb_hash_has_value(VALUE hash, VALUE val)
1386 {
1387     VALUE data[2];
1388
1389     data[0] = Qfalse;
1390     data[1] = val;
1391     rb_hash_foreach(hash, rb_hash_search_value, (st_data_t)data);
1392     return data[0];
1393 }
1394
1395 struct equal_data {
1396     VALUE result;
1397     st_table *tbl;
1398     int eql;
1399 };
1400
1401 static int
1402 eql_i(VALUE key, VALUE val1, struct equal_data *data)
1403 {
1404     VALUE val2;
1405
1406     if (key == Qundef) return ST_CONTINUE;
1407     if (!st_lookup(data->tbl, key, &val2)) {
1408         data->result = Qfalse;
1409         return ST_STOP;
1410     }
1411     if (!(data->eql ? rb_eql(val1, val2) : rb_equal(val1, val2))) {
1412         data->result = Qfalse;
1413         return ST_STOP;
1414     }
1415     return ST_CONTINUE;
1416 }
1417
1418 static VALUE
1419 recursive_eql(VALUE hash, VALUE dt, int recur)
1420 {
1421     struct equal_data *data;
1422
1423     if (recur) return Qfalse;
1424     data = (struct equal_data*)dt;
1425     data->result = Qtrue;
1426     rb_hash_foreach(hash, eql_i, (st_data_t)data);
1427
1428     return data->result;
1429 }
1430
1431 static VALUE
1432 hash_equal(VALUE hash1, VALUE hash2, int eql)
1433 {
1434     struct equal_data data;
1435
1436     if (hash1 == hash2) return Qtrue;
1437     if (TYPE(hash2) != T_HASH) {
1438         if (!rb_respond_to(hash2, rb_intern("to_hash"))) {
1439             return Qfalse;
1440         }
1441         if (eql)
1442             return rb_eql(hash2, hash1);
1443         else
1444             return rb_equal(hash2, hash1);
1445     }
1446     if (RHASH_SIZE(hash1) != RHASH_SIZE(hash2))
1447         return Qfalse;
1448     if (!RHASH(hash1)->ntbl || !RHASH(hash2)->ntbl)
1449         return Qtrue;
1450     if (RHASH(hash1)->ntbl->type != RHASH(hash2)->ntbl->type)
1451         return Qfalse;
1452 #if 0
1453     if (!(rb_equal(RHASH(hash1)->ifnone, RHASH(hash2)->ifnone) &&
1454           FL_TEST(hash1, HASH_PROC_DEFAULT) == FL_TEST(hash2, HASH_PROC_DEFAULT)))
1455         return Qfalse;
1456 #endif
1457
1458     data.tbl = RHASH(hash2)->ntbl;
1459     data.eql = eql;
1460     return rb_exec_recursive(recursive_eql, hash1, (VALUE)&data);
1461 }
1462
1463 /*
1464  *  call-seq:
1465  *     hsh == other_hash    => true or false
1466  *
1467  *  Equality---Two hashes are equal if they each contain the same number
1468  *  of keys and if each key-value pair is equal to (according to
1469  *  <code>Object#==</code>) the corresponding elements in the other
1470  *  hash.
1471  *
1472  *     h1 = { "a" => 1, "c" => 2 }
1473  *     h2 = { 7 => 35, "c" => 2, "a" => 1 }
1474  *     h3 = { "a" => 1, "c" => 2, 7 => 35 }
1475  *     h4 = { "a" => 1, "d" => 2, "f" => 35 }
1476  *     h1 == h2   #=> false
1477  *     h2 == h3   #=> true
1478  *     h3 == h4   #=> false
1479  *
1480  */
1481
1482 static VALUE
1483 rb_hash_equal(VALUE hash1, VALUE hash2)
1484 {
1485     return hash_equal(hash1, hash2, Qfalse);
1486 }
1487
1488 /*
1489  *  call-seq:
1490  *     hash.eql?(other)  -> true or false
1491  *
1492  *  Returns <code>true</code> if <i>hash</i> and <i>other</i> are
1493  *  both hashes with the same content.
1494  */
1495
1496 static VALUE
1497 rb_hash_eql(VALUE hash1, VALUE hash2)
1498 {
1499     return hash_equal(hash1, hash2, Qtrue);
1500 }
1501
1502 static int
1503 hash_i(VALUE key, VALUE val, int *hval)
1504 {
1505     if (key == Qundef) return ST_CONTINUE;
1506     *hval ^= rb_hash(key);
1507     *hval ^= rb_hash(val);
1508     return ST_CONTINUE;
1509 }
1510
1511 static VALUE
1512 recursive_hash(VALUE hash, VALUE dummy, int recur)
1513 {
1514     int hval;
1515
1516     if (recur) {
1517         return LONG2FIX(0);
1518     }
1519     if (!RHASH(hash)->ntbl)
1520         return LONG2FIX(0);
1521     hval = RHASH(hash)->ntbl->num_entries;
1522     rb_hash_foreach(hash, hash_i, (st_data_t)&hval);
1523     return INT2FIX(hval);
1524 }
1525
1526 /*
1527  *  call-seq:
1528  *     array.hash   -> fixnum
1529  *
1530  *  Compute a hash-code for this array. Two arrays with the same content
1531  *  will have the same hash code (and will compare using <code>eql?</code>).
1532  */
1533
1534 static VALUE
1535 rb_hash_hash(VALUE hash)
1536 {
1537     return rb_exec_recursive(recursive_hash, hash, 0);
1538 }
1539
1540 static int
1541 rb_hash_invert_i(VALUE key, VALUE value, VALUE hash)
1542 {
1543     if (key == Qundef) return ST_CONTINUE;
1544     rb_hash_aset(hash, value, key);
1545     return ST_CONTINUE;
1546 }
1547
1548 /*
1549  *  call-seq:
1550  *     hsh.invert -> aHash
1551  *
1552  *  Returns a new hash created by using <i>hsh</i>'s values as keys, and
1553  *  the keys as values.
1554  *
1555  *     h = { "n" => 100, "m" => 100, "y" => 300, "d" => 200, "a" => 0 }
1556  *     h.invert   #=> {0=>"a", 100=>"m", 200=>"d", 300=>"y"}
1557  *
1558  */
1559
1560 static VALUE
1561 rb_hash_invert(VALUE hash)
1562 {
1563     VALUE h = rb_hash_new();
1564
1565     rb_hash_foreach(hash, rb_hash_invert_i, h);
1566     return h;
1567 }
1568
1569 static int
1570 rb_hash_update_i(VALUE key, VALUE value, VALUE hash)
1571 {
1572     if (key == Qundef) return ST_CONTINUE;
1573     rb_hash_aset(hash, key, value);
1574     return ST_CONTINUE;
1575 }
1576
1577 static int
1578 rb_hash_update_block_i(VALUE key, VALUE value, VALUE hash)
1579 {
1580     if (key == Qundef) return ST_CONTINUE;
1581     if (rb_hash_has_key(hash, key)) {
1582         value = rb_yield_values(3, key, rb_hash_aref(hash, key), value);
1583     }
1584     rb_hash_aset(hash, key, value);
1585     return ST_CONTINUE;
1586 }
1587
1588 /*
1589  *  call-seq:
1590  *     hsh.merge!(other_hash)                                 => hsh
1591  *     hsh.update(other_hash)                                 => hsh
1592  *     hsh.merge!(other_hash){|key, oldval, newval| block}    => hsh
1593  *     hsh.update(other_hash){|key, oldval, newval| block}    => hsh
1594  *
1595  *  Adds the contents of <i>other_hash</i> to <i>hsh</i>.  If no
1596  *  block is specified entries with duplicate keys are overwritten
1597  *  with the values from <i>other_hash</i>, otherwise the value
1598  *  of each duplicate key is determined by calling the block with
1599  *  the key, its value in <i>hsh</i> and its value in <i>other_hash</i>.
1600  *
1601  *     h1 = { "a" => 100, "b" => 200 }
1602  *     h2 = { "b" => 254, "c" => 300 }
1603  *     h1.merge!(h2)   #=> {"a"=>100, "b"=>254, "c"=>300}
1604  *
1605  *     h1 = { "a" => 100, "b" => 200 }
1606  *     h2 = { "b" => 254, "c" => 300 }
1607  *     h1.merge!(h2) { |key, v1, v2| v1 }
1608  *                     #=> {"a"=>100, "b"=>200, "c"=>300}
1609  */
1610
1611 static VALUE
1612 rb_hash_update(VALUE hash1, VALUE hash2)
1613 {
1614     hash2 = to_hash(hash2);
1615     if (rb_block_given_p()) {
1616         rb_hash_foreach(hash2, rb_hash_update_block_i, hash1);
1617     }
1618     else {
1619         rb_hash_foreach(hash2, rb_hash_update_i, hash1);
1620     }
1621     return hash1;
1622 }
1623
1624 /*
1625  *  call-seq:
1626  *     hsh.merge(other_hash)                              -> a_hash
1627  *     hsh.merge(other_hash){|key, oldval, newval| block} -> a_hash
1628  *
1629  *  Returns a new hash containing the contents of <i>other_hash</i> and
1630  *  the contents of <i>hsh</i>, overwriting entries in <i>hsh</i> with
1631  *  duplicate keys with those from <i>other_hash</i>.
1632  *
1633  *     h1 = { "a" => 100, "b" => 200 }
1634  *     h2 = { "b" => 254, "c" => 300 }
1635  *     h1.merge(h2)   #=> {"a"=>100, "b"=>254, "c"=>300}
1636  *     h1             #=> {"a"=>100, "b"=>200}
1637  *
1638  */
1639
1640 static VALUE
1641 rb_hash_merge(VALUE hash1, VALUE hash2)
1642 {
1643     return rb_hash_update(rb_obj_dup(hash1), hash2);
1644 }
1645
1646 static int
1647 assoc_i(VALUE key, VALUE val, VALUE *args)
1648 {
1649     if (key == Qundef) return ST_CONTINUE;
1650     if (RTEST(rb_equal(args[0], key))) {
1651         args[1] = rb_assoc_new(key, val);
1652         return ST_STOP;
1653     }
1654     return ST_CONTINUE;
1655 }
1656
1657 /*
1658  *  call-seq:
1659  *     hash.assoc(obj)   ->  an_array  or  nil
1660  *
1661  *  Searches through the hash comparing _obj_ with the key using <code>==</code>.
1662  *  Returns the key-value pair (two elements array) or +nil+
1663  *  if no match is found.  See <code>Array#assoc</code>.
1664  *
1665  *     h = {"colors"  => ["red", "blue", "green"],
1666  *          "letters" => ["a", "b", "c" ]}
1667  *     h.assoc("letters")  #=> ["letters", ["a", "b", "c"]]
1668  *     h.assoc("foo")      #=> nil
1669  */
1670
1671 VALUE
1672 rb_hash_assoc(VALUE hash, VALUE obj)
1673 {
1674     VALUE args[2];
1675
1676     args[0] = obj;
1677     args[1] = Qnil;
1678     rb_hash_foreach(hash, assoc_i, (st_data_t)args);
1679     return args[1];
1680 }
1681
1682 static int
1683 rassoc_i(VALUE key, VALUE val, VALUE *args)
1684 {
1685     if (key == Qundef) return ST_CONTINUE;
1686     if (RTEST(rb_equal(args[0], val))) {
1687         args[1] = rb_assoc_new(key, val);
1688         return ST_STOP;
1689     }
1690     return ST_CONTINUE;
1691 }
1692
1693 /*
1694  *  call-seq:
1695  *     hash.rassoc(key) -> an_array or nil
1696  *
1697  *  Searches through the hash comparing _obj_ with the value using <code>==</code>.
1698  *  Returns the first key-value pair (two elements array) that matches. See
1699  *  also <code>Array#rassoc</code>.
1700  *
1701  *     a = {1=> "one", 2 => "two", 3 => "three", "ii" => "two"}
1702  *     a.rassoc("two")    #=> [2, "two"]
1703  *     a.rassoc("four")   #=> nil
1704  */
1705
1706 VALUE
1707 rb_hash_rassoc(VALUE hash, VALUE obj)
1708 {
1709     VALUE args[2];
1710
1711     args[0] = obj;
1712     args[1] = Qnil;
1713     rb_hash_foreach(hash, rassoc_i, (st_data_t)args);
1714     return args[1];
1715 }
1716
1717 /*
1718  *  call-seq:
1719  *     hash.flatten -> an_array
1720  *     hash.flatten(level) -> an_array
1721  *
1722  *  Returns a new array that is a one-dimensional flattening of this
1723  *  hash. That is, for every key or value that is an array, extract
1724  *  its elements into the new array.  Unlike Array#flatten, this
1725  *  method does not flatten recursively by default.  If the optional
1726  *  <i>level</i> argument determines the level of recursion to flatten.
1727  *
1728  *     a =  {1=> "one", 2 => [2,"two"], 3 => "three"}
1729  *     a.flatten    # => [1, "one", 2, [2, "two"], 3, "three"]
1730  *     a.flatten(2) # => [1, "one", 2, 2, "two", 3, "three"]
1731  */
1732
1733 static VALUE
1734 rb_hash_flatten(int argc, VALUE *argv, VALUE hash)
1735 {
1736     VALUE ary, tmp;
1737
1738     ary = rb_hash_to_a(hash);
1739     if (argc == 0) {
1740         argc = 1;
1741         tmp = INT2FIX(1);
1742         argv = &tmp;
1743     }
1744     rb_funcall2(ary, rb_intern("flatten!"), argc, argv);
1745     return ary;
1746 }
1747
1748 /*
1749  *  call-seq:
1750  *     hsh.compare_by_identity => hsh
1751  *
1752  *  Makes <i>hsh</i> to compare its keys by their identity, i.e. it
1753  *  will consider exact same objects as same keys.
1754  *
1755  *     h1 = { "a" => 100, "b" => 200, :c => "c" }
1756  *     h1["a"]        #=> 100
1757  *     h1.compare_by_identity
1758  *     h1.compare_by_identity? #=> true
1759  *     h1["a"]        #=> nil  # different objects.
1760  *     h1[:c]         #=> "c"  # same symbols are all same.
1761  *
1762  */
1763
1764 static VALUE
1765 rb_hash_compare_by_id(VALUE hash)
1766 {
1767     rb_hash_modify(hash);
1768     RHASH(hash)->ntbl->type = &identhash;
1769     rb_hash_rehash(hash);
1770     return hash;
1771 }
1772
1773 /*
1774  *  call-seq:
1775  *     hsh.compare_by_identity? => true or false
1776  *
1777  *  Returns <code>true</code> if <i>hsh</i> will compare its keys by
1778  *  their identity.  Also see <code>Hash#compare_by_identity</code>.
1779  *
1780  */
1781
1782 static VALUE
1783 rb_hash_compare_by_id_p(VALUE hash)
1784 {
1785     if (!RHASH(hash)->ntbl)
1786         return Qfalse;
1787     if (RHASH(hash)->ntbl->type == &identhash) {
1788         return Qtrue;
1789     }
1790     return Qfalse;
1791 }
1792
1793 static int path_tainted = -1;
1794
1795 static char **origenviron;
1796 #ifdef _WIN32
1797 #define GET_ENVIRON(e) (e = rb_w32_get_environ())
1798 #define FREE_ENVIRON(e) rb_w32_free_environ(e)
1799 static char **my_environ;
1800 #undef environ
1801 #define environ my_environ
1802 #elif defined(__APPLE__)
1803 #undef environ
1804 #define environ (*_NSGetEnviron())
1805 #define GET_ENVIRON(e) (e)
1806 #define FREE_ENVIRON(e)
1807 #else
1808 extern char **environ;
1809 #define GET_ENVIRON(e) (e)
1810 #define FREE_ENVIRON(e)
1811 #endif
1812
1813 static VALUE
1814 env_str_new(const char *ptr, long len)
1815 {
1816     VALUE str = rb_tainted_str_new(ptr, len);
1817
1818     rb_obj_freeze(str);
1819     return str;
1820 }
1821
1822 static VALUE
1823 env_str_new2(const char *ptr)
1824 {
1825     if (!ptr) return Qnil;
1826     return env_str_new(ptr, strlen(ptr));
1827 }
1828
1829 static VALUE
1830 env_delete(VALUE obj, VALUE name)
1831 {
1832     char *nam, *val;
1833
1834     rb_secure(4);
1835     SafeStringValue(name);
1836     nam = RSTRING_PTR(name);
1837     if (strlen(nam) != RSTRING_LEN(name)) {
1838         rb_raise(rb_eArgError, "bad environment variable name");
1839     }
1840     val = getenv(nam);
1841     if (val) {
1842         VALUE value = env_str_new2(val);
1843
1844         ruby_setenv(nam, 0);
1845 #ifdef ENV_IGNORECASE
1846         if (STRCASECMP(nam, PATH_ENV) == 0)
1847 #else
1848         if (strcmp(nam, PATH_ENV) == 0)
1849 #endif
1850         {
1851             path_tainted = 0;
1852         }
1853         return value;
1854     }
1855     return Qnil;
1856 }
1857
1858 static VALUE
1859 env_delete_m(VALUE obj, VALUE name)
1860 {
1861     VALUE val;
1862
1863     val = env_delete(obj, name);
1864     if (NIL_P(val) && rb_block_given_p()) rb_yield(name);
1865     return val;
1866 }
1867
1868 static VALUE
1869 rb_f_getenv(VALUE obj, VALUE name)
1870 {
1871     char *nam, *env;
1872
1873     rb_secure(4);
1874     SafeStringValue(name);
1875     nam = RSTRING_PTR(name);
1876     if (strlen(nam) != RSTRING_LEN(name)) {
1877         rb_raise(rb_eArgError, "bad environment variable name");
1878     }
1879     env = getenv(nam);
1880     if (env) {
1881 #ifdef ENV_IGNORECASE
1882         if (STRCASECMP(nam, PATH_ENV) == 0 && !rb_env_path_tainted())
1883 #else
1884         if (strcmp(nam, PATH_ENV) == 0 && !rb_env_path_tainted())
1885 #endif
1886         {
1887             VALUE str = rb_str_new2(env);
1888
1889             rb_obj_freeze(str);
1890             return str;
1891         }
1892         return env_str_new2(env);
1893     }
1894     return Qnil;
1895 }
1896
1897 static VALUE
1898 env_fetch(int argc, VALUE *argv)
1899 {
1900     VALUE key, if_none;
1901     long block_given;
1902     char *nam, *env;
1903
1904     rb_secure(4);
1905     rb_scan_args(argc, argv, "11", &key, &if_none);
1906     block_given = rb_block_given_p();
1907     if (block_given && argc == 2) {
1908         rb_warn("block supersedes default value argument");
1909     }
1910     SafeStringValue(key);
1911     nam = RSTRING_PTR(key);
1912     if (strlen(nam) != RSTRING_LEN(key)) {
1913         rb_raise(rb_eArgError, "bad environment variable name");
1914     }
1915     env = getenv(nam);
1916     if (!env) {
1917         if (block_given) return rb_yield(key);
1918         if (argc == 1) {
1919             rb_raise(rb_eKeyError, "key not found");
1920         }
1921         return if_none;
1922     }
1923 #ifdef ENV_IGNORECASE
1924     if (STRCASECMP(nam, PATH_ENV) == 0 && !rb_env_path_tainted())
1925 #else
1926     if (strcmp(nam, PATH_ENV) == 0 && !rb_env_path_tainted())
1927 #endif
1928         return rb_str_new2(env);
1929     return env_str_new2(env);
1930 }
1931
1932 static void
1933 path_tainted_p(char *path)
1934 {
1935     path_tainted = rb_path_check(path)?0:1;
1936 }
1937
1938 int
1939 rb_env_path_tainted(void)
1940 {
1941     if (path_tainted < 0) {
1942         path_tainted_p(getenv(PATH_ENV));
1943     }
1944     return path_tainted;
1945 }
1946
1947 #if !defined(_WIN32) && !(defined(HAVE_SETENV) && defined(HAVE_UNSETENV))
1948 static int
1949 envix(const char *nam)
1950 {
1951     register int i, len = strlen(nam);
1952     char **env;
1953
1954     env = GET_ENVIRON(environ);
1955     for (i = 0; env[i]; i++) {
1956         if (
1957 #ifdef ENV_IGNORECASE
1958             STRNCASECMP(env[i],nam,len) == 0
1959 #else
1960             memcmp(env[i],nam,len) == 0
1961 #endif
1962             && env[i][len] == '=')
1963             break;                      /* memcmp must come first to avoid */
1964     }                                   /* potential SEGV's */
1965     FREE_ENVIRON(environ);
1966     return i;
1967 }
1968 #endif
1969
1970 void
1971 ruby_setenv(const char *name, const char *value)
1972 {
1973 #if defined(_WIN32)
1974     /* The sane way to deal with the environment.
1975      * Has these advantages over putenv() & co.:
1976      *  * enables us to store a truly empty value in the
1977      *    environment (like in UNIX).
1978      *  * we don't have to deal with RTL globals, bugs and leaks.
1979      *  * Much faster.
1980      * Why you may want to enable USE_WIN32_RTL_ENV:
1981      *  * environ[] and RTL functions will not reflect changes,
1982      *    which might be an issue if extensions want to access
1983      *    the env. via RTL.  This cuts both ways, since RTL will
1984      *    not see changes made by extensions that call the Win32
1985      *    functions directly, either.
1986      * GSAR 97-06-07
1987      *
1988      * REMARK: USE_WIN32_RTL_ENV is already obsoleted since we don't use
1989      *         RTL's environ global variable directly yet.
1990      */
1991     SetEnvironmentVariable(name,value);
1992 #elif defined(HAVE_SETENV) && defined(HAVE_UNSETENV)
1993 #undef setenv
1994 #undef unsetenv
1995     if (value)
1996         setenv(name,value,1);
1997     else
1998         unsetenv(name);
1999 #else  /* WIN32 */
2000     size_t len;
2001     int i=envix(name);                  /* where does it go? */
2002
2003     if (environ == origenviron) {       /* need we copy environment? */
2004         int j;
2005         int max;
2006         char **tmpenv;
2007
2008         for (max = i; environ[max]; max++) ;
2009         tmpenv = ALLOC_N(char*, max+2);
2010         for (j=0; j<max; j++)           /* copy environment */
2011             tmpenv[j] = strdup(environ[j]);
2012         tmpenv[max] = 0;
2013         environ = tmpenv;               /* tell exec where it is now */
2014     }
2015     if (environ[i]) {
2016         char **envp = origenviron;
2017         while (*envp && *envp != environ[i]) envp++;
2018         if (!*envp)
2019             xfree(environ[i]);
2020         if (!value) {
2021             while (environ[i]) {
2022                 environ[i] = environ[i+1];
2023                 i++;
2024             }
2025             return;
2026         }
2027     }
2028     else {                      /* does not exist yet */
2029         if (!value) return;
2030         REALLOC_N(environ, char*, i+2); /* just expand it a bit */
2031         environ[i+1] = 0;       /* make sure it's null terminated */
2032     }
2033     len = strlen(name) + strlen(value) + 2;
2034     environ[i] = ALLOC_N(char, len);
2035 #ifndef MSDOS
2036     snprintf(environ[i],len,"%s=%s",name,value); /* all that work just for this */
2037 #else
2038     /* MS-DOS requires environment variable names to be in uppercase */
2039     /* [Tom Dinger, 27 August 1990: Well, it doesn't _require_ it, but
2040      * some utilities and applications may break because they only look
2041      * for upper case strings. (Fixed strupr() bug here.)]
2042      */
2043     strcpy(environ[i],name); strupr(environ[i]);
2044     sprintf(environ[i] + strlen(name),"=%s", value);
2045 #endif /* MSDOS */
2046
2047 #endif /* WIN32 */
2048 }
2049
2050 void
2051 ruby_unsetenv(const char *name)
2052 {
2053     ruby_setenv(name, 0);
2054 }
2055
2056 static VALUE
2057 env_aset(VALUE obj, VALUE nm, VALUE val)
2058 {
2059     char *name, *value;
2060
2061     if (rb_safe_level() >= 4) {
2062         rb_raise(rb_eSecurityError, "can't change environment variable");
2063     }
2064
2065     if (NIL_P(val)) {
2066         rb_raise(rb_eTypeError, "cannot assign nil; use Hash#delete instead");
2067     }
2068     StringValue(nm);
2069     StringValue(val);
2070     name = RSTRING_PTR(nm);
2071     value = RSTRING_PTR(val);
2072     if (strlen(name) != RSTRING_LEN(nm))
2073         rb_raise(rb_eArgError, "bad environment variable name");
2074     if (strlen(value) != RSTRING_LEN(val))
2075         rb_raise(rb_eArgError, "bad environment variable value");
2076
2077     ruby_setenv(name, value);
2078 #ifdef ENV_IGNORECASE
2079     if (STRCASECMP(name, PATH_ENV) == 0) {
2080 #else
2081     if (strcmp(name, PATH_ENV) == 0) {
2082 #endif
2083         if (OBJ_TAINTED(val)) {
2084             /* already tainted, no check */
2085             path_tainted = 1;
2086             return val;
2087         }
2088         else {
2089             path_tainted_p(value);
2090         }
2091     }
2092     return val;
2093 }
2094
2095 static VALUE
2096 env_keys(void)
2097 {
2098     char **env;
2099     VALUE ary;
2100
2101     rb_secure(4);
2102     ary = rb_ary_new();
2103     env = GET_ENVIRON(environ);
2104     while (*env) {
2105         char *s = strchr(*env, '=');
2106         if (s) {
2107             rb_ary_push(ary, env_str_new(*env, s-*env));
2108         }
2109         env++;
2110     }
2111     FREE_ENVIRON(environ);
2112     return ary;
2113 }
2114
2115 static VALUE
2116 env_each_key(VALUE ehash)
2117 {
2118     VALUE keys;
2119     long i;
2120
2121     RETURN_ENUMERATOR(ehash, 0, 0);
2122     keys = env_keys();  /* rb_secure(4); */
2123     for (i=0; i<RARRAY_LEN(keys); i++) {
2124         rb_yield(RARRAY_PTR(keys)[i]);
2125     }
2126     return ehash;
2127 }
2128
2129 static VALUE
2130 env_values(void)
2131 {
2132     VALUE ary;
2133     char **env;
2134
2135     rb_secure(4);
2136     ary = rb_ary_new();
2137     env = GET_ENVIRON(environ);
2138     while (*env) {
2139         char *s = strchr(*env, '=');
2140         if (s) {
2141             rb_ary_push(ary, env_str_new2(s+1));
2142         }
2143         env++;
2144     }
2145     FREE_ENVIRON(environ);
2146     return ary;
2147 }
2148
2149 static VALUE
2150 env_each_value(VALUE ehash)
2151 {
2152     VALUE values;
2153     long i;
2154
2155     RETURN_ENUMERATOR(ehash, 0, 0);
2156     values = env_values();      /* rb_secure(4); */
2157     for (i=0; i<RARRAY_LEN(values); i++) {
2158         rb_yield(RARRAY_PTR(values)[i]);
2159     }
2160     return ehash;
2161 }
2162
2163 static VALUE
2164 env_each_pair(VALUE ehash)
2165 {
2166     char **env;
2167     VALUE ary;
2168     long i;
2169
2170     RETURN_ENUMERATOR(ehash, 0, 0);
2171
2172     rb_secure(4);
2173     ary = rb_ary_new();
2174     env = GET_ENVIRON(environ);
2175     while (*env) {
2176         char *s = strchr(*env, '=');
2177         if (s) {
2178             rb_ary_push(ary, env_str_new(*env, s-*env));
2179             rb_ary_push(ary, env_str_new2(s+1));
2180         }
2181         env++;
2182     }
2183     FREE_ENVIRON(environ);
2184
2185     for (i=0; i<RARRAY_LEN(ary); i+=2) {
2186         rb_yield(rb_assoc_new(RARRAY_PTR(ary)[i], RARRAY_PTR(ary)[i+1]));
2187     }
2188     return ehash;
2189 }
2190
2191 static VALUE
2192 env_reject_bang(VALUE ehash)
2193 {
2194     volatile VALUE keys;
2195     long i;
2196     int del = 0;
2197
2198     RETURN_ENUMERATOR(ehash, 0, 0);
2199     keys = env_keys();  /* rb_secure(4); */
2200     for (i=0; i<RARRAY_LEN(keys); i++) {
2201         VALUE val = rb_f_getenv(Qnil, RARRAY_PTR(keys)[i]);
2202         if (!NIL_P(val)) {
2203             if (RTEST(rb_yield_values(2, RARRAY_PTR(keys)[i], val))) {
2204                 FL_UNSET(RARRAY_PTR(keys)[i], FL_TAINT);
2205                 env_delete(Qnil, RARRAY_PTR(keys)[i]);
2206                 del++;
2207             }
2208         }
2209     }
2210     if (del == 0) return Qnil;
2211     return envtbl;
2212 }
2213
2214 static VALUE
2215 env_delete_if(VALUE ehash)
2216 {
2217     RETURN_ENUMERATOR(ehash, 0, 0);
2218     env_reject_bang(ehash);
2219     return envtbl;
2220 }
2221
2222 static VALUE
2223 env_values_at(int argc, VALUE *argv)
2224 {
2225     VALUE result;
2226     long i;
2227
2228     rb_secure(4);
2229     result = rb_ary_new();
2230     for (i=0; i<argc; i++) {
2231         rb_ary_push(result, rb_f_getenv(Qnil, argv[i]));
2232     }
2233     return result;
2234 }
2235
2236 static VALUE
2237 env_select(VALUE ehash)
2238 {
2239     VALUE result;
2240     char **env;
2241
2242     RETURN_ENUMERATOR(ehash, 0, 0);
2243     rb_secure(4);
2244     result = rb_hash_new();
2245     env = GET_ENVIRON(environ);
2246     while (*env) {
2247         char *s = strchr(*env, '=');
2248         if (s) {
2249             VALUE k = env_str_new(*env, s-*env);
2250             VALUE v = env_str_new2(s+1);
2251             if (RTEST(rb_yield_values(2, k, v))) {
2252                 rb_hash_aset(result, k, v);
2253             }
2254         }
2255         env++;
2256     }
2257     FREE_ENVIRON(environ);
2258
2259     return result;
2260 }
2261
2262 VALUE
2263 rb_env_clear(void)
2264 {
2265     volatile VALUE keys;
2266     long i;
2267
2268     keys = env_keys();  /* rb_secure(4); */
2269     for (i=0; i<RARRAY_LEN(keys); i++) {
2270         VALUE val = rb_f_getenv(Qnil, RARRAY_PTR(keys)[i]);
2271         if (!NIL_P(val)) {
2272             env_delete(Qnil, RARRAY_PTR(keys)[i]);
2273         }
2274     }
2275     return envtbl;
2276 }
2277
2278 static VALUE
2279 env_to_s(void)
2280 {
2281     return rb_usascii_str_new2("ENV");
2282 }
2283
2284 static VALUE
2285 env_inspect(void)
2286 {
2287     char **env;
2288     VALUE str, i;
2289
2290     rb_secure(4);
2291     str = rb_str_buf_new2("{");
2292     env = GET_ENVIRON(environ);
2293     while (*env) {
2294         char *s = strchr(*env, '=');
2295
2296         if (env != environ) {
2297             rb_str_buf_cat2(str, ", ");
2298         }
2299         if (s) {
2300             rb_str_buf_cat2(str, "\"");
2301             rb_str_buf_cat(str, *env, s-*env);
2302             rb_str_buf_cat2(str, "\"=>");
2303             i = rb_inspect(rb_str_new2(s+1));
2304             rb_str_buf_append(str, i);
2305         }
2306         env++;
2307     }
2308     FREE_ENVIRON(environ);
2309     rb_str_buf_cat2(str, "}");
2310     OBJ_TAINT(str);
2311
2312     return str;
2313 }
2314
2315 static VALUE
2316 env_to_a(void)
2317 {
2318     char **env;
2319     VALUE ary;
2320
2321     rb_secure(4);
2322     ary = rb_ary_new();
2323     env = GET_ENVIRON(environ);
2324     while (*env) {
2325         char *s = strchr(*env, '=');
2326         if (s) {
2327             rb_ary_push(ary, rb_assoc_new(env_str_new(*env, s-*env),
2328                                           env_str_new2(s+1)));
2329         }
2330         env++;
2331     }
2332     FREE_ENVIRON(environ);
2333     return ary;
2334 }
2335
2336 static VALUE
2337 env_none(void)
2338 {
2339     return Qnil;
2340 }
2341
2342 static VALUE
2343 env_size(void)
2344 {
2345     int i;
2346     char **env;
2347
2348     rb_secure(4);
2349     env = GET_ENVIRON(environ);
2350     for(i=0; env[i]; i++)
2351         ;
2352     FREE_ENVIRON(environ);
2353     return INT2FIX(i);
2354 }
2355
2356 static VALUE
2357 env_empty_p(void)
2358 {
2359     char **env;
2360
2361     rb_secure(4);
2362     env = GET_ENVIRON(environ);
2363     if (env[0] == 0) {
2364         FREE_ENVIRON(environ);
2365         return Qtrue;
2366     }
2367     FREE_ENVIRON(environ);
2368     return Qfalse;
2369 }
2370
2371 static VALUE
2372 env_has_key(VALUE env, VALUE key)
2373 {
2374     char *s;
2375
2376     rb_secure(4);
2377     s = StringValuePtr(key);
2378     if (strlen(s) != RSTRING_LEN(key))
2379         rb_raise(rb_eArgError, "bad environment variable name");
2380     if (getenv(s)) return Qtrue;
2381     return Qfalse;
2382 }
2383
2384 static VALUE
2385 env_assoc(VALUE env, VALUE key)
2386 {
2387     char *s, *e;
2388
2389     rb_secure(4);
2390     s = StringValuePtr(key);
2391     if (strlen(s) != RSTRING_LEN(key))
2392         rb_raise(rb_eArgError, "bad environment variable name");
2393     e = getenv(s);
2394     if (e) return rb_assoc_new(key, rb_tainted_str_new2(e));
2395     return Qnil;
2396 }
2397
2398 static VALUE
2399 env_has_value(VALUE dmy, VALUE obj)
2400 {
2401     char **env;
2402
2403     rb_secure(4);
2404     obj = rb_check_string_type(obj);
2405     if (NIL_P(obj)) return Qnil;
2406     env = GET_ENVIRON(environ);
2407     while (*env) {
2408         char *s = strchr(*env, '=');
2409         if (s++) {
2410             long len = strlen(s);
2411             if (RSTRING_LEN(obj) == len && strncmp(s, RSTRING_PTR(obj), len) == 0) {
2412                 FREE_ENVIRON(environ);
2413                 return Qtrue;
2414             }
2415         }
2416         env++;
2417     }
2418     FREE_ENVIRON(environ);
2419     return Qfalse;
2420 }
2421
2422 static VALUE
2423 env_rassoc(VALUE dmy, VALUE obj)
2424 {
2425     char **env;
2426
2427     rb_secure(4);
2428     obj = rb_check_string_type(obj);
2429     if (NIL_P(obj)) return Qnil;
2430     env = GET_ENVIRON(environ);
2431     while (*env) {
2432         char *s = strchr(*env, '=');
2433         if (s++) {
2434             long len = strlen(s);
2435             if (RSTRING_LEN(obj) == len && strncmp(s, RSTRING_PTR(obj), len) == 0) {
2436                 VALUE result = rb_assoc_new(rb_tainted_str_new(*env, s-*env-1), obj);
2437                 FREE_ENVIRON(environ);
2438                 return result;
2439             }
2440         }
2441         env++;
2442     }
2443     FREE_ENVIRON(environ);
2444     return Qnil;
2445 }
2446
2447 static VALUE
2448 env_key(VALUE dmy, VALUE value)
2449 {
2450     char **env;
2451     VALUE str;
2452
2453     rb_secure(4);
2454     StringValue(value);
2455     env = GET_ENVIRON(environ);
2456     while (*env) {
2457         char *s = strchr(*env, '=');
2458         if (s++) {
2459             long len = strlen(s);
2460             if (RSTRING_LEN(value) == len && strncmp(s, RSTRING_PTR(value), len) == 0) {
2461                 str = env_str_new(*env, s-*env-1);
2462                 FREE_ENVIRON(environ);
2463                 return str;
2464             }
2465         }
2466         env++;
2467     }
2468     FREE_ENVIRON(environ);
2469     return Qnil;
2470 }
2471
2472 static VALUE
2473 env_index(VALUE dmy, VALUE value)
2474 {
2475     rb_warn("ENV.index is deprecated; use ENV.key");
2476     return env_key(dmy, value);
2477 }
2478
2479 static VALUE
2480 env_to_hash(void)
2481 {
2482     char **env;
2483     VALUE hash;
2484
2485     rb_secure(4);
2486     hash = rb_hash_new();
2487     env = GET_ENVIRON(environ);
2488     while (*env) {
2489         char *s = strchr(*env, '=');
2490         if (s) {
2491             rb_hash_aset(hash, env_str_new(*env, s-*env),
2492                                env_str_new2(s+1));
2493         }
2494         env++;
2495     }
2496     FREE_ENVIRON(environ);
2497     return hash;
2498 }
2499
2500 static VALUE
2501 env_reject(void)
2502 {
2503     return rb_hash_delete_if(env_to_hash());
2504 }
2505
2506 static VALUE
2507 env_shift(void)
2508 {
2509     char **env;
2510
2511     rb_secure(4);
2512     env = GET_ENVIRON(environ);
2513     if (*env) {
2514         char *s = strchr(*env, '=');
2515         if (s) {
2516             VALUE key = env_str_new(*env, s-*env);
2517             VALUE val = env_str_new2(getenv(RSTRING_PTR(key)));
2518             env_delete(Qnil, key);
2519             return rb_assoc_new(key, val);
2520         }
2521     }
2522     FREE_ENVIRON(environ);
2523     return Qnil;
2524 }
2525
2526 static VALUE
2527 env_invert(void)
2528 {
2529     return rb_hash_invert(env_to_hash());
2530 }
2531
2532 static int
2533 env_replace_i(VALUE key, VALUE val, VALUE keys)
2534 {
2535     if (key != Qundef) {
2536         env_aset(Qnil, key, val);
2537         if (rb_ary_includes(keys, key)) {
2538             rb_ary_delete(keys, key);
2539         }
2540     }
2541     return ST_CONTINUE;
2542 }
2543
2544 static VALUE
2545 env_replace(VALUE env, VALUE hash)
2546 {
2547     volatile VALUE keys;
2548     long i;
2549
2550     keys = env_keys();  /* rb_secure(4); */
2551     if (env == hash) return env;
2552     hash = to_hash(hash);
2553     rb_hash_foreach(hash, env_replace_i, keys);
2554
2555     for (i=0; i<RARRAY_LEN(keys); i++) {
2556         env_delete(env, RARRAY_PTR(keys)[i]);
2557     }
2558     return env;
2559 }
2560
2561 static int
2562 env_update_i(VALUE key, VALUE val)
2563 {
2564     if (key != Qundef) {
2565         if (rb_block_given_p()) {
2566             val = rb_yield_values(3, key, rb_f_getenv(Qnil, key), val);
2567         }
2568         env_aset(Qnil, key, val);
2569     }
2570     return ST_CONTINUE;
2571 }
2572
2573 static VALUE
2574 env_update(VALUE env, VALUE hash)
2575 {
2576     rb_secure(4);
2577     if (env == hash) return env;
2578     hash = to_hash(hash);
2579     rb_hash_foreach(hash, env_update_i, 0);
2580     return env;
2581 }
2582
2583 /*
2584  *  A <code>Hash</code> is a collection of key-value pairs. It is
2585  *  similar to an <code>Array</code>, except that indexing is done via
2586  *  arbitrary keys of any object type, not an integer index. The order
2587  *  in which you traverse a hash by either key or value may seem
2588  *  arbitrary, and will generally not be in the insertion order.
2589  *
2590  *  Hashes have a <em>default value</em> that is returned when accessing
2591  *  keys that do not exist in the hash. By default, that value is
2592  *  <code>nil</code>.
2593  *
2594  */
2595
2596 void
2597 Init_Hash(void)
2598 {
2599 #undef rb_intern
2600 #define rb_intern(str) rb_intern_const(str)
2601
2602     id_hash = rb_intern("hash");
2603     id_yield = rb_intern("yield");
2604     id_default = rb_intern("default");
2605
2606     rb_cHash = rb_define_class("Hash", rb_cObject);
2607
2608     rb_include_module(rb_cHash, rb_mEnumerable);
2609
2610     rb_define_alloc_func(rb_cHash, hash_alloc);
2611     rb_define_singleton_method(rb_cHash, "[]", rb_hash_s_create, -1);
2612     rb_define_singleton_method(rb_cHash, "try_convert", rb_hash_s_try_convert, 1);
2613     rb_define_method(rb_cHash,"initialize", rb_hash_initialize, -1);
2614     rb_define_method(rb_cHash,"initialize_copy", rb_hash_replace, 1);
2615     rb_define_method(rb_cHash,"rehash", rb_hash_rehash, 0);
2616
2617     rb_define_method(rb_cHash,"to_hash", rb_hash_to_hash, 0);
2618     rb_define_method(rb_cHash,"to_a", rb_hash_to_a, 0);
2619     rb_define_method(rb_cHash,"to_s", rb_hash_inspect, 0);
2620     rb_define_method(rb_cHash,"inspect", rb_hash_inspect, 0);
2621
2622     rb_define_method(rb_cHash,"==", rb_hash_equal, 1);
2623     rb_define_method(rb_cHash,"[]", rb_hash_aref, 1);
2624     rb_define_method(rb_cHash,"hash", rb_hash_hash, 0);
2625     rb_define_method(rb_cHash,"eql?", rb_hash_eql, 1);
2626     rb_define_method(rb_cHash,"fetch", rb_hash_fetch, -1);
2627     rb_define_method(rb_cHash,"[]=", rb_hash_aset, 2);
2628     rb_define_method(rb_cHash,"store", rb_hash_aset, 2);
2629     rb_define_method(rb_cHash,"default", rb_hash_default, -1);
2630     rb_define_method(rb_cHash,"default=", rb_hash_set_default, 1);
2631     rb_define_method(rb_cHash,"default_proc", rb_hash_default_proc, 0);
2632     rb_define_method(rb_cHash,"default_proc=", rb_hash_set_default_proc, 1);
2633     rb_define_method(rb_cHash,"key", rb_hash_key, 1);
2634     rb_define_method(rb_cHash,"index", rb_hash_index, 1);
2635     rb_define_method(rb_cHash,"size", rb_hash_size, 0);
2636     rb_define_method(rb_cHash,"length", rb_hash_size, 0);
2637     rb_define_method(rb_cHash,"empty?", rb_hash_empty_p, 0);
2638
2639     rb_define_method(rb_cHash,"each_value", rb_hash_each_value, 0);
2640     rb_define_method(rb_cHash,"each_key", rb_hash_each_key, 0);
2641     rb_define_method(rb_cHash,"each_pair", rb_hash_each_pair, 0);
2642     rb_define_method(rb_cHash,"each", rb_hash_each_pair, 0);
2643
2644     rb_define_method(rb_cHash,"keys", rb_hash_keys, 0);
2645     rb_define_method(rb_cHash,"values", rb_hash_values, 0);
2646     rb_define_method(rb_cHash,"values_at", rb_hash_values_at, -1);
2647
2648     rb_define_method(rb_cHash,"shift", rb_hash_shift, 0);
2649     rb_define_method(rb_cHash,"delete", rb_hash_delete, 1);
2650     rb_define_method(rb_cHash,"delete_if", rb_hash_delete_if, 0);
2651     rb_define_method(rb_cHash,"select", rb_hash_select, 0);
2652     rb_define_method(rb_cHash,"reject", rb_hash_reject, 0);
2653     rb_define_method(rb_cHash,"reject!", rb_hash_reject_bang, 0);
2654     rb_define_method(rb_cHash,"clear", rb_hash_clear, 0);
2655     rb_define_method(rb_cHash,"invert", rb_hash_invert, 0);
2656     rb_define_method(rb_cHash,"update", rb_hash_update, 1);
2657     rb_define_method(rb_cHash,"replace", rb_hash_replace, 1);
2658     rb_define_method(rb_cHash,"merge!", rb_hash_update, 1);
2659     rb_define_method(rb_cHash,"merge", rb_hash_merge, 1);
2660     rb_define_method(rb_cHash, "assoc", rb_hash_assoc, 1);
2661     rb_define_method(rb_cHash, "rassoc", rb_hash_rassoc, 1);
2662     rb_define_method(rb_cHash, "flatten", rb_hash_flatten, -1);
2663
2664     rb_define_method(rb_cHash,"include?", rb_hash_has_key, 1);
2665     rb_define_method(rb_cHash,"member?", rb_hash_has_key, 1);
2666     rb_define_method(rb_cHash,"has_key?", rb_hash_has_key, 1);
2667     rb_define_method(rb_cHash,"has_value?", rb_hash_has_value, 1);
2668     rb_define_method(rb_cHash,"key?", rb_hash_has_key, 1);
2669     rb_define_method(rb_cHash,"value?", rb_hash_has_value, 1);
2670
2671     rb_define_method(rb_cHash,"compare_by_identity", rb_hash_compare_by_id, 0);
2672     rb_define_method(rb_cHash,"compare_by_identity?", rb_hash_compare_by_id_p, 0);
2673
2674 #ifndef __MACOS__ /* environment variables nothing on MacOS. */
2675     origenviron = environ;
2676     envtbl = rb_obj_alloc(rb_cObject);
2677     rb_extend_object(envtbl, rb_mEnumerable);
2678
2679     rb_define_singleton_method(envtbl,"[]", rb_f_getenv, 1);
2680     rb_define_singleton_method(envtbl,"fetch", env_fetch, -1);
2681     rb_define_singleton_method(envtbl,"[]=", env_aset, 2);
2682     rb_define_singleton_method(envtbl,"store", env_aset, 2);
2683     rb_define_singleton_method(envtbl,"each", env_each_pair, 0);
2684     rb_define_singleton_method(envtbl,"each_pair", env_each_pair, 0);
2685     rb_define_singleton_method(envtbl,"each_key", env_each_key, 0);
2686     rb_define_singleton_method(envtbl,"each_value", env_each_value, 0);
2687     rb_define_singleton_method(envtbl,"delete", env_delete_m, 1);
2688     rb_define_singleton_method(envtbl,"delete_if", env_delete_if, 0);
2689     rb_define_singleton_method(envtbl,"clear", rb_env_clear, 0);
2690     rb_define_singleton_method(envtbl,"reject", env_reject, 0);
2691     rb_define_singleton_method(envtbl,"reject!", env_reject_bang, 0);
2692     rb_define_singleton_method(envtbl,"select", env_select, 0);
2693     rb_define_singleton_method(envtbl,"shift", env_shift, 0);
2694     rb_define_singleton_method(envtbl,"invert", env_invert, 0);
2695     rb_define_singleton_method(envtbl,"replace", env_replace, 1);
2696     rb_define_singleton_method(envtbl,"update", env_update, 1);
2697     rb_define_singleton_method(envtbl,"inspect", env_inspect, 0);
2698     rb_define_singleton_method(envtbl,"rehash", env_none, 0);
2699     rb_define_singleton_method(envtbl,"to_a", env_to_a, 0);
2700     rb_define_singleton_method(envtbl,"to_s", env_to_s, 0);
2701     rb_define_singleton_method(envtbl,"key", env_key, 1);
2702     rb_define_singleton_method(envtbl,"index", env_index, 1);
2703     rb_define_singleton_method(envtbl,"size", env_size, 0);
2704     rb_define_singleton_method(envtbl,"length", env_size, 0);
2705     rb_define_singleton_method(envtbl,"empty?", env_empty_p, 0);
2706     rb_define_singleton_method(envtbl,"keys", env_keys, 0);
2707     rb_define_singleton_method(envtbl,"values", env_values, 0);
2708     rb_define_singleton_method(envtbl,"values_at", env_values_at, -1);
2709     rb_define_singleton_method(envtbl,"include?", env_has_key, 1);
2710     rb_define_singleton_method(envtbl,"member?", env_has_key, 1);
2711     rb_define_singleton_method(envtbl,"has_key?", env_has_key, 1);
2712     rb_define_singleton_method(envtbl,"has_value?", env_has_value, 1);
2713     rb_define_singleton_method(envtbl,"key?", env_has_key, 1);
2714     rb_define_singleton_method(envtbl,"value?", env_has_value, 1);
2715     rb_define_singleton_method(envtbl,"to_hash", env_to_hash, 0);
2716     rb_define_singleton_method(envtbl,"assoc", env_assoc, 1);
2717     rb_define_singleton_method(envtbl,"rassoc", env_rassoc, 1);
2718
2719     rb_define_global_const("ENV", envtbl);
2720 #else /* __MACOS__ */
2721         envtbl = rb_hash_s_new(0, NULL, rb_cHash);
2722     rb_define_global_const("ENV", envtbl);
2723 #endif  /* ifndef __MACOS__  environment variables nothing on MacOS. */
2724 }