w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

hash.c
Go to the documentation of this file.
1 /*
2 ** hash.c - Hash class
3 **
4 ** See Copyright Notice in mruby.h
5 */
6 
7 #include <string.h>
8 #include <mruby.h>
9 #include <mruby/array.h>
10 #include <mruby/class.h>
11 #include <mruby/hash.h>
12 #include <mruby/string.h>
13 #include <mruby/variable.h>
14 #include <mruby/presym.h>
15 
16 /*
17  * === Glossary
18  *
19  * [EA]
20  * Entry Array. Store `Hash' entries in insertion order.
21  *
22  * [AR]
23  * Array Table Implementation. The structure of `Hash` that doesn't have a
24  * hash table and linearly searches EA. It is used when `Hash` size <= 16.
25  *
26  * [IB]
27  * Index Buckets. The buckets of hash table, where the bucket value is EA
28  * index. The index is represented by variable length bits according to
29  * the capacity.
30  *
31  * [HT]
32  * Hash Table Implementation. The structure of `Hash` that has IB and is
33  * searched by hash table algorithm. It is used when `Hash` size > 16.
34  * Collision resolution strategy is open addressing method.
35  *
36  * [size]
37  * The number of `Hash` entries (value of `Hash#size`).
38  *
39  * [slot]
40  * The generic term for EA or IB elements.
41  *
42  * [active]
43  * The state in which a slot is recognized as a `Hash` entry.
44  *
45  * [deleted]
46  * The state in which a slot is marked as deleted.
47  *
48  * [used]
49  * The state in which a slot is active or deleted.
50  *
51  * [empty]
52  * The state in which a slot is not used. Capacity is equal to the sum of
53  * the number of used slots and the number of empty slots.
54  */
55 
56 #define EA_N_RESERVED_INDICES 2 /* empty and deleted */
57 #define EA_INCREASE_RATIO 6 / 5 + 6
58 #define EA_MAX_INCREASE UINT16_MAX
59 #define EA_MAX_CAPA U32(lesser(IB_MAX_CAPA - EA_N_RESERVED_INDICES, MRB_INT_MAX))
60 #define IB_MAX_CAPA (U32(1) << IB_MAX_BIT)
61 #define IB_TYPE_BIT 32
62 #define IB_INIT_BIT ( \
63  ib_upper_bound_for(32) <= AR_MAX_SIZE ? 6 : \
64  ib_upper_bound_for(16) <= AR_MAX_SIZE ? 5 : \
65  4 \
66 )
67 #define IB_MAX_BIT (IB_TYPE_BIT - 1)
68 #define AR_DEFAULT_CAPA 4
69 #define AR_MAX_SIZE 16
70 #define H_MAX_SIZE EA_MAX_CAPA
71 
74 
75 typedef struct hash_entry {
79 
80 typedef struct hash_table {
82 #ifdef MRB_32BIT
83  uint32_t ea_capa;
84  uint32_t ea_n_used;
85 #endif
88 
89 typedef struct index_buckets_iter {
90  struct RHash *h;
100 
101 /*
102  * `c_` :: receiver class (category)
103  * `n_` :: attribute name
104  * `t_` :: attribute type
105  * `p_` :: struct member path
106  * `k_` :: macro key
107  */
108 #define DEFINE_GETTER(c_, n_, t_, p_) \
109  MRB_INLINE t_ c_##_##n_(const struct RHash *h) {return h->p_;}
110 #define DEFINE_SETTER(c_, n_, t_, p_) \
111  MRB_INLINE void c_##_set_##n_(struct RHash *h, t_ v) {h->p_ = v;}
112 #define DEFINE_ACCESSOR(c_, n_, t_, p_) \
113  DEFINE_GETTER(c_, n_, t_, p_) \
114  DEFINE_SETTER(c_, n_, t_, p_)
115 #define DEFINE_FLAG_GETTER(c_, n_, t_, k_) \
116  MRB_INLINE t_ c_##_##n_(const struct RHash *h) { \
117  return (t_)((h->flags & MRB_HASH_##k_##_MASK) >> MRB_HASH_##k_##_SHIFT); \
118  }
119 #define DEFINE_FLAG_SETTER(c_, n_, t_, k_) \
120  MRB_INLINE void c_##_set_##n_(struct RHash *h, t_ v) { \
121  h->flags &= ~MRB_HASH_##k_##_MASK; \
122  h->flags |= v << MRB_HASH_##k_##_SHIFT; \
123  }
124 #define DEFINE_FLAG_ACCESSOR(c_, n_, t_, k_) \
125  DEFINE_FLAG_GETTER(c_, n_, t_, k_) \
126  DEFINE_FLAG_SETTER(c_, n_, t_, k_)
127 #define DEFINE_INCREMENTER(c_, n_) \
128  MRB_INLINE void c_##_inc_##n_(struct RHash *h) { \
129  c_##_set_##n_(h, c_##_##n_(h) + 1); \
130  }
131 #define DEFINE_DECREMENTER(c_, n_) \
132  MRB_INLINE void c_##_dec_##n_(struct RHash *h) { \
133  c_##_set_##n_(h, c_##_##n_(h) - 1); \
134  }
135 #define DEFINE_SWITCHER(n_, k_) \
136  MRB_INLINE void h_##n_##_on(struct RHash *h) { \
137  h->flags |= MRB_HASH_##k_; \
138  } \
139  MRB_INLINE void h_##n_##_off(struct RHash *h) { \
140  h->flags &= ~MRB_HASH_##k_; \
141  } \
142  MRB_INLINE mrb_bool h_##n_##_p(const struct RHash *h) { \
143  return (h->flags & MRB_HASH_##k_) == MRB_HASH_##k_; \
144  }
145 
146 #ifdef MRB_64BIT
147 DEFINE_ACCESSOR(ar, ea_capa, uint32_t, ea_capa)
148 DEFINE_ACCESSOR(ar, ea_n_used, uint32_t, ea_n_used)
149 DEFINE_ACCESSOR(ht, ea_capa, uint32_t, ea_capa)
150 DEFINE_ACCESSOR(ht, ea_n_used, uint32_t, ea_n_used)
151 #else
152 DEFINE_FLAG_ACCESSOR(ar, ea_capa, uint32_t, AR_EA_CAPA)
153 DEFINE_FLAG_ACCESSOR(ar, ea_n_used, uint32_t, AR_EA_N_USED)
154 DEFINE_ACCESSOR(ht, ea_capa, uint32_t, ht->ea_capa)
155 DEFINE_ACCESSOR(ht, ea_n_used, uint32_t, ht->ea_n_used)
156 #endif
169 
170 #define ea_each_used(ea, n_used, entry_var, code) do { \
171  hash_entry *entry_var = ea, *ea_end__ = entry_var + (n_used); \
172  for (; entry_var < ea_end__; ++entry_var) { \
173  code; \
174  } \
175 } while (0)
176 
177 #define ea_each(ea, size, entry_var, code) do { \
178  hash_entry *entry_var = ea; \
179  uint32_t size__ = size; \
180  for (; 0 < size__; ++entry_var) { \
181  if (entry_deleted_p(entry_var)) continue; \
182  --size__; \
183  code; \
184  } \
185 } while (0)
186 
187 #define ib_cycle_by_key(mrb, h, key, it_var, code) do { \
188  index_buckets_iter it_var[1]; \
189  ib_it_init(mrb, it_var, h, key); \
190  for (;;) { \
191  ib_it_next(it_var); \
192  code; \
193  } \
194 } while (0)
195 
196 #define ib_find_by_key(mrb, h_, key_, it_var, code) do { \
197  mrb_value ib_fbk_key__ = key_; \
198  ib_cycle_by_key(mrb, h_, ib_fbk_key__, it_var, { \
199  if (ib_it_empty_p(it_var)) break; \
200  if (ib_it_deleted_p(it_var)) continue; \
201  if (obj_eql(mrb, ib_fbk_key__, ib_it_entry(it_var)->key, it_var->h)) { \
202  code; \
203  break; \
204  } \
205  }); \
206 } while (0)
207 
208 #define h_each(h, entry_var, code) do { \
209  struct RHash *h__ = h; \
210  hash_entry *h_e_ea__; \
211  uint32_t h_e_size__; \
212  h_ar_p(h) ? (h_e_ea__ = ar_ea(h__), h_e_size__ = ar_size(h__)) : \
213  (h_e_ea__ = ht_ea(h__), h_e_size__ = ht_size(h__)); \
214  ea_each(h_e_ea__, h_e_size__, entry_var, code); \
215 } while (0)
216 
217 /*
218  * `h_check_modified` raises an exception when a dangerous modification is
219  * made to `h` by executing `code`.
220  *
221  * This macro is not called if `h->ht` (`h->ea`) is `NULL` (`Hash` size is
222  * zero). And because the `hash_entry` is rather large, `h->ht->ea` and
223  * `h->ht->ea_capa` are able to be safely accessed even in AR. This nature
224  * is used to eliminate branch of AR or HT.
225  *
226  * `HT_ASSERT_SAFE_READ` checks if members can be accessed according to its
227  * assumptions.
228  */
229 #define HT_ASSERT_SAFE_READ(attr_name) \
230  mrb_static_assert1( \
231  offsetof(hash_table, attr_name) + sizeof(((hash_table*)0)->attr_name) <= \
232  sizeof(hash_entry))
234 #ifdef MRB_32BIT
235 HT_ASSERT_SAFE_READ(ea_capa);
236 #endif
237 #undef HT_ASSERT_SAFE_READ
238 #define h_check_modified(mrb, h, code) do { \
239  struct RHash *h__ = h; \
240  uint32_t mask = MRB_HASH_HT|MRB_HASH_IB_BIT_MASK|MRB_HASH_AR_EA_CAPA_MASK; \
241  uint32_t flags = h__->flags & mask; \
242  void* tbl__ = (mrb_assert(h__->ht), h__->ht); \
243  uint32_t ht_ea_capa__ = ht_ea_capa(h__); \
244  hash_entry *ht_ea__ = ht_ea(h__); \
245  code; \
246  if (flags != (h__->flags & mask) || \
247  tbl__ != h__->ht || \
248  ht_ea_capa__ != ht_ea_capa(h__) || \
249  ht_ea__ != ht_ea(h__)) { \
250  mrb_raise(mrb, E_RUNTIME_ERROR, "hash modified"); \
251  } \
252 } while (0)
253 
254 #define U32(v) ((uint32_t)(v))
255 #define h_ar_p(h) (!h_ht_p(h))
256 #define h_ar_on(h) h_ht_off(h)
257 #define lesser(a, b) ((a) < (b) ? (a) : (b))
258 #define RHASH_IFNONE(hash) mrb_iv_get(mrb, (hash), MRB_SYM(ifnone))
259 #define RHASH_PROCDEFAULT(hash) RHASH_IFNONE(hash)
260 
263 static void ht_init(
264  mrb_state *mrb, struct RHash *h, uint32_t size,
266 static void ht_set_without_ib_adjustment(
267  mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val);
268 
269 static uint32_t
271 {
272  mrb_assert(v != 0);
273 #ifdef __GNUC__
274  return U32(1) << ((sizeof(unsigned) * CHAR_BIT) - __builtin_clz(v));
275 #else
276  v |= v >> 1;
277  v |= v >> 2;
278  v |= v >> 4;
279  v |= v >> 8;
280  v |= v >> 16;
281  ++v;
282  return v;
283 #endif
284 }
285 
286 static uint32_t
288 {
289  enum mrb_vtype tt = mrb_type(key);
290  uint32_t hash_code;
291  mrb_value hash_code_obj;
292  switch (tt) {
293  case MRB_TT_STRING:
294  hash_code = mrb_str_hash(mrb, key);
295  break;
296  case MRB_TT_TRUE:
297  case MRB_TT_FALSE:
298  case MRB_TT_SYMBOL:
299  case MRB_TT_INTEGER:
300 #ifndef MRB_NO_FLOAT
301  case MRB_TT_FLOAT:
302 #endif
303  hash_code = U32(mrb_obj_id(key));
304  break;
305  default:
306  h_check_modified(mrb, h, {
307  hash_code_obj = mrb_funcall_argv(mrb, key, MRB_SYM(hash), 0, NULL);
308  });
309 
310  hash_code = U32(tt) ^ U32(mrb_integer(hash_code_obj));
311  break;
312  }
313  return hash_code ^ (hash_code << 2) ^ (hash_code >> 2);
314 }
315 
316 static mrb_bool
318 {
319  enum mrb_vtype tt = mrb_type(a);
320  mrb_bool eql;
321 
322  switch (tt) {
323  case MRB_TT_STRING:
324  return mrb_str_equal(mrb, a, b);
325 
326  case MRB_TT_SYMBOL:
327  if (!mrb_symbol_p(b)) return FALSE;
328  return mrb_symbol(a) == mrb_symbol(b);
329 
330  case MRB_TT_INTEGER:
331  if (!mrb_integer_p(b)) return FALSE;
332  return mrb_integer(a) == mrb_integer(b);
333 
334 #ifndef MRB_NO_FLOAT
335  case MRB_TT_FLOAT:
336  if (!mrb_float_p(b)) return FALSE;
337  return mrb_float(a) == mrb_float(b);
338 #endif
339 
340  default:
341  h_check_modified(mrb, h, {eql = mrb_eql(mrb, a, b);});
342  return eql;
343  }
344 }
345 
346 static mrb_bool
348 {
349  return mrb_undef_p(entry->key);
350 }
351 
352 static void
354 {
355  entry->key = mrb_undef_value();
356 }
357 
358 static uint32_t
360 {
361  if (size < AR_DEFAULT_CAPA) {
362  return AR_DEFAULT_CAPA;
363  }
364  else {
365  /*
366  * For 32-bit CPU, the theoretical value of maximum EA capacity is
367  * `UINT32_MAX / sizeof (hash_entry)`. At this time, if
368  * `EA_INCREASE_RATIO` is the current value, 32-bit range will not be
369  * exceeded during the calculation of `capa`, so `size_t` is used.
370  */
371  size_t capa = (size_t)size * EA_INCREASE_RATIO, inc = capa - size;
372  if (EA_MAX_INCREASE < inc) capa = size + EA_MAX_INCREASE;
373  return capa <= max_capa ? U32(capa) : max_capa;
374  }
375 }
376 
377 static hash_entry*
379 {
380  return (hash_entry*)mrb_realloc(mrb, ea, sizeof(hash_entry) * capa);
381 }
382 
383 static void
385 {
386  hash_entry *w_entry = ea;
387  ea_each_used(ea, n_used, r_entry, {
388  if (entry_deleted_p(r_entry)) continue;
389  if (r_entry != w_entry) *w_entry = *r_entry;
390  ++w_entry;
391  });
392 }
393 
394 /*
395  * Increase or decrease capacity of `ea` to a standard size that can
396  * accommodate `*capap + 1` entries (but, not exceed `max_capa`). Set the
397  * changed capacity to `*capap` and return a pointer to `mrb_realloc`ed EA.
398  */
399 static hash_entry*
401 {
402  *capap = ea_next_capa_for(*capap, max_capa);
403  return ea_resize(mrb, ea, *capap);
404 }
405 
406 static hash_entry*
407 ea_dup(mrb_state *mrb, const hash_entry *ea, uint32_t capa)
408 {
409  size_t byte_size = sizeof(hash_entry) * capa;
410  hash_entry *new_ea = (hash_entry*)mrb_malloc(mrb, byte_size);
411  return (hash_entry*)memcpy(new_ea, ea, byte_size);
412 }
413 
414 static hash_entry*
416  struct RHash *h)
417 {
418  ea_each(ea, size, entry, {
419  if (obj_eql(mrb, key, entry->key, h)) return entry;
420  });
421  return NULL;
422 }
423 
424 static hash_entry*
426 {
427  return &ea[index];
428 }
429 
430 static void
432 {
433  ea[index].key = key;
434  ea[index].val = val;
435 }
436 
437 static void
439  hash_entry *ea, uint32_t ea_capa, uint32_t ea_n_used)
440 {
441  h_ar_on(h);
442  ar_set_size(h, size);
443  ar_set_ea(h, ea);
444  ar_set_ea_capa(h, ea_capa);
445  ar_set_ea_n_used(h, ea_n_used);
446 }
447 
448 static void
449 ar_free(mrb_state *mrb, struct RHash *h)
450 {
451  mrb_free(mrb, ar_ea(h));
452 }
453 
454 static void
455 ar_adjust_ea(mrb_state *mrb, struct RHash *h, uint32_t size, uint32_t max_ea_capa)
456 {
457  uint32_t ea_capa = size;
458  hash_entry *ea = ea_adjust(mrb, ar_ea(h), &ea_capa, max_ea_capa);
459  ar_set_ea(h, ea);
460  ar_set_ea_capa(h, ea_capa);
461 }
462 
463 static void
464 ar_compress(mrb_state *mrb, struct RHash *h)
465 {
466  uint32_t size = ar_size(h);
470 }
471 
472 static mrb_bool
473 ar_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
474 {
475  ea_each(ar_ea(h), ar_size(h), entry, {
476  if (!obj_eql(mrb, key, entry->key, h)) continue;
477  *valp = entry->val;
478  return TRUE;
479  });
480  return FALSE;
481 }
482 
483 static void
485 {
486  uint32_t size = ar_size(h);
487  hash_entry *entry;
488  if ((entry = ea_get_by_key(mrb, ar_ea(h), size, key, h))) {
489  entry->val = val;
490  }
491  else {
492  uint32_t ea_capa = ar_ea_capa(h), ea_n_used = ar_ea_n_used(h);
493  if (ea_capa == ea_n_used) {
494  if (size == ea_n_used) {
495  if (size == AR_MAX_SIZE) {
496  hash_entry *ea = ea_adjust(mrb, ar_ea(h), &ea_capa, EA_MAX_CAPA);
497  ea_set(ea, ea_n_used, key, val);
498  ht_init(mrb, h, ++size, ea, ea_capa, NULL, IB_INIT_BIT);
499  return;
500  }
501  else {
502  ar_adjust_ea(mrb, h, size, AR_MAX_SIZE);
503  }
504  }
505  else {
506  ar_compress(mrb, h);
507  ea_n_used = size;
508  }
509  }
510  ea_set(ar_ea(h), ea_n_used, key, val);
511  ar_set_size(h, ++size);
512  ar_set_ea_n_used(h, ++ea_n_used);
513  }
514 }
515 
516 static mrb_bool
518 {
520  if (!entry) return FALSE;
521  *valp = entry->val;
523  ar_dec_size(h);
524  return TRUE;
525 }
526 
527 static void
528 ar_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
529 {
530  uint32_t size = ar_size(h);
531  ea_each(ar_ea(h), size, entry, {
532  *keyp = entry->key;
533  *valp = entry->val;
535  ar_set_size(h, --size);
536  return;
537  });
538 }
539 
540 static void
541 ar_rehash(mrb_state *mrb, struct RHash *h)
542 {
543  /* see comments in `h_rehash` */
544  uint32_t size = ar_size(h), w_size = 0, ea_capa = ar_ea_capa(h);
545  hash_entry *ea = ar_ea(h), *w_entry;
546  ea_each(ea, size, r_entry, {
547  if ((w_entry = ea_get_by_key(mrb, ea, w_size, r_entry->key, h))) {
548  w_entry->val = r_entry->val;
549  ar_set_size(h, --size);
550  entry_delete(r_entry);
551  }
552  else {
553  if (w_size != U32(r_entry - ea)) {
554  ea_set(ea, w_size, r_entry->key, r_entry->val);
555  entry_delete(r_entry);
556  }
557  ++w_size;
558  }
559  });
560  mrb_assert(size == w_size);
562  ar_adjust_ea(mrb, h, size, ea_capa);
563 }
564 
565 static uint32_t
567 {
568  return v & it->mask;
569 }
570 
571 static uint32_t
573 {
574  return it->mask;
575 }
576 
577 static uint32_t
579 {
580  return it->mask - 1;
581 }
582 
583 static mrb_bool
585 {
586  return it->ea_index == ib_it_empty_value(it);
587 }
588 
589 static mrb_bool
591 {
592  return it->ea_index == ib_it_deleted_value(it);
593 }
594 
595 static mrb_bool
597 {
598  return it->ea_index < ib_it_deleted_value(it);
599 }
600 
601 static void
603 {
604  it->h = h;
605  it->bit = ib_bit(h);
606  it->mask = ib_bit_to_capa(it->bit) - 1;
607  it->pos = ib_it_pos_for(it, obj_hash_code(mrb, key, h));
608  it->step = 0;
609 }
610 
611 static void
613 {
614  /*
615  * [IB image]
616  *
617  * ary_index(1) --.
618  * \ .-- shift1(3) .-- shift2(29)
619  * pos(6) --. \ / /
620  * View | \ \ <-o-> <----------o---------->
621  * -------- +---------------------\----\--+-----------------------------+-----
622  * array | 0 `--. `-|--- o 1 | ...
623  * +---------+---------+-----+\--+-----+---------+---------+---+-----
624  * buckets | 0 | 1 | ... | o 6 | 7 | 8 | ...
625  * +---------+---------+-----+=========+---------+---------+---------
626  * bit set |1 1 1 0 0|0 0 0 1 1| ... |0 1 0 1 1|0 1 1 1 0|0 1 0 1 0| ...
627  * +---------+---------+-----+========*+---------+---------+---------
628  * <---o---> \
629  * \ `-- bit_pos(34)
630  * `-- bit(5)
631  */
632 
633  /* Slide to handle as `capa == 32` to avoid 64-bit operations */
634  uint32_t slid_pos = it->pos & (IB_TYPE_BIT - 1);
635  uint32_t slid_bit_pos = it->bit * (slid_pos + 1) - 1;
636  uint32_t slid_ary_index = slid_bit_pos / IB_TYPE_BIT;
637  it->ary_index = slid_ary_index + it->pos / IB_TYPE_BIT * it->bit;
638  it->shift2 = (slid_ary_index + 1) * IB_TYPE_BIT - slid_bit_pos - 1;
639  it->ea_index = (ht_ib(it->h)[it->ary_index] >> it->shift2) & it->mask;
640  if (IB_TYPE_BIT - it->bit < it->shift2) {
641  it->shift1 = IB_TYPE_BIT - it->shift2;
642  it->ea_index |= (ht_ib(it->h)[it->ary_index - 1] << it->shift1) & it->mask;
643  }
644  else {
645  it->shift1 = 0;
646  }
647  it->pos = ib_it_pos_for(it, it->pos + (++it->step));
648 }
649 
650 static uint32_t
652 {
653  return it->ea_index;
654 }
655 
656 static void
658 {
659  uint32_t mask, i;
660  it->ea_index = ea_index;
661  if (it->shift1) {
662  i = it->ary_index - 1;
663  mask = it->mask >> it->shift1;
664  ht_ib(it->h)[i] = (ht_ib(it->h)[i] & ~~mask) | (ea_index >> it->shift1);
665  }
666  i = it->ary_index;
667  mask = it->mask << it->shift2;
668  ht_ib(it->h)[i] = (ht_ib(it->h)[i] & ~~mask) | (ea_index << it->shift2);
669 }
670 
671 static void
673 {
675 }
676 
677 static hash_entry*
679 {
680  return ea_get(ht_ea(it->h), it->ea_index);
681 }
682 
683 static uint32_t
685 {
686 #ifdef __GNUC__
687  return U32(__builtin_ctz(capa));
688 #else
689  /* http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn */
690  static const uint32_t MultiplyDeBruijnBitPosition2[] = {
691  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
692  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
693  };
694  return MultiplyDeBruijnBitPosition2[U32(capa * 0x077CB531U) >> 27];
695 #endif
696 }
697 
698 static uint32_t
700 {
701  return U32(1) << bit;
702 }
703 
704 static uint32_t
706 {
707  return (capa >> 2) | (capa >> 1); /* 3/4 */
708 }
709 
710 static uint32_t
712 {
713  uint32_t capa = next_power2(size);
714  if (capa != IB_MAX_CAPA && ib_upper_bound_for(capa) < size) capa *= 2;
715  return ib_capa_to_bit(capa);
716 }
717 
718 static uint32_t
720 {
721  uint32_t ary_size = IB_INIT_BIT == 4 ?
722  ib_bit_to_capa(ib_bit) * 2 / IB_TYPE_BIT * ib_bit / 2 :
724  return U32(sizeof(uint32_t) * ary_size);
725 }
726 
727 static void
728 ib_init(mrb_state *mrb, struct RHash *h, uint32_t ib_bit, size_t ib_byte_size)
729 {
730  hash_entry *ea = ht_ea(h);
731  memset(ht_ib(h), 0xff, ib_byte_size);
732  ib_set_bit(h, ib_bit);
734  ib_cycle_by_key(mrb, h, entry->key, it, {
735  if (!ib_it_empty_p(it)) continue;
736  ib_it_set(it, U32(entry - ea));
737  break;
738  });
739  });
740 }
741 
742 static void
745 {
746  size_t ib_byte_size = ib_byte_size_for(ib_bit);
747  size_t ht_byte_size = sizeof(hash_table) + ib_byte_size;
748  h_ht_on(h);
749  h_set_ht(h, (hash_table*)mrb_realloc(mrb, ht, ht_byte_size));
750  ht_set_size(h, size);
751  ht_set_ea(h, ea);
752  ht_set_ea_capa(h, ea_capa);
754  ib_init(mrb, h, ib_bit, ib_byte_size);
755 }
756 
757 static void
758 ht_free(mrb_state *mrb, struct RHash *h)
759 {
760  mrb_free(mrb, ht_ea(h));
761  mrb_free(mrb, h_ht(h));
762 }
763 
764 static hash_table*
765 ht_dup(mrb_state *mrb, const struct RHash *h)
766 {
767  size_t ib_byte_size = ib_byte_size_for(ib_bit(h));
768  size_t ht_byte_size = sizeof(hash_table) + ib_byte_size;
769  hash_table *new_ht = (hash_table*)mrb_malloc(mrb, ht_byte_size);
770  return (hash_table*)memcpy(new_ht, h_ht(h), ht_byte_size);
771 }
772 
773 static void
774 ht_adjust_ea(mrb_state *mrb, struct RHash *h, uint32_t size, uint32_t max_ea_capa)
775 {
776  uint32_t ea_capa = size;
777  hash_entry *ea = ea_adjust(mrb, ht_ea(h), &ea_capa, max_ea_capa);
778  ht_set_ea(h, ea);
779  ht_set_ea_capa(h, ea_capa);
780 }
781 
782 static void
783 ht_to_ar(mrb_state *mrb, struct RHash *h)
784 {
785  uint32_t size = ht_size(h), ea_capa = size;
786  hash_entry *ea = ht_ea(h);
788  ea = ea_adjust(mrb, ea, &ea_capa, AR_MAX_SIZE);
789  mrb_free(mrb, h_ht(h));
790  ar_init(h, size, ea, ea_capa, size);
791 }
792 
793 static mrb_bool
794 ht_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
795 {
796  ib_find_by_key(mrb, h, key, it, {
797  *valp = ib_it_entry(it)->val;
798  return TRUE;
799  });
800  return FALSE;
801 }
802 
803 static void
805 {
806  ht_to_ar(mrb, h);
807  ar_set(mrb, h, key, val);
808 }
809 
810 static void
813 {
815  ib_cycle_by_key(mrb, h, key, it, {
816  if (ib_it_active_p(it)) {
817  if (!obj_eql(mrb, key, ib_it_entry(it)->key, h)) continue;
818  ib_it_entry(it)->val = val;
819  }
820  else {
821  uint32_t ea_n_used = ht_ea_n_used(h);
822  if (ea_n_used == H_MAX_SIZE) {
823  mrb_assert(ht_size(h) == ea_n_used);
824  mrb_raise(mrb, E_ARGUMENT_ERROR, "hash too big");
825  }
826  if (ea_n_used == ht_ea_capa(h)) ht_adjust_ea(mrb, h, ea_n_used, EA_MAX_CAPA);
827  ib_it_set(it, ea_n_used);
828  ea_set(ht_ea(h), ea_n_used, key, val);
829  ht_inc_size(h);
830  ht_set_ea_n_used(h, ++ea_n_used);
831  }
832  return;
833  });
834 }
835 
836 static void
838 {
839  uint32_t size = ht_size(h);
840  uint32_t ib_bit_width = ib_bit(h), ib_capa = ib_bit_to_capa(ib_bit_width);
841  if (ib_upper_bound_for(ib_capa) <= size) {
843  ht_init(mrb, h, size, ht_ea(h), ht_ea_capa(h), h_ht(h), ++ib_bit_width);
844  }
845  else if (size != ht_ea_n_used(h)) {
846  if (ib_capa - EA_N_RESERVED_INDICES <= ht_ea_n_used(h)) goto compress;
847  if (ht_ea_capa(h) == ht_ea_n_used(h)) {
848  if (size <= AR_MAX_SIZE) {ht_set_as_ar(mrb, h, key, val); return;}
850  compress:
852  ht_adjust_ea(mrb, h, size, ht_ea_capa(h));
853  ht_init(mrb, h, size, ht_ea(h), ht_ea_capa(h), h_ht(h), ib_bit_width);
854  }
855  }
856  }
858 }
859 
860 static mrb_bool
862 {
863  ib_find_by_key(mrb, h, key, it, {
865  *valp = entry->val;
866  ib_it_delete(it);
868  ht_dec_size(h);
869  return TRUE;
870  });
871  return FALSE;
872 }
873 
874 static void
875 ht_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
876 {
877  hash_entry *ea = ht_ea(h);
878  ea_each(ea, ht_size(h), entry, {
879  ib_cycle_by_key(mrb, h, entry->key, it, {
880  if (ib_it_get(it) != U32(entry - ea)) continue;
881  *keyp = entry->key;
882  *valp = entry->val;
883  ib_it_delete(it);
884  entry_delete(entry);
885  ht_dec_size(h);
886  return;
887  });
888  });
889 }
890 
891 static void
892 ht_rehash(mrb_state *mrb, struct RHash *h)
893 {
894  /* see comments in `h_rehash` */
895  uint32_t size = ht_size(h), w_size = 0, ea_capa = ht_ea_capa(h);
896  hash_entry *ea = ht_ea(h);
897  ht_init(mrb, h, 0, ea, ea_capa, h_ht(h), ib_bit_for(size));
898  ht_set_size(h, size);
900  ea_each(ea, size, r_entry, {
901  ib_cycle_by_key(mrb, h, r_entry->key, it, {
902  if (ib_it_active_p(it)) {
903  if (!obj_eql(mrb, r_entry->key, ib_it_entry(it)->key, h)) continue;
904  ib_it_entry(it)->val = r_entry->val;
905  ht_set_size(h, --size);
906  entry_delete(r_entry);
907  }
908  else {
909  if (w_size != U32(r_entry - ea)) {
910  ea_set(ea, w_size, r_entry->key, r_entry->val);
911  entry_delete(r_entry);
912  }
913  ib_it_set(it, w_size++);
914  }
915  break;
916  });
917  });
918  mrb_assert(size == w_size);
920  size <= AR_MAX_SIZE ? ht_to_ar(mrb, h) : ht_adjust_ea(mrb, h, size, ea_capa);
921 }
922 
923 static mrb_value
925 {
927  key = mrb_str_dup(mrb, key);
929  }
930  return key;
931 }
932 
933 static struct RHash*
935 {
936  return (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);
937 }
938 
939 static void
940 h_init(struct RHash *h)
941 {
942  ar_init(h, 0, NULL, 0, 0);
943 }
944 
945 static void
947 {
948  (h_ar_p(h) ? ar_free : ht_free)(mrb, h);
949 }
950 
951 static void
952 h_clear(mrb_state *mrb, struct RHash *h)
953 {
954  h_free_table(mrb, h);
955  h_init(h);
956 }
957 
958 static mrb_bool
959 h_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
960 {
961  return (h_ar_p(h) ? ar_get : ht_get)(mrb, h, key, valp);
962 }
963 
964 static void
966 {
967  (h_ar_p(h) ? ar_set : ht_set)(mrb, h, key, val);
968 }
969 
970 static mrb_bool
972 {
973  return (h_ar_p(h) ? ar_delete : ht_delete)(mrb, h, key, valp);
974 }
975 
976 /* find first element in the table, and remove it. */
977 static void
978 h_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
979 {
980  (h_ar_p(h) ? ar_shift : ht_shift)(mrb, h, keyp, valp);
981 }
982 
983 static void
984 h_rehash(mrb_state *mrb, struct RHash *h)
985 {
986  /*
987  * ==== Comments common to `ar_rehash` and `ht_rehash`
988  *
989  * - Because reindex (such as elimination of duplicate keys) must be
990  * guaranteed, it is necessary to set one by one.
991  *
992  * - To prevent EA from breaking if an exception occurs in the middle,
993  * delete the slot before moving when moving the entry, and update size
994  * at any time when overwriting.
995  */
996  (h_size(h) == 0 ? h_clear : h_ar_p(h) ? ar_rehash : ht_rehash)(mrb, h);
997 }
998 
999 static void
1000 h_replace(mrb_state *mrb, struct RHash *h, struct RHash *orig_h)
1001 {
1002  uint32_t size = h_size(orig_h);
1003  if (size == 0) {
1004  h_clear(mrb, h);
1005  }
1006  else if (h_ar_p(orig_h)) {
1007  uint32_t ea_capa = ar_ea_capa(orig_h);
1008  hash_entry *ea = ea_dup(mrb, ar_ea(orig_h), ea_capa);
1009  h_free_table(mrb, h);
1010  ar_init(h, size, ea, ea_capa, ar_ea_n_used(orig_h));
1011  }
1012  else { /* HT */
1013  uint32_t ea_capa = ht_ea_capa(orig_h);
1014  hash_entry *ea = ea_dup(mrb, ht_ea(orig_h), ea_capa);
1015  hash_table *ht = ht_dup(mrb, orig_h);
1016  h_free_table(mrb, h);
1017  h_ht_on(h);
1018  h_set_ht(h, ht);
1019  ht_set_size(h, size);
1020  ht_set_ea(h, ea);
1021 #ifdef MRB_64BIT
1022  ht_set_ea_capa(h, ea_capa);
1023  ht_set_ea_n_used(h, ht_ea_n_used(orig_h));
1024 #endif
1025  ib_set_bit(h, ib_bit(orig_h));
1026  }
1027 }
1028 
1029 void
1031 {
1032  h_each(h, entry, {
1033  mrb_gc_mark_value(mrb, entry->key);
1034  mrb_gc_mark_value(mrb, entry->val);
1035  });
1036 }
1037 
1038 size_t
1040 {
1041  return h_size(h) * 2;
1042 }
1043 
1044 void
1046 {
1047  h_free_table(mrb, h);
1048 }
1049 
1050 size_t
1052 {
1053  struct RHash *h = mrb_hash_ptr(self);
1054  return mrb_obj_iv_tbl_memsize(self) +
1055  (h_ar_p(h) ? (ar_ea_capa(h) * sizeof(hash_entry)) :
1056  (ht_ea_capa(h) * sizeof(hash_entry) +
1057  sizeof(hash_table) +
1059 }
1060 
1061 /* Iterates over the key/value pairs. */
1062 MRB_API void
1064 {
1065  h_each(h, entry, {
1066  if (func(mrb, entry->key, entry->val, data) != 0) return;
1067  });
1068 }
1069 
1072 {
1073  struct RHash *h = h_alloc(mrb);
1074  return mrb_obj_value(h);
1075 }
1076 
1077 /*
1078  * Set the capacity of EA and IB to minimum capacity (and appropriate load
1079  * factor) that does not cause expansion when inserting `capa` elements.
1080  */
1083 {
1084  if (capa < 0 || EA_MAX_CAPA < capa) {
1085  mrb_raise(mrb, E_ARGUMENT_ERROR, "hash too big");
1086  return mrb_nil_value(); /* not reached */
1087  }
1088  else if (capa == 0) {
1089  return mrb_hash_new(mrb);
1090  }
1091  else {
1092  uint32_t size = U32(capa);
1093  struct RHash *h = h_alloc(mrb);
1094  hash_entry *ea = ea_resize(mrb, NULL, size);
1095  if (size <= AR_MAX_SIZE) {
1096  ar_init(h, 0, ea, size, 0);
1097  }
1098  else {
1099  ht_init(mrb, h, 0, ea, size, NULL, ib_bit_for(size));
1100  }
1101  return mrb_obj_value(h);
1102  }
1103 }
1104 
1106 
1107 static void
1109 {
1111 }
1112 
1113 static mrb_value
1115 {
1116  if (MRB_RHASH_DEFAULT_P(hash)) {
1118  return mrb_funcall_id(mrb, RHASH_PROCDEFAULT(hash), MRB_SYM(call), 2, hash, key);
1119  }
1120  else {
1121  return RHASH_IFNONE(hash);
1122  }
1123  }
1124  return mrb_nil_value();
1125 }
1126 
1127 static void
1129 {
1130  struct RHash *h = mrb_hash_ptr(self), *orig_h = mrb_hash_ptr(orig);
1132  mrb_sym name;
1133  h_replace(mrb, h, orig_h);
1134  name = MRB_SYM(ifnone);
1135  if (orig_h->flags & MRB_HASH_DEFAULT) {
1136  mrb_iv_set(mrb, self, name, mrb_iv_get(mrb, orig, name));
1137  }
1138  else {
1139  mrb_iv_remove(mrb, self, name);
1140  }
1141  h->flags &= ~~mask;
1142  h->flags |= orig_h->flags & mask;
1143 }
1144 
1145 static mrb_value
1147 {
1148  mrb_value orig;
1149  mrb_get_args(mrb, "H", &orig);
1150  hash_modify(mrb, self);
1151  if (mrb_hash_ptr(self) != mrb_hash_ptr(orig)) hash_replace(mrb, self, orig);
1152  return self;
1153 }
1154 
1155 void
1157 {
1158  h_each(mrb_hash_ptr(self), entry, {
1159  if (mrb_symbol_p(entry->key)) continue;
1160  mrb_raise(mrb, E_ARGUMENT_ERROR, "keyword argument hash with non symbol keys");
1161  });
1162 }
1163 
1166 {
1167  struct RHash* copy_h = h_alloc(mrb);
1168  mrb_value copy = mrb_obj_value(copy_h);
1169  copy_h->c = mrb_hash_ptr(self)->c;
1170  hash_replace(mrb, copy, self);
1171  return copy;
1172 }
1173 
1176 {
1177  mrb_value val;
1178  mrb_sym mid;
1179 
1180  if (h_get(mrb, mrb_hash_ptr(hash), key, &val)) {
1181  return val;
1182  }
1183 
1184  mid = MRB_SYM(default);
1185  if (mrb_func_basic_p(mrb, hash, mid, mrb_hash_default)) {
1186  return hash_default(mrb, hash, key);
1187  }
1188  /* xxx mrb_funcall_tailcall(mrb, hash, "default", 1, key); */
1189  return mrb_funcall_argv(mrb, hash, mid, 1, &key);
1190 }
1191 
1194 {
1195  mrb_value val;
1196 
1197  if (h_get(mrb, mrb_hash_ptr(hash), key, &val)) {
1198  return val;
1199  }
1200  /* not found */
1201  return def;
1202 }
1203 
1204 MRB_API void
1206 {
1207  hash_modify(mrb, hash);
1208  key = h_key_for(mrb, key);
1209  h_set(mrb, mrb_hash_ptr(hash), key, val);
1212 }
1213 
1214 /* 15.2.13.4.16 */
1215 /*
1216  * call-seq:
1217  * Hash.new -> new_hash
1218  * Hash.new(obj) -> new_hash
1219  * Hash.new {|hash, key| block } -> new_hash
1220  *
1221  * Returns a new, empty hash. If this hash is subsequently accessed by
1222  * a key that doesn't correspond to a hash entry, the value returned
1223  * depends on the style of <code>new</code> used to create the hash. In
1224  * the first form, the access returns <code>nil</code>. If
1225  * <i>obj</i> is specified, this single object will be used for
1226  * all <em>default values</em>. If a block is specified, it will be
1227  * called with the hash object and the key, and should return the
1228  * default value. It is the block's responsibility to store the value
1229  * in the hash if required.
1230  *
1231  * h = Hash.new("Go Fish")
1232  * h["a"] = 100
1233  * h["b"] = 200
1234  * h["a"] #=> 100
1235  * h["c"] #=> "Go Fish"
1236  * # The following alters the single default object
1237  * h["c"].upcase! #=> "GO FISH"
1238  * h["d"] #=> "GO FISH"
1239  * h.keys #=> ["a", "b"]
1240  *
1241  * # While this creates a new default object each time
1242  * h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
1243  * h["c"] #=> "Go Fish: c"
1244  * h["c"].upcase! #=> "GO FISH: C"
1245  * h["d"] #=> "Go Fish: d"
1246  * h.keys #=> ["c", "d"]
1247  *
1248  */
1249 
1250 static mrb_value
1252 {
1253  mrb_value block, ifnone;
1254  mrb_bool ifnone_p;
1255 
1256  ifnone = mrb_nil_value();
1257  mrb_get_args(mrb, "&|o?", &block, &ifnone, &ifnone_p);
1258  hash_modify(mrb, hash);
1259  if (!mrb_nil_p(block)) {
1260  if (ifnone_p) {
1261  mrb_argnum_error(mrb, 1, 0, 0);
1262  }
1263  RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
1264  ifnone = block;
1265  }
1266  if (!mrb_nil_p(ifnone)) {
1267  RHASH(hash)->flags |= MRB_HASH_DEFAULT;
1268  mrb_iv_set(mrb, hash, MRB_SYM(ifnone), ifnone);
1269  }
1270  return hash;
1271 }
1272 
1273 /* 15.2.13.4.2 */
1274 /*
1275  * call-seq:
1276  * hsh[key] -> value
1277  *
1278  * Element Reference---Retrieves the <i>value</i> object corresponding
1279  * to the <i>key</i> object. If not found, returns the default value (see
1280  * <code>Hash::new</code> for details).
1281  *
1282  * h = { "a" => 100, "b" => 200 }
1283  * h["a"] #=> 100
1284  * h["c"] #=> nil
1285  *
1286  */
1287 static mrb_value
1289 {
1290  mrb_value key = mrb_get_arg1(mrb);
1291 
1292  return mrb_hash_get(mrb, self, key);
1293 }
1294 
1295 /* 15.2.13.4.5 */
1296 /*
1297  * call-seq:
1298  * hsh.default(key=nil) -> obj
1299  *
1300  * Returns the default value, the value that would be returned by
1301  * <i>hsh</i>[<i>key</i>] if <i>key</i> did not exist in <i>hsh</i>.
1302  * See also <code>Hash::new</code> and <code>Hash#default=</code>.
1303  *
1304  * h = Hash.new #=> {}
1305  * h.default #=> nil
1306  * h.default(2) #=> nil
1307  *
1308  * h = Hash.new("cat") #=> {}
1309  * h.default #=> "cat"
1310  * h.default(2) #=> "cat"
1311  *
1312  * h = Hash.new {|h,k| h[k] = k.to_i*10} #=> {}
1313  * h.default #=> nil
1314  * h.default(2) #=> 20
1315  */
1316 
1317 static mrb_value
1319 {
1320  mrb_value key;
1321  mrb_bool given;
1322 
1323  mrb_get_args(mrb, "|o?", &key, &given);
1324  if (MRB_RHASH_DEFAULT_P(hash)) {
1326  if (!given) return mrb_nil_value();
1327  return mrb_funcall_id(mrb, RHASH_PROCDEFAULT(hash), MRB_SYM(call), 2, hash, key);
1328  }
1329  else {
1330  return RHASH_IFNONE(hash);
1331  }
1332  }
1333  return mrb_nil_value();
1334 }
1335 
1336 /* 15.2.13.4.6 */
1337 /*
1338  * call-seq:
1339  * hsh.default = obj -> obj
1340  *
1341  * Sets the default value, the value returned for a key that does not
1342  * exist in the hash. It is not possible to set the default to a
1343  * <code>Proc</code> that will be executed on each key lookup.
1344  *
1345  * h = { "a" => 100, "b" => 200 }
1346  * h.default = "Go fish"
1347  * h["a"] #=> 100
1348  * h["z"] #=> "Go fish"
1349  * # This doesn't do what you might hope...
1350  * h.default = proc do |hash, key|
1351  * hash[key] = key + key
1352  * end
1353  * h[2] #=> #<Proc:0x401b3948@-:6>
1354  * h["cat"] #=> #<Proc:0x401b3948@-:6>
1355  */
1356 
1357 static mrb_value
1359 {
1360  mrb_value ifnone = mrb_get_arg1(mrb);
1361 
1362  hash_modify(mrb, hash);
1363  mrb_iv_set(mrb, hash, MRB_SYM(ifnone), ifnone);
1364  RHASH(hash)->flags &= ~~MRB_HASH_PROC_DEFAULT;
1365  if (!mrb_nil_p(ifnone)) {
1366  RHASH(hash)->flags |= MRB_HASH_DEFAULT;
1367  }
1368  else {
1369  RHASH(hash)->flags &= ~~MRB_HASH_DEFAULT;
1370  }
1371  return ifnone;
1372 }
1373 
1374 /* 15.2.13.4.7 */
1375 /*
1376  * call-seq:
1377  * hsh.default_proc -> anObject
1378  *
1379  * If <code>Hash::new</code> was invoked with a block, return that
1380  * block, otherwise return <code>nil</code>.
1381  *
1382  * h = Hash.new {|h,k| h[k] = k*k } #=> {}
1383  * p = h.default_proc #=> #<Proc:0x401b3d08@-:1>
1384  * a = [] #=> []
1385  * p.call(a, 2)
1386  * a #=> [nil, nil, 4]
1387  */
1388 
1389 static mrb_value
1391 {
1393  return RHASH_PROCDEFAULT(hash);
1394  }
1395  return mrb_nil_value();
1396 }
1397 
1398 /*
1399  * call-seq:
1400  * hsh.default_proc = proc_obj -> proc_obj
1401  *
1402  * Sets the default proc to be executed on each key lookup.
1403  *
1404  * h.default_proc = proc do |hash, key|
1405  * hash[key] = key + key
1406  * end
1407  * h[2] #=> 4
1408  * h["cat"] #=> "catcat"
1409  */
1410 
1411 static mrb_value
1413 {
1414  mrb_value ifnone = mrb_get_arg1(mrb);
1415 
1416  hash_modify(mrb, hash);
1417  mrb_iv_set(mrb, hash, MRB_SYM(ifnone), ifnone);
1418  if (!mrb_nil_p(ifnone)) {
1419  RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT;
1420  RHASH(hash)->flags |= MRB_HASH_DEFAULT;
1421  }
1422  else {
1423  RHASH(hash)->flags &= ~~MRB_HASH_DEFAULT;
1424  RHASH(hash)->flags &= ~~MRB_HASH_PROC_DEFAULT;
1425  }
1426 
1427  return ifnone;
1428 }
1429 
1432 {
1433  mrb_value del_val;
1434 
1435  hash_modify(mrb, hash);
1436  if (h_delete(mrb, mrb_hash_ptr(hash), key, &del_val)) {
1437  return del_val;
1438  }
1439 
1440  /* not found */
1441  return mrb_nil_value();
1442 }
1443 
1444 static mrb_value
1446 {
1447  mrb_value key = mrb_get_arg1(mrb);
1448  return mrb_hash_delete_key(mrb, self, key);
1449 }
1450 
1451 /* 15.2.13.4.24 */
1452 /*
1453  * call-seq:
1454  * hsh.shift -> anArray or obj
1455  *
1456  * Removes a key-value pair from <i>hsh</i> and returns it as the
1457  * two-item array <code>[</code> <i>key, value</i> <code>]</code>, or
1458  * the hash's default value if the hash is empty.
1459  *
1460  * h = { 1 => "a", 2 => "b", 3 => "c" }
1461  * h.shift #=> [1, "a"]
1462  * h #=> {2=>"b", 3=>"c"}
1463  */
1464 
1465 static mrb_value
1467 {
1468  struct RHash *h = mrb_hash_ptr(hash);
1469 
1470  hash_modify(mrb, hash);
1471  if (h_size(h) == 0) {
1472  return hash_default(mrb, hash, mrb_nil_value());
1473  }
1474  else {
1475  mrb_value del_key, del_val;
1476  h_shift(mrb, h, &del_key, &del_val);
1477  mrb_gc_protect(mrb, del_key);
1478  mrb_gc_protect(mrb, del_val);
1479  return mrb_assoc_new(mrb, del_key, del_val);
1480  }
1481 }
1482 
1483 /* 15.2.13.4.4 */
1484 /*
1485  * call-seq:
1486  * hsh.clear -> hsh
1487  *
1488  * Removes all key-value pairs from `hsh`.
1489  *
1490  * h = { "a" => 100, "b" => 200 } #=> {"a"=>100, "b"=>200}
1491  * h.clear #=> {}
1492  *
1493  */
1494 
1497 {
1498  hash_modify(mrb, hash);
1499  h_clear(mrb, mrb_hash_ptr(hash));
1500  return hash;
1501 }
1502 
1503 /* 15.2.13.4.3 */
1504 /* 15.2.13.4.26 */
1505 /*
1506  * call-seq:
1507  * hsh[key] = value -> value
1508  * hsh.store(key, value) -> value
1509  *
1510  * Element Assignment---Associates the value given by
1511  * <i>value</i> with the key given by <i>key</i>.
1512  * <i>key</i> should not have its value changed while it is in
1513  * use as a key (a <code>String</code> passed as a key will be
1514  * duplicated and frozen).
1515  *
1516  * h = { "a" => 100, "b" => 200 }
1517  * h["a"] = 9
1518  * h["c"] = 4
1519  * h #=> {"a"=>9, "b"=>200, "c"=>4}
1520  *
1521  */
1522 static mrb_value
1524 {
1525  mrb_value key, val;
1526 
1527  mrb_get_args(mrb, "oo", &key, &val);
1528  mrb_hash_set(mrb, self, key, val);
1529  return val;
1530 }
1531 
1534 {
1535  return (mrb_int)h_size(mrb_hash_ptr(hash));
1536 }
1537 
1538 /* 15.2.13.4.20 */
1539 /* 15.2.13.4.25 */
1540 /*
1541  * call-seq:
1542  * hsh.length -> integer
1543  * hsh.size -> integer
1544  *
1545  * Returns the number of key-value pairs in the hash.
1546  *
1547  * h = { "d" => 100, "a" => 200, "v" => 300, "e" => 400 }
1548  * h.length #=> 4
1549  * h.delete("a") #=> 200
1550  * h.length #=> 3
1551  */
1552 static mrb_value
1554 {
1555  mrb_int size = mrb_hash_size(mrb, self);
1556  return mrb_int_value(mrb, size);
1557 }
1558 
1561 {
1562  return h_size(mrb_hash_ptr(self)) == 0;
1563 }
1564 
1565 /* 15.2.13.4.12 */
1566 /*
1567  * call-seq:
1568  * hsh.empty? -> true or false
1569  *
1570  * Returns <code>true</code> if <i>hsh</i> contains no key-value pairs.
1571  *
1572  * {}.empty? #=> true
1573  *
1574  */
1575 static mrb_value
1577 {
1578  return mrb_bool_value(mrb_hash_empty_p(mrb, self));
1579 }
1580 
1581 /* 15.2.13.4.19 */
1582 /*
1583  * call-seq:
1584  * hsh.keys -> array
1585  *
1586  * Returns a new array populated with the keys from this hash. See also
1587  * <code>Hash#values</code>.
1588  *
1589  * h = { "a" => 100, "b" => 200, "c" => 300, "d" => 400 }
1590  * h.keys #=> ["a", "b", "c", "d"]
1591  *
1592  */
1593 
1596 {
1597  struct RHash *h = mrb_hash_ptr(hash);
1598  mrb_value ary = mrb_ary_new_capa(mrb, (mrb_int)h_size(h));
1599  h_each(h, entry, {
1600  mrb_ary_push(mrb, ary, entry->key);
1601  });
1602  return ary;
1603 }
1604 
1605 /* 15.2.13.4.28 */
1606 /*
1607  * call-seq:
1608  * hsh.values -> array
1609  *
1610  * Returns a new array populated with the values from <i>hsh</i>. See
1611  * also <code>Hash#keys</code>.
1612  *
1613  * h = { "a" => 100, "b" => 200, "c" => 300 }
1614  * h.values #=> [100, 200, 300]
1615  *
1616  */
1617 
1620 {
1621  struct RHash *h = mrb_hash_ptr(hash);
1622  mrb_value ary = mrb_ary_new_capa(mrb, (mrb_int)h_size(h));
1623  h_each(h, entry, {
1624  mrb_ary_push(mrb, ary, entry->val);
1625  });
1626  return ary;
1627 }
1628 
1629 /* 15.2.13.4.13 */
1630 /* 15.2.13.4.15 */
1631 /* 15.2.13.4.18 */
1632 /* 15.2.13.4.21 */
1633 /*
1634  * call-seq:
1635  * hsh.has_key?(key) -> true or false
1636  * hsh.include?(key) -> true or false
1637  * hsh.key?(key) -> true or false
1638  * hsh.member?(key) -> true or false
1639  *
1640  * Returns <code>true</code> if the given key is present in <i>hsh</i>.
1641  *
1642  * h = { "a" => 100, "b" => 200 }
1643  * h.has_key?("a") #=> true
1644  * h.has_key?("z") #=> false
1645  *
1646  */
1647 
1650 {
1651  mrb_value val;
1652  return h_get(mrb, mrb_hash_ptr(hash), key, &val);
1653 }
1654 
1655 static mrb_value
1657 {
1658  mrb_value key = mrb_get_arg1(mrb);
1659  mrb_bool key_p;
1660 
1661  key_p = mrb_hash_key_p(mrb, hash, key);
1662  return mrb_bool_value(key_p);
1663 }
1664 
1665 /* 15.2.13.4.14 */
1666 /* 15.2.13.4.27 */
1667 /*
1668  * call-seq:
1669  * hsh.has_value?(value) -> true or false
1670  * hsh.value?(value) -> true or false
1671  *
1672  * Returns <code>true</code> if the given value is present for some key
1673  * in <i>hsh</i>.
1674  *
1675  * h = { "a" => 100, "b" => 200 }
1676  * h.has_value?(100) #=> true
1677  * h.has_value?(999) #=> false
1678  */
1679 
1680 static mrb_value
1682 {
1683  mrb_value val = mrb_get_arg1(mrb);
1684  struct RHash *h = mrb_hash_ptr(hash);
1685  h_each(h, entry, {
1686  h_check_modified(mrb, h, {
1687  if (mrb_equal(mrb, val, entry->val)) return mrb_true_value();
1688  });
1689  });
1690  return mrb_false_value();
1691 }
1692 
1693 MRB_API void
1695 {
1696  struct RHash *h1, *h2;
1697 
1698  hash_modify(mrb, hash1);
1699  mrb_ensure_hash_type(mrb, hash2);
1700  h1 = mrb_hash_ptr(hash1);
1701  h2 = mrb_hash_ptr(hash2);
1702 
1703  if (h1 == h2) return;
1704  if (h_size(h2) == 0) return;
1705  h_each(h2, entry, {
1706  h_check_modified(mrb, h2, {h_set(mrb, h1, entry->key, entry->val);});
1707  mrb_field_write_barrier_value(mrb, (struct RBasic *)h1, entry->key);
1708  mrb_field_write_barrier_value(mrb, (struct RBasic *)h1, entry->val);
1709  });
1710 }
1711 
1712 /*
1713  * call-seq:
1714  * hsh.rehash -> hsh
1715  *
1716  * Rebuilds the hash based on the current hash values for each key. If
1717  * values of key objects have changed since they were inserted, this
1718  * method will reindex <i>hsh</i>.
1719  *
1720  * keys = (1..17).map{|n| [n]}
1721  * k = keys[0]
1722  * h = {}
1723  * keys.each{|key| h[key] = key[0]}
1724  * h #=> { [1]=>1, [2]=>2, ... [16]=>16, [17]=>17}
1725  * h[k] #=> 1
1726  * k[0] = keys.size + 1
1727  * h #=> {[18]=>1, [2]=>2, ... [16]=>16, [17]=>17}
1728  * h[k] #=> nil
1729  * h.rehash
1730  * h[k] #=> 1
1731  */
1732 static mrb_value
1734 {
1735  h_rehash(mrb, mrb_hash_ptr(self));
1736  return self;
1737 }
1738 
1739 void
1741 {
1742  struct RClass *h;
1743 
1744  mrb->hash_class = h = mrb_define_class(mrb, "Hash", mrb->object_class); /* 15.2.13 */
1746 
1747  mrb_define_method(mrb, h, "[]", mrb_hash_aget, MRB_ARGS_REQ(1)); /* 15.2.13.4.2 */
1748  mrb_define_method(mrb, h, "[]=", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.3 */
1749  mrb_define_method(mrb, h, "clear", mrb_hash_clear, MRB_ARGS_NONE()); /* 15.2.13.4.4 */
1750  mrb_define_method(mrb, h, "default", mrb_hash_default, MRB_ARGS_OPT(1)); /* 15.2.13.4.5 */
1751  mrb_define_method(mrb, h, "default=", mrb_hash_set_default, MRB_ARGS_REQ(1)); /* 15.2.13.4.6 */
1752  mrb_define_method(mrb, h, "default_proc", mrb_hash_default_proc,MRB_ARGS_NONE()); /* 15.2.13.4.7 */
1753  mrb_define_method(mrb, h, "default_proc=", mrb_hash_set_default_proc,MRB_ARGS_REQ(1)); /* 15.2.13.4.7 */
1754  mrb_define_method(mrb, h, "__delete", mrb_hash_delete, MRB_ARGS_REQ(1)); /* core of 15.2.13.4.8 */
1755  mrb_define_method(mrb, h, "empty?", mrb_hash_empty_m, MRB_ARGS_NONE()); /* 15.2.13.4.12 */
1756  mrb_define_method(mrb, h, "has_key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.13 */
1757  mrb_define_method(mrb, h, "has_value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.14 */
1758  mrb_define_method(mrb, h, "include?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.15 */
1759  mrb_define_method(mrb, h, "initialize", mrb_hash_init, MRB_ARGS_OPT(1)|MRB_ARGS_BLOCK()); /* 15.2.13.4.16 */
1760  mrb_define_method(mrb, h, "initialize_copy", mrb_hash_init_copy, MRB_ARGS_REQ(1)); /* 15.2.13.4.17 */
1761  mrb_define_method(mrb, h, "key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.18 */
1762  mrb_define_method(mrb, h, "keys", mrb_hash_keys, MRB_ARGS_NONE()); /* 15.2.13.4.19 */
1763  mrb_define_method(mrb, h, "length", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.20 */
1764  mrb_define_method(mrb, h, "member?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.21 */
1765  mrb_define_method(mrb, h, "replace", mrb_hash_init_copy, MRB_ARGS_REQ(1)); /* 15.2.13.4.23 */
1766  mrb_define_method(mrb, h, "shift", mrb_hash_shift, MRB_ARGS_NONE()); /* 15.2.13.4.24 */
1767  mrb_define_method(mrb, h, "size", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.25 */
1768  mrb_define_method(mrb, h, "store", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.26 */
1769  mrb_define_method(mrb, h, "value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.27 */
1770  mrb_define_method(mrb, h, "values", mrb_hash_values, MRB_ARGS_NONE()); /* 15.2.13.4.28 */
1771  mrb_define_method(mrb, h, "rehash", mrb_hash_rehash, MRB_ARGS_NONE());
1772 }
#define CHAR_BIT
Definition: ChkTeX.h:91
#define name
#define call
Definition: aptex-macros.h:493
#define mrb_symbol(o)
Definition: boxing_nan.h:72
#define mrb_integer(o)
Definition: boxing_nan.h:71
#define mrb_string_p(o)
Definition: boxing_word.h:153
#define mrb_integer_p(o)
Definition: boxing_word.h:139
#define mrb_symbol_p(o)
Definition: boxing_word.h:143
#define mrb_undef_p(o)
Definition: boxing_word.h:145
#define mrb_float_p(o)
Definition: boxing_word.h:150
#define mrb_nil_p(o)
Definition: boxing_word.h:146
MRB_INLINE enum mrb_vtype mrb_type(mrb_value o)
Definition: boxing_word.h:195
#define MRB_SET_INSTANCE_TT(c, tt)
Definition: class.h:73
#define b
Definition: jpegint.h:372
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
char * def
Definition: definitions.c:41
#define MRB_SYM(name)
Definition: disable.h:20
int v
Definition: dviconv.c:10
int h
Definition: dviconv.c:9
struct rect data
Definition: dvipdfm.c:64
static void copy(GlyphCachePtr *root)
Definition: gcache.c:378
#define a(n)
Definition: gpos-common.c:148
#define memcpy(d, s, n)
Definition: gsftopk.c:64
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
unsigned int uint32_t
Definition: stdint.h:80
pdf_obj * entry
Definition: pdfdoc.c:64
#define compress(c)
Definition: ctangleboot.c:151
static luaL_Reg func[]
Definition: except.c:32
#define size_t
Definition: glob.c:257
struct RBasic * mrb_obj_alloc(mrb_state *, enum mrb_vtype, struct RClass *)
Definition: gc.c:535
void mrb_argnum_error(mrb_state *mrb, mrb_int argc, int min, int max)
Definition: error.c:547
#define mrb_field_write_barrier_value(mrb, obj, val)
Definition: mruby.h:1252
void mrb_gc_protect(mrb_state *mrb, mrb_value obj)
Definition: gc.c:471
mrb_value mrb_funcall_id(mrb_state *mrb, mrb_value val, mrb_sym mid, mrb_int argc,...)
Definition: vm.c:337
mrb_value mrb_funcall_argv(mrb_state *mrb, mrb_value val, mrb_sym name, mrb_int argc, const mrb_value *argv)
Definition: vm.c:481
#define mrb_gc_mark_value(mrb, val)
Definition: mruby.h:1248
void * mrb_realloc(mrb_state *, void *, size_t)
Definition: gc.c:238
#define MRB_ARGS_OPT(n)
Definition: mruby.h:845
mrb_value mrb_get_arg1(mrb_state *mrb)
Definition: class.c:840
mrb_bool mrb_func_basic_p(mrb_state *mrb, mrb_value obj, mrb_sym mid, mrb_func_t func)
Definition: kernel.c:19
#define mrb_assert(p)
Definition: mruby.h:65
mrb_int mrb_get_args(mrb_state *mrb, mrb_args_format format,...)
Definition: class.c:891
void mrb_raise(mrb_state *mrb, struct RClass *c, const char *msg)
Definition: error.c:214
mrb_int mrb_obj_id(mrb_value obj)
Definition: etc.c:104
void mrb_free(mrb_state *, void *)
Definition: gc.c:288
#define MRB_ARGS_NONE()
Definition: mruby.h:879
#define MRB_ARGS_REQ(n)
Definition: mruby.h:837
mrb_bool mrb_equal(mrb_state *mrb, mrb_value obj1, mrb_value obj2)
Definition: object.c:46
#define MRB_ARGS_BLOCK()
Definition: mruby.h:869
static void mrb_check_frozen(mrb_state *mrb, void *o)
Definition: mruby.h:1348
void * mrb_malloc(mrb_state *, size_t)
Definition: gc.c:256
mrb_bool mrb_eql(mrb_state *mrb, mrb_value obj1, mrb_value obj2)
Definition: object.c:661
#define mrb_static_assert1(exp)
Definition: mruby.h:89
#define E_ARGUMENT_ERROR
Definition: mruby.h:1310
#define MRB_SET_FROZEN_FLAG(o)
Definition: object.h:26
#define MRB_FROZEN_P(o)
Definition: object.h:25
#define mrb_basic_ptr(v)
Definition: object.h:22
unsigned char bit
Definition: pbm.h:9
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 abits op endm macro pixldst3 mem_operand op endm macro pixldst30 mem_operand op endm macro pixldst abits if abits elseif abits elseif abits elseif abits elseif abits pixldst0 abits else pixldst0 abits pixldst0 abits pixldst0 abits pixldst0 abits endif elseif abits else pixldst0 abits pixldst0 abits endif elseif abits else error unsupported bpp *numpix else pixst endif endm macro pixld1_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl else error unsupported endif endm macro pixld2_s mem_operand if mov asr add asl add asl mov asr sub UNIT_X add asl mov asr add asl add asl mov asr add UNIT_X add asl else pixld1_s mem_operand pixld1_s mem_operand endif endm macro pixld0_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl endif endm macro pixld_s_internal mem_operand if mem_operand pixld2_s mem_operand pixdeinterleave basereg elseif mem_operand elseif mem_operand elseif mem_operand elseif mem_operand pixld0_s mem_operand else pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else error unsupported mem_operand if bpp mem_operand endif endm macro vuzp8 reg2 vuzp d d &reg2 endm macro vzip8 reg2 vzip d d &reg2 endm macro pixdeinterleave basereg basereg basereg basereg basereg endif endm macro pixinterleave basereg basereg basereg basereg basereg endif endm macro PF boost_increment endif if endif PF tst PF addne PF subne PF cmp ORIG_W if endif if endif if endif PF subge ORIG_W PF subges if endif if endif if endif endif endm macro cache_preload_simple endif if dst_r_bpp pld[DST_R, #(PREFETCH_DISTANCE_SIMPLE *dst_r_bpp/8)] endif if mask_bpp pld if[MASK, #(PREFETCH_DISTANCE_SIMPLE *mask_bpp/8)] endif endif endm macro fetch_mask_pixblock pixld mask_basereg pixblock_size MASK endm macro ensure_destination_ptr_alignment process_pixblock_tail_head if beq irp skip1(dst_w_bpp<=(lowbit *8)) &&((lowbit *8)<(pixblock_size *dst_w_bpp)) .if lowbit< 16 tst DST_R
#define index(s, c)
Definition: plain2.h:351
integer iv
Definition: pmxab.c:86
static int size
Definition: ppmlabel.c:24
bstring c int memset(void *s, int c, int length)
mrb_value mrb_ary_new_capa(mrb_state *, mrb_int)
Definition: array.c:46
void mrb_ary_push(mrb_state *mrb, mrb_value array, mrb_value value)
Definition: array.c:495
mrb_value mrb_assoc_new(mrb_state *mrb, mrb_value car, mrb_value cdr)
Definition: array.c:101
#define MRB_API
Definition: common.h:73
#define MRB_HASH_PROC_DEFAULT
Definition: hash.h:226
#define MRB_HASH_DEFAULT
Definition: hash.h:225
#define MRB_HASH_AR_EA_CAPA_BIT
Definition: hash.h:217
#define MRB_RHASH_DEFAULT_P(hash)
Definition: hash.h:228
#define RHASH(hash)
Definition: hash.h:214
int() mrb_hash_foreach_func(mrb_state *mrb, mrb_value key, mrb_value val, void *data)
Definition: hash.h:237
mrb_value mrb_ensure_hash_type(mrb_state *mrb, mrb_value hash)
Definition: object.c:639
#define MRB_RHASH_PROCDEFAULT_P(hash)
Definition: hash.h:229
#define mrb_hash_ptr(v)
Definition: hash.h:35
#define mrb_define_method(mrb, c, name, f, a)
Definition: scanning.h:15
#define mrb_define_class(mrb, name, s)
Definition: scanning.h:18
size_t mrb_obj_iv_tbl_memsize(mrb_value)
Definition: variable.c:1124
mrb_value mrb_iv_get(mrb_state *mrb, mrb_value obj, mrb_sym sym)
Definition: variable.c:320
mrb_value mrb_iv_remove(mrb_state *mrb, mrb_value obj, mrb_sym sym)
Definition: variable.c:508
void mrb_iv_set(mrb_state *mrb, mrb_value obj, mrb_sym sym, mrb_value v)
Definition: variable.c:389
static void ar_init(struct RHash *h, uint32_t size, hash_entry *ea, uint32_t ea_capa, uint32_t ea_n_used)
Definition: hash.c:438
static uint32_t ar_size(const struct RHash *h)
Definition: hash.c:158
static mrb_value mrb_hash_default(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1318
#define ib_cycle_by_key(mrb, h, key, it_var, code)
Definition: hash.c:187
static uint32_t ib_upper_bound_for(uint32_t capa)
Definition: hash.c:705
static void ht_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
Definition: hash.c:875
#define U32(v)
Definition: hash.c:254
static uint32_t ht_ea_capa(const struct RHash *h)
Definition: hash.c:149
static void ar_free(mrb_state *mrb, struct RHash *h)
Definition: hash.c:449
static void ib_it_next(index_buckets_iter *it)
Definition: hash.c:612
static void ht_set_ea_n_used(struct RHash *h, uint32_t v)
Definition: hash.c:150
static uint32_t ib_capa_to_bit(uint32_t capa)
Definition: hash.c:684
static hash_entry * ar_ea(const struct RHash *h)
Definition: hash.c:159
static mrb_bool ht_delete(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
Definition: hash.c:861
static uint32_t ib_it_get(const index_buckets_iter *it)
Definition: hash.c:651
static mrb_value mrb_hash_rehash(mrb_state *mrb, mrb_value self)
Definition: hash.c:1733
static uint32_t obj_hash_code(mrb_state *mrb, mrb_value key, struct RHash *h)
Definition: hash.c:287
static uint32_t ib_it_deleted_value(const index_buckets_iter *it)
Definition: hash.c:578
static void hash_replace(mrb_state *mrb, mrb_value self, mrb_value orig)
Definition: hash.c:1128
static void ht_set_without_ib_adjustment(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
Definition: hash.c:811
static void ht_adjust_ea(mrb_state *mrb, struct RHash *h, uint32_t size, uint32_t max_ea_capa)
Definition: hash.c:774
#define h_ar_p(h)
Definition: hash.c:255
#define ib_find_by_key(mrb, h_, key_, it_var, code)
Definition: hash.c:196
#define DEFINE_DECREMENTER(c_, n_)
Definition: hash.c:131
#define AR_MAX_SIZE
Definition: hash.c:69
static uint32_t ib_bit(const struct RHash *h)
Definition: hash.c:157
static void ar_set_ea_capa(struct RHash *h, uint32_t v)
Definition: hash.c:147
#define EA_N_RESERVED_INDICES
Definition: hash.c:56
static mrb_value mrb_hash_set_default_proc(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1412
static void h_rehash(mrb_state *mrb, struct RHash *h)
Definition: hash.c:984
static mrb_value mrb_hash_init(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1251
void mrb_hash_merge(mrb_state *mrb, mrb_value hash1, mrb_value hash2)
Definition: hash.c:1694
#define lesser(a, b)
Definition: hash.c:257
#define EA_MAX_CAPA
Definition: hash.c:59
static hash_entry * ea_dup(mrb_state *mrb, const hash_entry *ea, uint32_t capa)
Definition: hash.c:407
static void ea_compress(hash_entry *ea, uint32_t n_used)
Definition: hash.c:384
static void ib_it_init(mrb_state *mrb, index_buckets_iter *it, struct RHash *h, mrb_value key)
Definition: hash.c:602
#define EA_MAX_INCREASE
Definition: hash.c:58
static mrb_value mrb_hash_has_key(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1656
static mrb_value mrb_hash_has_value(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1681
static mrb_bool obj_eql(mrb_state *mrb, mrb_value a, mrb_value b, struct RHash *h)
Definition: hash.c:317
static void h_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
Definition: hash.c:978
static void h_init(struct RHash *h)
Definition: hash.c:940
static mrb_value mrb_hash_set_default(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1358
static void ht_inc_size(struct RHash *h)
Definition: hash.c:164
static mrb_value mrb_hash_delete(mrb_state *mrb, mrb_value self)
Definition: hash.c:1445
static void ar_shift(mrb_state *mrb, struct RHash *h, mrb_value *keyp, mrb_value *valp)
Definition: hash.c:528
static mrb_bool ib_it_deleted_p(const index_buckets_iter *it)
Definition: hash.c:590
static mrb_bool ar_delete(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
Definition: hash.c:517
#define H_MAX_SIZE
Definition: hash.c:70
#define RHASH_PROCDEFAULT(hash)
Definition: hash.c:259
mrb_value mrb_hash_dup(mrb_state *mrb, mrb_value self)
Definition: hash.c:1165
mrb_value mrb_hash_values(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1619
size_t mrb_gc_mark_hash_size(mrb_state *mrb, struct RHash *h)
Definition: hash.c:1039
#define ea_each(ea, size, entry_var, code)
Definition: hash.c:177
#define IB_TYPE_BIT
Definition: hash.c:61
static mrb_value mrb_hash_shift(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1466
static hash_entry * ea_adjust(mrb_state *mrb, hash_entry *ea, uint32_t *capap, uint32_t max_capa)
Definition: hash.c:400
static uint32_t ar_ea_capa(const struct RHash *h)
Definition: hash.c:147
static void ht_rehash(mrb_state *mrb, struct RHash *h)
Definition: hash.c:892
void mrb_hash_foreach(mrb_state *mrb, struct RHash *h, mrb_hash_foreach_func *func, void *data)
Definition: hash.c:1063
#define EA_INCREASE_RATIO
Definition: hash.c:57
mrb_value mrb_hash_new_capa(mrb_state *mrb, mrb_int capa)
Definition: hash.c:1082
static uint32_t h_size(const struct RHash *h)
Definition: hash.c:166
static void h_clear(mrb_state *mrb, struct RHash *h)
Definition: hash.c:952
struct index_buckets_iter index_buckets_iter
static void h_set(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
Definition: hash.c:965
mrb_value mrb_hash_keys(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1595
static void ar_set_size(struct RHash *h, uint32_t v)
Definition: hash.c:158
#define AR_DEFAULT_CAPA
Definition: hash.c:68
void mrb_hash_set(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value val)
Definition: hash.c:1205
static hash_entry * ea_get(hash_entry *ea, uint32_t index)
Definition: hash.c:425
static void ht_set_ea_capa(struct RHash *h, uint32_t v)
Definition: hash.c:149
static void ar_set_ea_n_used(struct RHash *h, uint32_t v)
Definition: hash.c:148
static void ar_dec_size(struct RHash *h)
Definition: hash.c:160
static mrb_bool entry_deleted_p(const hash_entry *entry)
Definition: hash.c:347
#define IB_INIT_BIT
Definition: hash.c:62
static hash_entry * ht_ea(const struct RHash *h)
Definition: hash.c:162
static uint32_t ib_bit_for(uint32_t size)
Definition: hash.c:711
static hash_table * h_ht(const struct RHash *h)
Definition: hash.c:167
static void h_set_ht(struct RHash *h, hash_table *v)
Definition: hash.c:167
static mrb_value mrb_hash_size_m(mrb_state *mrb, mrb_value self)
Definition: hash.c:1553
static uint32_t * ht_ib(const struct RHash *h)
Definition: hash.c:163
mrb_int mrb_hash_size(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1533
#define h_ar_on(h)
Definition: hash.c:256
static mrb_bool ar_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
Definition: hash.c:473
static mrb_value mrb_hash_init_copy(mrb_state *mrb, mrb_value self)
Definition: hash.c:1146
static uint32_t ib_byte_size_for(uint32_t ib_bit)
Definition: hash.c:719
static void entry_delete(hash_entry *entry)
Definition: hash.c:353
#define h_check_modified(mrb, h, code)
Definition: hash.c:238
#define DEFINE_FLAG_ACCESSOR(c_, n_, t_, k_)
Definition: hash.c:124
struct hash_table hash_table
static void ht_set_size(struct RHash *h, uint32_t v)
Definition: hash.c:161
static void ar_set(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
Definition: hash.c:484
static hash_table * ht_dup(mrb_state *mrb, const struct RHash *h)
Definition: hash.c:765
static void ht_set_as_ar(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
Definition: hash.c:804
static hash_entry * ib_it_entry(index_buckets_iter *it)
Definition: hash.c:678
#define HT_ASSERT_SAFE_READ(attr_name)
Definition: hash.c:229
static void ea_set(hash_entry *ea, uint32_t index, mrb_value key, mrb_value val)
Definition: hash.c:431
mrb_value mrb_hash_clear(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1496
#define ea_each_used(ea, n_used, entry_var, code)
Definition: hash.c:170
static mrb_value mrb_hash_aset(mrb_state *mrb, mrb_value self)
Definition: hash.c:1523
mrb_value mrb_hash_new(mrb_state *mrb)
Definition: hash.c:1071
static mrb_bool ht_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
Definition: hash.c:794
void mrb_init_hash(mrb_state *mrb)
Definition: hash.c:1740
static void ht_dec_size(struct RHash *h)
Definition: hash.c:165
#define h_each(h, entry_var, code)
Definition: hash.c:208
static uint32_t ar_ea_n_used(const struct RHash *h)
Definition: hash.c:148
static mrb_bool ib_it_empty_p(const index_buckets_iter *it)
Definition: hash.c:584
static void hash_modify(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1108
static void h_ht_on(struct RHash *h)
Definition: hash.c:168
#define DEFINE_INCREMENTER(c_, n_)
Definition: hash.c:127
static void ht_set_ea(struct RHash *h, hash_entry *v)
Definition: hash.c:162
static mrb_bool h_get(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
Definition: hash.c:959
static void ht_set(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value val)
Definition: hash.c:837
static void ar_adjust_ea(mrb_state *mrb, struct RHash *h, uint32_t size, uint32_t max_ea_capa)
Definition: hash.c:455
#define DEFINE_SWITCHER(n_, k_)
Definition: hash.c:135
static mrb_value mrb_hash_empty_m(mrb_state *mrb, mrb_value self)
Definition: hash.c:1576
static mrb_bool h_delete(mrb_state *mrb, struct RHash *h, mrb_value key, mrb_value *valp)
Definition: hash.c:971
#define IB_MAX_CAPA
Definition: hash.c:60
static uint32_t ht_ea_n_used(const struct RHash *h)
Definition: hash.c:150
static void ar_compress(mrb_state *mrb, struct RHash *h)
Definition: hash.c:464
static void ht_init(mrb_state *mrb, struct RHash *h, uint32_t size, hash_entry *ea, uint32_t ea_capa, hash_table *ht, uint32_t ib_bit)
Definition: hash.c:743
static uint32_t ib_it_pos_for(index_buckets_iter *it, uint32_t v)
Definition: hash.c:566
static mrb_value hash_default(mrb_state *mrb, mrb_value hash, mrb_value key)
Definition: hash.c:1114
mrb_bool mrb_hash_key_p(mrb_state *mrb, mrb_value hash, mrb_value key)
Definition: hash.c:1649
#define DEFINE_ACCESSOR(c_, n_, t_, p_)
Definition: hash.c:112
static mrb_value mrb_hash_default_proc(mrb_state *mrb, mrb_value hash)
Definition: hash.c:1390
size_t mrb_hash_memsize(mrb_value self)
Definition: hash.c:1051
static mrb_value mrb_hash_aget(mrb_state *mrb, mrb_value self)
Definition: hash.c:1288
#define DEFINE_GETTER(c_, n_, t_, p_)
Definition: hash.c:108
mrb_value mrb_hash_fetch(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value def)
Definition: hash.c:1193
static uint32_t ea_next_capa_for(uint32_t size, uint32_t max_capa)
Definition: hash.c:359
static struct RHash * h_alloc(mrb_state *mrb)
Definition: hash.c:934
mrb_value mrb_hash_delete_key(mrb_state *mrb, mrb_value hash, mrb_value key)
Definition: hash.c:1431
static uint32_t next_power2(uint32_t v)
Definition: hash.c:270
mrb_value mrb_hash_get(mrb_state *mrb, mrb_value hash, mrb_value key)
Definition: hash.c:1175
static hash_entry * ea_resize(mrb_state *mrb, hash_entry *ea, uint32_t capa)
Definition: hash.c:378
static uint32_t ib_bit_to_capa(uint32_t bit)
Definition: hash.c:699
static hash_entry * ea_get_by_key(mrb_state *mrb, hash_entry *ea, uint32_t size, mrb_value key, struct RHash *h)
Definition: hash.c:415
static void ht_free(mrb_state *mrb, struct RHash *h)
Definition: hash.c:758
void mrb_gc_free_hash(mrb_state *mrb, struct RHash *h)
Definition: hash.c:1045
static void ib_set_bit(struct RHash *h, uint32_t v)
Definition: hash.c:157
static void ib_init(mrb_state *mrb, struct RHash *h, uint32_t ib_bit, size_t ib_byte_size)
Definition: hash.c:728
static void h_free_table(mrb_state *mrb, struct RHash *h)
Definition: hash.c:946
void mrb_hash_check_kdict(mrb_state *mrb, mrb_value self)
Definition: hash.c:1156
static void ib_it_set(index_buckets_iter *it, uint32_t ea_index)
Definition: hash.c:657
static uint32_t ht_size(const struct RHash *h)
Definition: hash.c:161
static void ar_rehash(mrb_state *mrb, struct RHash *h)
Definition: hash.c:541
static mrb_value h_key_for(mrb_state *mrb, mrb_value key)
Definition: hash.c:924
static void ht_to_ar(mrb_state *mrb, struct RHash *h)
Definition: hash.c:783
static uint32_t ib_it_empty_value(const index_buckets_iter *it)
Definition: hash.c:572
static void h_replace(mrb_state *mrb, struct RHash *h, struct RHash *orig_h)
Definition: hash.c:1000
static mrb_bool ib_it_active_p(const index_buckets_iter *it)
Definition: hash.c:596
static void ar_set_ea(struct RHash *h, hash_entry *v)
Definition: hash.c:159
mrb_bool mrb_hash_empty_p(mrb_state *mrb, mrb_value self)
Definition: hash.c:1560
struct hash_entry hash_entry
#define RHASH_IFNONE(hash)
Definition: hash.c:258
static void ib_it_delete(index_buckets_iter *it)
Definition: hash.c:672
void mrb_gc_mark_hash(mrb_state *mrb, struct RHash *h)
Definition: hash.c:1030
#define mask(n)
Definition: lbitlib.c:93
#define offsetof(T, M)
Definition: dir.c:27
static unsigned hash(hash_table_type table, const_string key)
Definition: hash.c:31
#define mrb_str_ptr(s)
Definition: string.h:98
mrb_bool mrb_str_equal(mrb_state *mrb, mrb_value str1, mrb_value str2)
Definition: string.c:1052
mrb_value mrb_str_dup(mrb_state *mrb, mrb_value str)
Definition: string.c:1095
uint32_t mrb_str_hash(mrb_state *mrb, mrb_value str)
Definition: string.c:1752
Definition: object.h:19
Definition: class.h:17
Definition: hash.h:18
struct hash_entry * ea
Definition: hash.h:30
struct hash_table * ht
Definition: hash.h:31
Definition: object.h:30
Definition: hash.c:75
mrb_value key
Definition: hash.c:76
mrb_value val
Definition: hash.c:77
hash_entry * ea
Definition: hash.c:81
uint32_t ib[]
Definition: hash.c:86
uint32_t ary_index
Definition: hash.c:94
uint32_t shift2
Definition: hash.c:97
uint32_t step
Definition: hash.c:98
uint32_t bit
Definition: hash.c:91
uint32_t ea_index
Definition: hash.c:95
struct RHash * h
Definition: hash.c:90
uint32_t mask
Definition: hash.c:92
uint32_t shift1
Definition: hash.c:96
uint32_t pos
Definition: hash.c:93
Definition: mendex.h:20
struct RClass * object_class
Definition: mruby.h:242
struct RClass * hash_class
Definition: mruby.h:248
Definition: strexpr.c:21
#define key
Definition: tex2xindy.c:753
val
Definition: tex4ht.c:3227
static mrb_value mrb_true_value(void)
Definition: value.h:352
int32_t mrb_int
Definition: value.h:35
static mrb_value mrb_false_value(void)
Definition: value.h:342
static mrb_value mrb_nil_value(void)
Definition: value.h:332
static mrb_value mrb_bool_value(mrb_bool boolean)
Definition: value.h:360
double mrb_float
Definition: value.h:85
mrb_vtype
Definition: value.h:107
@ MRB_TT_TRUE
Definition: value.h:109
@ MRB_TT_STRING
Definition: value.h:124
@ MRB_TT_FALSE
Definition: value.h:108
@ MRB_TT_HASH
Definition: value.h:123
@ MRB_TT_SYMBOL
Definition: value.h:112
@ MRB_TT_FLOAT
Definition: value.h:110
@ MRB_TT_INTEGER
Definition: value.h:111
static mrb_value mrb_undef_value(void)
Definition: value.h:368
static mrb_value mrb_int_value(struct mrb_state *mrb, mrb_int i)
Definition: value.h:294
static mrb_value mrb_obj_value(void *p)
Definition: value.h:317