src/pmc/orderedhash.pmc

   1 /*
   2 Copyright (C) 2001-2009, Parrot Foundation.
   3 $Id$
   4
   5 =head1 NAME
   6
   7 src/pmc/orderedhash.pmc - Ordered Hash
   8
   9 =head1 DESCRIPTION
  10
  11 C<OrderedHash> extends C<Hash> to provide the interfaces of C<array> and
  12 C<hash>. To achieve ordering, hash there are a few restrictions:
  13 C<delete_keyed> never removes items; they are just nulled.
  14
  15 Please note that if values are set via integer idx, these indices have to be in
  16 strict order. Using C<push_xx> simplifies this task.  This creates a key
  17 "\1idx" for C<idx> and is therefore not fully transparent.
  18
  19 There are two iterator interfaces:
  20
  21 =over 4
  22
  23 =item * retrieve values (in creation order)
  24
  25 Please note that after a C<delete_keyed> operation, iterating over
  26 values doesn't work any more.  You'll get an error 'No such key'.
  27
  28 =item * retrieve keys (in creation order)
  29
  30 =back
  31
  32 See F<t/pmc/orderedhash.t>.
  33
  34 =head2 Methods
  35
  36 =over 4
  37
  38 =cut
  39
  40 */
  41
  42 pmclass OrderedHash extends Hash need_ext provides array provides hash {
  43
  44 /*
  45
  46 =item C<void mark()>
  47
  48 Marks the OrderedHash as live.
  49
  50 =cut
  51
  52 */
  53
  54     VTABLE void mark() {
  55         Hash * const h = (Hash *)SELF.get_pointer();
  56         INTVAL  i;
  57
  58         if (!h)
  59             return;
  60
  61         /* RT #53890 - keys can be NULL on purpose; move to src/hash.c ? */
  62         for (i = h->mask; i >= 0; --i) {
  63             HashBucket *b = h->bi[i];
  64
  65             while (b) {
  66
  67                 if (b->key) {
  68                     Parrot_gc_mark_PObj_alive(interp, (PObj *)b->key);
  69                     if (b->value)
  70                         Parrot_gc_mark_PObj_alive(interp, (PObj *)b->value);
  71                 }
  72
  73                 b = b->next;
  74             }
  75         }
  76     }
  77
  78 /*
  79
  80 =item C<PMC *get_iter()>
  81
  82 Return a new iterator
  83
  84 =cut
  85
  86 */
  87
  88     VTABLE PMC *get_iter() {
  89         return pmc_new_init(INTERP, enum_class_OrderedHashIterator, SELF);
  90     }
  91
  92 /*
  93
  94 =item C<PMC *get_pmc_keyed(PMC *key)>
  95
  96 =item C<PMC *get_pmc_keyed_int(INTVAL key)>
  97
  98 =item C<PMC *get_pmc_keyed_str(STRING *key)>
  99
 100 =cut
 101
 102 */
 103
 104     VTABLE PMC *get_pmc_keyed_int(INTVAL idx) {
 105         Hash * const h = (Hash *)SELF.get_pointer();
 106         const INTVAL n = h->entries;
 107         HashBucket *b;
 108
 109         if (idx < 0)
 110             idx += n;
 111
 112         if (idx < 0 || idx >= n)
 113             Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_KEY_NOT_FOUND,
 114                 "OrderedHash: index out of bounds!");
 115
 116         b = h->bs + idx;
 117
 118         if (b->key)
 119             return (PMC *)b->value;
 120
 121         Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_KEY_NOT_FOUND,
 122             "OrderedHash: No such key");
 123     }
 124
 125     VTABLE PMC *get_pmc_keyed(PMC *key) {
 126         if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG) {
 127             PMC * const item = SELF.get_pmc_keyed_int(VTABLE_get_integer(INTERP, key));
 128             PMC * const next = VTABLE_shift_pmc(INTERP, key);
 129
 130             if (!next)
 131                 return item;
 132
 133             return VTABLE_get_pmc_keyed(INTERP, item, next);
 134         }
 135
 136         return INTERP->vtables[enum_class_Hash]->get_pmc_keyed(INTERP, SELF, key);
 137     }
 138
 139 /*
 140
 141 =item C<STRING *get_string_keyed(PMC *key)>
 142
 143 =item C<STRING *get_string_keyed_int(INTVAL key)>
 144
 145 =item C<STRING *get_string_keyed_str(STRING *key)>
 146
 147 =cut
 148
 149 */
 150
 151     VTABLE STRING *get_string_keyed_int(INTVAL idx) {
 152         Hash * const h = (Hash *)SELF.get_pointer();
 153         const INTVAL n = h->entries;
 154
 155         HashBucket *b;
 156
 157         if (idx < 0)
 158             idx += n;
 159
 160         if (idx < 0 || idx >= n)
 161             Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_KEY_NOT_FOUND,
 162                 "OrderedHash: index out of bounds!");
 163
 164         b = h->bs + idx;
 165
 166         if (b->key)
 167             return VTABLE_get_string(INTERP, (PMC *)b->value);
 168
 169         Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_KEY_NOT_FOUND,
 170             "OrderedHash: No such key");
 171     }
 172
 173     VTABLE STRING *get_string_keyed(PMC *key) {
 174         if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG) {
 175             PMC * const item = SELF.get_pmc_keyed_int(VTABLE_get_integer(INTERP, key));
 176             PMC * const next = VTABLE_shift_pmc(INTERP, key);
 177
 178             if (!next)
 179                 return VTABLE_get_string(INTERP, item);
 180
 181             return VTABLE_get_string_keyed(INTERP, item, next);
 182         }
 183
 184         return INTERP->vtables[enum_class_Hash]->get_string_keyed(INTERP, SELF, key);
 185     }
 186 /*
 187
 188 =item C<INTVAL get_integer_keyed(PMC *key)>
 189
 190 =item C<INTVAL get_integer_keyed_str(STRING *key)>
 191
 192 =item C<INTVAL get_integer_keyed_int(INTVAL key)>
 193
 194 Returns the integer value associated with C<key>.
 195
 196 =cut
 197
 198 */
 199
 200     VTABLE INTVAL get_integer_keyed_int(INTVAL idx) {
 201         Hash * const h = (Hash *)SELF.get_pointer();
 202         const INTVAL n = h->entries;
 203         HashBucket *b;
 204
 205         if (idx < 0)
 206             idx += n;
 207
 208         if (idx < 0 || idx >= n)
 209             Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
 210                 "OrderedHash: index out of bounds!");
 211
 212         b = h->bs + idx;
 213
 214         if (b->key)
 215             return VTABLE_get_integer(INTERP, (PMC *)b->value);
 216
 217         Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_KEY_NOT_FOUND,
 218             "OrderedHash: No such key");
 219     }
 220
 221     VTABLE INTVAL get_integer_keyed(PMC *key) {
 222
 223         if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG) {
 224             PMC * const item = SELF.get_pmc_keyed_int(VTABLE_get_integer(INTERP, key));
 225             PMC * const next = VTABLE_shift_pmc(INTERP, key);
 226
 227             if (!next)
 228                 return VTABLE_get_integer(INTERP, item);
 229
 230             return VTABLE_get_integer_keyed(INTERP, item, next);
 231         }
 232
 233         return INTERP->vtables[enum_class_Hash]->get_integer_keyed(INTERP, SELF, key);
 234     }
 235
 236 /*
 237
 238 =item C<FLOATVAL get_number_keyed(PMC *key)>
 239
 240 =item C<FLOATVAL get_number_keyed_int(INTVAL key)>
 241
 242 =item C<FLOATVAL get_number_keyed_str(STRING *key)>
 243
 244 Returns the floating-point value for the element at C<key>.
 245
 246 =cut
 247
 248 */
 249
 250     VTABLE FLOATVAL get_number_keyed_int(INTVAL idx) {
 251         Hash * const h = (Hash *)SELF.get_pointer();
 252         const INTVAL n = h->entries;
 253         HashBucket *b;
 254
 255         if (idx < 0)
 256             idx += n;
 257
 258         if (idx < 0 || idx >= n)
 259             Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
 260                 "OrderedHash: index out of bounds!");
 261
 262         b = h->bs + idx;
 263
 264         if (b->key)
 265             return VTABLE_get_number(INTERP, (PMC *)b->value);
 266
 267         Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_KEY_NOT_FOUND,
 268             "OrderedHash: No such key");
 269     }
 270
 271     VTABLE FLOATVAL get_number_keyed(PMC *key) {
 272         if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG) {
 273             PMC * const item = SELF.get_pmc_keyed_int(VTABLE_get_integer(INTERP, key));
 274             PMC * const next = VTABLE_shift_pmc(INTERP, key);
 275
 276             if (!next)
 277                 return VTABLE_get_number(INTERP, item);
 278
 279             return VTABLE_get_number_keyed(INTERP, item, next);
 280         }
 281
 282         return SUPER(key);
 283     }
 284
 285 /*
 286
 287 =item C<void set_pmc_keyed_int(INTVAL idx, PMC *val)>
 288
 289 =item C<void set_integer_keyed_int(INTVAL key, INTVAL value)>
 290
 291 =item C<void set_number_keyed_int(INTVAL key, FLOATVAL value)>
 292
 293 =item C<void set_string_keyed_int(INTVAL key, STRING *value)>
 294
 295 Sets the PMC value of the element at index C<key> to C<val>.
 296 The created key = "\1idx".
 297
 298 =cut
 299
 300 */
 301
 302     VTABLE void set_pmc_keyed_int(INTVAL idx, PMC *val) {
 303         Hash * const     h = (Hash *)SELF.get_pointer();
 304         const INTVAL     n = h->entries;
 305         STRING * const fmt = CONST_STRING(INTERP, "\1%d");
 306
 307         if (idx < -n)
 308             idx = -idx - n - 1;
 309         else if (idx < 0)
 310             idx += n;
 311
 312         if (idx >= n) {
 313             /* TODO warn or fill if there are holes */
 314             STRING * const key = Parrot_sprintf_s(INTERP, fmt, idx);
 315             SELF.set_pmc_keyed_str(key, val);
 316         }
 317         else {
 318             HashBucket * const b = h->bs + idx;
 319
 320             if (!b->key)
 321                 b->key = Parrot_sprintf_s(INTERP, fmt, idx);
 322
 323             b->value     = val;
 324         }
 325     }
 326
 327     VTABLE void set_integer_keyed_int(INTVAL idx, INTVAL value) {
 328         PMC * const v = pmc_new(INTERP, Parrot_get_ctx_HLL_type(INTERP,
 329                     enum_class_Integer));
 330         VTABLE_set_integer_native(INTERP, v, value);
 331         SELF.set_pmc_keyed_int(idx, v);
 332     }
 333
 334     VTABLE void set_number_keyed_int(INTVAL idx, FLOATVAL value) {
 335         PMC * const v = pmc_new(INTERP, Parrot_get_ctx_HLL_type(INTERP,
 336                     enum_class_Float));
 337         VTABLE_set_number_native(INTERP, v, value);
 338         SELF.set_pmc_keyed_int(idx, v);
 339     }
 340
 341     VTABLE void set_string_keyed_int(INTVAL idx, STRING *value) {
 342         PMC * const v = pmc_new(INTERP, Parrot_get_ctx_HLL_type(INTERP,
 343                     enum_class_String));
 344         VTABLE_set_string_native(INTERP, v, value);
 345         SELF.set_pmc_keyed_int(idx, v);
 346     }
 347 /*
 348
 349 =item C<void push_float(FLOATVAL value)>
 350
 351 =item C<void push_integer(INTVAL value)>
 352
 353 =item C<void push_pmc(PMC *value)>
 354
 355 =item C<void push_string(STRING *value)>
 356
 357 =cut
 358
 359 */
 360
 361     VTABLE void push_pmc(PMC *value) {
 362         const INTVAL n = SELF.elements();
 363         SELF.set_pmc_keyed_int(n, value);
 364     }
 365
 366     VTABLE void push_float(FLOATVAL value) {
 367         const INTVAL n = SELF.elements();
 368         SELF.set_number_keyed_int(n, value);
 369     }
 370
 371     VTABLE void push_integer(INTVAL value) {
 372         const INTVAL n = SELF.elements();
 373         SELF.set_integer_keyed_int(n, value);
 374     }
 375
 376     VTABLE void push_string(STRING *value) {
 377         const INTVAL n = SELF.elements();
 378         SELF.set_string_keyed_int(n, value);
 379     }
 380
 381 /*
 382
 383 =item C<INTVAL exists_keyed(PMC *key)>
 384
 385 =item C<INTVAL exists_keyed_str(STRING *key)>
 386
 387 =item C<INTVAL exists_keyed_int(INTVAL key)>
 388
 389 =cut
 390
 391 */
 392
 393     VTABLE INTVAL exists_keyed_int(INTVAL idx) {
 394         Hash * const h = (Hash *)SELF.get_pointer();
 395         const INTVAL n = h->entries;
 396         HashBucket  *b;
 397
 398         if (idx < 0)
 399             idx += n;
 400
 401         if (idx < 0 || idx >= n)
 402             return 0;
 403
 404         b = h->bs + idx;
 405
 406         if (b->key)
 407             return 1;
 408
 409         return 0;
 410     }
 411
 412     VTABLE INTVAL exists_keyed(PMC *key) {
 413         if (PObj_get_FLAGS(key) & KEY_integer_FLAG) {
 414             PMC        *item, *next;
 415             HashBucket *b;
 416             Hash       * const h   = (Hash *)SELF.get_pointer();
 417             INTVAL             idx = VTABLE_get_integer(INTERP, key);
 418             const INTVAL       n   = h->entries;
 419
 420             if (idx < 0)
 421                 idx += n;
 422
 423             if (idx < 0 || idx >= n)
 424                 return 0;
 425
 426             b = h->bs + idx;
 427
 428             if (!b->key)
 429                 return 0;
 430
 431             item = (PMC *)b->value;
 432             next = VTABLE_shift_pmc(INTERP, key);
 433
 434             if (!next)
 435                 return 1;
 436
 437             return VTABLE_exists_keyed(INTERP, item, next);
 438         }
 439
 440         return SUPER(key);
 441     }
 442
 443     VTABLE INTVAL exists_keyed_str(STRING *key) {
 444         const Hash       * const h = (Hash *)SELF.get_pointer();
 445         const HashBucket * const b = parrot_hash_get_bucket(INTERP, h, key);
 446
 447         return (b && b->key);
 448     }
 449
 450 /*
 451
 452 =item C<INTVAL defined_keyed(PMC *key)>
 453
 454 =item C<INTVAL defined_keyed_str(STRING *key)>
 455
 456 =item C<INTVAL defined_keyed_int(INTVAL key)>
 457
 458 =cut
 459
 460 */
 461
 462     VTABLE INTVAL defined_keyed(PMC *key) {
 463         if (PObj_get_FLAGS(key) & KEY_integer_FLAG) {
 464             Hash * const h   = (Hash *)SELF.get_pointer();
 465             INTVAL       idx = VTABLE_get_integer(INTERP, key);
 466             const INTVAL n   = h->entries;
 467
 468             HashBucket *b;
 469             PMC        *item, *next;
 470
 471             if (idx < 0)
 472                 idx += n;
 473
 474             /* XXX non-existent is undefined - is this correct */
 475             if (idx < 0 || idx >= n)
 476                 return 0;
 477
 478             b = h->bs + idx;
 479
 480             if (!b->key)
 481                 return 0;
 482
 483             item = (PMC *)b->value;
 484             next = VTABLE_shift_pmc(INTERP, key);
 485
 486             if (!next)
 487                 return VTABLE_defined(INTERP, item);
 488
 489             return VTABLE_defined_keyed(INTERP, item, next);
 490         }
 491
 492         return SUPER(key);
 493     }
 494
 495     VTABLE INTVAL defined_keyed_int(INTVAL idx) {
 496         Hash * const h = (Hash *)SELF.get_pointer();
 497         const INTVAL n = h->entries;
 498         HashBucket  *b;
 499
 500         if (idx < 0)
 501             idx += n;
 502
 503         if (idx < 0 || idx >= n)
 504             return 0;
 505
 506         b = h->bs + idx;
 507
 508         if (b->key)
 509             return VTABLE_defined(INTERP, (PMC *)b->value);
 510
 511         return 0;
 512     }
 513
 514 /*
 515
 516 =item C<void delete_keyed(PMC *key)>
 517
 518 =item C<void delete_keyed_str(STRING *key)>
 519
 520 =item C<void delete_keyed_int(INTVAL key)>
 521
 522 Deletes the key C<*key> from the hash.
 523
 524 =cut
 525
 526 */
 527
 528     VTABLE void delete_keyed(PMC *key) {
 529         PMC * const next = key_next(INTERP, key);
 530
 531         if (PObj_get_FLAGS(key) & KEY_integer_FLAG) {
 532             if (next) {
 533                 PMC * const item = SELF.get_pmc_keyed_int(VTABLE_get_integer(INTERP, key));
 534                 VTABLE_delete_keyed(INTERP, item, next);
 535                 return;
 536             }
 537
 538             SELF.delete_keyed_int(VTABLE_get_integer(INTERP, key));
 539         }
 540         else {
 541             if (next) {
 542                 PMC * const item = SELF.get_pmc_keyed_str(VTABLE_get_string(INTERP, key));
 543                 VTABLE_delete_keyed(INTERP, item, next);
 544                 return;
 545             }
 546             SELF.delete_keyed_str(VTABLE_get_string(INTERP, key));
 547         }
 548     }
 549
 550     VTABLE void delete_keyed_int(INTVAL idx) {
 551         Hash * const h = (Hash *)SELF.get_pointer();
 552         const INTVAL n = h->entries;
 553         HashBucket  *b;
 554
 555         if (idx < 0)
 556             idx += n;
 557
 558         if (idx < 0 || idx >= n)
 559             return;
 560
 561         b = h->bs + idx;
 562
 563         if (!b)
 564             return;
 565
 566         b->key       = NULL;
 567         b->value     = NULL;
 568     }
 569
 570     VTABLE void delete_keyed_str(STRING *key) {
 571         const Hash * const h = (Hash *)SELF.get_pointer();
 572         HashBucket * const b = parrot_hash_get_bucket(INTERP, h, key);
 573
 574         if (!b)
 575             return;
 576
 577         b->key       = NULL;
 578         b->value     = NULL;
 579     }
 580
 581 /*
 582
 583 =item C<PMC *clone()>
 584
 585 Create a clone of the OrderedHash. Non-existent keys are compacted.  Accessing
 586 the clone via integers has different indices, if items were deleted.
 587
 588 =cut
 589
 590 */
 591
 592     VTABLE PMC *clone() {
 593         PMC  * const dest   = pmc_new(INTERP, SELF->vtable->base_type);
 594         Hash * const hash   = (Hash *)SELF.get_pointer();
 595         Hash * const h_dest = (Hash *)VTABLE_get_pointer(INTERP, dest);
 596         UINTVAL     i;
 597
 598         for (i = 0; i <= N_BUCKETS(hash->mask-1); i++) {
 599             HashBucket * const b      = hash->bs + i;
 600             void       * const key    = b->key;
 601
 602             if (key)
 603                 parrot_hash_put(INTERP, h_dest, key,
 604                     (void *)VTABLE_clone(INTERP, (PMC *)b->value));
 605         }
 606
 607         return dest;
 608     }
 609 /*
 610
 611 =item C<void visit(visit_info *info)>
 612
 613 Used during archiving to visit the elements in the hash.
 614
 615 =item C<void freeze(visit_info *info)>
 616
 617 Used to archive the hash.
 618
 619 =item C<void thaw(visit_info *info)>
 620
 621 Used to unarchive the hash.
 622
 623 Freeze/thaw are inherited from hash.  Only thaw.visit is special, as we have to
 624 preserve key/value order.
 625
 626 =cut
 627
 628 */
 629
 630     VTABLE void visit(visit_info *info) {
 631         info->container  = SELF;
 632
 633         switch (info->what) {
 634             case VISIT_THAW_NORMAL:
 635             case VISIT_THAW_CONSTANTS:
 636                 SUPER(info);
 637                 break;
 638
 639             case VISIT_FREEZE_NORMAL:
 640             case VISIT_FREEZE_AT_DESTRUCT:
 641                 {
 642                     Hash     * const hash = (Hash *)SELF.get_pointer();
 643                     IMAGE_IO * const io   = info->image_io;
 644                     const UINTVAL entries = hash->entries;
 645                     UINTVAL i;
 646
 647                     for (i = 0; i < entries; i++) {
 648                         HashBucket * const b   = hash->bs + i;
 649
 650                         if (b) {
 651                             STRING * const key = (STRING *)b->key;
 652                             if (key) {
 653                                 VTABLE_push_string(interp, io, key);
 654                                 (info->visit_pmc_now)(interp, (PMC *)b->value, info);
 655                             }
 656                         }
 657                     }
 658                 }
 659                 break;
 660             default:
 661                 Parrot_ex_throw_from_c_args(interp, NULL,
 662                     EXCEPTION_INVALID_OPERATION,
 663                     "unhandled visit action (%d)", info->what);
 664         }
 665     }
 666 }
 667
 668 /*
 669
 670 =back
 671
 672 =head1 SEE ALSO
 673
 674 F<docs/pdds/pdd08_keys.pod>.
 675
 676 =head1 HISTORY
 677
 678 Initial rev by leo 2003-08-21.
 679
 680 =cut
 681
 682 */
 683
 684 /*
 685  * Local variables:
 686  *   c-file-style: "parrot"
 687  * End:
 688  * vim: expandtab shiftwidth=4:
 689  */