4 ** See Copyright Notice in mruby.h
8 #include <mruby/array.h>
9 #include <mruby/class.h>
10 #include <mruby/hash.h>
11 #include <mruby/string.h>
12 #include <mruby/variable.h>
14 #ifndef MRB_WITHOUT_FLOAT
15 /* a function to get hash value of a float number */
16 mrb_int mrb_float_id(mrb_float f);
19 #ifndef MRB_HT_INIT_SIZE
20 #define MRB_HT_INIT_SIZE 4
22 #define HT_SEG_INCREASE_RATIO 6 / 5
29 typedef struct segment {
35 typedef struct segindex {
38 struct segkv *table[];
41 /* hash table structure */
42 typedef struct htable {
50 static /* inline */ size_t
51 ht_hash_func(mrb_state *mrb, htable *t, mrb_value key)
53 enum mrb_vtype tt = mrb_type(key);
56 segindex *index = t->index;
57 size_t capa = index ? index->capa : 0;
61 h = mrb_str_hash(mrb, key);
68 #ifndef MRB_WITHOUT_FLOAT
71 h = (size_t)mrb_obj_id(key);
75 hv = mrb_funcall(mrb, key, "hash", 0);
76 h = (size_t)tt ^ (size_t)mrb_fixnum(hv);
79 if (index && (index != t->index || capa != index->capa)) {
80 mrb_raise(mrb, E_RUNTIME_ERROR, "hash modified");
82 return ((h)^((h)<<2)^((h)>>2));
85 static inline mrb_bool
86 ht_hash_equal(mrb_state *mrb, htable *t, mrb_value a, mrb_value b)
88 enum mrb_vtype tt = mrb_type(a);
92 return mrb_str_equal(mrb, a, b);
95 if (!mrb_symbol_p(b)) return FALSE;
96 return mrb_symbol(a) == mrb_symbol(b);
99 switch (mrb_type(b)) {
101 return mrb_fixnum(a) == mrb_fixnum(b);
102 #ifndef MRB_WITHOUT_FLOAT
104 return (mrb_float)mrb_fixnum(a) == mrb_float(b);
110 #ifndef MRB_WITHOUT_FLOAT
112 switch (mrb_type(b)) {
114 return mrb_float(a) == (mrb_float)mrb_fixnum(b);
116 return mrb_float(a) == mrb_float(b);
124 segindex *index = t->index;
125 size_t capa = index ? index->capa : 0;
126 mrb_bool eql = mrb_eql(mrb, a, b);
127 if (index && (index != t->index || capa != index->capa)) {
128 mrb_raise(mrb, E_RUNTIME_ERROR, "hash modified");
135 /* Creates the hash table. */
137 ht_new(mrb_state *mrb)
141 t = (htable*)mrb_malloc(mrb, sizeof(htable));
151 #define power2(v) do { \
162 #define UPPER_BOUND(x) ((x)>>2|(x)>>1)
165 #define HT_MASK(index) ((index->capa)-1)
167 /* Build index for the hash table */
169 ht_index(mrb_state *mrb, htable *t)
171 size_t size = (size_t)t->size;
173 segindex *index = t->index;
177 /* allocate index table */
178 if (index && index->size >= UPPER_BOUND(index->capa)) {
179 size = index->capa+1;
182 if (!index || index->capa < size) {
183 index = (segindex*)mrb_realloc_simple(mrb, index, sizeof(segindex)+sizeof(struct segkv*)*size);
185 mrb_free(mrb, t->index);
191 index->size = t->size;
193 for (i=0; i<size; i++) {
194 index->table[i] = NULL;
198 mask = HT_MASK(index);
201 for (i=0; i<seg->size; i++) {
205 if (!seg->next && i >= (size_t)t->last_len) {
209 if (mrb_undef_p(key)) continue;
210 k = ht_hash_func(mrb, t, key) & mask;
211 while (index->table[k]) {
212 k = (k+(++step)) & mask;
214 index->table[k] = &seg->e[i];
220 /* Compacts the hash table removing deleted entries. */
222 ht_compact(mrb_state *mrb, htable *t)
226 segment *seg2 = NULL;
229 if (t == NULL) return;
231 if (t->index && (size_t)t->size == t->index->size) {
236 for (i=0; i<seg->size; i++) {
237 mrb_value k = seg->e[i].key;
239 if (!seg->next && i >= t->last_len) {
242 if (mrb_undef_p(k)) { /* found deleted key */
251 seg2->e[i2++] = seg->e[i];
252 if (i2 >= seg2->size) {
281 segment_alloc(mrb_state *mrb, segment *seg)
285 if (!seg) size = MRB_HT_INIT_SIZE;
287 size = seg->size*HT_SEG_INCREASE_RATIO + 1;
288 if (size > UINT16_MAX) size = UINT16_MAX;
291 seg = (segment*)mrb_malloc(mrb, sizeof(segment)+sizeof(struct segkv)*size);
298 /* Set the value for the key in the indexed table. */
300 ht_index_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val)
302 segindex *index = t->index;
303 size_t k, sp, step = 0, mask;
306 if (index->size >= UPPER_BOUND(index->capa)) {
307 /* need to expand table */
311 mask = HT_MASK(index);
313 k = ht_hash_func(mrb, t, key) & mask;
314 while (index->table[k]) {
315 mrb_value key2 = index->table[k]->key;
316 if (mrb_undef_p(key2)) {
317 if (sp == index->capa) sp = k;
319 else if (ht_hash_equal(mrb, t, key, key2)) {
320 index->table[k]->val = val;
323 k = (k+(++step)) & mask;
325 if (sp < index->capa) {
329 /* put the value at the last */
331 if (t->last_len < seg->size) {
332 index->table[k] = &seg->e[t->last_len++];
334 else { /* append a new segment */
335 seg->next = segment_alloc(mrb, seg);
340 index->table[k] = &seg->e[0];
342 index->table[k]->key = key;
343 index->table[k]->val = val;
348 /* Set the value for the key in the hash table. */
350 ht_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val)
353 mrb_int i, deleted = 0;
355 if (t == NULL) return;
357 ht_index_put(mrb, t, key, val);
362 for (i=0; i<seg->size; i++) {
363 mrb_value k = seg->e[i].key;
364 /* Found room in last segment after last_len */
365 if (!seg->next && i >= t->last_len) {
368 t->last_len = (uint16_t)i+1;
372 if (mrb_undef_p(k)) {
376 if (ht_hash_equal(mrb, t, key, k)) {
385 /* Compact if last segment has room */
386 if (deleted > 0 && deleted > MRB_HT_INIT_SIZE) {
391 /* check if thre's room after compaction */
392 if (t->lastseg && t->last_len < t->lastseg->size) {
397 /* append new segment */
398 seg = segment_alloc(mrb, t->lastseg);
400 if (t->rootseg == NULL) {
404 t->lastseg->next = seg;
410 t->last_len = (uint16_t)i+1;
411 if (t->index == NULL && t->size > MRB_HT_INIT_SIZE*4) {
416 /* Get a value for a key from the indexed table. */
418 ht_index_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
420 segindex *index = t->index;
421 size_t mask = HT_MASK(index);
422 size_t k = ht_hash_func(mrb, t, key) & mask;
425 while (index->table[k]) {
426 mrb_value key2 = index->table[k]->key;
427 if (!mrb_undef_p(key2) && ht_hash_equal(mrb, t, key, key2)) {
428 if (vp) *vp = index->table[k]->val;
431 k = (k+(++step)) & mask;
436 /* Get a value for a key from the hash table. */
438 ht_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
443 if (t == NULL) return FALSE;
445 return ht_index_get(mrb, t, key, vp);
450 for (i=0; i<seg->size; i++) {
451 mrb_value k = seg->e[i].key;
453 if (!seg->next && i >= t->last_len) {
456 if (mrb_undef_p(k)) continue;
457 if (ht_hash_equal(mrb, t, key, k)) {
458 if (vp) *vp = seg->e[i].val;
467 /* Deletes the value for the symbol from the hash table. */
468 /* Deletion is done by overwriting keys by `undef`. */
470 ht_del(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
475 if (t == NULL) return FALSE;
478 for (i=0; i<seg->size; i++) {
481 if (!seg->next && i >= t->last_len) {
485 key2 = seg->e[i].key;
486 if (!mrb_undef_p(key2) && ht_hash_equal(mrb, t, key, key2)) {
487 if (vp) *vp = seg->e[i].val;
488 seg->e[i].key = mrb_undef_value();
498 /* Iterates over the hash table. */
500 ht_foreach(mrb_state *mrb, htable *t, mrb_hash_foreach_func *func, void *p)
505 if (t == NULL) return;
508 for (i=0; i<seg->size; i++) {
509 /* no value in last segment after last_len */
510 if (!seg->next && i >= t->last_len) {
513 if (mrb_undef_p(seg->e[i].key)) continue;
514 if ((*func)(mrb, seg->e[i].key, seg->e[i].val, p) != 0)
521 /* Iterates over the hash table. */
523 mrb_hash_foreach(mrb_state *mrb, struct RHash *hash, mrb_hash_foreach_func *func, void *p)
525 ht_foreach(mrb, hash->ht, func, p);
528 /* Copy the hash table. */
530 ht_copy(mrb_state *mrb, htable *t)
538 if (t->size == 0) return t2;
541 for (i=0; i<seg->size; i++) {
542 mrb_value key = seg->e[i].key;
543 mrb_value val = seg->e[i].val;
545 if ((seg->next == NULL) && (i >= t->last_len)) {
548 if (mrb_undef_p(key)) continue; /* skip deleted key */
549 ht_put(mrb, t2, key, val);
556 /* Free memory of the hash table. */
558 ht_free(mrb_state *mrb, htable *t)
569 if (t->index) mrb_free(mrb, t->index);
573 static void mrb_hash_modify(mrb_state *mrb, mrb_value hash);
575 static inline mrb_value
576 ht_key(mrb_state *mrb, mrb_value key)
578 if (mrb_string_p(key) && !mrb_frozen_p(mrb_str_ptr(key))) {
579 key = mrb_str_dup(mrb, key);
580 MRB_SET_FROZEN_FLAG(mrb_str_ptr(key));
585 #define KEY(key) ht_key(mrb, key)
588 hash_mark_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
590 mrb_gc_mark_value(mrb, key);
591 mrb_gc_mark_value(mrb, val);
596 mrb_gc_mark_hash(mrb_state *mrb, struct RHash *hash)
598 ht_foreach(mrb, hash->ht, hash_mark_i, NULL);
602 mrb_gc_mark_hash_size(mrb_state *mrb, struct RHash *hash)
604 if (!hash->ht) return 0;
605 return hash->ht->size*2;
609 mrb_gc_free_hash(mrb_state *mrb, struct RHash *hash)
611 ht_free(mrb, hash->ht);
615 mrb_hash_new(mrb_state *mrb)
619 h = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
622 return mrb_obj_value(h);
626 mrb_hash_new_capa(mrb_state *mrb, mrb_int capa)
630 h = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
631 /* preallocate hash table */
633 /* capacity ignored */
635 return mrb_obj_value(h);
638 static mrb_value mrb_hash_default(mrb_state *mrb, mrb_value hash);
639 static mrb_value hash_default(mrb_state *mrb, mrb_value hash, mrb_value key);
642 mrb_hash_init_copy(mrb_state *mrb, mrb_value self)
644 mrb_value orig = mrb_get_arg1(mrb);
647 mrb_value ifnone, vret;
649 if (mrb_obj_equal(mrb, self, orig)) return self;
650 if ((mrb_type(self) != mrb_type(orig)) || (mrb_obj_class(mrb, self) != mrb_obj_class(mrb, orig))) {
651 mrb_raise(mrb, E_TYPE_ERROR, "initialize_copy should take same class object");
654 orig_h = RHASH_TBL(self);
655 copy = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
656 copy->ht = ht_copy(mrb, orig_h);
658 if (MRB_RHASH_DEFAULT_P(self)) {
659 copy->flags |= MRB_HASH_DEFAULT;
661 if (MRB_RHASH_PROCDEFAULT_P(self)) {
662 copy->flags |= MRB_HASH_PROC_DEFAULT;
664 vret = mrb_obj_value(copy);
665 ifnone = RHASH_IFNONE(self);
666 if (!mrb_nil_p(ifnone)) {
667 mrb_iv_set(mrb, vret, mrb_intern_lit(mrb, "ifnone"), ifnone);
673 check_kdict_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
675 if (!mrb_symbol_p(key)) {
676 mrb_raise(mrb, E_ARGUMENT_ERROR, "keyword argument hash with non symbol keys");
682 mrb_hash_check_kdict(mrb_state *mrb, mrb_value self)
687 if (!t || t->size == 0) return;
688 ht_foreach(mrb, t, check_kdict_i, NULL);
692 mrb_hash_dup(mrb_state *mrb, mrb_value self)
697 orig_h = RHASH_TBL(self);
698 copy = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
699 copy->ht = orig_h ? ht_copy(mrb, orig_h) : NULL;
700 return mrb_obj_value(copy);
704 mrb_hash_get(mrb_state *mrb, mrb_value hash, mrb_value key)
709 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) {
713 mid = mrb_intern_lit(mrb, "default");
714 if (mrb_func_basic_p(mrb, hash, mid, mrb_hash_default)) {
715 return hash_default(mrb, hash, key);
717 /* xxx mrb_funcall_tailcall(mrb, hash, "default", 1, key); */
718 return mrb_funcall_argv(mrb, hash, mid, 1, &key);
722 mrb_hash_fetch(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value def)
726 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) {
734 mrb_hash_set(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value val)
736 mrb_hash_modify(mrb, hash);
739 ht_put(mrb, RHASH_TBL(hash), key, val);
740 mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), key);
741 mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), val);
746 mrb_hash_modify(mrb_state *mrb, mrb_value hash)
748 mrb_check_frozen(mrb, mrb_hash_ptr(hash));
749 if (!RHASH_TBL(hash)) {
750 RHASH_TBL(hash) = ht_new(mrb);
757 * Hash.new -> new_hash
758 * Hash.new(obj) -> new_hash
759 * Hash.new {|hash, key| block } -> new_hash
761 * Returns a new, empty hash. If this hash is subsequently accessed by
762 * a key that doesn't correspond to a hash entry, the value returned
763 * depends on the style of <code>new</code> used to create the hash. In
764 * the first form, the access returns <code>nil</code>. If
765 * <i>obj</i> is specified, this single object will be used for
766 * all <em>default values</em>. If a block is specified, it will be
767 * called with the hash object and the key, and should return the
768 * default value. It is the block's responsibility to store the value
769 * in the hash if required.
771 * h = Hash.new("Go Fish")
775 * h["c"] #=> "Go Fish"
776 * # The following alters the single default object
777 * h["c"].upcase! #=> "GO FISH"
778 * h["d"] #=> "GO FISH"
779 * h.keys #=> ["a", "b"]
781 * # While this creates a new default object each time
782 * h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
783 * h["c"] #=> "Go Fish: c"
784 * h["c"].upcase! #=> "GO FISH: C"
785 * h["d"] #=> "Go Fish: d"
786 * h.keys #=> ["c", "d"]
791 mrb_hash_init(mrb_state *mrb, mrb_value hash)
793 mrb_value block, ifnone;
796 ifnone = mrb_nil_value();
797 mrb_get_args(mrb, "&|o?", &block, &ifnone, &ifnone_p);
798 mrb_hash_modify(mrb, hash);
799 if (!mrb_nil_p(block)) {
801 mrb_argnum_error(mrb, 1, 0, 0);
803 RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
806 if (!mrb_nil_p(ifnone)) {
807 RHASH(hash)->flags |= MRB_HASH_DEFAULT;
808 mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
818 * Element Reference---Retrieves the <i>value</i> object corresponding
819 * to the <i>key</i> object. If not found, returns the default value (see
820 * <code>Hash::new</code> for details).
822 * h = { "a" => 100, "b" => 200 }
828 mrb_hash_aget(mrb_state *mrb, mrb_value self)
830 mrb_value key = mrb_get_arg1(mrb);
832 return mrb_hash_get(mrb, self, key);
836 hash_default(mrb_state *mrb, mrb_value hash, mrb_value key)
838 if (MRB_RHASH_DEFAULT_P(hash)) {
839 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
840 return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, key);
843 return RHASH_IFNONE(hash);
846 return mrb_nil_value();
852 * hsh.default(key=nil) -> obj
854 * Returns the default value, the value that would be returned by
855 * <i>hsh</i>[<i>key</i>] if <i>key</i> did not exist in <i>hsh</i>.
856 * See also <code>Hash::new</code> and <code>Hash#default=</code>.
858 * h = Hash.new #=> {}
860 * h.default(2) #=> nil
862 * h = Hash.new("cat") #=> {}
863 * h.default #=> "cat"
864 * h.default(2) #=> "cat"
866 * h = Hash.new {|h,k| h[k] = k.to_i*10} #=> {}
868 * h.default(2) #=> 20
872 mrb_hash_default(mrb_state *mrb, mrb_value hash)
877 mrb_get_args(mrb, "|o?", &key, &given);
878 if (MRB_RHASH_DEFAULT_P(hash)) {
879 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
880 if (!given) return mrb_nil_value();
881 return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, key);
884 return RHASH_IFNONE(hash);
887 return mrb_nil_value();
893 * hsh.default = obj -> obj
895 * Sets the default value, the value returned for a key that does not
896 * exist in the hash. It is not possible to set the default to a
897 * <code>Proc</code> that will be executed on each key lookup.
899 * h = { "a" => 100, "b" => 200 }
900 * h.default = "Go fish"
902 * h["z"] #=> "Go fish"
903 * # This doesn't do what you might hope...
904 * h.default = proc do |hash, key|
905 * hash[key] = key + key
907 * h[2] #=> #<Proc:0x401b3948@-:6>
908 * h["cat"] #=> #<Proc:0x401b3948@-:6>
912 mrb_hash_set_default(mrb_state *mrb, mrb_value hash)
914 mrb_value ifnone = mrb_get_arg1(mrb);
916 mrb_hash_modify(mrb, hash);
917 mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
918 RHASH(hash)->flags &= ~MRB_HASH_PROC_DEFAULT;
919 if (!mrb_nil_p(ifnone)) {
920 RHASH(hash)->flags |= MRB_HASH_DEFAULT;
923 RHASH(hash)->flags &= ~MRB_HASH_DEFAULT;
931 * hsh.default_proc -> anObject
933 * If <code>Hash::new</code> was invoked with a block, return that
934 * block, otherwise return <code>nil</code>.
936 * h = Hash.new {|h,k| h[k] = k*k } #=> {}
937 * p = h.default_proc #=> #<Proc:0x401b3d08@-:1>
940 * a #=> [nil, nil, 4]
945 mrb_hash_default_proc(mrb_state *mrb, mrb_value hash)
947 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
948 return RHASH_PROCDEFAULT(hash);
950 return mrb_nil_value();
955 * hsh.default_proc = proc_obj -> proc_obj
957 * Sets the default proc to be executed on each key lookup.
959 * h.default_proc = proc do |hash, key|
960 * hash[key] = key + key
963 * h["cat"] #=> "catcat"
967 mrb_hash_set_default_proc(mrb_state *mrb, mrb_value hash)
969 mrb_value ifnone = mrb_get_arg1(mrb);
971 mrb_hash_modify(mrb, hash);
972 mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
973 if (!mrb_nil_p(ifnone)) {
974 RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
975 RHASH(hash)->flags |= MRB_HASH_DEFAULT;
978 RHASH(hash)->flags &= ~MRB_HASH_DEFAULT;
979 RHASH(hash)->flags &= ~MRB_HASH_PROC_DEFAULT;
986 mrb_hash_delete_key(mrb_state *mrb, mrb_value hash, mrb_value key)
988 htable *t = RHASH_TBL(hash);
991 if (ht_del(mrb, t, key, &del_val)) {
996 return mrb_nil_value();
1000 mrb_hash_delete(mrb_state *mrb, mrb_value self)
1002 mrb_value key = mrb_get_arg1(mrb);
1004 mrb_hash_modify(mrb, self);
1005 return mrb_hash_delete_key(mrb, self, key);
1008 /* find first element in the hash table, and remove it. */
1010 ht_shift(mrb_state *mrb, htable *t, mrb_value *kp, mrb_value *vp)
1012 segment *seg = t->rootseg;
1016 for (i=0; i<seg->size; i++) {
1019 if (!seg->next && i >= t->last_len) {
1022 key = seg->e[i].key;
1023 if (mrb_undef_p(key)) continue;
1025 *vp = seg->e[i].val;
1026 /* delete element */
1027 seg->e[i].key = mrb_undef_value();
1038 * hsh.shift -> anArray or obj
1040 * Removes a key-value pair from <i>hsh</i> and returns it as the
1041 * two-item array <code>[</code> <i>key, value</i> <code>]</code>, or
1042 * the hash's default value if the hash is empty.
1044 * h = { 1 => "a", 2 => "b", 3 => "c" }
1045 * h.shift #=> [1, "a"]
1046 * h #=> {2=>"b", 3=>"c"}
1050 mrb_hash_shift(mrb_state *mrb, mrb_value hash)
1052 htable *t = RHASH_TBL(hash);
1054 mrb_hash_modify(mrb, hash);
1055 if (t && t->size > 0) {
1056 mrb_value del_key, del_val;
1058 ht_shift(mrb, t, &del_key, &del_val);
1059 mrb_gc_protect(mrb, del_key);
1060 mrb_gc_protect(mrb, del_val);
1061 return mrb_assoc_new(mrb, del_key, del_val);
1064 if (MRB_RHASH_DEFAULT_P(hash)) {
1065 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
1066 return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, mrb_nil_value());
1069 return RHASH_IFNONE(hash);
1072 return mrb_nil_value();
1080 * Removes all key-value pairs from `hsh`.
1082 * h = { "a" => 100, "b" => 200 } #=> {"a"=>100, "b"=>200}
1088 mrb_hash_clear(mrb_state *mrb, mrb_value hash)
1090 htable *t = RHASH_TBL(hash);
1092 mrb_hash_modify(mrb, hash);
1095 RHASH_TBL(hash) = NULL;
1104 * hsh[key] = value -> value
1105 * hsh.store(key, value) -> value
1107 * Element Assignment---Associates the value given by
1108 * <i>value</i> with the key given by <i>key</i>.
1109 * <i>key</i> should not have its value changed while it is in
1110 * use as a key (a <code>String</code> passed as a key will be
1111 * duplicated and frozen).
1113 * h = { "a" => 100, "b" => 200 }
1116 * h #=> {"a"=>9, "b"=>200, "c"=>4}
1120 mrb_hash_aset(mrb_state *mrb, mrb_value self)
1124 mrb_get_args(mrb, "oo", &key, &val);
1125 mrb_hash_set(mrb, self, key, val);
1130 mrb_hash_size(mrb_state *mrb, mrb_value hash)
1132 htable *t = RHASH_TBL(hash);
1142 * hsh.length -> fixnum
1143 * hsh.size -> fixnum
1145 * Returns the number of key-value pairs in the hash.
1147 * h = { "d" => 100, "a" => 200, "v" => 300, "e" => 400 }
1149 * h.delete("a") #=> 200
1153 mrb_hash_size_m(mrb_state *mrb, mrb_value self)
1155 mrb_int size = mrb_hash_size(mrb, self);
1156 return mrb_fixnum_value(size);
1160 mrb_hash_empty_p(mrb_state *mrb, mrb_value self)
1162 htable *t = RHASH_TBL(self);
1164 if (!t) return TRUE;
1165 return t->size == 0;
1171 * hsh.empty? -> true or false
1173 * Returns <code>true</code> if <i>hsh</i> contains no key-value pairs.
1175 * {}.empty? #=> true
1179 mrb_hash_empty_m(mrb_state *mrb, mrb_value self)
1181 return mrb_bool_value(mrb_hash_empty_p(mrb, self));
1185 hash_keys_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1187 mrb_ary_push(mrb, *(mrb_value*)p, key);
1196 * Returns a new array populated with the keys from this hash. See also
1197 * <code>Hash#values</code>.
1199 * h = { "a" => 100, "b" => 200, "c" => 300, "d" => 400 }
1200 * h.keys #=> ["a", "b", "c", "d"]
1205 mrb_hash_keys(mrb_state *mrb, mrb_value hash)
1207 htable *t = RHASH_TBL(hash);
1211 if (!t || (size = t->size) == 0)
1212 return mrb_ary_new(mrb);
1213 ary = mrb_ary_new_capa(mrb, size);
1214 ht_foreach(mrb, t, hash_keys_i, (void*)&ary);
1219 hash_vals_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1221 mrb_ary_push(mrb, *(mrb_value*)p, val);
1228 * hsh.values -> array
1230 * Returns a new array populated with the values from <i>hsh</i>. See
1231 * also <code>Hash#keys</code>.
1233 * h = { "a" => 100, "b" => 200, "c" => 300 }
1234 * h.values #=> [100, 200, 300]
1239 mrb_hash_values(mrb_state *mrb, mrb_value hash)
1241 htable *t = RHASH_TBL(hash);
1245 if (!t || (size = t->size) == 0)
1246 return mrb_ary_new(mrb);
1247 ary = mrb_ary_new_capa(mrb, size);
1248 ht_foreach(mrb, t, hash_vals_i, (void*)&ary);
1258 * hsh.has_key?(key) -> true or false
1259 * hsh.include?(key) -> true or false
1260 * hsh.key?(key) -> true or false
1261 * hsh.member?(key) -> true or false
1263 * Returns <code>true</code> if the given key is present in <i>hsh</i>.
1265 * h = { "a" => 100, "b" => 200 }
1266 * h.has_key?("a") #=> true
1267 * h.has_key?("z") #=> false
1272 mrb_hash_key_p(mrb_state *mrb, mrb_value hash, mrb_value key)
1276 t = RHASH_TBL(hash);
1277 if (ht_get(mrb, t, key, NULL)) {
1284 mrb_hash_has_key(mrb_state *mrb, mrb_value hash)
1286 mrb_value key = mrb_get_arg1(mrb);
1289 key_p = mrb_hash_key_p(mrb, hash, key);
1290 return mrb_bool_value(key_p);
1299 hash_has_value_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1301 struct has_v_arg *arg = (struct has_v_arg*)p;
1303 if (mrb_equal(mrb, arg->val, val)) {
1314 * hsh.has_value?(value) -> true or false
1315 * hsh.value?(value) -> true or false
1317 * Returns <code>true</code> if the given value is present for some key
1320 * h = { "a" => 100, "b" => 200 }
1321 * h.has_value?(100) #=> true
1322 * h.has_value?(999) #=> false
1326 mrb_hash_has_value(mrb_state *mrb, mrb_value hash)
1328 mrb_value val = mrb_get_arg1(mrb);
1329 struct has_v_arg arg;
1333 ht_foreach(mrb, RHASH_TBL(hash), hash_has_value_i, &arg);
1334 return mrb_bool_value(arg.found);
1338 merge_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
1340 htable *h1 = (htable*)data;
1342 ht_put(mrb, h1, key, val);
1347 mrb_hash_merge(mrb_state *mrb, mrb_value hash1, mrb_value hash2)
1351 mrb_hash_modify(mrb, hash1);
1352 hash2 = mrb_ensure_hash_type(mrb, hash2);
1353 h1 = RHASH_TBL(hash1);
1354 h2 = RHASH_TBL(hash2);
1358 RHASH_TBL(hash1) = ht_copy(mrb, h2);
1361 ht_foreach(mrb, h2, merge_i, h1);
1362 mrb_write_barrier(mrb, (struct RBasic*)RHASH(hash1));
1370 * Rebuilds the hash based on the current hash values for each key. If
1371 * values of key objects have changed since they were inserted, this
1372 * method will reindex <i>hsh</i>.
1374 * keys = (1..17).map{|n| [n]}
1377 * keys.each{|key| h[key] = key[0]}
1378 * h #=> { [1]=> 1, [2]=> 2, [3]=> 3, [4]=> 4, [5]=> 5, [6]=> 6, [7]=> 7,
1379 * [8]=> 8, [9]=> 9,[10]=>10,[11]=>11,[12]=>12,[13]=>13,[14]=>14,
1380 * [15]=>15,[16]=>16,[17]=>17}
1382 * k[0] = keys.size + 1
1383 * h #=> {[18]=> 1, [2]=> 2, [3]=> 3, [4]=> 4, [5]=> 5, [6]=> 6, [7]=> 7,
1384 * [8]=> 8, [9]=> 9,[10]=>10,[11]=>11,[12]=>12,[13]=>13,[14]=>14,
1385 * [15]=>15,[16]=>16,[17]=>17}
1391 mrb_hash_rehash(mrb_state *mrb, mrb_value self)
1393 ht_compact(mrb, RHASH_TBL(self));
1398 mrb_init_hash(mrb_state *mrb)
1402 mrb->hash_class = h = mrb_define_class(mrb, "Hash", mrb->object_class); /* 15.2.13 */
1403 MRB_SET_INSTANCE_TT(h, MRB_TT_HASH);
1405 mrb_define_method(mrb, h, "initialize_copy", mrb_hash_init_copy, MRB_ARGS_REQ(1));
1406 mrb_define_method(mrb, h, "[]", mrb_hash_aget, MRB_ARGS_REQ(1)); /* 15.2.13.4.2 */
1407 mrb_define_method(mrb, h, "[]=", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.3 */
1408 mrb_define_method(mrb, h, "clear", mrb_hash_clear, MRB_ARGS_NONE()); /* 15.2.13.4.4 */
1409 mrb_define_method(mrb, h, "default", mrb_hash_default, MRB_ARGS_OPT(1)); /* 15.2.13.4.5 */
1410 mrb_define_method(mrb, h, "default=", mrb_hash_set_default, MRB_ARGS_REQ(1)); /* 15.2.13.4.6 */
1411 mrb_define_method(mrb, h, "default_proc", mrb_hash_default_proc,MRB_ARGS_NONE()); /* 15.2.13.4.7 */
1412 mrb_define_method(mrb, h, "default_proc=", mrb_hash_set_default_proc,MRB_ARGS_REQ(1)); /* 15.2.13.4.7 */
1413 mrb_define_method(mrb, h, "__delete", mrb_hash_delete, MRB_ARGS_REQ(1)); /* core of 15.2.13.4.8 */
1414 mrb_define_method(mrb, h, "empty?", mrb_hash_empty_m, MRB_ARGS_NONE()); /* 15.2.13.4.12 */
1415 mrb_define_method(mrb, h, "has_key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.13 */
1416 mrb_define_method(mrb, h, "has_value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.14 */
1417 mrb_define_method(mrb, h, "include?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.15 */
1418 mrb_define_method(mrb, h, "initialize", mrb_hash_init, MRB_ARGS_OPT(1)|MRB_ARGS_BLOCK()); /* 15.2.13.4.16 */
1419 mrb_define_method(mrb, h, "key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.18 */
1420 mrb_define_method(mrb, h, "keys", mrb_hash_keys, MRB_ARGS_NONE()); /* 15.2.13.4.19 */
1421 mrb_define_method(mrb, h, "length", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.20 */
1422 mrb_define_method(mrb, h, "member?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.21 */
1423 mrb_define_method(mrb, h, "shift", mrb_hash_shift, MRB_ARGS_NONE()); /* 15.2.13.4.24 */
1424 mrb_define_method(mrb, h, "size", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.25 */
1425 mrb_define_method(mrb, h, "store", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.26 */
1426 mrb_define_method(mrb, h, "value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.27 */
1427 mrb_define_method(mrb, h, "values", mrb_hash_values, MRB_ARGS_NONE()); /* 15.2.13.4.28 */
1428 mrb_define_method(mrb, h, "rehash", mrb_hash_rehash, MRB_ARGS_NONE());