Changeset 439 for EcnlProtoTool/trunk/mruby-2.1.1/src/hash.c
- Timestamp:
- Jul 9, 2020, 8:51:43 AM (4 years ago)
- Location:
- EcnlProtoTool/trunk/mruby-2.1.1
- Files:
-
- 1 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
EcnlProtoTool/trunk/mruby-2.1.1/src/hash.c
r331 r439 9 9 #include <mruby/class.h> 10 10 #include <mruby/hash.h> 11 #include <mruby/khash.h>12 11 #include <mruby/string.h> 13 12 #include <mruby/variable.h> 14 13 14 #ifndef MRB_WITHOUT_FLOAT 15 15 /* a function to get hash value of a float number */ 16 16 mrb_int mrb_float_id(mrb_float f); 17 18 static inline khint_t 19 mrb_hash_ht_hash_func(mrb_state *mrb, mrb_value key) 20 { 21 enum mrb_vtype t = mrb_type(key); 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 51 ht_hash_func(mrb_state *mrb, htable *t, mrb_value key) 52 { 53 enum mrb_vtype tt = mrb_type(key); 22 54 mrb_value hv; 23 const char *p;24 mrb_int i, len;25 khint_t h;26 27 switch (t ) {55 size_t h; 56 segindex *index = t->index; 57 size_t capa = index ? index->capa : 0; 58 59 switch (tt) { 28 60 case MRB_TT_STRING: 29 p = RSTRING_PTR(key); 30 len = RSTRING_LEN(key); 31 h = 0; 32 for (i=0; i<len; i++) { 33 h = (h << 5) - h + *p++; 34 } 35 return h; 36 61 h = mrb_str_hash(mrb, key); 62 break; 63 64 case MRB_TT_TRUE: 65 case MRB_TT_FALSE: 37 66 case MRB_TT_SYMBOL: 38 h = (khint_t)mrb_symbol(key);39 return kh_int_hash_func(mrb, h);40 41 67 case MRB_TT_FIXNUM: 42 h = (khint_t)mrb_float_id((mrb_float)mrb_fixnum(key)); 43 return kh_int_hash_func(mrb, h); 44 68 #ifndef MRB_WITHOUT_FLOAT 45 69 case MRB_TT_FLOAT: 46 h = (khint_t)mrb_float_id(mrb_float(key)); 47 return kh_int_hash_func(mrb, h); 70 #endif 71 h = (size_t)mrb_obj_id(key); 72 break; 48 73 49 74 default: 50 75 hv = mrb_funcall(mrb, key, "hash", 0); 51 h = (khint_t)t ^ mrb_fixnum(hv); 52 return kh_int_hash_func(mrb, h); 53 } 54 } 55 56 static inline khint_t 57 mrb_hash_ht_hash_equal(mrb_state *mrb, mrb_value a, mrb_value b) 58 { 59 enum mrb_vtype t = mrb_type(a); 60 61 switch (t) { 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 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) { 62 91 case MRB_TT_STRING: 63 92 return mrb_str_equal(mrb, a, b); 64 93 65 94 case MRB_TT_SYMBOL: 66 if ( mrb_type(b) != MRB_TT_SYMBOL) return FALSE;95 if (!mrb_symbol_p(b)) return FALSE; 67 96 return mrb_symbol(a) == mrb_symbol(b); 68 97 … … 71 100 case MRB_TT_FIXNUM: 72 101 return mrb_fixnum(a) == mrb_fixnum(b); 102 #ifndef MRB_WITHOUT_FLOAT 73 103 case MRB_TT_FLOAT: 74 104 return (mrb_float)mrb_fixnum(a) == mrb_float(b); 105 #endif 75 106 default: 76 107 return FALSE; 77 108 } 78 109 110 #ifndef MRB_WITHOUT_FLOAT 79 111 case MRB_TT_FLOAT: 80 112 switch (mrb_type(b)) { … … 86 118 return FALSE; 87 119 } 120 #endif 88 121 89 122 default: 90 return mrb_eql(mrb, a, b); 91 } 92 } 93 94 KHASH_DEFINE (ht, mrb_value, mrb_hash_value, TRUE, mrb_hash_ht_hash_func, mrb_hash_ht_hash_equal) 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* 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 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, t->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 222 ht_compact(mrb_state *mrb, htable *t) 223 { 224 segment *seg; 225 uint16_t i, i2; 226 segment *seg2 = NULL; 227 mrb_int size = 0; 228 229 if (t == NULL) return; 230 seg = t->rootseg; 231 if (t->index && (size_t)t->size == t->index->size) { 232 ht_index(mrb, t); 233 return; 234 } 235 while (seg) { 236 for (i=0; i<seg->size; i++) { 237 mrb_value k = seg->e[i].key; 238 239 if (!seg->next && i >= t->last_len) { 240 goto exit; 241 } 242 if (mrb_undef_p(k)) { /* found deleted key */ 243 if (seg2 == NULL) { 244 seg2 = seg; 245 i2 = i; 246 } 247 } 248 else { 249 size++; 250 if (seg2 != NULL) { 251 seg2->e[i2++] = seg->e[i]; 252 if (i2 >= seg2->size) { 253 seg2 = seg2->next; 254 i2 = 0; 255 } 256 } 257 } 258 } 259 seg = seg->next; 260 } 261 exit: 262 /* reached at end */ 263 t->size = size; 264 if (seg2) { 265 seg = seg2->next; 266 seg2->next = NULL; 267 t->last_len = i2; 268 t->lastseg = seg2; 269 while (seg) { 270 seg2 = seg->next; 271 mrb_free(mrb, seg); 272 seg = seg2; 273 } 274 } 275 if (t->index) { 276 ht_index(mrb, t); 277 } 278 } 279 280 static segment* 281 segment_alloc(mrb_state *mrb, segment *seg) 282 { 283 uint32_t size; 284 285 if (!seg) size = MRB_HT_INIT_SIZE; 286 else { 287 size = seg->size*HT_SEG_INCREASE_RATIO + 1; 288 if (size > UINT16_MAX) size = UINT16_MAX; 289 } 290 291 seg = (segment*)mrb_malloc(mrb, sizeof(segment)+sizeof(struct segkv)*size); 292 seg->size = size; 293 seg->next = NULL; 294 295 return seg; 296 } 297 298 /* Set the value for the key in the indexed table. */ 299 static void 300 ht_index_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val) 301 { 302 segindex *index = t->index; 303 size_t k, sp, step = 0, mask; 304 segment *seg; 305 306 if (index->size >= UPPER_BOUND(index->capa)) { 307 /* need to expand table */ 308 ht_compact(mrb, t); 309 index = t->index; 310 } 311 mask = HT_MASK(index); 312 sp = index->capa; 313 k = ht_hash_func(mrb, t, key) & mask; 314 while (index->table[k]) { 315 mrb_value key2 = index->table[k]->key; 316 if (mrb_undef_p(key2)) { 317 if (sp == index->capa) sp = k; 318 } 319 else if (ht_hash_equal(mrb, t, key, key2)) { 320 index->table[k]->val = val; 321 return; 322 } 323 k = (k+(++step)) & mask; 324 } 325 if (sp < index->capa) { 326 k = sp; 327 } 328 329 /* put the value at the last */ 330 seg = t->lastseg; 331 if (t->last_len < seg->size) { 332 index->table[k] = &seg->e[t->last_len++]; 333 } 334 else { /* append a new segment */ 335 seg->next = segment_alloc(mrb, seg); 336 seg = seg->next; 337 seg->next = NULL; 338 t->lastseg = seg; 339 t->last_len = 1; 340 index->table[k] = &seg->e[0]; 341 } 342 index->table[k]->key = key; 343 index->table[k]->val = val; 344 index->size++; 345 t->size++; 346 } 347 348 /* Set the value for the key in the hash table. */ 349 static void 350 ht_put(mrb_state *mrb, htable *t, mrb_value key, mrb_value val) 351 { 352 segment *seg; 353 mrb_int i, deleted = 0; 354 355 if (t == NULL) return; 356 if (t->index) { 357 ht_index_put(mrb, t, key, val); 358 return; 359 } 360 seg = t->rootseg; 361 while (seg) { 362 for (i=0; i<seg->size; i++) { 363 mrb_value k = seg->e[i].key; 364 /* Found room in last segment after last_len */ 365 if (!seg->next && i >= t->last_len) { 366 seg->e[i].key = key; 367 seg->e[i].val = val; 368 t->last_len = i+1; 369 t->size++; 370 return; 371 } 372 if (mrb_undef_p(k)) { 373 deleted++; 374 continue; 375 } 376 if (ht_hash_equal(mrb, t, k, key)) { 377 seg->e[i].val = val; 378 return; 379 } 380 } 381 seg = seg->next; 382 } 383 /* Not found */ 384 385 /* Compact if last segment has room */ 386 if (deleted > 0 && deleted > MRB_HT_INIT_SIZE) { 387 ht_compact(mrb, t); 388 } 389 t->size++; 390 391 /* check if thre's room after compaction */ 392 if (t->lastseg && t->last_len < t->lastseg->size) { 393 seg = t->lastseg; 394 i = t->last_len; 395 } 396 else { 397 /* append new segment */ 398 seg = segment_alloc(mrb, t->lastseg); 399 i = 0; 400 if (t->rootseg == NULL) { 401 t->rootseg = seg; 402 } 403 else { 404 t->lastseg->next = seg; 405 } 406 t->lastseg = seg; 407 } 408 seg->e[i].key = key; 409 seg->e[i].val = val; 410 t->last_len = i+1; 411 if (t->index == NULL && t->size > MRB_HT_INIT_SIZE*4) { 412 ht_index(mrb, t); 413 } 414 } 415 416 /* Get a value for a key from the indexed table. */ 417 static mrb_bool 418 ht_index_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp) 419 { 420 segindex *index = t->index; 421 size_t mask = HT_MASK(index); 422 size_t k = ht_hash_func(mrb, t, key) & mask; 423 size_t step = 0; 424 425 while (index->table[k]) { 426 mrb_value key2 = index->table[k]->key; 427 if (!mrb_undef_p(key2) && ht_hash_equal(mrb, t, key, key2)) { 428 if (vp) *vp = index->table[k]->val; 429 return TRUE; 430 } 431 k = (k+(++step)) & mask; 432 } 433 return FALSE; 434 } 435 436 /* Get a value for a key from the hash table. */ 437 static mrb_bool 438 ht_get(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp) 439 { 440 segment *seg; 441 mrb_int i; 442 443 if (t == NULL) return FALSE; 444 if (t->index) { 445 return ht_index_get(mrb, t, key, vp); 446 } 447 448 seg = t->rootseg; 449 while (seg) { 450 for (i=0; i<seg->size; i++) { 451 mrb_value k = seg->e[i].key; 452 453 if (!seg->next && i >= t->last_len) { 454 return FALSE; 455 } 456 if (mrb_undef_p(k)) continue; 457 if (ht_hash_equal(mrb, t, k, key)) { 458 if (vp) *vp = seg->e[i].val; 459 return TRUE; 460 } 461 } 462 seg = seg->next; 463 } 464 return FALSE; 465 } 466 467 /* Deletes the value for the symbol from the hash table. */ 468 /* Deletion is done by overwriting keys by `undef`. */ 469 static mrb_bool 470 ht_del(mrb_state *mrb, htable *t, mrb_value key, mrb_value *vp) 471 { 472 segment *seg; 473 mrb_int i; 474 475 if (t == NULL) return FALSE; 476 seg = t->rootseg; 477 while (seg) { 478 for (i=0; i<seg->size; i++) { 479 mrb_value key2; 480 481 if (!seg->next && i >= t->last_len) { 482 /* not found */ 483 return FALSE; 484 } 485 key2 = seg->e[i].key; 486 if (!mrb_undef_p(key2) && ht_hash_equal(mrb, t, key, key2)) { 487 if (vp) *vp = seg->e[i].val; 488 seg->e[i].key = mrb_undef_value(); 489 t->size--; 490 return TRUE; 491 } 492 } 493 seg = seg->next; 494 } 495 return FALSE; 496 } 497 498 /* Iterates over the hash table. */ 499 static void 500 ht_foreach(mrb_state *mrb, htable *t, mrb_hash_foreach_func *func, void *p) 501 { 502 segment *seg; 503 mrb_int i; 504 505 if (t == NULL) return; 506 seg = t->rootseg; 507 while (seg) { 508 for (i=0; i<seg->size; i++) { 509 /* no value in last segment after last_len */ 510 if (!seg->next && i >= t->last_len) { 511 return; 512 } 513 if (mrb_undef_p(seg->e[i].key)) continue; 514 if ((*func)(mrb, seg->e[i].key, seg->e[i].val, p) != 0) 515 return; 516 } 517 seg = seg->next; 518 } 519 } 520 521 /* Iterates over the hash table. */ 522 MRB_API void 523 mrb_hash_foreach(mrb_state *mrb, struct RHash *hash, mrb_hash_foreach_func *func, void *p) 524 { 525 ht_foreach(mrb, hash->ht, func, p); 526 } 527 528 /* Copy the hash table. */ 529 static htable* 530 ht_copy(mrb_state *mrb, htable *t) 531 { 532 segment *seg; 533 htable *t2; 534 mrb_int i; 535 536 seg = t->rootseg; 537 t2 = ht_new(mrb); 538 if (t->size == 0) return t2; 539 540 while (seg) { 541 for (i=0; i<seg->size; i++) { 542 mrb_value key = seg->e[i].key; 543 mrb_value val = seg->e[i].val; 544 545 if ((seg->next == NULL) && (i >= t->last_len)) { 546 return t2; 547 } 548 if (mrb_undef_p(key)) continue; /* skip deleted key */ 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 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 } 95 572 96 573 static void mrb_hash_modify(mrb_state *mrb, mrb_value hash); 97 574 98 575 static inline mrb_value 99 mrb_hash_ht_key(mrb_state *mrb, mrb_value key)100 { 101 if (mrb_string_p(key) && ! MRB_FROZEN_P(mrb_str_ptr(key))) {576 ht_key(mrb_state *mrb, mrb_value key) 577 { 578 if (mrb_string_p(key) && !mrb_frozen_p(mrb_str_ptr(key))) { 102 579 key = mrb_str_dup(mrb, key); 103 580 MRB_SET_FROZEN_FLAG(mrb_str_ptr(key)); … … 106 583 } 107 584 108 #define KEY(key) mrb_hash_ht_key(mrb, key) 585 #define KEY(key) ht_key(mrb, key) 586 587 static int 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 } 109 594 110 595 void 111 596 mrb_gc_mark_hash(mrb_state *mrb, struct RHash *hash) 112 597 { 113 khiter_t k; 114 khash_t(ht) *h = hash->ht; 115 116 if (!h) return; 117 for (k = kh_begin(h); k != kh_end(h); k++) { 118 if (kh_exist(h, k)) { 119 mrb_value key = kh_key(h, k); 120 mrb_value val = kh_value(h, k).v; 121 122 mrb_gc_mark_value(mrb, key); 123 mrb_gc_mark_value(mrb, val); 124 } 125 } 598 ht_foreach(mrb, hash->ht, hash_mark_i, NULL); 126 599 } 127 600 … … 130 603 { 131 604 if (!hash->ht) return 0; 132 return kh_size(hash->ht)*2;605 return hash->ht->size*2; 133 606 } 134 607 … … 136 609 mrb_gc_free_hash(mrb_state *mrb, struct RHash *hash) 137 610 { 138 if (hash->ht) kh_destroy(ht, mrb, hash->ht); 139 } 140 611 ht_free(mrb, hash->ht); 612 } 613 614 MRB_API mrb_value 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 } 141 624 142 625 MRB_API mrb_value … … 146 629 147 630 h = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class); 148 h->ht = kh_init(ht, mrb); 149 if (capa > 0) { 150 kh_resize(ht, mrb, h->ht, capa); 151 } 631 /* preallocate hash table */ 632 h->ht = ht_new(mrb); 633 /* capacity ignored */ 152 634 h->iv = 0; 153 635 return mrb_obj_value(h); 154 636 } 155 637 156 MRB_API mrb_value157 mrb_hash_new(mrb_state *mrb)158 {159 return mrb_hash_new_capa(mrb, 0);160 }161 162 638 static mrb_value mrb_hash_default(mrb_state *mrb, mrb_value hash); 163 639 static mrb_value hash_default(mrb_state *mrb, mrb_value hash, mrb_value key); 164 640 641 static mrb_value 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 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 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 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 165 704 MRB_API mrb_value 166 705 mrb_hash_get(mrb_state *mrb, mrb_value hash, mrb_value key) 167 706 { 168 khash_t(ht) *h = RHASH_TBL(hash); 169 khiter_t k; 707 mrb_value val; 170 708 mrb_sym mid; 171 709 172 if (h) { 173 k = kh_get(ht, mrb, h, key); 174 if (k != kh_end(h)) 175 return kh_value(h, k).v; 710 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) { 711 return val; 176 712 } 177 713 … … 187 723 mrb_hash_fetch(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value def) 188 724 { 189 khash_t(ht) *h = RHASH_TBL(hash); 190 khiter_t k; 191 192 if (h) { 193 k = kh_get(ht, mrb, h, key); 194 if (k != kh_end(h)) 195 return kh_value(h, k).v; 196 } 197 725 mrb_value val; 726 727 if (ht_get(mrb, RHASH_TBL(hash), key, &val)) { 728 return val; 729 } 198 730 /* not found */ 199 731 return def; … … 203 735 mrb_hash_set(mrb_state *mrb, mrb_value hash, mrb_value key, mrb_value val) 204 736 { 205 khash_t(ht) *h;206 khiter_t k;207 int r;208 209 737 mrb_hash_modify(mrb, hash); 210 h = RHASH_TBL(hash); 211 212 if (!h) h = RHASH_TBL(hash) = kh_init(ht, mrb); 213 k = kh_put2(ht, mrb, h, key, &r); 214 kh_value(h, k).v = val; 215 216 if (r != 0) { 217 /* expand */ 218 int ai = mrb_gc_arena_save(mrb); 219 key = kh_key(h, k) = KEY(key); 220 mrb_gc_arena_restore(mrb, ai); 221 kh_value(h, k).n = kh_size(h)-1; 222 } 223 738 739 key = KEY(key); 740 ht_put(mrb, RHASH_TBL(hash), key, val); 224 741 mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), key); 225 742 mrb_field_write_barrier_value(mrb, (struct RBasic*)RHASH(hash), val); … … 227 744 } 228 745 229 static mrb_value230 mrb_hash_dup(mrb_state *mrb, mrb_value hash)231 {232 struct RHash* ret;233 khash_t(ht) *h, *ret_h;234 khiter_t k, ret_k;235 mrb_value ifnone, vret;236 237 h = RHASH_TBL(hash);238 ret = (struct RHash*)mrb_obj_alloc(mrb, MRB_TT_HASH, mrb->hash_class);239 ret->ht = kh_init(ht, mrb);240 241 if (h && kh_size(h) > 0) {242 ret_h = ret->ht;243 244 for (k = kh_begin(h); k != kh_end(h); k++) {245 if (kh_exist(h, k)) {246 int ai = mrb_gc_arena_save(mrb);247 ret_k = kh_put(ht, mrb, ret_h, KEY(kh_key(h, k)));248 mrb_gc_arena_restore(mrb, ai);249 kh_val(ret_h, ret_k).v = kh_val(h, k).v;250 kh_val(ret_h, ret_k).n = kh_size(ret_h)-1;251 }252 }253 }254 255 if (MRB_RHASH_DEFAULT_P(hash)) {256 ret->flags |= MRB_HASH_DEFAULT;257 }258 if (MRB_RHASH_PROCDEFAULT_P(hash)) {259 ret->flags |= MRB_HASH_PROC_DEFAULT;260 }261 vret = mrb_obj_value(ret);262 ifnone = RHASH_IFNONE(hash);263 if (!mrb_nil_p(ifnone)) {264 mrb_iv_set(mrb, vret, mrb_intern_lit(mrb, "ifnone"), ifnone);265 }266 return vret;267 }268 269 MRB_API mrb_value270 mrb_check_hash_type(mrb_state *mrb, mrb_value hash)271 {272 return mrb_check_convert_type(mrb, hash, MRB_TT_HASH, "Hash", "to_hash");273 }274 275 MRB_API khash_t(ht)*276 mrb_hash_tbl(mrb_state *mrb, mrb_value hash)277 {278 khash_t(ht) *h = RHASH_TBL(hash);279 280 if (!h) {281 return RHASH_TBL(hash) = kh_init(ht, mrb);282 }283 return h;284 }285 286 746 static void 287 747 mrb_hash_modify(mrb_state *mrb, mrb_value hash) 288 748 { 289 if (MRB_FROZEN_P(mrb_hash_ptr(hash))) {290 mrb_raise(mrb, E_RUNTIME_ERROR, "can't modify frozen hash");291 }292 mrb_hash_tbl(mrb, hash);749 mrb_check_frozen(mrb, mrb_hash_ptr(hash)); 750 if (!RHASH_TBL(hash)) { 751 RHASH_TBL(hash) = ht_new(mrb); 752 } 293 753 } 294 754 … … 340 800 if (!mrb_nil_p(block)) { 341 801 if (ifnone_p) { 342 mrb_ raise(mrb, E_ARGUMENT_ERROR, "wrong number of arguments");802 mrb_argnum_error(mrb, 1, 0, 0); 343 803 } 344 804 RHASH(hash)->flags |= MRB_HASH_PROC_DEFAULT; … … 530 990 mrb_hash_delete_key(mrb_state *mrb, mrb_value hash, mrb_value key) 531 991 { 532 khash_t(ht) *h = RHASH_TBL(hash); 533 khiter_t k; 534 mrb_value delVal; 535 mrb_int n; 536 537 if (h) { 538 k = kh_get(ht, mrb, h, key); 539 if (k != kh_end(h)) { 540 delVal = kh_value(h, k).v; 541 n = kh_value(h, k).n; 542 kh_del(ht, mrb, h, k); 543 for (k = kh_begin(h); k != kh_end(h); k++) { 544 if (!kh_exist(h, k)) continue; 545 if (kh_value(h, k).n > n) kh_value(h, k).n--; 546 } 547 return delVal; 548 } 992 htable *t = RHASH_TBL(hash); 993 mrb_value del_val; 994 995 if (ht_del(mrb, t, key, &del_val)) { 996 return del_val; 549 997 } 550 998 … … 553 1001 } 554 1002 555 /* 15.2.13.4.8 */556 /*557 * call-seq:558 * hsh.delete(key) -> value559 * hsh.delete(key) {| key | block } -> value560 *561 * Deletes and returns a key-value pair from <i>hsh</i> whose key is562 * equal to <i>key</i>. If the key is not found, returns the563 * <em>default value</em>. If the optional code block is given and the564 * key is not found, pass in the key and return the result of565 * <i>block</i>.566 *567 * h = { "a" => 100, "b" => 200 }568 * h.delete("a") #=> 100569 * h.delete("z") #=> nil570 * h.delete("z") { |el| "#{el} not found" } #=> "z not found"571 *572 */573 1003 static mrb_value 574 1004 mrb_hash_delete(mrb_state *mrb, mrb_value self) … … 581 1011 } 582 1012 1013 /* find first element in the hash table, and remove it. */ 1014 static void 1015 ht_shift(mrb_state *mrb, htable *t, mrb_value *kp, mrb_value *vp) 1016 { 1017 segment *seg = t->rootseg; 1018 mrb_int i; 1019 1020 while (seg) { 1021 for (i=0; i<seg->size; i++) { 1022 mrb_value key; 1023 1024 if (!seg->next && i >= t->last_len) { 1025 return; 1026 } 1027 key = seg->e[i].key; 1028 if (mrb_undef_p(key)) continue; 1029 *kp = key; 1030 *vp = seg->e[i].val; 1031 /* delete element */ 1032 seg->e[i].key = mrb_undef_value(); 1033 t->size--; 1034 return; 1035 } 1036 seg = seg->next; 1037 } 1038 } 1039 583 1040 /* 15.2.13.4.24 */ 584 1041 /* … … 598 1055 mrb_hash_shift(mrb_state *mrb, mrb_value hash) 599 1056 { 600 khash_t(ht) *h = RHASH_TBL(hash); 601 khiter_t k; 602 mrb_value delKey, delVal; 1057 htable *t = RHASH_TBL(hash); 603 1058 604 1059 mrb_hash_modify(mrb, hash); 605 if (h && kh_size(h) > 0) { 606 for (k = kh_begin(h); k != kh_end(h); k++) { 607 if (!kh_exist(h, k)) continue; 608 609 delKey = kh_key(h, k); 610 mrb_gc_protect(mrb, delKey); 611 delVal = mrb_hash_delete_key(mrb, hash, delKey); 612 mrb_gc_protect(mrb, delVal); 613 614 return mrb_assoc_new(mrb, delKey, delVal); 615 } 1060 if (t && t->size > 0) { 1061 mrb_value del_key, del_val; 1062 1063 ht_shift(mrb, t, &del_key, &del_val); 1064 mrb_gc_protect(mrb, del_key); 1065 mrb_gc_protect(mrb, del_val); 1066 return mrb_assoc_new(mrb, del_key, del_val); 616 1067 } 617 1068 … … 642 1093 mrb_hash_clear(mrb_state *mrb, mrb_value hash) 643 1094 { 644 khash_t(ht) *h= RHASH_TBL(hash);1095 htable *t = RHASH_TBL(hash); 645 1096 646 1097 mrb_hash_modify(mrb, hash); 647 if (h) kh_clear(ht, mrb, h); 1098 if (t) { 1099 ht_free(mrb, t); 1100 RHASH_TBL(hash) = NULL; 1101 } 648 1102 return hash; 649 1103 } … … 678 1132 } 679 1133 1134 MRB_API mrb_int 1135 mrb_hash_size(mrb_state *mrb, mrb_value hash) 1136 { 1137 htable *t = RHASH_TBL(hash); 1138 1139 if (!t) return 0; 1140 return t->size; 1141 } 1142 680 1143 /* 15.2.13.4.20 */ 681 1144 /* 15.2.13.4.25 */ … … 695 1158 mrb_hash_size_m(mrb_state *mrb, mrb_value self) 696 1159 { 697 khash_t(ht) *h = RHASH_TBL(self); 698 699 if (!h) return mrb_fixnum_value(0); 700 return mrb_fixnum_value(kh_size(h)); 1160 mrb_int size = mrb_hash_size(mrb, self); 1161 return mrb_fixnum_value(size); 1162 } 1163 1164 MRB_API mrb_bool 1165 mrb_hash_empty_p(mrb_state *mrb, mrb_value self) 1166 { 1167 htable *t = RHASH_TBL(self); 1168 1169 if (!t) return TRUE; 1170 return t->size == 0; 701 1171 } 702 1172 … … 711 1181 * 712 1182 */ 713 MRB_API mrb_value 714 mrb_hash_empty_p(mrb_state *mrb, mrb_value self) 715 { 716 khash_t(ht) *h = RHASH_TBL(self); 717 718 if (h) return mrb_bool_value(kh_size(h) == 0); 719 return mrb_true_value(); 720 } 721 722 /* 15.2.13.4.29 (x)*/ 723 /* 724 * call-seq: 725 * hsh.to_hash => hsh 726 * 727 * Returns +self+. 728 */ 729 730 static mrb_value 731 mrb_hash_to_hash(mrb_state *mrb, mrb_value hash) 732 { 733 return hash; 1183 static mrb_value 1184 mrb_hash_empty_m(mrb_state *mrb, mrb_value self) 1185 { 1186 return mrb_bool_value(mrb_hash_empty_p(mrb, self)); 1187 } 1188 1189 static int 1190 hash_keys_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p) 1191 { 1192 mrb_ary_push(mrb, *(mrb_value*)p, key); 1193 return 0; 734 1194 } 735 1195 … … 750 1210 mrb_hash_keys(mrb_state *mrb, mrb_value hash) 751 1211 { 752 khash_t(ht) *h = RHASH_TBL(hash); 753 khiter_t k; 754 mrb_int end; 1212 htable *t = RHASH_TBL(hash); 1213 mrb_int size; 755 1214 mrb_value ary; 756 mrb_value *p; 757 758 if (!h || kh_size(h) == 0) return mrb_ary_new(mrb); 759 ary = mrb_ary_new_capa(mrb, kh_size(h)); 760 end = kh_size(h)-1; 761 mrb_ary_set(mrb, ary, end, mrb_nil_value()); 762 p = mrb_ary_ptr(ary)->ptr; 763 for (k = kh_begin(h); k != kh_end(h); k++) { 764 if (kh_exist(h, k)) { 765 mrb_value kv = kh_key(h, k); 766 mrb_hash_value hv = kh_value(h, k); 767 768 if (hv.n <= end) { 769 p[hv.n] = kv; 770 } 771 else { 772 p[end] = kv; 773 } 774 } 775 } 1215 1216 if (!t || (size = t->size) == 0) 1217 return mrb_ary_new(mrb); 1218 ary = mrb_ary_new_capa(mrb, size); 1219 ht_foreach(mrb, t, hash_keys_i, (void*)&ary); 776 1220 return ary; 1221 } 1222 1223 static int 1224 hash_vals_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p) 1225 { 1226 mrb_ary_push(mrb, *(mrb_value*)p, val); 1227 return 0; 777 1228 } 778 1229 … … 793 1244 mrb_hash_values(mrb_state *mrb, mrb_value hash) 794 1245 { 795 khash_t(ht) *h= RHASH_TBL(hash);796 khiter_t k;1246 htable *t = RHASH_TBL(hash); 1247 mrb_int size; 797 1248 mrb_value ary; 798 1249 799 if (!h) return mrb_ary_new(mrb); 800 ary = mrb_ary_new_capa(mrb, kh_size(h)); 801 for (k = kh_begin(h); k != kh_end(h); k++) { 802 if (kh_exist(h, k)) { 803 mrb_hash_value hv = kh_value(h, k); 804 805 mrb_ary_set(mrb, ary, hv.n, hv.v); 806 } 807 } 1250 if (!t || (size = t->size) == 0) 1251 return mrb_ary_new(mrb); 1252 ary = mrb_ary_new_capa(mrb, size); 1253 ht_foreach(mrb, t, hash_vals_i, (void*)&ary); 808 1254 return ary; 809 1255 } … … 828 1274 */ 829 1275 1276 MRB_API mrb_bool 1277 mrb_hash_key_p(mrb_state *mrb, mrb_value hash, mrb_value key) 1278 { 1279 htable *t; 1280 1281 t = RHASH_TBL(hash); 1282 if (ht_get(mrb, t, key, NULL)) { 1283 return TRUE; 1284 } 1285 return FALSE; 1286 } 1287 830 1288 static mrb_value 831 1289 mrb_hash_has_key(mrb_state *mrb, mrb_value hash) 832 1290 { 833 1291 mrb_value key; 834 khash_t(ht) *h; 835 khiter_t k; 1292 mrb_bool key_p; 836 1293 837 1294 mrb_get_args(mrb, "o", &key); 838 839 h = RHASH_TBL(hash); 840 if (h) { 841 k = kh_get(ht, mrb, h, key); 842 return mrb_bool_value(k != kh_end(h)); 843 } 844 return mrb_false_value(); 1295 key_p = mrb_hash_key_p(mrb, hash, key); 1296 return mrb_bool_value(key_p); 1297 } 1298 1299 struct has_v_arg { 1300 mrb_bool found; 1301 mrb_value val; 1302 }; 1303 1304 static int 1305 hash_has_value_i(mrb_state *mrb, mrb_value key, mrb_value val, void *p) 1306 { 1307 struct has_v_arg *arg = (struct has_v_arg*)p; 1308 1309 if (mrb_equal(mrb, arg->val, val)) { 1310 arg->found = TRUE; 1311 return 1; 1312 } 1313 return 0; 845 1314 } 846 1315 … … 864 1333 { 865 1334 mrb_value val; 866 khash_t(ht) *h; 867 khiter_t k; 868 1335 struct has_v_arg arg; 1336 869 1337 mrb_get_args(mrb, "o", &val); 870 h = RHASH_TBL(hash); 871 872 if (h) { 873 for (k = kh_begin(h); k != kh_end(h); k++) { 874 if (!kh_exist(h, k)) continue; 875 876 if (mrb_equal(mrb, kh_value(h, k).v, val)) { 877 return mrb_true_value(); 878 } 879 } 880 } 881 return mrb_false_value(); 1338 arg.found = FALSE; 1339 arg.val = val; 1340 ht_foreach(mrb, RHASH_TBL(hash), hash_has_value_i, &arg); 1341 return mrb_bool_value(arg.found); 1342 } 1343 1344 static int 1345 merge_i(mrb_state *mrb, mrb_value key, mrb_value val, void *data) 1346 { 1347 htable *h1 = (htable*)data; 1348 1349 ht_put(mrb, h1, key, val); 1350 return 0; 1351 } 1352 1353 MRB_API void 1354 mrb_hash_merge(mrb_state *mrb, mrb_value hash1, mrb_value hash2) 1355 { 1356 htable *h1, *h2; 1357 1358 mrb_hash_modify(mrb, hash1); 1359 hash2 = mrb_ensure_hash_type(mrb, hash2); 1360 h1 = RHASH_TBL(hash1); 1361 h2 = RHASH_TBL(hash2); 1362 1363 if (!h2) return; 1364 if (!h1) { 1365 RHASH_TBL(hash1) = ht_copy(mrb, h2); 1366 return; 1367 } 1368 ht_foreach(mrb, h2, merge_i, h1); 1369 mrb_write_barrier(mrb, (struct RBasic*)RHASH(hash1)); 1370 return; 1371 } 1372 1373 /* 1374 * call-seq: 1375 * hsh.rehash -> hsh 1376 * 1377 * Rebuilds the hash based on the current hash values for each key. If 1378 * values of key objects have changed since they were inserted, this 1379 * method will reindex <i>hsh</i>. 1380 * 1381 * keys = (1..17).map{|n| [n]} 1382 * k = keys[0] 1383 * h = {} 1384 * keys.each{|key| h[key] = key[0]} 1385 * h #=> { [1]=> 1, [2]=> 2, [3]=> 3, [4]=> 4, [5]=> 5, [6]=> 6, [7]=> 7, 1386 * [8]=> 8, [9]=> 9,[10]=>10,[11]=>11,[12]=>12,[13]=>13,[14]=>14, 1387 * [15]=>15,[16]=>16,[17]=>17} 1388 * h[k] #=> 1 1389 * k[0] = keys.size + 1 1390 * h #=> {[18]=> 1, [2]=> 2, [3]=> 3, [4]=> 4, [5]=> 5, [6]=> 6, [7]=> 7, 1391 * [8]=> 8, [9]=> 9,[10]=>10,[11]=>11,[12]=>12,[13]=>13,[14]=>14, 1392 * [15]=>15,[16]=>16,[17]=>17} 1393 * h[k] #=> nil 1394 * h.rehash 1395 * h[k] #=> 1 1396 */ 1397 static mrb_value 1398 mrb_hash_rehash(mrb_state *mrb, mrb_value self) 1399 { 1400 ht_compact(mrb, RHASH_TBL(self)); 1401 return self; 882 1402 } 883 1403 … … 890 1410 MRB_SET_INSTANCE_TT(h, MRB_TT_HASH); 891 1411 1412 mrb_define_method(mrb, h, "initialize_copy", mrb_hash_init_copy, MRB_ARGS_REQ(1)); 892 1413 mrb_define_method(mrb, h, "[]", mrb_hash_aget, MRB_ARGS_REQ(1)); /* 15.2.13.4.2 */ 893 1414 mrb_define_method(mrb, h, "[]=", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.3 */ 894 1415 mrb_define_method(mrb, h, "clear", mrb_hash_clear, MRB_ARGS_NONE()); /* 15.2.13.4.4 */ 895 mrb_define_method(mrb, h, "default", mrb_hash_default, MRB_ARGS_ ANY()); /* 15.2.13.4.5 */1416 mrb_define_method(mrb, h, "default", mrb_hash_default, MRB_ARGS_OPT(1)); /* 15.2.13.4.5 */ 896 1417 mrb_define_method(mrb, h, "default=", mrb_hash_set_default, MRB_ARGS_REQ(1)); /* 15.2.13.4.6 */ 897 1418 mrb_define_method(mrb, h, "default_proc", mrb_hash_default_proc,MRB_ARGS_NONE()); /* 15.2.13.4.7 */ 898 1419 mrb_define_method(mrb, h, "default_proc=", mrb_hash_set_default_proc,MRB_ARGS_REQ(1)); /* 15.2.13.4.7 */ 899 1420 mrb_define_method(mrb, h, "__delete", mrb_hash_delete, MRB_ARGS_REQ(1)); /* core of 15.2.13.4.8 */ 900 mrb_define_method(mrb, h, "empty?", mrb_hash_empty_ p, MRB_ARGS_NONE()); /* 15.2.13.4.12 */1421 mrb_define_method(mrb, h, "empty?", mrb_hash_empty_m, MRB_ARGS_NONE()); /* 15.2.13.4.12 */ 901 1422 mrb_define_method(mrb, h, "has_key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.13 */ 902 1423 mrb_define_method(mrb, h, "has_value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.14 */ 903 1424 mrb_define_method(mrb, h, "include?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.15 */ 904 mrb_define_method(mrb, h, "initialize", mrb_hash_init, MRB_ARGS_OPT(1) ); /* 15.2.13.4.16 */1425 mrb_define_method(mrb, h, "initialize", mrb_hash_init, MRB_ARGS_OPT(1)|MRB_ARGS_BLOCK()); /* 15.2.13.4.16 */ 905 1426 mrb_define_method(mrb, h, "key?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.18 */ 906 1427 mrb_define_method(mrb, h, "keys", mrb_hash_keys, MRB_ARGS_NONE()); /* 15.2.13.4.19 */ … … 908 1429 mrb_define_method(mrb, h, "member?", mrb_hash_has_key, MRB_ARGS_REQ(1)); /* 15.2.13.4.21 */ 909 1430 mrb_define_method(mrb, h, "shift", mrb_hash_shift, MRB_ARGS_NONE()); /* 15.2.13.4.24 */ 910 mrb_define_method(mrb, h, "dup", mrb_hash_dup, MRB_ARGS_NONE());911 1431 mrb_define_method(mrb, h, "size", mrb_hash_size_m, MRB_ARGS_NONE()); /* 15.2.13.4.25 */ 912 1432 mrb_define_method(mrb, h, "store", mrb_hash_aset, MRB_ARGS_REQ(2)); /* 15.2.13.4.26 */ 913 1433 mrb_define_method(mrb, h, "value?", mrb_hash_has_value, MRB_ARGS_REQ(1)); /* 15.2.13.4.27 */ 914 1434 mrb_define_method(mrb, h, "values", mrb_hash_values, MRB_ARGS_NONE()); /* 15.2.13.4.28 */ 915 916 mrb_define_method(mrb, h, "to_hash", mrb_hash_to_hash, MRB_ARGS_NONE()); /* 15.2.13.4.29 (x)*/ 917 } 1435 mrb_define_method(mrb, h, "rehash", mrb_hash_rehash, MRB_ARGS_NONE()); 1436 }
Note:
See TracChangeset
for help on using the changeset viewer.