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)t ^ (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_type(b) != MRB_TT_SYMBOL) 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, 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;
230 if (t == NULL) return;
232 if (t->index && (size_t)t->size == t->index->size) {
237 for (i=0; i<seg->size; i++) {
238 mrb_value k = seg->e[i].key;
240 if (!seg->next && i >= t->last_len) {
243 if (mrb_undef_p(k)) { /* found delete key */
252 seg2->e[i2++] = seg->e[i];
253 if (i2 >= seg2->size) {
282 segment_alloc(mrb_state *mrb, segment *seg)
286 if (!seg) size = MRB_HT_INIT_SIZE;
288 size = seg->size*HT_SEG_INCREASE_RATIO + 1;
289 if (size > UINT16_MAX) size = UINT16_MAX;
292 seg = (segment*)mrb_malloc(mrb, sizeof(segment)+sizeof(struct segkv)*size);
299 /* Set the value for the key in the indexed table. */
301 ht_index_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val)
303 segindex *index = t->index;
304 size_t k, sp, step = 0, mask;
307 if (index->size >= UPPER_BOUND(index->capa)) {
308 /* need to expand table */
312 mask = HT_MASK(index);
314 k = ht_hash_func(mrb, t, key) & mask;
315 while (index->table[k]) {
316 mrb_value key2 = index->table[k]->key;
317 if (mrb_undef_p(key2)) {
318 if (sp == index->capa) sp = k;
320 else if (ht_hash_equal(mrb, t, key, key2)) {
321 index->table[k]->val = val;
324 k = (k+(++step)) & mask;
326 if (sp < index->capa) {
330 /* put the value at the last */
332 if (t->last_len < seg->size) {
333 index->table[k] = &seg->e[t->last_len++];
335 else { /* append a new segment */
336 seg->next = segment_alloc(mrb, seg);
341 index->table[k] = &seg->e[0];
343 index->table[k]->key = key;
344 index->table[k]->val = val;
349 /* Set the value for the key in the hash table. */
351 ht_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val)
354 mrb_int i, deleted = 0;
356 if (t == NULL) return;
358 ht_index_put(mrb, t, key, val);
363 for (i=0; i<seg->size; i++) {
364 mrb_value k = seg->e[i].key;
365 /* Found room in last segment after last_len */
366 if (!seg->next && i >= t->last_len) {
373 if (mrb_undef_p(k)) {
377 if (ht_hash_equal(mrb, t, k, key)) {
386 /* Compact if last segment has room */
387 if (deleted > 0 && deleted > MRB_HT_INIT_SIZE) {
392 /* check if thre's room after compaction */
393 if (t->lastseg && t->last_len < t->lastseg->size) {
398 /* append new segment */
399 seg = segment_alloc(mrb, t->lastseg);
401 if (t->rootseg == NULL) {
405 t->lastseg->next = seg;
412 if (t->index == NULL && t->size > MRB_HT_INIT_SIZE*4) {
417 /* Get a value for a key from the indexed table. */
419 ht_index_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
421 segindex *index = t->index;
422 size_t mask = HT_MASK(index);
423 size_t k = ht_hash_func(mrb, t, key) & mask;
426 while (index->table[k]) {
427 mrb_value key2 = index->table[k]->key;
428 if (!mrb_undef_p(key2) && ht_hash_equal(mrb, t, key, key2)) {
429 if (vp) *vp = index->table[k]->val;
432 k = (k+(++step)) & mask;
437 /* Get a value for a key from the hash table. */
439 ht_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
444 if (t == NULL) return FALSE;
446 return ht_index_get(mrb, t, key, vp);
451 for (i=0; i<seg->size; i++) {
452 mrb_value k = seg->e[i].key;
454 if (!seg->next && i >= t->last_len) {
457 if (mrb_undef_p(k)) continue;
458 if (ht_hash_equal(mrb, t, k, key)) {
459 if (vp) *vp = seg->e[i].val;
468 /* Deletes the value for the symbol from the hash table. */
469 /* Deletion is done by overwriting keys by `undef`. */
471 ht_del(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
476 if (t == NULL) return FALSE;
479 for (i=0; i<seg->size; i++) {
482 if (!seg->next && i >= t->last_len) {
486 key2 = seg->e[i].key;
487 if (!mrb_undef_p(key2) && ht_hash_equal(mrb, t, key, key2)) {
488 if (vp) *vp = seg->e[i].val;
489 seg->e[i].key = mrb_undef_value();
499 /* Iterates over the hash table. */
501 ht_foreach(mrb_state *mrb, htable *t, mrb_hash_foreach_func *func, void *p)
506 if (t == NULL) return;
509 for (i=0; i<seg->size; i++) {
510 /* no value in last segment after last_len */
511 if (!seg->next && i >= t->last_len) {
514 if (mrb_undef_p(seg->e[i].key)) continue;
515 if ((*func)(mrb, seg->e[i].key, seg->e[i].val, p) != 0)
522 /* Iterates over the hash table. */
524 mrb_hash_foreach(mrb_state *mrb, struct RHash *hash, mrb_hash_foreach_func *func, void *p)
526 ht_foreach(mrb, hash->ht, func, p);
529 /* Copy the hash table. */
531 ht_copy(mrb_state *mrb, htable *t)
539 if (t->size == 0) return t2;
542 for (i=0; i<seg->size; i++) {
543 mrb_value key = seg->e[i].key;
544 mrb_value val = seg->e[i].val;
546 if ((seg->next == NULL) && (i >= t->last_len)) {
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)
647 mrb_value ifnone, vret;
649 mrb_get_args(mrb, "o", &orig);
650 if (mrb_obj_equal(mrb, self, orig)) return self;
651 if ((mrb_type(self) != mrb_type(orig)) || (mrb_obj_class(mrb, self) != mrb_obj_class(mrb, orig))) {
652 mrb_raise(mrb, E_TYPE_ERROR, "initialize_copy should take same class object");
655 orig_h = RHASH_TBL(self);
656 copy = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
657 copy->ht = ht_copy(mrb, orig_h);
659 if (MRB_RHASH_DEFAULT_P(self)) {
660 copy->flags |= MRB_HASH_DEFAULT;
662 if (MRB_RHASH_PROCDEFAULT_P(self)) {
663 copy->flags |= MRB_HASH_PROC_DEFAULT;
665 vret = mrb_obj_value(copy);
666 ifnone = RHASH_IFNONE(self);
667 if (!mrb_nil_p(ifnone)) {
668 mrb_iv_set(mrb, vret, mrb_intern_lit(mrb, "ifnone"), ifnone);
674 check_kdict_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
676 if (!mrb_symbol_p(key)) {
677 mrb_raise(mrb, E_ARGUMENT_ERROR, "keyword argument hash with non symbol keys");
683 mrb_hash_check_kdict(mrb_state *mrb, mrb_value self)
688 if (!t || t->size == 0) return;
689 ht_foreach(mrb, t, check_kdict_i, NULL);
693 mrb_hash_dup(mrb_state *mrb, mrb_value self)
698 orig_h = RHASH_TBL(self);
699 copy = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
700 copy->ht = orig_h ? ht_copy(mrb, orig_h) : NULL;
701 return mrb_obj_value(copy);
705 mrb_hash_get(mrb_state *mrb, mrb_value hash, mrb_value key)
710 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) {
714 mid = mrb_intern_lit(mrb, "default");
715 if (mrb_func_basic_p(mrb, hash, mid, mrb_hash_default)) {
716 return hash_default(mrb, hash, key);
718 /* xxx mrb_funcall_tailcall(mrb, hash, "default", 1, key); */
719 return mrb_funcall_argv(mrb, hash, mid, 1, &key);
723 mrb_hash_fetch(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value def)
727 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) {
735 mrb_hash_set(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value val)
737 mrb_hash_modify(mrb, hash);
740 ht_put(mrb, RHASH_TBL(hash), key, val);
741 mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), key);
742 mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), val);
747 mrb_hash_modify(mrb_state *mrb, mrb_value hash)
749 if (MRB_FROZEN_P(mrb_hash_ptr(hash))) {
750 mrb_raise(mrb, E_FROZEN_ERROR, "can't modify frozen hash");
753 if (!RHASH_TBL(hash)) {
754 RHASH_TBL(hash) = ht_new(mrb);
761 * Hash.new -> new_hash
762 * Hash.new(obj) -> new_hash
763 * Hash.new {|hash, key| block } -> new_hash
765 * Returns a new, empty hash. If this hash is subsequently accessed by
766 * a key that doesn't correspond to a hash entry, the value returned
767 * depends on the style of <code>new</code> used to create the hash. In
768 * the first form, the access returns <code>nil</code>. If
769 * <i>obj</i> is specified, this single object will be used for
770 * all <em>default values</em>. If a block is specified, it will be
771 * called with the hash object and the key, and should return the
772 * default value. It is the block's responsibility to store the value
773 * in the hash if required.
775 * h = Hash.new("Go Fish")
779 * h["c"] #=> "Go Fish"
780 * # The following alters the single default object
781 * h["c"].upcase! #=> "GO FISH"
782 * h["d"] #=> "GO FISH"
783 * h.keys #=> ["a", "b"]
785 * # While this creates a new default object each time
786 * h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
787 * h["c"] #=> "Go Fish: c"
788 * h["c"].upcase! #=> "GO FISH: C"
789 * h["d"] #=> "Go Fish: d"
790 * h.keys #=> ["c", "d"]
795 mrb_hash_init(mrb_state *mrb, mrb_value hash)
797 mrb_value block, ifnone;
800 ifnone = mrb_nil_value();
801 mrb_get_args(mrb, "&|o?", &block, &ifnone, &ifnone_p);
802 mrb_hash_modify(mrb, hash);
803 if (!mrb_nil_p(block)) {
805 mrb_raise(mrb, E_ARGUMENT_ERROR, "wrong number of arguments");
807 RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
810 if (!mrb_nil_p(ifnone)) {
811 RHASH(hash)->flags |= MRB_HASH_DEFAULT;
812 mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
822 * Element Reference---Retrieves the <i>value</i> object corresponding
823 * to the <i>key</i> object. If not found, returns the default value (see
824 * <code>Hash::new</code> for details).
826 * h = { "a" => 100, "b" => 200 }
832 mrb_hash_aget(mrb_state *mrb, mrb_value self)
836 mrb_get_args(mrb, "o", &key);
837 return mrb_hash_get(mrb, self, key);
841 hash_default(mrb_state *mrb, mrb_value hash, mrb_value key)
843 if (MRB_RHASH_DEFAULT_P(hash)) {
844 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
845 return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, key);
848 return RHASH_IFNONE(hash);
851 return mrb_nil_value();
857 * hsh.default(key=nil) -> obj
859 * Returns the default value, the value that would be returned by
860 * <i>hsh</i>[<i>key</i>] if <i>key</i> did not exist in <i>hsh</i>.
861 * See also <code>Hash::new</code> and <code>Hash#default=</code>.
863 * h = Hash.new #=> {}
865 * h.default(2) #=> nil
867 * h = Hash.new("cat") #=> {}
868 * h.default #=> "cat"
869 * h.default(2) #=> "cat"
871 * h = Hash.new {|h,k| h[k] = k.to_i*10} #=> {}
873 * h.default(2) #=> 20
877 mrb_hash_default(mrb_state *mrb, mrb_value hash)
882 mrb_get_args(mrb, "|o?", &key, &given);
883 if (MRB_RHASH_DEFAULT_P(hash)) {
884 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
885 if (!given) return mrb_nil_value();
886 return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, key);
889 return RHASH_IFNONE(hash);
892 return mrb_nil_value();
898 * hsh.default = obj -> obj
900 * Sets the default value, the value returned for a key that does not
901 * exist in the hash. It is not possible to set the default to a
902 * <code>Proc</code> that will be executed on each key lookup.
904 * h = { "a" => 100, "b" => 200 }
905 * h.default = "Go fish"
907 * h["z"] #=> "Go fish"
908 * # This doesn't do what you might hope...
909 * h.default = proc do |hash, key|
910 * hash[key] = key + key
912 * h[2] #=> #<Proc:0x401b3948@-:6>
913 * h["cat"] #=> #<Proc:0x401b3948@-:6>
917 mrb_hash_set_default(mrb_state *mrb, mrb_value hash)
921 mrb_get_args(mrb, "o", &ifnone);
922 mrb_hash_modify(mrb, hash);
923 mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
924 RHASH(hash)->flags &= ~MRB_HASH_PROC_DEFAULT;
925 if (!mrb_nil_p(ifnone)) {
926 RHASH(hash)->flags |= MRB_HASH_DEFAULT;
929 RHASH(hash)->flags &= ~MRB_HASH_DEFAULT;
937 * hsh.default_proc -> anObject
939 * If <code>Hash::new</code> was invoked with a block, return that
940 * block, otherwise return <code>nil</code>.
942 * h = Hash.new {|h,k| h[k] = k*k } #=> {}
943 * p = h.default_proc #=> #<Proc:0x401b3d08@-:1>
946 * a #=> [nil, nil, 4]
951 mrb_hash_default_proc(mrb_state *mrb, mrb_value hash)
953 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
954 return RHASH_PROCDEFAULT(hash);
956 return mrb_nil_value();
961 * hsh.default_proc = proc_obj -> proc_obj
963 * Sets the default proc to be executed on each key lookup.
965 * h.default_proc = proc do |hash, key|
966 * hash[key] = key + key
969 * h["cat"] #=> "catcat"
973 mrb_hash_set_default_proc(mrb_state *mrb, mrb_value hash)
977 mrb_get_args(mrb, "o", &ifnone);
978 mrb_hash_modify(mrb, hash);
979 mrb_iv_set(mrb, hash, mrb_intern_lit(mrb, "ifnone"), ifnone);
980 if (!mrb_nil_p(ifnone)) {
981 RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
982 RHASH(hash)->flags |= MRB_HASH_DEFAULT;
985 RHASH(hash)->flags &= ~MRB_HASH_DEFAULT;
986 RHASH(hash)->flags &= ~MRB_HASH_PROC_DEFAULT;
993 mrb_hash_delete_key(mrb_state *mrb, mrb_value hash, mrb_value key)
995 htable *t = RHASH_TBL(hash);
998 if (ht_del(mrb, t, key, &del_val)) {
1003 return mrb_nil_value();
1007 mrb_hash_delete(mrb_state *mrb, mrb_value self)
1011 mrb_get_args(mrb, "o", &key);
1012 mrb_hash_modify(mrb, self);
1013 return mrb_hash_delete_key(mrb, self, key);
1016 /* find first element in the hash table, and remove it. */
1018 ht_shift(mrb_state *mrb, htable *t, mrb_value *kp, mrb_value *vp)
1020 segment *seg = t->rootseg;
1024 for (i=0; i<seg->size; i++) {
1027 if (!seg->next && i >= t->last_len) {
1030 key = seg->e[i].key;
1031 if (mrb_undef_p(key)) continue;
1033 *vp = seg->e[i].val;
1034 /* delete element */
1035 seg->e[i].key = mrb_undef_value();
1046 * hsh.shift -> anArray or obj
1048 * Removes a key-value pair from <i>hsh</i> and returns it as the
1049 * two-item array <code>[</code> <i>key, value</i> <code>]</code>, or
1050 * the hash's default value if the hash is empty.
1052 * h = { 1 => "a", 2 => "b", 3 => "c" }
1053 * h.shift #=> [1, "a"]
1054 * h #=> {2=>"b", 3=>"c"}
1058 mrb_hash_shift(mrb_state *mrb, mrb_value hash)
1060 htable *t = RHASH_TBL(hash);
1062 mrb_hash_modify(mrb, hash);
1063 if (t && t->size > 0) {
1064 mrb_value del_key, del_val;
1066 ht_shift(mrb, t, &del_key, &del_val);
1067 mrb_gc_protect(mrb, del_key);
1068 mrb_gc_protect(mrb, del_val);
1069 return mrb_assoc_new(mrb, del_key, del_val);
1072 if (MRB_RHASH_DEFAULT_P(hash)) {
1073 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
1074 return mrb_funcall(mrb, RHASH_PROCDEFAULT(hash), "call", 2, hash, mrb_nil_value());
1077 return RHASH_IFNONE(hash);
1080 return mrb_nil_value();
1088 * Removes all key-value pairs from `hsh`.
1090 * h = { "a" => 100, "b" => 200 } #=> {"a"=>100, "b"=>200}
1096 mrb_hash_clear(mrb_state *mrb, mrb_value hash)
1098 htable *t = RHASH_TBL(hash);
1100 mrb_hash_modify(mrb, hash);
1103 RHASH_TBL(hash) = NULL;
1112 * hsh[key] = value -> value
1113 * hsh.store(key, value) -> value
1115 * Element Assignment---Associates the value given by
1116 * <i>value</i> with the key given by <i>key</i>.
1117 * <i>key</i> should not have its value changed while it is in
1118 * use as a key (a <code>String</code> passed as a key will be
1119 * duplicated and frozen).
1121 * h = { "a" => 100, "b" => 200 }
1124 * h #=> {"a"=>9, "b"=>200, "c"=>4}
1128 mrb_hash_aset(mrb_state *mrb, mrb_value self)
1132 mrb_get_args(mrb, "oo", &key, &val);
1133 mrb_hash_set(mrb, self, key, val);
1138 mrb_hash_size(mrb_state *mrb, mrb_value hash)
1140 htable *t = RHASH_TBL(hash);
1150 * hsh.length -> fixnum
1151 * hsh.size -> fixnum
1153 * Returns the number of key-value pairs in the hash.
1155 * h = { "d" => 100, "a" => 200, "v" => 300, "e" => 400 }
1157 * h.delete("a") #=> 200
1161 mrb_hash_size_m(mrb_state *mrb, mrb_value self)
1163 mrb_int size = mrb_hash_size(mrb, self);
1164 return mrb_fixnum_value(size);
1168 mrb_hash_empty_p(mrb_state *mrb, mrb_value self)
1170 htable *t = RHASH_TBL(self);
1172 if (!t) return TRUE;
1173 return t->size == 0;
1179 * hsh.empty? -> true or false
1181 * Returns <code>true</code> if <i>hsh</i> contains no key-value pairs.
1183 * {}.empty? #=> true
1187 mrb_hash_empty_m(mrb_state *mrb, mrb_value self)
1189 return mrb_bool_value(mrb_hash_empty_p(mrb, self));
1193 hash_keys_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1195 mrb_ary_push(mrb, *(mrb_value*)p, key);
1204 * Returns a new array populated with the keys from this hash. See also
1205 * <code>Hash#values</code>.
1207 * h = { "a" => 100, "b" => 200, "c" => 300, "d" => 400 }
1208 * h.keys #=> ["a", "b", "c", "d"]
1213 mrb_hash_keys(mrb_state *mrb, mrb_value hash)
1215 htable *t = RHASH_TBL(hash);
1219 if (!t || (size = t->size) == 0)
1220 return mrb_ary_new(mrb);
1221 ary = mrb_ary_new_capa(mrb, size);
1222 ht_foreach(mrb, t, hash_keys_i, (void*)&ary);
1227 hash_vals_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1229 mrb_ary_push(mrb, *(mrb_value*)p, val);
1236 * hsh.values -> array
1238 * Returns a new array populated with the values from <i>hsh</i>. See
1239 * also <code>Hash#keys</code>.
1241 * h = { "a" => 100, "b" => 200, "c" => 300 }
1242 * h.values #=> [100, 200, 300]
1247 mrb_hash_values(mrb_state *mrb, mrb_value hash)
1249 htable *t = RHASH_TBL(hash);
1253 if (!t || (size = t->size) == 0)
1254 return mrb_ary_new(mrb);
1255 ary = mrb_ary_new_capa(mrb, size);
1256 ht_foreach(mrb, t, hash_vals_i, (void*)&ary);
1266 * hsh.has_key?(key) -> true or false
1267 * hsh.include?(key) -> true or false
1268 * hsh.key?(key) -> true or false
1269 * hsh.member?(key) -> true or false
1271 * Returns <code>true</code> if the given key is present in <i>hsh</i>.
1273 * h = { "a" => 100, "b" => 200 }
1274 * h.has_key?("a") #=> true
1275 * h.has_key?("z") #=> false
1280 mrb_hash_key_p(mrb_state *mrb, mrb_value hash, mrb_value key)
1284 t = RHASH_TBL(hash);
1285 if (ht_get(mrb, t, key, NULL)) {
1292 mrb_hash_has_key(mrb_state *mrb, mrb_value hash)
1297 mrb_get_args(mrb, "o", &key);
1298 key_p = mrb_hash_key_p(mrb, hash, key);
1299 return mrb_bool_value(key_p);
1308 hash_has_value_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1310 struct has_v_arg *arg = (struct has_v_arg*)p;
1312 if (mrb_equal(mrb, arg->val, val)) {
1323 * hsh.has_value?(value) -> true or false
1324 * hsh.value?(value) -> true or false
1326 * Returns <code>true</code> if the given value is present for some key
1329 * h = { "a" => 100, "b" => 200 }
1330 * h.has_value?(100) #=> true
1331 * h.has_value?(999) #=> false
1335 mrb_hash_has_value(mrb_state *mrb, mrb_value hash)
1338 struct has_v_arg arg;
1340 mrb_get_args(mrb, "o", &val);
1343 ht_foreach(mrb, RHASH_TBL(hash), hash_has_value_i, &arg);
1344 return mrb_bool_value(arg.found);
1348 merge_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
1350 htable *h1 = (htable*)data;
1352 ht_put(mrb, h1, key, val);
1357 mrb_hash_merge(mrb_state *mrb, mrb_value hash1, mrb_value hash2)
1361 mrb_hash_modify(mrb, hash1);
1362 hash2 = mrb_ensure_hash_type(mrb, hash2);
1363 h1 = RHASH_TBL(hash1);
1364 h2 = RHASH_TBL(hash2);
1368 RHASH_TBL(hash1) = ht_copy(mrb, h2);
1371 ht_foreach(mrb, h2, merge_i, h1);
1372 mrb_write_barrier(mrb, (struct RBasic*)RHASH(hash1));
1380 * Rebuilds the hash based on the current hash values for each key. If
1381 * values of key objects have changed since they were inserted, this
1382 * method will reindex <i>hsh</i>.
1384 * h = {"AAA" => "b"}
1386 * h.rehash #=> {"AA"=>"b"}
1390 mrb_hash_rehash(mrb_state *mrb, mrb_value self)
1392 ht_compact(mrb, RHASH_TBL(self));
1397 mrb_init_hash(mrb_state *mrb)
1401 mrb->hash_class = h = mrb_define_class(mrb, "Hash", mrb->object_class); /* 15.2.13 */
1402 MRB_SET_INSTANCE_TT(h, MRB_TT_HASH);
1404 mrb_define_method(mrb, h, "initialize_copy", mrb_hash_init_copy, MRB_ARGS_REQ(1));
1405 mrb_define_method(mrb, h, "[]", mrb_hash_aget, MRB_ARGS_REQ(1)); /* 15.2.13.4.2 */
1406 mrb_define_method(mrb, h, "[]=", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.3 */
1407 mrb_define_method(mrb, h, "clear", mrb_hash_clear, MRB_ARGS_NONE()); /* 15.2.13.4.4 */
1408 mrb_define_method(mrb, h, "default", mrb_hash_default, MRB_ARGS_ANY()); /* 15.2.13.4.5 */
1409 mrb_define_method(mrb, h, "default=", mrb_hash_set_default, MRB_ARGS_REQ(1)); /* 15.2.13.4.6 */
1410 mrb_define_method(mrb, h, "default_proc", mrb_hash_default_proc,MRB_ARGS_NONE()); /* 15.2.13.4.7 */
1411 mrb_define_method(mrb, h, "default_proc=", mrb_hash_set_default_proc,MRB_ARGS_REQ(1)); /* 15.2.13.4.7 */
1412 mrb_define_method(mrb, h, "__delete", mrb_hash_delete, MRB_ARGS_REQ(1)); /* core of 15.2.13.4.8 */
1413 mrb_define_method(mrb, h, "empty?", mrb_hash_empty_m, MRB_ARGS_NONE()); /* 15.2.13.4.12 */
1414 mrb_define_method(mrb, h, "has_key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.13 */
1415 mrb_define_method(mrb, h, "has_value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.14 */
1416 mrb_define_method(mrb, h, "include?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.15 */
1417 mrb_define_method(mrb, h, "initialize", mrb_hash_init, MRB_ARGS_OPT(1)); /* 15.2.13.4.16 */
1418 mrb_define_method(mrb, h, "key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.18 */
1419 mrb_define_method(mrb, h, "keys", mrb_hash_keys, MRB_ARGS_NONE()); /* 15.2.13.4.19 */
1420 mrb_define_method(mrb, h, "length", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.20 */
1421 mrb_define_method(mrb, h, "member?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.21 */
1422 mrb_define_method(mrb, h, "shift", mrb_hash_shift, MRB_ARGS_NONE()); /* 15.2.13.4.24 */
1423 mrb_define_method(mrb, h, "size", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.25 */
1424 mrb_define_method(mrb, h, "store", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.26 */
1425 mrb_define_method(mrb, h, "value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.27 */
1426 mrb_define_method(mrb, h, "values", mrb_hash_values, MRB_ARGS_NONE()); /* 15.2.13.4.28 */
1427 mrb_define_method(mrb, h, "rehash", mrb_hash_rehash, MRB_ARGS_NONE());