1 /*
2 ** hash.c - Hash class
3 **
4 ** See Copyright Notice in mruby.h
5 */
6
7 #include <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>
13
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);
17 #endif
18
19 #ifndef MRB_HT_INIT_SIZE
20 #define MRB_HT_INIT_SIZE 4
21 #endif
22 #define HT_SEG_INCREASE_RATIO 6 / 5
23
24 struct segkv {
25 mrb_value key;
26 mrb_value val;
27 };
28
29 typedef struct segment {
30 uint16_t size;
31 struct segment *next;
32 struct segkv e[];
33 } segment;
34
35 typedef struct segindex {
36 size_t size;
37 size_t capa;
38 struct segkv *table[];
39 } segindex;
40
41 /* hash table structure */
42 typedef struct htable {
43 segment *rootseg;
44 segment *lastseg;
45 mrb_int size;
46 uint16_t last_len;
47 segindex *index;
48 } htable;
49
50 static /* inline */ size_t
ht_hash_func(mrb_state * mrb,htable * t,mrb_value key)51 ht_hash_func(mrb_state *mrb, htable *t, mrb_value key)
52 {
53 enum mrb_vtype tt = mrb_type(key);
54 mrb_value hv;
55 size_t h;
56 segindex *index = t->index;
57 size_t capa = index ? index->capa : 0;
58
59 switch (tt) {
60 case MRB_TT_STRING:
61 h = mrb_str_hash(mrb, key);
62 break;
63
64 case MRB_TT_TRUE:
65 case MRB_TT_FALSE:
66 case MRB_TT_SYMBOL:
67 case MRB_TT_FIXNUM:
68 #ifndef MRB_WITHOUT_FLOAT
69 case MRB_TT_FLOAT:
70 #endif
71 h = (size_t)mrb_obj_id(key);
72 break;
73
74 default:
75 hv = mrb_funcall(mrb, key, "hash", 0);
76 h = (size_t)t ^ (size_t)mrb_fixnum(hv);
77 break;
78 }
79 if (index && (index != t->index || capa != index->capa)) {
80 mrb_raise(mrb, E_RUNTIME_ERROR, "hash modified");
81 }
82 return ((h)^((h)<<2)^((h)>>2));
83 }
84
85 static inline mrb_bool
ht_hash_equal(mrb_state * mrb,htable * t,mrb_value a,mrb_value b)86 ht_hash_equal(mrb_state *mrb, htable *t, mrb_value a, mrb_value b)
87 {
88 enum mrb_vtype tt = mrb_type(a);
89
90 switch (tt) {
91 case MRB_TT_STRING:
92 return mrb_str_equal(mrb, a, b);
93
94 case MRB_TT_SYMBOL:
95 if (mrb_type(b) != MRB_TT_SYMBOL) return FALSE;
96 return mrb_symbol(a) == mrb_symbol(b);
97
98 case MRB_TT_FIXNUM:
99 switch (mrb_type(b)) {
100 case MRB_TT_FIXNUM:
101 return mrb_fixnum(a) == mrb_fixnum(b);
102 #ifndef MRB_WITHOUT_FLOAT
103 case MRB_TT_FLOAT:
104 return (mrb_float)mrb_fixnum(a) == mrb_float(b);
105 #endif
106 default:
107 return FALSE;
108 }
109
110 #ifndef MRB_WITHOUT_FLOAT
111 case MRB_TT_FLOAT:
112 switch (mrb_type(b)) {
113 case MRB_TT_FIXNUM:
114 return mrb_float(a) == (mrb_float)mrb_fixnum(b);
115 case MRB_TT_FLOAT:
116 return mrb_float(a) == mrb_float(b);
117 default:
118 return FALSE;
119 }
120 #endif
121
122 default:
123 {
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");
129 }
130 return eql;
131 }
132 }
133 }
134
135 /* Creates the hash table. */
136 static htable*
ht_new(mrb_state * mrb)137 ht_new(mrb_state *mrb)
138 {
139 htable *t;
140
141 t = (htable*)mrb_malloc(mrb, sizeof(htable));
142 t->size = 0;
143 t->rootseg = NULL;
144 t->lastseg = NULL;
145 t->last_len = 0;
146 t->index = NULL;
147
148 return t;
149 }
150
151 #define power2(v) do { \
152 v--;\
153 v |= v >> 1;\
154 v |= v >> 2;\
155 v |= v >> 4;\
156 v |= v >> 8;\
157 v |= v >> 16;\
158 v++;\
159 } while (0)
160
161 #ifndef UPPER_BOUND
162 #define UPPER_BOUND(x) ((x)>>2|(x)>>1)
163 #endif
164
165 #define HT_MASK(index) ((index->capa)-1)
166
167 /* Build index for the hash table */
168 static void
ht_index(mrb_state * mrb,htable * t)169 ht_index(mrb_state *mrb, htable *t)
170 {
171 size_t size = (size_t)t->size;
172 size_t mask;
173 segindex *index = t->index;
174 segment *seg;
175 size_t i;
176
177 /* allocate index table */
178 if (index && index->size >= UPPER_BOUND(index->capa)) {
179 size = index->capa+1;
180 }
181 power2(size);
182 if (!index || index->capa < size) {
183 index = (segindex*)mrb_realloc_simple(mrb, index, sizeof(segindex)+sizeof(struct segkv*)*size);
184 if (index == NULL) {
185 mrb_free(mrb, index);
186 t->index = NULL;
187 return;
188 }
189 t->index = index;
190 }
191 index->size = t->size;
192 index->capa = size;
193 for (i=0; i<size; i++) {
194 index->table[i] = NULL;
195 }
196
197 /* rebuld index */
198 mask = HT_MASK(index);
199 seg = t->rootseg;
200 while (seg) {
201 for (i=0; i<seg->size; i++) {
202 mrb_value key;
203 size_t k, step = 0;
204
205 if (!seg->next && i >= (size_t)t->last_len) {
206 return;
207 }
208 key = seg->e[i].key;
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;
213 }
214 index->table[k] = &seg->e[i];
215 }
216 seg = seg->next;
217 }
218 }
219
220 /* Compacts the hash table removing deleted entries. */
221 static void
ht_compact(mrb_state * mrb,htable * t)222 ht_compact(mrb_state *mrb, htable *t)
223 {
224 segment *seg;
225 mrb_int i;
226 segment *seg2 = NULL;
227 mrb_int i2;
228 mrb_int size = 0;
229
230 if (t == NULL) return;
231 seg = t->rootseg;
232 if (t->index && (size_t)t->size == t->index->size) {
233 ht_index(mrb, t);
234 return;
235 }
236 while (seg) {
237 for (i=0; i<seg->size; i++) {
238 mrb_value k = seg->e[i].key;
239
240 if (!seg->next && i >= t->last_len) {
241 goto exit;
242 }
243 if (mrb_undef_p(k)) { /* found delete key */
244 if (seg2 == NULL) {
245 seg2 = seg;
246 i2 = i;
247 }
248 }
249 else {
250 size++;
251 if (seg2 != NULL) {
252 seg2->e[i2++] = seg->e[i];
253 if (i2 >= seg2->size) {
254 seg2 = seg2->next;
255 i2 = 0;
256 }
257 }
258 }
259 }
260 seg = seg->next;
261 }
262 exit:
263 /* reached at end */
264 t->size = size;
265 if (seg2) {
266 seg = seg2->next;
267 seg2->next = NULL;
268 t->last_len = i2;
269 t->lastseg = seg2;
270 while (seg) {
271 seg2 = seg->next;
272 mrb_free(mrb, seg);
273 seg = seg2;
274 }
275 }
276 if (t->index) {
277 ht_index(mrb, t);
278 }
279 }
280
281 static segment*
segment_alloc(mrb_state * mrb,segment * seg)282 segment_alloc(mrb_state *mrb, segment *seg)
283 {
284 uint32_t size;
285
286 if (!seg) size = MRB_HT_INIT_SIZE;
287 else {
288 size = seg->size*HT_SEG_INCREASE_RATIO + 1;
289 if (size > UINT16_MAX) size = UINT16_MAX;
290 }
291
292 seg = (segment*)mrb_malloc(mrb, sizeof(segment)+sizeof(struct segkv)*size);
293 seg->size = size;
294 seg->next = NULL;
295
296 return seg;
297 }
298
299 /* Set the value for the key in the indexed table. */
300 static void
ht_index_put(mrb_state * mrb,htable * t,mrb_value key,mrb_value val)301 ht_index_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val)
302 {
303 segindex *index = t->index;
304 size_t k, sp, step = 0, mask;
305 segment *seg;
306
307 if (index->size >= UPPER_BOUND(index->capa)) {
308 /* need to expand table */
309 ht_compact(mrb, t);
310 index = t->index;
311 }
312 mask = HT_MASK(index);
313 sp = index->capa;
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;
319 }
320 else if (ht_hash_equal(mrb, t, key, key2)) {
321 index->table[k]->val = val;
322 return;
323 }
324 k = (k+(++step)) & mask;
325 }
326 if (sp < index->capa) {
327 k = sp;
328 }
329
330 /* put the value at the last */
331 seg = t->lastseg;
332 if (t->last_len < seg->size) {
333 index->table[k] = &seg->e[t->last_len++];
334 }
335 else { /* append a new segment */
336 seg->next = segment_alloc(mrb, seg);
337 seg = seg->next;
338 seg->next = NULL;
339 t->lastseg = seg;
340 t->last_len = 1;
341 index->table[k] = &seg->e[0];
342 }
343 index->table[k]->key = key;
344 index->table[k]->val = val;
345 index->size++;
346 t->size++;
347 }
348
349 /* Set the value for the key in the hash table. */
350 static void
ht_put(mrb_state * mrb,htable * t,mrb_value key,mrb_value val)351 ht_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val)
352 {
353 segment *seg;
354 mrb_int i, deleted = 0;
355
356 if (t == NULL) return;
357 if (t->index) {
358 ht_index_put(mrb, t, key, val);
359 return;
360 }
361 seg = t->rootseg;
362 while (seg) {
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) {
367 seg->e[i].key = key;
368 seg->e[i].val = val;
369 t->last_len = i+1;
370 t->size++;
371 return;
372 }
373 if (mrb_undef_p(k)) {
374 deleted++;
375 continue;
376 }
377 if (ht_hash_equal(mrb, t, k, key)) {
378 seg->e[i].val = val;
379 return;
380 }
381 }
382 seg = seg->next;
383 }
384 /* Not found */
385
386 /* Compact if last segment has room */
387 if (deleted > 0 && deleted > MRB_HT_INIT_SIZE) {
388 ht_compact(mrb, t);
389 }
390 t->size++;
391
392 /* check if thre's room after compaction */
393 if (t->lastseg && t->last_len < t->lastseg->size) {
394 seg = t->lastseg;
395 i = t->last_len;
396 }
397 else {
398 /* append new segment */
399 seg = segment_alloc(mrb, t->lastseg);
400 i = 0;
401 if (t->rootseg == NULL) {
402 t->rootseg = seg;
403 }
404 else {
405 t->lastseg->next = seg;
406 }
407 t->lastseg = seg;
408 }
409 seg->e[i].key = key;
410 seg->e[i].val = val;
411 t->last_len = i+1;
412 if (t->index == NULL && t->size > MRB_HT_INIT_SIZE*4) {
413 ht_index(mrb, t);
414 }
415 }
416
417 /* Get a value for a key from the indexed table. */
418 static mrb_bool
ht_index_get(mrb_state * mrb,htable * t,mrb_value key,mrb_value * vp)419 ht_index_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
420 {
421 segindex *index = t->index;
422 size_t mask = HT_MASK(index);
423 size_t k = ht_hash_func(mrb, t, key) & mask;
424 size_t step = 0;
425
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;
430 return TRUE;
431 }
432 k = (k+(++step)) & mask;
433 }
434 return FALSE;
435 }
436
437 /* Get a value for a key from the hash table. */
438 static mrb_bool
ht_get(mrb_state * mrb,htable * t,mrb_value key,mrb_value * vp)439 ht_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
440 {
441 segment *seg;
442 mrb_int i;
443
444 if (t == NULL) return FALSE;
445 if (t->index) {
446 return ht_index_get(mrb, t, key, vp);
447 }
448
449 seg = t->rootseg;
450 while (seg) {
451 for (i=0; i<seg->size; i++) {
452 mrb_value k = seg->e[i].key;
453
454 if (!seg->next && i >= t->last_len) {
455 return FALSE;
456 }
457 if (mrb_undef_p(k)) continue;
458 if (ht_hash_equal(mrb, t, k, key)) {
459 if (vp) *vp = seg->e[i].val;
460 return TRUE;
461 }
462 }
463 seg = seg->next;
464 }
465 return FALSE;
466 }
467
468 /* Deletes the value for the symbol from the hash table. */
469 /* Deletion is done by overwriting keys by `undef`. */
470 static mrb_bool
ht_del(mrb_state * mrb,htable * t,mrb_value key,mrb_value * vp)471 ht_del(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp)
472 {
473 segment *seg;
474 mrb_int i;
475
476 if (t == NULL) return FALSE;
477 seg = t->rootseg;
478 while (seg) {
479 for (i=0; i<seg->size; i++) {
480 mrb_value key2;
481
482 if (!seg->next && i >= t->last_len) {
483 /* not found */
484 return FALSE;
485 }
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();
490 t->size--;
491 return TRUE;
492 }
493 }
494 seg = seg->next;
495 }
496 return FALSE;
497 }
498
499 /* Iterates over the hash table. */
500 static void
ht_foreach(mrb_state * mrb,htable * t,mrb_hash_foreach_func * func,void * p)501 ht_foreach(mrb_state *mrb, htable *t, mrb_hash_foreach_func *func, void *p)
502 {
503 segment *seg;
504 mrb_int i;
505
506 if (t == NULL) return;
507 seg = t->rootseg;
508 while (seg) {
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) {
512 return;
513 }
514 if (mrb_undef_p(seg->e[i].key)) continue;
515 if ((*func)(mrb, seg->e[i].key, seg->e[i].val, p) != 0)
516 return;
517 }
518 seg = seg->next;
519 }
520 }
521
522 /* Iterates over the hash table. */
523 MRB_API void
mrb_hash_foreach(mrb_state * mrb,struct RHash * hash,mrb_hash_foreach_func * func,void * p)524 mrb_hash_foreach(mrb_state *mrb, struct RHash *hash, mrb_hash_foreach_func *func, void *p)
525 {
526 ht_foreach(mrb, hash->ht, func, p);
527 }
528
529 /* Copy the hash table. */
530 static htable*
ht_copy(mrb_state * mrb,htable * t)531 ht_copy(mrb_state *mrb, htable *t)
532 {
533 segment *seg;
534 htable *t2;
535 mrb_int i;
536
537 seg = t->rootseg;
538 t2 = ht_new(mrb);
539 if (t->size == 0) return t2;
540
541 while (seg) {
542 for (i=0; i<seg->size; i++) {
543 mrb_value key = seg->e[i].key;
544 mrb_value val = seg->e[i].val;
545
546 if ((seg->next == NULL) && (i >= t->last_len)) {
547 return t2;
548 }
549 ht_put(mrb, t2, key, val);
550 }
551 seg = seg->next;
552 }
553 return t2;
554 }
555
556 /* Free memory of the hash table. */
557 static void
ht_free(mrb_state * mrb,htable * t)558 ht_free(mrb_state *mrb, htable *t)
559 {
560 segment *seg;
561
562 if (!t) return;
563 seg = t->rootseg;
564 while (seg) {
565 segment *p = seg;
566 seg = seg->next;
567 mrb_free(mrb, p);
568 }
569 if (t->index) mrb_free(mrb, t->index);
570 mrb_free(mrb, t);
571 }
572
573 static void mrb_hash_modify(mrb_state *mrb, mrb_value hash);
574
575 static inline mrb_value
ht_key(mrb_state * mrb,mrb_value key)576 ht_key(mrb_state *mrb, mrb_value key)
577 {
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));
581 }
582 return key;
583 }
584
585 #define KEY(key) ht_key(mrb, key)
586
587 static int
hash_mark_i(mrb_state * mrb,mrb_value key,mrb_value val,void * p)588 hash_mark_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
589 {
590 mrb_gc_mark_value(mrb, key);
591 mrb_gc_mark_value(mrb, val);
592 return 0;
593 }
594
595 void
mrb_gc_mark_hash(mrb_state * mrb,struct RHash * hash)596 mrb_gc_mark_hash(mrb_state *mrb, struct RHash *hash)
597 {
598 ht_foreach(mrb, hash->ht, hash_mark_i, NULL);
599 }
600
601 size_t
mrb_gc_mark_hash_size(mrb_state * mrb,struct RHash * hash)602 mrb_gc_mark_hash_size(mrb_state *mrb, struct RHash *hash)
603 {
604 if (!hash->ht) return 0;
605 return hash->ht->size*2;
606 }
607
608 void
mrb_gc_free_hash(mrb_state * mrb,struct RHash * hash)609 mrb_gc_free_hash(mrb_state *mrb, struct RHash *hash)
610 {
611 ht_free(mrb, hash->ht);
612 }
613
614 MRB_API mrb_value
mrb_hash_new(mrb_state * mrb)615 mrb_hash_new(mrb_state *mrb)
616 {
617 struct RHash *h;
618
619 h = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
620 h->ht = 0;
621 h->iv = 0;
622 return mrb_obj_value(h);
623 }
624
625 MRB_API mrb_value
mrb_hash_new_capa(mrb_state * mrb,mrb_int capa)626 mrb_hash_new_capa(mrb_state *mrb, mrb_int capa)
627 {
628 struct RHash *h;
629
630 h = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
631 /* preallocate hash table */
632 h->ht = ht_new(mrb);
633 /* capacity ignored */
634 h->iv = 0;
635 return mrb_obj_value(h);
636 }
637
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);
640
641 static mrb_value
mrb_hash_init_copy(mrb_state * mrb,mrb_value self)642 mrb_hash_init_copy(mrb_state *mrb, mrb_value self)
643 {
644 mrb_value orig;
645 struct RHash* copy;
646 htable *orig_h;
647 mrb_value ifnone, vret;
648
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");
653 }
654
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);
658
659 if (MRB_RHASH_DEFAULT_P(self)) {
660 copy->flags |= MRB_HASH_DEFAULT;
661 }
662 if (MRB_RHASH_PROCDEFAULT_P(self)) {
663 copy->flags |= MRB_HASH_PROC_DEFAULT;
664 }
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);
669 }
670 return vret;
671 }
672
673 static int
check_kdict_i(mrb_state * mrb,mrb_value key,mrb_value val,void * data)674 check_kdict_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
675 {
676 if (!mrb_symbol_p(key)) {
677 mrb_raise(mrb, E_ARGUMENT_ERROR, "keyword argument hash with non symbol keys");
678 }
679 return 0;
680 }
681
682 void
mrb_hash_check_kdict(mrb_state * mrb,mrb_value self)683 mrb_hash_check_kdict(mrb_state *mrb, mrb_value self)
684 {
685 htable *t;
686
687 t = RHASH_TBL(self);
688 if (!t || t->size == 0) return;
689 ht_foreach(mrb, t, check_kdict_i, NULL);
690 }
691
692 MRB_API mrb_value
mrb_hash_dup(mrb_state * mrb,mrb_value self)693 mrb_hash_dup(mrb_state *mrb, mrb_value self)
694 {
695 struct RHash* copy;
696 htable *orig_h;
697
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);
702 }
703
704 MRB_API mrb_value
mrb_hash_get(mrb_state * mrb,mrb_value hash,mrb_value key)705 mrb_hash_get(mrb_state *mrb, mrb_value hash, mrb_value key)
706 {
707 mrb_value val;
708 mrb_sym mid;
709
710 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) {
711 return val;
712 }
713
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);
717 }
718 /* xxx mrb_funcall_tailcall(mrb, hash, "default", 1, key); */
719 return mrb_funcall_argv(mrb, hash, mid, 1, &key);
720 }
721
722 MRB_API mrb_value
mrb_hash_fetch(mrb_state * mrb,mrb_value hash,mrb_value key,mrb_value def)723 mrb_hash_fetch(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value def)
724 {
725 mrb_value val;
726
727 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) {
728 return val;
729 }
730 /* not found */
731 return def;
732 }
733
734 MRB_API void
mrb_hash_set(mrb_state * mrb,mrb_value hash,mrb_value key,mrb_value val)735 mrb_hash_set(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value val)
736 {
737 mrb_hash_modify(mrb, hash);
738
739 key = KEY(key);
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);
743 return;
744 }
745
746 static void
mrb_hash_modify(mrb_state * mrb,mrb_value hash)747 mrb_hash_modify(mrb_state *mrb, mrb_value hash)
748 {
749 if (MRB_FROZEN_P(mrb_hash_ptr(hash))) {
750 mrb_raise(mrb, E_FROZEN_ERROR, "can't modify frozen hash");
751 }
752
753 if (!RHASH_TBL(hash)) {
754 RHASH_TBL(hash) = ht_new(mrb);
755 }
756 }
757
758 /* 15.2.13.4.16 */
759 /*
760 * call-seq:
761 * Hash.new -> new_hash
762 * Hash.new(obj) -> new_hash
763 * Hash.new {|hash, key| block } -> new_hash
764 *
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.
774 *
775 * h = Hash.new("Go Fish")
776 * h["a"] = 100
777 * h["b"] = 200
778 * h["a"] #=> 100
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"]
784 *
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"]
791 *
792 */
793
794 static mrb_value
mrb_hash_init(mrb_state * mrb,mrb_value hash)795 mrb_hash_init(mrb_state *mrb, mrb_value hash)
796 {
797 mrb_value block, ifnone;
798 mrb_bool ifnone_p;
799
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)) {
804 if (ifnone_p) {
805 mrb_raise(mrb, E_ARGUMENT_ERROR, "wrong number of arguments");
806 }
807 RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
808 ifnone = block;
809 }
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);
813 }
814 return hash;
815 }
816
817 /* 15.2.13.4.2 */
818 /*
819 * call-seq:
820 * hsh[key] -> value
821 *
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).
825 *
826 * h = { "a" => 100, "b" => 200 }
827 * h["a"] #=> 100
828 * h["c"] #=> nil
829 *
830 */
831 static mrb_value
mrb_hash_aget(mrb_state * mrb,mrb_value self)832 mrb_hash_aget(mrb_state *mrb, mrb_value self)
833 {
834 mrb_value key;
835
836 mrb_get_args(mrb, "o", &key);
837 return mrb_hash_get(mrb, self, key);
838 }
839
840 static mrb_value
hash_default(mrb_state * mrb,mrb_value hash,mrb_value key)841 hash_default(mrb_state *mrb, mrb_value hash, mrb_value key)
842 {
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);
846 }
847 else {
848 return RHASH_IFNONE(hash);
849 }
850 }
851 return mrb_nil_value();
852 }
853
854 /* 15.2.13.4.5 */
855 /*
856 * call-seq:
857 * hsh.default(key=nil) -> obj
858 *
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>.
862 *
863 * h = Hash.new #=> {}
864 * h.default #=> nil
865 * h.default(2) #=> nil
866 *
867 * h = Hash.new("cat") #=> {}
868 * h.default #=> "cat"
869 * h.default(2) #=> "cat"
870 *
871 * h = Hash.new {|h,k| h[k] = k.to_i*10} #=> {}
872 * h.default #=> nil
873 * h.default(2) #=> 20
874 */
875
876 static mrb_value
mrb_hash_default(mrb_state * mrb,mrb_value hash)877 mrb_hash_default(mrb_state *mrb, mrb_value hash)
878 {
879 mrb_value key;
880 mrb_bool given;
881
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);
887 }
888 else {
889 return RHASH_IFNONE(hash);
890 }
891 }
892 return mrb_nil_value();
893 }
894
895 /* 15.2.13.4.6 */
896 /*
897 * call-seq:
898 * hsh.default = obj -> obj
899 *
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.
903 *
904 * h = { "a" => 100, "b" => 200 }
905 * h.default = "Go fish"
906 * h["a"] #=> 100
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
911 * end
912 * h[2] #=> #<Proc:0x401b3948@-:6>
913 * h["cat"] #=> #<Proc:0x401b3948@-:6>
914 */
915
916 static mrb_value
mrb_hash_set_default(mrb_state * mrb,mrb_value hash)917 mrb_hash_set_default(mrb_state *mrb, mrb_value hash)
918 {
919 mrb_value ifnone;
920
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;
927 }
928 else {
929 RHASH(hash)->flags &= ~MRB_HASH_DEFAULT;
930 }
931 return ifnone;
932 }
933
934 /* 15.2.13.4.7 */
935 /*
936 * call-seq:
937 * hsh.default_proc -> anObject
938 *
939 * If <code>Hash::new</code> was invoked with a block, return that
940 * block, otherwise return <code>nil</code>.
941 *
942 * h = Hash.new {|h,k| h[k] = k*k } #=> {}
943 * p = h.default_proc #=> #<Proc:0x401b3d08@-:1>
944 * a = [] #=> []
945 * p.call(a, 2)
946 * a #=> [nil, nil, 4]
947 */
948
949
950 static mrb_value
mrb_hash_default_proc(mrb_state * mrb,mrb_value hash)951 mrb_hash_default_proc(mrb_state *mrb, mrb_value hash)
952 {
953 if (MRB_RHASH_PROCDEFAULT_P(hash)) {
954 return RHASH_PROCDEFAULT(hash);
955 }
956 return mrb_nil_value();
957 }
958
959 /*
960 * call-seq:
961 * hsh.default_proc = proc_obj -> proc_obj
962 *
963 * Sets the default proc to be executed on each key lookup.
964 *
965 * h.default_proc = proc do |hash, key|
966 * hash[key] = key + key
967 * end
968 * h[2] #=> 4
969 * h["cat"] #=> "catcat"
970 */
971
972 static mrb_value
mrb_hash_set_default_proc(mrb_state * mrb,mrb_value hash)973 mrb_hash_set_default_proc(mrb_state *mrb, mrb_value hash)
974 {
975 mrb_value ifnone;
976
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;
983 }
984 else {
985 RHASH(hash)->flags &= ~MRB_HASH_DEFAULT;
986 RHASH(hash)->flags &= ~MRB_HASH_PROC_DEFAULT;
987 }
988
989 return ifnone;
990 }
991
992 MRB_API mrb_value
mrb_hash_delete_key(mrb_state * mrb,mrb_value hash,mrb_value key)993 mrb_hash_delete_key(mrb_state *mrb, mrb_value hash, mrb_value key)
994 {
995 htable *t = RHASH_TBL(hash);
996 mrb_value del_val;
997
998 if (ht_del(mrb, t, key, &del_val)) {
999 return del_val;
1000 }
1001
1002 /* not found */
1003 return mrb_nil_value();
1004 }
1005
1006 static mrb_value
mrb_hash_delete(mrb_state * mrb,mrb_value self)1007 mrb_hash_delete(mrb_state *mrb, mrb_value self)
1008 {
1009 mrb_value key;
1010
1011 mrb_get_args(mrb, "o", &key);
1012 mrb_hash_modify(mrb, self);
1013 return mrb_hash_delete_key(mrb, self, key);
1014 }
1015
1016 /* find first element in the hash table, and remove it. */
1017 static void
ht_shift(mrb_state * mrb,htable * t,mrb_value * kp,mrb_value * vp)1018 ht_shift(mrb_state *mrb, htable *t, mrb_value *kp, mrb_value *vp)
1019 {
1020 segment *seg = t->rootseg;
1021 mrb_int i;
1022
1023 while (seg) {
1024 for (i=0; i<seg->size; i++) {
1025 mrb_value key;
1026
1027 if (!seg->next && i >= t->last_len) {
1028 return;
1029 }
1030 key = seg->e[i].key;
1031 if (mrb_undef_p(key)) continue;
1032 *kp = key;
1033 *vp = seg->e[i].val;
1034 /* delete element */
1035 seg->e[i].key = mrb_undef_value();
1036 t->size--;
1037 return;
1038 }
1039 seg = seg->next;
1040 }
1041 }
1042
1043 /* 15.2.13.4.24 */
1044 /*
1045 * call-seq:
1046 * hsh.shift -> anArray or obj
1047 *
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.
1051 *
1052 * h = { 1 => "a", 2 => "b", 3 => "c" }
1053 * h.shift #=> [1, "a"]
1054 * h #=> {2=>"b", 3=>"c"}
1055 */
1056
1057 static mrb_value
mrb_hash_shift(mrb_state * mrb,mrb_value hash)1058 mrb_hash_shift(mrb_state *mrb, mrb_value hash)
1059 {
1060 htable *t = RHASH_TBL(hash);
1061
1062 mrb_hash_modify(mrb, hash);
1063 if (t && t->size > 0) {
1064 mrb_value del_key, del_val;
1065
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);
1070 }
1071
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());
1075 }
1076 else {
1077 return RHASH_IFNONE(hash);
1078 }
1079 }
1080 return mrb_nil_value();
1081 }
1082
1083 /* 15.2.13.4.4 */
1084 /*
1085 * call-seq:
1086 * hsh.clear -> hsh
1087 *
1088 * Removes all key-value pairs from `hsh`.
1089 *
1090 * h = { "a" => 100, "b" => 200 } #=> {"a"=>100, "b"=>200}
1091 * h.clear #=> {}
1092 *
1093 */
1094
1095 MRB_API mrb_value
mrb_hash_clear(mrb_state * mrb,mrb_value hash)1096 mrb_hash_clear(mrb_state *mrb, mrb_value hash)
1097 {
1098 htable *t = RHASH_TBL(hash);
1099
1100 mrb_hash_modify(mrb, hash);
1101 if (t) {
1102 ht_free(mrb, t);
1103 RHASH_TBL(hash) = NULL;
1104 }
1105 return hash;
1106 }
1107
1108 /* 15.2.13.4.3 */
1109 /* 15.2.13.4.26 */
1110 /*
1111 * call-seq:
1112 * hsh[key] = value -> value
1113 * hsh.store(key, value) -> value
1114 *
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).
1120 *
1121 * h = { "a" => 100, "b" => 200 }
1122 * h["a"] = 9
1123 * h["c"] = 4
1124 * h #=> {"a"=>9, "b"=>200, "c"=>4}
1125 *
1126 */
1127 static mrb_value
mrb_hash_aset(mrb_state * mrb,mrb_value self)1128 mrb_hash_aset(mrb_state *mrb, mrb_value self)
1129 {
1130 mrb_value key, val;
1131
1132 mrb_get_args(mrb, "oo", &key, &val);
1133 mrb_hash_set(mrb, self, key, val);
1134 return val;
1135 }
1136
1137 MRB_API mrb_int
mrb_hash_size(mrb_state * mrb,mrb_value hash)1138 mrb_hash_size(mrb_state *mrb, mrb_value hash)
1139 {
1140 htable *t = RHASH_TBL(hash);
1141
1142 if (!t) return 0;
1143 return t->size;
1144 }
1145
1146 /* 15.2.13.4.20 */
1147 /* 15.2.13.4.25 */
1148 /*
1149 * call-seq:
1150 * hsh.length -> fixnum
1151 * hsh.size -> fixnum
1152 *
1153 * Returns the number of key-value pairs in the hash.
1154 *
1155 * h = { "d" => 100, "a" => 200, "v" => 300, "e" => 400 }
1156 * h.length #=> 4
1157 * h.delete("a") #=> 200
1158 * h.length #=> 3
1159 */
1160 static mrb_value
mrb_hash_size_m(mrb_state * mrb,mrb_value self)1161 mrb_hash_size_m(mrb_state *mrb, mrb_value self)
1162 {
1163 mrb_int size = mrb_hash_size(mrb, self);
1164 return mrb_fixnum_value(size);
1165 }
1166
1167 MRB_API mrb_bool
mrb_hash_empty_p(mrb_state * mrb,mrb_value self)1168 mrb_hash_empty_p(mrb_state *mrb, mrb_value self)
1169 {
1170 htable *t = RHASH_TBL(self);
1171
1172 if (!t) return TRUE;
1173 return t->size == 0;
1174 }
1175
1176 /* 15.2.13.4.12 */
1177 /*
1178 * call-seq:
1179 * hsh.empty? -> true or false
1180 *
1181 * Returns <code>true</code> if <i>hsh</i> contains no key-value pairs.
1182 *
1183 * {}.empty? #=> true
1184 *
1185 */
1186 static mrb_value
mrb_hash_empty_m(mrb_state * mrb,mrb_value self)1187 mrb_hash_empty_m(mrb_state *mrb, mrb_value self)
1188 {
1189 return mrb_bool_value(mrb_hash_empty_p(mrb, self));
1190 }
1191
1192 static int
hash_keys_i(mrb_state * mrb,mrb_value key,mrb_value val,void * p)1193 hash_keys_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1194 {
1195 mrb_ary_push(mrb, *(mrb_value*)p, key);
1196 return 0;
1197 }
1198
1199 /* 15.2.13.4.19 */
1200 /*
1201 * call-seq:
1202 * hsh.keys -> array
1203 *
1204 * Returns a new array populated with the keys from this hash. See also
1205 * <code>Hash#values</code>.
1206 *
1207 * h = { "a" => 100, "b" => 200, "c" => 300, "d" => 400 }
1208 * h.keys #=> ["a", "b", "c", "d"]
1209 *
1210 */
1211
1212 MRB_API mrb_value
mrb_hash_keys(mrb_state * mrb,mrb_value hash)1213 mrb_hash_keys(mrb_state *mrb, mrb_value hash)
1214 {
1215 htable *t = RHASH_TBL(hash);
1216 mrb_int size;
1217 mrb_value ary;
1218
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);
1223 return ary;
1224 }
1225
1226 static int
hash_vals_i(mrb_state * mrb,mrb_value key,mrb_value val,void * p)1227 hash_vals_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1228 {
1229 mrb_ary_push(mrb, *(mrb_value*)p, val);
1230 return 0;
1231 }
1232
1233 /* 15.2.13.4.28 */
1234 /*
1235 * call-seq:
1236 * hsh.values -> array
1237 *
1238 * Returns a new array populated with the values from <i>hsh</i>. See
1239 * also <code>Hash#keys</code>.
1240 *
1241 * h = { "a" => 100, "b" => 200, "c" => 300 }
1242 * h.values #=> [100, 200, 300]
1243 *
1244 */
1245
1246 MRB_API mrb_value
mrb_hash_values(mrb_state * mrb,mrb_value hash)1247 mrb_hash_values(mrb_state *mrb, mrb_value hash)
1248 {
1249 htable *t = RHASH_TBL(hash);
1250 mrb_int size;
1251 mrb_value ary;
1252
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);
1257 return ary;
1258 }
1259
1260 /* 15.2.13.4.13 */
1261 /* 15.2.13.4.15 */
1262 /* 15.2.13.4.18 */
1263 /* 15.2.13.4.21 */
1264 /*
1265 * call-seq:
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
1270 *
1271 * Returns <code>true</code> if the given key is present in <i>hsh</i>.
1272 *
1273 * h = { "a" => 100, "b" => 200 }
1274 * h.has_key?("a") #=> true
1275 * h.has_key?("z") #=> false
1276 *
1277 */
1278
1279 MRB_API mrb_bool
mrb_hash_key_p(mrb_state * mrb,mrb_value hash,mrb_value key)1280 mrb_hash_key_p(mrb_state *mrb, mrb_value hash, mrb_value key)
1281 {
1282 htable *t;
1283
1284 t = RHASH_TBL(hash);
1285 if (ht_get(mrb, t, key, NULL)) {
1286 return TRUE;
1287 }
1288 return FALSE;
1289 }
1290
1291 static mrb_value
mrb_hash_has_key(mrb_state * mrb,mrb_value hash)1292 mrb_hash_has_key(mrb_state *mrb, mrb_value hash)
1293 {
1294 mrb_value key;
1295 mrb_bool key_p;
1296
1297 mrb_get_args(mrb, "o", &key);
1298 key_p = mrb_hash_key_p(mrb, hash, key);
1299 return mrb_bool_value(key_p);
1300 }
1301
1302 struct has_v_arg {
1303 mrb_bool found;
1304 mrb_value val;
1305 };
1306
1307 static int
hash_has_value_i(mrb_state * mrb,mrb_value key,mrb_value val,void * p)1308 hash_has_value_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p)
1309 {
1310 struct has_v_arg *arg = (struct has_v_arg*)p;
1311
1312 if (mrb_equal(mrb, arg->val, val)) {
1313 arg->found = TRUE;
1314 return 1;
1315 }
1316 return 0;
1317 }
1318
1319 /* 15.2.13.4.14 */
1320 /* 15.2.13.4.27 */
1321 /*
1322 * call-seq:
1323 * hsh.has_value?(value) -> true or false
1324 * hsh.value?(value) -> true or false
1325 *
1326 * Returns <code>true</code> if the given value is present for some key
1327 * in <i>hsh</i>.
1328 *
1329 * h = { "a" => 100, "b" => 200 }
1330 * h.has_value?(100) #=> true
1331 * h.has_value?(999) #=> false
1332 */
1333
1334 static mrb_value
mrb_hash_has_value(mrb_state * mrb,mrb_value hash)1335 mrb_hash_has_value(mrb_state *mrb, mrb_value hash)
1336 {
1337 mrb_value val;
1338 struct has_v_arg arg;
1339
1340 mrb_get_args(mrb, "o", &val);
1341 arg.found = FALSE;
1342 arg.val = val;
1343 ht_foreach(mrb, RHASH_TBL(hash), hash_has_value_i, &arg);
1344 return mrb_bool_value(arg.found);
1345 }
1346
1347 static int
merge_i(mrb_state * mrb,mrb_value key,mrb_value val,void * data)1348 merge_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
1349 {
1350 htable *h1 = (htable*)data;
1351
1352 ht_put(mrb, h1, key, val);
1353 return 0;
1354 }
1355
1356 MRB_API void
mrb_hash_merge(mrb_state * mrb,mrb_value hash1,mrb_value hash2)1357 mrb_hash_merge(mrb_state *mrb, mrb_value hash1, mrb_value hash2)
1358 {
1359 htable *h1, *h2;
1360
1361 mrb_hash_modify(mrb, hash1);
1362 hash2 = mrb_ensure_hash_type(mrb, hash2);
1363 h1 = RHASH_TBL(hash1);
1364 h2 = RHASH_TBL(hash2);
1365
1366 if (!h2) return;
1367 if (!h1) {
1368 RHASH_TBL(hash1) = ht_copy(mrb, h2);
1369 return;
1370 }
1371 ht_foreach(mrb, h2, merge_i, h1);
1372 mrb_write_barrier(mrb, (struct RBasic*)RHASH(hash1));
1373 return;
1374 }
1375
1376 /*
1377 * call-seq:
1378 * hsh.rehash -> hsh
1379 *
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>.
1383 *
1384 * h = {"AAA" => "b"}
1385 * h.keys[0].chop!
1386 * h.rehash #=> {"AA"=>"b"}
1387 * h["AA"] #=> "b"
1388 */
1389 static mrb_value
mrb_hash_rehash(mrb_state * mrb,mrb_value self)1390 mrb_hash_rehash(mrb_state *mrb, mrb_value self)
1391 {
1392 ht_compact(mrb, RHASH_TBL(self));
1393 return self;
1394 }
1395
1396 void
mrb_init_hash(mrb_state * mrb)1397 mrb_init_hash(mrb_state *mrb)
1398 {
1399 struct RClass *h;
1400
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);
1403
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());
1428 }
1429