hash.c

00001 /*
00002 ** hash.c - Hash class
00003 **
00004 ** See Copyright Notice in mruby.h
00005 */
00006 
00007 #include "mruby.h"
00008 #include "mruby/array.h"
00009 #include "mruby/class.h"
00010 #include "mruby/hash.h"
00011 #include "mruby/khash.h"
00012 #include "mruby/string.h"
00013 #include "mruby/variable.h"
00014 
00015 /* a function to get hash value of a float number */
00016 mrb_int mrb_float_id(mrb_float f);
00017 
00018 static inline khint_t
00019 mrb_hash_ht_hash_func(mrb_state *mrb, mrb_value key)
00020 {
00021   enum mrb_vtype t = mrb_type(key);
00022   mrb_value hv;
00023   const char *p;
00024   mrb_int i, len;
00025   khint_t h;
00026 
00027   switch (t) {
00028   case MRB_TT_STRING:
00029     p = RSTRING_PTR(key);
00030     len = RSTRING_LEN(key);
00031     h = 0;
00032     for (i=0; i<len; i++) {
00033       h = (h << 5) - h + *p++;
00034     }
00035     return h;
00036 
00037   case MRB_TT_SYMBOL:
00038     h = (khint_t)mrb_symbol(key);
00039     return kh_int_hash_func(mrb, h);
00040 
00041   case MRB_TT_FIXNUM:
00042     h = (khint_t)mrb_float_id((mrb_float)mrb_fixnum(key));
00043     return kh_int_hash_func(mrb, h);
00044 
00045   case MRB_TT_FLOAT:
00046     h = (khint_t)mrb_float_id(mrb_float(key));
00047     return kh_int_hash_func(mrb, h);
00048 
00049   default:
00050     hv = mrb_funcall(mrb, key, "hash", 0);
00051     h = (khint_t)t ^ mrb_fixnum(hv);
00052     return kh_int_hash_func(mrb, h);
00053   }
00054 }
00055 
00056 static inline khint_t
00057 mrb_hash_ht_hash_equal(mrb_state *mrb, mrb_value a, mrb_value b)
00058 {
00059   enum mrb_vtype t = mrb_type(a);
00060 
00061   switch (t) {
00062   case MRB_TT_STRING:
00063     return mrb_str_equal(mrb, a, b);
00064 
00065   case MRB_TT_SYMBOL:
00066     if (mrb_type(b) != MRB_TT_SYMBOL) return FALSE;
00067     return mrb_symbol(a) == mrb_symbol(b);
00068 
00069   case MRB_TT_FIXNUM:
00070     switch (mrb_type(b)) {
00071     case MRB_TT_FIXNUM:
00072       return mrb_fixnum(a) == mrb_fixnum(b);
00073     case MRB_TT_FLOAT:
00074       return (mrb_float)mrb_fixnum(a) == mrb_float(b);
00075     default:
00076       return FALSE;
00077     }
00078 
00079   case MRB_TT_FLOAT:
00080     switch (mrb_type(b)) {
00081     case MRB_TT_FIXNUM:
00082       return mrb_float(a) == (mrb_float)mrb_fixnum(b);
00083     case MRB_TT_FLOAT:
00084       return mrb_float(a) == mrb_float(b);
00085     default:
00086       return FALSE;
00087     }
00088 
00089   default:
00090     return mrb_eql(mrb, a, b);
00091   }
00092 }
00093 
00094 typedef struct {
00095   mrb_value v;
00096   mrb_int n;
00097 } mrb_hash_value;
00098 
00099 KHASH_DECLARE(ht, mrb_value, mrb_hash_value, TRUE)
00100 KHASH_DEFINE (ht, mrb_value, mrb_hash_value, TRUE, mrb_hash_ht_hash_func, mrb_hash_ht_hash_equal)
00101 
00102 static void mrb_hash_modify(mrb_state *mrb, mrb_value hash);
00103 
00104 static inline mrb_value
00105 mrb_hash_ht_key(mrb_state *mrb, mrb_value key)
00106 {
00107   if (mrb_string_p(key))
00108     return mrb_str_dup(mrb, key);
00109   else
00110     return key;
00111 }
00112 
00113 #define KEY(key) mrb_hash_ht_key(mrb, key)
00114 
00115 void
00116 mrb_gc_mark_hash(mrb_state *mrb, struct RHash *hash)
00117 {
00118   khiter_t k;
00119   khash_t(ht) *h = hash->ht;
00120 
00121   if (!h) return;
00122   for (k = kh_begin(h); k != kh_end(h); k++) {
00123     if (kh_exist(h, k)) {
00124       mrb_value key = kh_key(h, k);
00125       mrb_value val = kh_value(h, k).v;
00126 
00127       mrb_gc_mark_value(mrb, key);
00128       mrb_gc_mark_value(mrb, val);
00129     }
00130   }
00131 }
00132 
00133 size_t
00134 mrb_gc_mark_hash_size(mrb_state *mrb, struct RHash *hash)
00135 {
00136   if (!hash->ht) return 0;
00137   return kh_size(hash->ht)*2;
00138 }
00139 
00140 void
00141 mrb_gc_free_hash(mrb_state *mrb, struct RHash *hash)
00142 {
00143   if (hash->ht) kh_destroy(ht, mrb, hash->ht);
00144 }
00145 
00146 
00147 MRB_API mrb_value
00148 mrb_hash_new_capa(mrb_state *mrb, int capa)
00149 {
00150   struct RHash *h;
00151 
00152   h = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
00153   h->ht = kh_init(ht, mrb);
00154   if (capa > 0) {
00155     kh_resize(ht, mrb, h->ht, capa);
00156   }
00157   h->iv = 0;
00158   return mrb_obj_value(h);
00159 }
00160 
00161 MRB_API mrb_value
00162 mrb_hash_new(mrb_state *mrb)
00163 {
00164   return mrb_hash_new_capa(mrb, 0);
00165 }
00166 
00167 MRB_API mrb_value
00168 mrb_hash_get(mrb_state *mrb, mrb_value hash, mrb_value key)
00169 {
00170   khash_t(ht) *h = RHASH_TBL(hash);
00171   khiter_t k;
00172 
00173   if (h) {
00174     k = kh_get(ht, mrb, h, key);
00175     if (k != kh_end(h))
00176       return kh_value(h, k).v;
00177   }
00178 
00179   /* not found */
00180   if (MRB_RHASH_PROCDEFAULT_P(hash)) {
00181     return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, key);
00182   }
00183   return RHASH_IFNONE(hash);
00184 }
00185 
00186 MRB_API mrb_value
00187 mrb_hash_fetch(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value def)
00188 {
00189   khash_t(ht) *h = RHASH_TBL(hash);
00190   khiter_t k;
00191 
00192   if (h) {
00193     k = kh_get(ht, mrb, h, key);
00194     if (k != kh_end(h))
00195       return kh_value(h, k).v;
00196   }
00197 
00198   /* not found */
00199   return def;
00200 }
00201 
00202 MRB_API void
00203 mrb_hash_set(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value val)
00204 {
00205   khash_t(ht) *h;
00206   khiter_t k;
00207   int r;
00208 
00209   mrb_hash_modify(mrb, hash);
00210   h = RHASH_TBL(hash);
00211 
00212   if (!h) h = RHASH_TBL(hash) = kh_init(ht, mrb);
00213   k = kh_put2(ht, mrb, h, key, &r);
00214   kh_value(h, k).v = val;
00215 
00216   if (r != 0) {
00217     /* expand */
00218     int ai = mrb_gc_arena_save(mrb);
00219     key = kh_key(h, k) = KEY(key);
00220     mrb_gc_arena_restore(mrb, ai);
00221     kh_value(h, k).n = kh_size(h)-1;
00222   }
00223 
00224   mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), key);
00225   mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), val);
00226   return;
00227 }
00228 
00229 static mrb_value
00230 mrb_hash_dup(mrb_state *mrb, mrb_value hash)
00231 {
00232   struct RHash* ret;
00233   khash_t(ht) *h, *ret_h;
00234   khiter_t k, ret_k;
00235 
00236   h = RHASH_TBL(hash);
00237   ret = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
00238   ret->ht = kh_init(ht, mrb);
00239 
00240   if (kh_size(h) > 0) {
00241     ret_h = ret->ht;
00242 
00243     for (k = kh_begin(h); k != kh_end(h); k++) {
00244       if (kh_exist(h, k)) {
00245         int ai = mrb_gc_arena_save(mrb);
00246         ret_k = kh_put(ht, mrb, ret_h, KEY(kh_key(h, k)));
00247         mrb_gc_arena_restore(mrb, ai);
00248         kh_val(ret_h, ret_k) = kh_val(h, k);
00249       }
00250     }
00251   }
00252 
00253   return mrb_obj_value(ret);
00254 }
00255 
00256 MRB_API mrb_value
00257 mrb_check_hash_type(mrb_state *mrb, mrb_value hash)
00258 {
00259   return mrb_check_convert_type(mrb, hash, MRB_TT_HASH, "Hash", "to_hash");
00260 }
00261 
00262 MRB_API khash_t(ht)*
00263 mrb_hash_tbl(mrb_state *mrb, mrb_value hash)
00264 {
00265   khash_t(ht) *h = RHASH_TBL(hash);
00266 
00267   if (!h) {
00268     return RHASH_TBL(hash) = kh_init(ht, mrb);
00269   }
00270   return h;
00271 }
00272 
00273 static void
00274 mrb_hash_modify(mrb_state *mrb, mrb_value hash)
00275 {
00276   mrb_hash_tbl(mrb, hash);
00277 }
00278 
00279 /* 15.2.13.4.16 */
00280 /*
00281  *  call-seq:
00282  *     Hash.new                          -> new_hash
00283  *     Hash.new(obj)                     -> new_hash
00284  *     Hash.new {|hash, key| block }     -> new_hash
00285  *
00286  *  Returns a new, empty hash. If this hash is subsequently accessed by
00287  *  a key that doesn't correspond to a hash entry, the value returned
00288  *  depends on the style of <code>new</code> used to create the hash. In
00289  *  the first form, the access returns <code>nil</code>. If
00290  *  <i>obj</i> is specified, this single object will be used for
00291  *  all <em>default values</em>. If a block is specified, it will be
00292  *  called with the hash object and the key, and should return the
00293  *  default value. It is the block's responsibility to store the value
00294  *  in the hash if required.
00295  *
00296  *     h = Hash.new("Go Fish")
00297  *     h["a"] = 100
00298  *     h["b"] = 200
00299  *     h["a"]           #=> 100
00300  *     h["c"]           #=> "Go Fish"
00301  *     # The following alters the single default object
00302  *     h["c"].upcase!   #=> "GO FISH"
00303  *     h["d"]           #=> "GO FISH"
00304  *     h.keys           #=> ["a", "b"]
00305  *
00306  *     # While this creates a new default object each time
00307  *     h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
00308  *     h["c"]           #=> "Go Fish: c"
00309  *     h["c"].upcase!   #=> "GO FISH: C"
00310  *     h["d"]           #=> "Go Fish: d"
00311  *     h.keys           #=> ["c", "d"]
00312  *
00313  */
00314 
00315 static mrb_value
00316 mrb_hash_init(mrb_state *mrb, mrb_value hash)
00317 {
00318   mrb_value block, ifnone;
00319   mrb_bool ifnone_p;
00320 
00321   ifnone = mrb_nil_value();
00322   mrb_get_args(mrb, "&|o?", &block, &ifnone, &ifnone_p);
00323   mrb_hash_modify(mrb, hash);
00324   if (!mrb_nil_p(block)) {
00325     if (ifnone_p) {
00326       mrb_raise(mrb, E_ARGUMENT_ERROR, "wrong number of arguments");
00327     }
00328     RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
00329     ifnone = block;
00330   }
00331   mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
00332   return hash;
00333 }
00334 
00335 /* 15.2.13.4.2  */
00336 /*
00337  *  call-seq:
00338  *     hsh[key]    ->  value
00339  *
00340  *  Element Reference---Retrieves the <i>value</i> object corresponding
00341  *  to the <i>key</i> object. If not found, returns the default value (see
00342  *  <code>Hash::new</code> for details).
00343  *
00344  *     h = { "a" => 100, "b" => 200 }
00345  *     h["a"]   #=> 100
00346  *     h["c"]   #=> nil
00347  *
00348  */
00349 static mrb_value
00350 mrb_hash_aget(mrb_state *mrb, mrb_value self)
00351 {
00352   mrb_value key;
00353 
00354   mrb_get_args(mrb, "o", &key);
00355   return mrb_hash_get(mrb, self, key);
00356 }
00357 
00358 /* 15.2.13.4.5  */
00359 /*
00360  *  call-seq:
00361  *     hsh.default(key=nil)   -> obj
00362  *
00363  *  Returns the default value, the value that would be returned by
00364  *  <i>hsh</i>[<i>key</i>] if <i>key</i> did not exist in <i>hsh</i>.
00365  *  See also <code>Hash::new</code> and <code>Hash#default=</code>.
00366  *
00367  *     h = Hash.new                            #=> {}
00368  *     h.default                               #=> nil
00369  *     h.default(2)                            #=> nil
00370  *
00371  *     h = Hash.new("cat")                     #=> {}
00372  *     h.default                               #=> "cat"
00373  *     h.default(2)                            #=> "cat"
00374  *
00375  *     h = Hash.new {|h,k| h[k] = k.to_i*10}   #=> {}
00376  *     h.default                               #=> nil
00377  *     h.default(2)                            #=> 20
00378  */
00379 
00380 static mrb_value
00381 mrb_hash_default(mrb_state *mrb, mrb_value hash)
00382 {
00383   mrb_value key;
00384   mrb_bool given;
00385 
00386   mrb_get_args(mrb, "|o?", &key, &given);
00387   if (MRB_RHASH_PROCDEFAULT_P(hash)) {
00388     if (!given) return mrb_nil_value();
00389     return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, key);
00390   }
00391   else {
00392     return RHASH_IFNONE(hash);
00393   }
00394 }
00395 
00396 /* 15.2.13.4.6  */
00397 /*
00398  *  call-seq:
00399  *     hsh.default = obj     -> obj
00400  *
00401  *  Sets the default value, the value returned for a key that does not
00402  *  exist in the hash. It is not possible to set the default to a
00403  *  <code>Proc</code> that will be executed on each key lookup.
00404  *
00405  *     h = { "a" => 100, "b" => 200 }
00406  *     h.default = "Go fish"
00407  *     h["a"]     #=> 100
00408  *     h["z"]     #=> "Go fish"
00409  *     # This doesn't do what you might hope...
00410  *     h.default = proc do |hash, key|
00411  *       hash[key] = key + key
00412  *     end
00413  *     h[2]       #=> #<Proc:0x401b3948@-:6>
00414  *     h["cat"]   #=> #<Proc:0x401b3948@-:6>
00415  */
00416 
00417 static mrb_value
00418 mrb_hash_set_default(mrb_state *mrb, mrb_value hash)
00419 {
00420   mrb_value ifnone;
00421 
00422   mrb_get_args(mrb, "o", &ifnone);
00423   mrb_hash_modify(mrb, hash);
00424   mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
00425   RHASH(hash)->flags &= ~(MRB_HASH_PROC_DEFAULT);
00426 
00427   return ifnone;
00428 }
00429 
00430 /* 15.2.13.4.7  */
00431 /*
00432  *  call-seq:
00433  *     hsh.default_proc -> anObject
00434  *
00435  *  If <code>Hash::new</code> was invoked with a block, return that
00436  *  block, otherwise return <code>nil</code>.
00437  *
00438  *     h = Hash.new {|h,k| h[k] = k*k }   #=> {}
00439  *     p = h.default_proc                 #=> #<Proc:0x401b3d08@-:1>
00440  *     a = []                             #=> []
00441  *     p.call(a, 2)
00442  *     a                                  #=> [nil, nil, 4]
00443  */
00444 
00445 
00446 static mrb_value
00447 mrb_hash_default_proc(mrb_state *mrb, mrb_value hash)
00448 {
00449   if (MRB_RHASH_PROCDEFAULT_P(hash)) {
00450     return RHASH_PROCDEFAULT(hash);
00451   }
00452   return mrb_nil_value();
00453 }
00454 
00455 /*
00456  *  call-seq:
00457  *     hsh.default_proc = proc_obj     -> proc_obj
00458  *
00459  *  Sets the default proc to be executed on each key lookup.
00460  *
00461  *     h.default_proc = proc do |hash, key|
00462  *       hash[key] = key + key
00463  *     end
00464  *     h[2]       #=> 4
00465  *     h["cat"]   #=> "catcat"
00466  */
00467 
00468 static mrb_value
00469 mrb_hash_set_default_proc(mrb_state *mrb, mrb_value hash)
00470 {
00471   mrb_value ifnone;
00472 
00473   mrb_get_args(mrb, "o", &ifnone);
00474   mrb_hash_modify(mrb, hash);
00475   mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
00476   RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
00477 
00478   return ifnone;
00479 }
00480 
00481 MRB_API mrb_value
00482 mrb_hash_delete_key(mrb_state *mrb, mrb_value hash, mrb_value key)
00483 {
00484   khash_t(ht) *h = RHASH_TBL(hash);
00485   khiter_t k;
00486   mrb_value delVal;
00487   mrb_int n;
00488 
00489   if (h) {
00490     k = kh_get(ht, mrb, h, key);
00491     if (k != kh_end(h)) {
00492       delVal = kh_value(h, k).v;
00493       n = kh_value(h, k).n;
00494       kh_del(ht, mrb, h, k);
00495       for (k = kh_begin(h); k != kh_end(h); k++) {
00496         if (!kh_exist(h, k)) continue;
00497         if (kh_value(h, k).n > n) kh_value(h, k).n--;
00498       }
00499       return delVal;
00500     }
00501   }
00502 
00503   /* not found */
00504   return mrb_nil_value();
00505 }
00506 
00507 /* 15.2.13.4.8  */
00508 /*
00509  *  call-seq:
00510  *     hsh.delete(key)                   -> value
00511  *     hsh.delete(key) {| key | block }  -> value
00512  *
00513  *  Deletes and returns a key-value pair from <i>hsh</i> whose key is
00514  *  equal to <i>key</i>. If the key is not found, returns the
00515  *  <em>default value</em>. If the optional code block is given and the
00516  *  key is not found, pass in the key and return the result of
00517  *  <i>block</i>.
00518  *
00519  *     h = { "a" => 100, "b" => 200 }
00520  *     h.delete("a")                              #=> 100
00521  *     h.delete("z")                              #=> nil
00522  *     h.delete("z") { |el| "#{el} not found" }   #=> "z not found"
00523  *
00524  */
00525 static mrb_value
00526 mrb_hash_delete(mrb_state *mrb, mrb_value self)
00527 {
00528   mrb_value key;
00529 
00530   mrb_get_args(mrb, "o", &key);
00531   return mrb_hash_delete_key(mrb, self, key);
00532 }
00533 
00534 /* 15.2.13.4.24 */
00535 /*
00536  *  call-seq:
00537  *     hsh.shift -> anArray or obj
00538  *
00539  *  Removes a key-value pair from <i>hsh</i> and returns it as the
00540  *  two-item array <code>[</code> <i>key, value</i> <code>]</code>, or
00541  *  the hash's default value if the hash is empty.
00542  *
00543  *     h = { 1 => "a", 2 => "b", 3 => "c" }
00544  *     h.shift   #=> [1, "a"]
00545  *     h         #=> {2=>"b", 3=>"c"}
00546  */
00547 
00548 static mrb_value
00549 mrb_hash_shift(mrb_state *mrb, mrb_value hash)
00550 {
00551   khash_t(ht) *h = RHASH_TBL(hash);
00552   khiter_t k;
00553   mrb_value delKey, delVal;
00554 
00555   mrb_hash_modify(mrb, hash);
00556   if (h && kh_size(h) > 0) {
00557     for (k = kh_begin(h); k != kh_end(h); k++) {
00558       if (!kh_exist(h, k)) continue;
00559 
00560       delKey = kh_key(h, k);
00561       mrb_gc_protect(mrb, delKey);
00562       delVal = mrb_hash_delete_key(mrb, hash, delKey);
00563       mrb_gc_protect(mrb, delVal);
00564 
00565       return mrb_assoc_new(mrb, delKey, delVal);
00566     }
00567   }
00568 
00569   if (MRB_RHASH_PROCDEFAULT_P(hash)) {
00570     return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, mrb_nil_value());
00571   }
00572   else {
00573     return RHASH_IFNONE(hash);
00574   }
00575 }
00576 
00577 /* 15.2.13.4.4  */
00578 /*
00579  *  call-seq:
00580  *     hsh.clear -> hsh
00581  *
00582  *  Removes all key-value pairs from <i>hsh</i>.
00583  *
00584  *     h = { "a" => 100, "b" => 200 }   #=> {"a"=>100, "b"=>200}
00585  *     h.clear                          #=> {}
00586  *
00587  */
00588 
00589 MRB_API mrb_value
00590 mrb_hash_clear(mrb_state *mrb, mrb_value hash)
00591 {
00592   khash_t(ht) *h = RHASH_TBL(hash);
00593 
00594   if (h) kh_clear(ht, mrb, h);
00595   return hash;
00596 }
00597 
00598 /* 15.2.13.4.3  */
00599 /* 15.2.13.4.26 */
00600 /*
00601  *  call-seq:
00602  *     hsh[key] = value        -> value
00603  *     hsh.store(key, value)   -> value
00604  *
00605  *  Element Assignment---Associates the value given by
00606  *  <i>value</i> with the key given by <i>key</i>.
00607  *  <i>key</i> should not have its value changed while it is in
00608  *  use as a key (a <code>String</code> passed as a key will be
00609  *  duplicated and frozen).
00610  *
00611  *     h = { "a" => 100, "b" => 200 }
00612  *     h["a"] = 9
00613  *     h["c"] = 4
00614  *     h   #=> {"a"=>9, "b"=>200, "c"=>4}
00615  *
00616  */
00617 static mrb_value
00618 mrb_hash_aset(mrb_state *mrb, mrb_value self)
00619 {
00620   mrb_value key, val;
00621 
00622   mrb_get_args(mrb, "oo", &key, &val);
00623   mrb_hash_set(mrb, self, key, val);
00624   return val;
00625 }
00626 
00627 /* 15.2.13.4.20 */
00628 /* 15.2.13.4.25 */
00629 /*
00630  *  call-seq:
00631  *     hsh.length    ->  fixnum
00632  *     hsh.size      ->  fixnum
00633  *
00634  *  Returns the number of key-value pairs in the hash.
00635  *
00636  *     h = { "d" => 100, "a" => 200, "v" => 300, "e" => 400 }
00637  *     h.length        #=> 4
00638  *     h.delete("a")   #=> 200
00639  *     h.length        #=> 3
00640  */
00641 static mrb_value
00642 mrb_hash_size_m(mrb_state *mrb, mrb_value self)
00643 {
00644   khash_t(ht) *h = RHASH_TBL(self);
00645 
00646   if (!h) return mrb_fixnum_value(0);
00647   return mrb_fixnum_value(kh_size(h));
00648 }
00649 
00650 /* 15.2.13.4.12 */
00651 /*
00652  *  call-seq:
00653  *     hsh.empty?    -> true or false
00654  *
00655  *  Returns <code>true</code> if <i>hsh</i> contains no key-value pairs.
00656  *
00657  *     {}.empty?   #=> true
00658  *
00659  */
00660 MRB_API mrb_value
00661 mrb_hash_empty_p(mrb_state *mrb, mrb_value self)
00662 {
00663   khash_t(ht) *h = RHASH_TBL(self);
00664 
00665   if (h) return mrb_bool_value(kh_size(h) == 0);
00666   return mrb_true_value();
00667 }
00668 
00669 /* 15.2.13.4.29 (x)*/
00670 /*
00671  * call-seq:
00672  *    hsh.to_hash   => hsh
00673  *
00674  * Returns +self+.
00675  */
00676 
00677 static mrb_value
00678 mrb_hash_to_hash(mrb_state *mrb, mrb_value hash)
00679 {
00680   return hash;
00681 }
00682 
00683 /* 15.2.13.4.19 */
00684 /*
00685  *  call-seq:
00686  *     hsh.keys    -> array
00687  *
00688  *  Returns a new array populated with the keys from this hash. See also
00689  *  <code>Hash#values</code>.
00690  *
00691  *     h = { "a" => 100, "b" => 200, "c" => 300, "d" => 400 }
00692  *     h.keys   #=> ["a", "b", "c", "d"]
00693  *
00694  */
00695 
00696 MRB_API mrb_value
00697 mrb_hash_keys(mrb_state *mrb, mrb_value hash)
00698 {
00699   khash_t(ht) *h = RHASH_TBL(hash);
00700   khiter_t k;
00701   mrb_value ary;
00702   mrb_value *p;
00703 
00704   if (!h || kh_size(h) == 0) return mrb_ary_new(mrb);
00705   ary = mrb_ary_new_capa(mrb, kh_size(h));
00706   mrb_ary_set(mrb, ary, kh_size(h)-1, mrb_nil_value());
00707   p = mrb_ary_ptr(ary)->ptr;
00708   for (k = kh_begin(h); k != kh_end(h); k++) {
00709     if (kh_exist(h, k)) {
00710       mrb_value kv = kh_key(h, k);
00711       mrb_hash_value hv = kh_value(h, k);
00712 
00713       p[hv.n] = kv;
00714     }
00715   }
00716   return ary;
00717 }
00718 
00719 /* 15.2.13.4.28 */
00720 /*
00721  *  call-seq:
00722  *     hsh.values    -> array
00723  *
00724  *  Returns a new array populated with the values from <i>hsh</i>. See
00725  *  also <code>Hash#keys</code>.
00726  *
00727  *     h = { "a" => 100, "b" => 200, "c" => 300 }
00728  *     h.values   #=> [100, 200, 300]
00729  *
00730  */
00731 
00732 static mrb_value
00733 mrb_hash_values(mrb_state *mrb, mrb_value hash)
00734 {
00735   khash_t(ht) *h = RHASH_TBL(hash);
00736   khiter_t k;
00737   mrb_value ary;
00738 
00739   if (!h) return mrb_ary_new(mrb);
00740   ary = mrb_ary_new_capa(mrb, kh_size(h));
00741   for (k = kh_begin(h); k != kh_end(h); k++) {
00742     if (kh_exist(h, k)) {
00743       mrb_hash_value hv = kh_value(h, k);
00744 
00745       mrb_ary_set(mrb, ary, hv.n, hv.v);
00746     }
00747   }
00748   return ary;
00749 }
00750 
00751 /* 15.2.13.4.13 */
00752 /* 15.2.13.4.15 */
00753 /* 15.2.13.4.18 */
00754 /* 15.2.13.4.21 */
00755 /*
00756  *  call-seq:
00757  *     hsh.has_key?(key)    -> true or false
00758  *     hsh.include?(key)    -> true or false
00759  *     hsh.key?(key)        -> true or false
00760  *     hsh.member?(key)     -> true or false
00761  *
00762  *  Returns <code>true</code> if the given key is present in <i>hsh</i>.
00763  *
00764  *     h = { "a" => 100, "b" => 200 }
00765  *     h.has_key?("a")   #=> true
00766  *     h.has_key?("z")   #=> false
00767  *
00768  */
00769 
00770 static mrb_value
00771 mrb_hash_has_key(mrb_state *mrb, mrb_value hash)
00772 {
00773   mrb_value key;
00774   khash_t(ht) *h;
00775   khiter_t k;
00776 
00777   mrb_get_args(mrb, "o", &key);
00778 
00779   h = RHASH_TBL(hash);
00780   if (h) {
00781     k = kh_get(ht, mrb, h, key);
00782     return mrb_bool_value(k != kh_end(h));
00783   }
00784   return mrb_false_value();
00785 }
00786 
00787 /* 15.2.13.4.14 */
00788 /* 15.2.13.4.27 */
00789 /*
00790  *  call-seq:
00791  *     hsh.has_value?(value)    -> true or false
00792  *     hsh.value?(value)        -> true or false
00793  *
00794  *  Returns <code>true</code> if the given value is present for some key
00795  *  in <i>hsh</i>.
00796  *
00797  *     h = { "a" => 100, "b" => 200 }
00798  *     h.has_value?(100)   #=> true
00799  *     h.has_value?(999)   #=> false
00800  */
00801 
00802 static mrb_value
00803 mrb_hash_has_value(mrb_state *mrb, mrb_value hash)
00804 {
00805   mrb_value val;
00806   khash_t(ht) *h;
00807   khiter_t k;
00808 
00809   mrb_get_args(mrb, "o", &val);
00810   h = RHASH_TBL(hash);
00811 
00812   if (h) {
00813     for (k = kh_begin(h); k != kh_end(h); k++) {
00814       if (!kh_exist(h, k)) continue;
00815 
00816       if (mrb_equal(mrb, kh_value(h, k).v, val)) {
00817         return mrb_true_value();
00818       }
00819     }
00820   }
00821   return mrb_false_value();
00822 }
00823 
00824 void
00825 mrb_init_hash(mrb_state *mrb)
00826 {
00827   struct RClass *h;
00828 
00829   h = mrb->hash_class = mrb_define_class(mrb, "Hash", mrb->object_class);              /* 15.2.13 */
00830   MRB_SET_INSTANCE_TT(h, MRB_TT_HASH);
00831 
00832   mrb_define_method(mrb, h, "[]",              mrb_hash_aget,        MRB_ARGS_REQ(1)); /* 15.2.13.4.2  */
00833   mrb_define_method(mrb, h, "[]=",             mrb_hash_aset,        MRB_ARGS_REQ(2)); /* 15.2.13.4.3  */
00834   mrb_define_method(mrb, h, "clear",           mrb_hash_clear,       MRB_ARGS_NONE()); /* 15.2.13.4.4  */
00835   mrb_define_method(mrb, h, "default",         mrb_hash_default,     MRB_ARGS_ANY());  /* 15.2.13.4.5  */
00836   mrb_define_method(mrb, h, "default=",        mrb_hash_set_default, MRB_ARGS_REQ(1)); /* 15.2.13.4.6  */
00837   mrb_define_method(mrb, h, "default_proc",    mrb_hash_default_proc,MRB_ARGS_NONE()); /* 15.2.13.4.7  */
00838   mrb_define_method(mrb, h, "default_proc=",   mrb_hash_set_default_proc,MRB_ARGS_REQ(1)); /* 15.2.13.4.7  */
00839   mrb_define_method(mrb, h, "__delete",        mrb_hash_delete,      MRB_ARGS_REQ(1)); /* core of 15.2.13.4.8  */
00840   mrb_define_method(mrb, h, "empty?",          mrb_hash_empty_p,     MRB_ARGS_NONE()); /* 15.2.13.4.12 */
00841   mrb_define_method(mrb, h, "has_key?",        mrb_hash_has_key,     MRB_ARGS_REQ(1)); /* 15.2.13.4.13 */
00842   mrb_define_method(mrb, h, "has_value?",      mrb_hash_has_value,   MRB_ARGS_REQ(1)); /* 15.2.13.4.14 */
00843   mrb_define_method(mrb, h, "include?",        mrb_hash_has_key,     MRB_ARGS_REQ(1)); /* 15.2.13.4.15 */
00844   mrb_define_method(mrb, h, "initialize",      mrb_hash_init,        MRB_ARGS_OPT(1)); /* 15.2.13.4.16 */
00845   mrb_define_method(mrb, h, "key?",            mrb_hash_has_key,     MRB_ARGS_REQ(1)); /* 15.2.13.4.18 */
00846   mrb_define_method(mrb, h, "keys",            mrb_hash_keys,        MRB_ARGS_NONE()); /* 15.2.13.4.19 */
00847   mrb_define_method(mrb, h, "length",          mrb_hash_size_m,      MRB_ARGS_NONE()); /* 15.2.13.4.20 */
00848   mrb_define_method(mrb, h, "member?",         mrb_hash_has_key,     MRB_ARGS_REQ(1)); /* 15.2.13.4.21 */
00849   mrb_define_method(mrb, h, "shift",           mrb_hash_shift,       MRB_ARGS_NONE()); /* 15.2.13.4.24 */
00850   mrb_define_method(mrb, h, "dup",             mrb_hash_dup,         MRB_ARGS_NONE());
00851   mrb_define_method(mrb, h, "size",            mrb_hash_size_m,      MRB_ARGS_NONE()); /* 15.2.13.4.25 */
00852   mrb_define_method(mrb, h, "store",           mrb_hash_aset,        MRB_ARGS_REQ(2)); /* 15.2.13.4.26 */
00853   mrb_define_method(mrb, h, "value?",          mrb_hash_has_value,   MRB_ARGS_REQ(1)); /* 15.2.13.4.27 */
00854   mrb_define_method(mrb, h, "values",          mrb_hash_values,      MRB_ARGS_NONE()); /* 15.2.13.4.28 */
00855 
00856   mrb_define_method(mrb, h, "to_hash",         mrb_hash_to_hash,     MRB_ARGS_NONE()); /* 15.2.13.4.29 (x)*/
00857 }
00858