2 Copyright (C) 2001-2009, Parrot Foundation.
7 src/hash.c - Hash table
11 A hashtable contains an array of bucket indexes. Buckets are nodes in a
12 linked list, each containing a C<void *> key and value. During hash
13 creation, the types of key and value as well as appropriate compare and
14 hashing functions can be set.
16 This hash implementation uses just one piece of malloced memory. The
17 C<< hash->bs >> bucket store points to this region.
19 This hash doesn't move during GC, therefore a lot of the old caveats
30 #include "parrot/parrot.h"
31 #include "pmc/pmc_key.h"
33 /* the number of entries above which it's faster to hash the hashval instead of
34 * looping over the used HashBuckets directly */
35 #define SMALL_HASH_SIZE 4
36 #define INITIAL_BUCKETS 4
38 /* HEADERIZER HFILE: include/parrot/hash.h */
40 /* HEADERIZER BEGIN: static */
41 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
43 PARROT_WARN_UNUSED_RESULT
45 static int cstring_compare(SHIM_INTERP
,
48 __attribute__nonnull__(2)
49 __attribute__nonnull__(3);
51 static void expand_hash(PARROT_INTERP
, ARGMOD(Hash
*hash
))
52 __attribute__nonnull__(1)
53 __attribute__nonnull__(2)
56 static void hash_freeze(PARROT_INTERP
,
57 ARGIN(const Hash
* const hash
),
58 ARGMOD(visit_info
*info
))
59 __attribute__nonnull__(1)
60 __attribute__nonnull__(2)
61 __attribute__nonnull__(3)
64 static void hash_thaw(PARROT_INTERP
,
66 ARGMOD(visit_info
*info
))
67 __attribute__nonnull__(1)
68 __attribute__nonnull__(2)
69 __attribute__nonnull__(3)
73 PARROT_WARN_UNUSED_RESULT
75 static size_t key_hash_cstring(SHIM_INTERP
,
76 ARGIN(const void *value
),
78 __attribute__nonnull__(2);
80 PARROT_WARN_UNUSED_RESULT
82 static size_t key_hash_pointer(SHIM_INTERP
,
83 ARGIN(const void *value
),
85 __attribute__nonnull__(2);
87 static void parrot_mark_hash_both(PARROT_INTERP
, ARGIN(Hash
*hash
))
88 __attribute__nonnull__(1)
89 __attribute__nonnull__(2);
91 static void parrot_mark_hash_keys(PARROT_INTERP
, ARGIN(Hash
*hash
))
92 __attribute__nonnull__(1)
93 __attribute__nonnull__(2);
95 static void parrot_mark_hash_values(PARROT_INTERP
, ARGIN(Hash
*hash
))
96 __attribute__nonnull__(1)
97 __attribute__nonnull__(2);
99 #define ASSERT_ARGS_cstring_compare __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
100 PARROT_ASSERT_ARG(a) \
101 , PARROT_ASSERT_ARG(b))
102 #define ASSERT_ARGS_expand_hash __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
103 PARROT_ASSERT_ARG(interp) \
104 , PARROT_ASSERT_ARG(hash))
105 #define ASSERT_ARGS_hash_freeze __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
106 PARROT_ASSERT_ARG(interp) \
107 , PARROT_ASSERT_ARG(hash) \
108 , PARROT_ASSERT_ARG(info))
109 #define ASSERT_ARGS_hash_thaw __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
110 PARROT_ASSERT_ARG(interp) \
111 , PARROT_ASSERT_ARG(hash) \
112 , PARROT_ASSERT_ARG(info))
113 #define ASSERT_ARGS_key_hash_cstring __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
114 PARROT_ASSERT_ARG(value))
115 #define ASSERT_ARGS_key_hash_pointer __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
116 PARROT_ASSERT_ARG(value))
117 #define ASSERT_ARGS_parrot_mark_hash_both __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
118 PARROT_ASSERT_ARG(interp) \
119 , PARROT_ASSERT_ARG(hash))
120 #define ASSERT_ARGS_parrot_mark_hash_keys __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
121 PARROT_ASSERT_ARG(interp) \
122 , PARROT_ASSERT_ARG(hash))
123 #define ASSERT_ARGS_parrot_mark_hash_values __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
124 PARROT_ASSERT_ARG(interp) \
125 , PARROT_ASSERT_ARG(hash))
126 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
127 /* HEADERIZER END: static */
133 =item C<size_t key_hash_STRING(PARROT_INTERP, STRING *s, size_t seed)>
135 Returns the hashed value of the key C<value>. See also string.c.
142 PARROT_WARN_UNUSED_RESULT
144 key_hash_STRING(PARROT_INTERP
, ARGMOD(STRING
*s
), SHIM(size_t seed
))
146 ASSERT_ARGS(key_hash_STRING
)
151 return Parrot_str_to_hashval(interp
, s
);
157 =item C<int STRING_compare(PARROT_INTERP, const void *search_key, const void
160 Compares the two strings, returning 0 if they are identical.
166 PARROT_WARN_UNUSED_RESULT
168 STRING_compare(PARROT_INTERP
, ARGIN(const void *search_key
), ARGIN_NULLOK(const void *bucket_key
))
170 ASSERT_ARGS(STRING_compare
)
171 STRING
const *s1
= (STRING
const *)search_key
;
172 STRING
const *s2
= (STRING
const *)bucket_key
;
177 if (s1
->hashval
!= s2
->hashval
)
181 if (Buffer_bufstart(s1
) == Buffer_bufstart(s2
) && s1
->bufused
== s2
->bufused
)
184 return CHARSET_COMPARE(interp
, s1
, s2
);
190 =item C<int pointer_compare(PARROT_INTERP, const void *a, const void *b)>
192 Compares the two pointers, returning 0 if they are identical
198 PARROT_WARN_UNUSED_RESULT
201 pointer_compare(SHIM_INTERP
, ARGIN_NULLOK(const void *a
), ARGIN_NULLOK(const void *b
))
203 ASSERT_ARGS(pointer_compare
)
210 =item C<static size_t key_hash_pointer(PARROT_INTERP, const void *value, size_t
213 Returns a hashvalue for a pointer.
219 PARROT_WARN_UNUSED_RESULT
222 key_hash_pointer(SHIM_INTERP
, ARGIN(const void *value
), size_t seed
)
224 ASSERT_ARGS(key_hash_pointer
)
225 return ((size_t) value
) ^ seed
;
231 =item C<static size_t key_hash_cstring(PARROT_INTERP, const void *value, size_t
234 Creates and returns a hash value from a string.
236 Takes an interpreter, a pointer to a string, and a seed value.
237 Returns the hash value.
239 Used by parrot_new_cstring_hash.
245 PARROT_WARN_UNUSED_RESULT
248 key_hash_cstring(SHIM_INTERP
, ARGIN(const void *value
), size_t seed
)
250 ASSERT_ARGS(key_hash_cstring
)
251 const unsigned char * p
= (const unsigned char *) value
;
252 register size_t h
= seed
;
265 =item C<static int cstring_compare(PARROT_INTERP, const char *a, const char *b)>
267 Compares two C strings for equality, returning -1, 0, and 1 if the first string
268 is less than, equal to, or greater than the second, respectively.
274 PARROT_WARN_UNUSED_RESULT
277 cstring_compare(SHIM_INTERP
, ARGIN(const char *a
), ARGIN(const char *b
))
279 ASSERT_ARGS(cstring_compare
)
286 =item C<size_t key_hash_PMC(PARROT_INTERP, PMC *value, size_t seed)>
288 Returns a hashed value for an PMC key (passed as a void pointer, sadly).
294 PARROT_WARN_UNUSED_RESULT
297 key_hash_PMC(PARROT_INTERP
, ARGIN(PMC
*value
), SHIM(size_t seed
))
299 ASSERT_ARGS(key_hash_PMC
)
300 return VTABLE_hashvalue(interp
, value
);
305 =item C<int PMC_compare(PARROT_INTERP, PMC *a, PMC *b)>
307 Compares two PMC for equality, returning 0 if the first is equal to second.
308 Uses void pointers to store the PMC, sadly.
314 PARROT_WARN_UNUSED_RESULT
317 PMC_compare(PARROT_INTERP
, ARGIN(PMC
*a
), ARGIN_NULLOK(PMC
*b
))
319 ASSERT_ARGS(PMC_compare
)
321 /* If pointers are same - PMCs are same */
325 /* PMCs of different types are differ */
326 if (a
->vtable
->base_type
!= b
->vtable
->base_type
)
329 return !VTABLE_is_equal(interp
, a
, b
);
334 =item C<size_t key_hash_int(PARROT_INTERP, const void *value, size_t seed)>
336 Returns a hashed value for an integer key (passed as a void pointer, sadly).
342 PARROT_WARN_UNUSED_RESULT
345 key_hash_int(SHIM_INTERP
, ARGIN_NULLOK(const void *value
), size_t seed
)
347 ASSERT_ARGS(key_hash_int
)
348 return (size_t)value
^ seed
;
353 =item C<int int_compare(PARROT_INTERP, const void *a, const void *b)>
355 Compares two integers for equality, returning -1, 0, and 1 if the first is less
356 than, equal to, or greater than the second, respectively. Uses void pointers
357 to store the integers, sadly.
363 PARROT_WARN_UNUSED_RESULT
366 int_compare(SHIM_INTERP
, ARGIN_NULLOK(const void *a
), ARGIN_NULLOK(const void *b
))
368 ASSERT_ARGS(int_compare
)
374 =item C<void parrot_dump_hash(PARROT_INTERP, const Hash *hash)>
376 Prints out the hash in human-readable form, at least once someone implements
385 parrot_dump_hash(SHIM_INTERP
, SHIM(const Hash
*hash
))
387 ASSERT_ARGS(parrot_dump_hash
)
393 =item C<void parrot_mark_hash(PARROT_INTERP, Hash *hash)>
395 Marks the hash and its contents as live. Assumes that key and value are non
404 parrot_mark_hash(PARROT_INTERP
, ARGIN(Hash
*hash
))
406 ASSERT_ARGS(parrot_mark_hash
)
410 if (hash
->entry_type
== (PARROT_DATA_TYPE
) enum_hash_string
411 || hash
->entry_type
== (PARROT_DATA_TYPE
) enum_hash_pmc
)
414 if (hash
->key_type
== Hash_key_type_STRING
415 || hash
->key_type
== Hash_key_type_PMC
)
420 parrot_mark_hash_both(interp
, hash
);
422 parrot_mark_hash_keys(interp
, hash
);
426 parrot_mark_hash_values(interp
, hash
);
433 =item C<static void parrot_mark_hash_keys(PARROT_INTERP, Hash *hash)>
435 Marks the hash and only its keys as live.
442 parrot_mark_hash_keys(PARROT_INTERP
, ARGIN(Hash
*hash
))
444 ASSERT_ARGS(parrot_mark_hash_keys
)
445 UINTVAL entries
= hash
->entries
;
449 for (i
= hash
->mask
; i
>= 0; --i
) {
450 HashBucket
*bucket
= hash
->bi
[i
];
453 if (++found
> entries
)
454 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
455 "Detected hash corruption at hash %p entries %d",
458 PARROT_ASSERT(bucket
->key
);
459 Parrot_gc_mark_PObj_alive(interp
, (PObj
*)bucket
->key
);
461 bucket
= bucket
->next
;
469 =item C<static void parrot_mark_hash_values(PARROT_INTERP, Hash *hash)>
471 Marks the hash and only its values as live.
478 parrot_mark_hash_values(PARROT_INTERP
, ARGIN(Hash
*hash
))
480 ASSERT_ARGS(parrot_mark_hash_values
)
481 const UINTVAL entries
= hash
->entries
;
485 for (i
= hash
->mask
; i
>= 0; --i
) {
486 HashBucket
*bucket
= hash
->bi
[i
];
489 if (++found
> entries
)
490 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
491 "Detected hash corruption at hash %p entries %d",
494 PARROT_ASSERT(bucket
->value
);
495 Parrot_gc_mark_PObj_alive(interp
, (PObj
*)bucket
->value
);
497 bucket
= bucket
->next
;
505 =item C<static void parrot_mark_hash_both(PARROT_INTERP, Hash *hash)>
507 Marks the hash and both its keys and values as live.
514 parrot_mark_hash_both(PARROT_INTERP
, ARGIN(Hash
*hash
))
516 ASSERT_ARGS(parrot_mark_hash_both
)
517 const UINTVAL entries
= hash
->entries
;
521 for (i
= hash
->mask
; i
>= 0; --i
) {
522 HashBucket
*bucket
= hash
->bi
[i
];
525 if (++found
> entries
)
526 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
527 "Detected hash corruption at hash %p entries %d",
530 PARROT_ASSERT(bucket
->key
);
531 Parrot_gc_mark_PObj_alive(interp
, (PObj
*)bucket
->key
);
533 PARROT_ASSERT(bucket
->value
);
534 Parrot_gc_mark_PObj_alive(interp
, (PObj
*)bucket
->value
);
536 bucket
= bucket
->next
;
544 =item C<static void hash_thaw(PARROT_INTERP, Hash *hash, visit_info *info)>
546 Visits the contents of a hash during freeze/thaw.
548 C<pinfo> is the visit info, (see include/parrot/pmc_freeze.h>).
555 hash_thaw(PARROT_INTERP
, ARGMOD(Hash
*hash
), ARGMOD(visit_info
*info
))
557 ASSERT_ARGS(hash_thaw
)
558 IMAGE_IO
* const io
= info
->image_io
;
560 /* during thaw, info->extra is the key/value count */
561 const size_t num_entries
= (size_t) hash
->entries
;
566 for (entry_index
= 0; entry_index
< num_entries
; ++entry_index
) {
569 switch (hash
->key_type
) {
570 case Hash_key_type_STRING
:
572 STRING
* const s_key
= VTABLE_shift_string(interp
, io
);
573 b
= parrot_hash_put(interp
, hash
, s_key
, NULL
);
576 case Hash_key_type_int
:
578 const INTVAL i_key
= VTABLE_shift_integer(interp
, io
);
579 b
= parrot_hash_put(interp
, hash
, (void*)i_key
, NULL
);
583 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
584 "unimplemented key type");
588 switch (hash
->entry_type
) {
591 /* this looks awful, but it avoids type-punning warnings */
592 void **ptr
= &b
->value
;
593 info
->thaw_ptr
= (PMC
**)ptr
;
594 (info
->visit_pmc_now
)(interp
, NULL
, info
);
599 const INTVAL i
= VTABLE_shift_integer(interp
, io
);
600 b
->value
= (void *)i
;
604 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
605 "unimplemented value type");
614 =item C<static void hash_freeze(PARROT_INTERP, const Hash * const hash,
617 Freezes hash into a string.
619 Takes an interpreter, a pointer to the hash, and a pointer to the structure
620 containing the string start location.
622 Use by parrot_hash_visit.
629 hash_freeze(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGMOD(visit_info
*info
))
631 ASSERT_ARGS(hash_freeze
)
632 IMAGE_IO
* const io
= info
->image_io
;
635 for (i
= 0; i
< hash
->entries
; i
++) {
636 HashBucket
* const b
= hash
->bs
+i
;
638 switch (hash
->key_type
) {
639 case Hash_key_type_STRING
:
640 VTABLE_push_string(interp
, io
, (STRING
*)b
->key
);
642 case Hash_key_type_int
:
643 VTABLE_push_integer(interp
, io
, (INTVAL
)b
->key
);
646 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
647 "unimplemented key type");
651 switch (hash
->entry_type
) {
653 (info
->visit_pmc_now
)(interp
, (PMC
*)b
->value
, info
);
656 VTABLE_push_integer(interp
, io
, (INTVAL
)b
->value
);
659 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
660 "unimplemented value type");
669 =item C<void parrot_hash_visit(PARROT_INTERP, Hash *hash, void *pinfo)>
671 Freezes or thaws a hash as specified. Takes an interpreter, a pointer to the
672 hash, and a pointer to the structure identifying what to do and the location of
681 parrot_hash_visit(PARROT_INTERP
, ARGMOD(Hash
*hash
), ARGMOD(void *pinfo
))
683 ASSERT_ARGS(parrot_hash_visit
)
684 visit_info
* const info
= (visit_info
*) pinfo
;
686 switch (info
->what
) {
687 case VISIT_THAW_NORMAL
:
688 case VISIT_THAW_CONSTANTS
:
689 hash_thaw(interp
, hash
, info
);
691 case VISIT_FREEZE_NORMAL
:
692 case VISIT_FREEZE_AT_DESTRUCT
:
693 hash_freeze(interp
, hash
, info
);
696 Parrot_ex_throw_from_c_args(interp
, NULL
, 1,
697 "unimplemented visit mode");
704 =item C<static void expand_hash(PARROT_INTERP, Hash *hash)>
706 Expands a hash when necessary.
708 For a hashtable of size N, we use C<MAXFULL_PERCENT> % of N as the
709 number of buckets. This way, as soon as we run out of buckets on the
710 free list, we know that it's time to resize the hashtable.
712 Algorithm for expansion: We exactly double the size of the hashtable.
713 Keys are assigned to buckets with the formula
715 bucket_index = hash(key) % parrot_hash_size
717 When doubling the size of the hashtable, we know that every key is either
718 already in the correct bucket, or belongs in the current bucket plus
719 C<parrot_hash_size> (the old C<parrot_hash_size>). In fact, because the
720 hashtable is always a power of two in size, it depends only on the next bit
721 in the hash value, after the ones previously used.
723 We scan through all the buckets in order, moving the buckets that need to be
724 moved. No bucket will be scanned twice, and the cache should be reasonably
725 happy because the hashtable accesses will be two parallel sequential scans.
726 (Of course, this also mucks with the C<< ->next >> pointers, and they'll be
734 expand_hash(PARROT_INTERP
, ARGMOD(Hash
*hash
))
736 ASSERT_ARGS(expand_hash
)
737 HashBucket
**old_bi
, **new_bi
;
738 HashBucket
*bs
, *b
, *new_mem
;
739 HashBucket
*old_offset
= (HashBucket
*)((char *)hash
+ sizeof (Hash
));
741 void * const old_mem
= hash
->bs
;
742 const UINTVAL old_size
= hash
->mask
+ 1;
743 const UINTVAL new_size
= old_size
<< 1;
744 const UINTVAL old_nb
= N_BUCKETS(old_size
);
745 size_t offset
, i
, new_loc
;
748 allocate some less buckets
749 e.g. 3 buckets, 4 pointers:
751 +---+---+---+-+-+-+-+
753 +---+---+---+-+-+-+-+
759 if (old_offset
!= old_mem
) {
760 /* This buffer has been reallocated at least once before. */
761 new_mem
= (HashBucket
*)mem_sys_realloc(old_mem
, HASH_ALLOC_SIZE(new_size
));
764 /* Allocate a new buffer. */
765 new_mem
= (HashBucket
*)mem_sys_allocate(HASH_ALLOC_SIZE(new_size
));
766 memcpy(new_mem
, old_mem
, HASH_ALLOC_SIZE(old_size
));
770 +---+---+---+---+---+---+-+-+-+-+-+-+-+-+
771 | bs | old_bi | new_bi |
772 +---+---+---+---+---+---+-+-+-+-+-+-+-+-+
777 old_bi
= (HashBucket
**)(bs
+ old_nb
);
778 new_bi
= (HashBucket
**)(bs
+ N_BUCKETS(new_size
));
780 /* things can have moved by this offset */
781 offset
= (char *)new_mem
- (char *)old_mem
;
783 /* relocate the bucket index */
784 mem_sys_memmove(new_bi
, old_bi
, old_size
* sizeof (HashBucket
*));
786 /* update hash data */
789 hash
->mask
= new_size
- 1;
791 /* clear freshly allocated bucket index */
792 memset(new_bi
+ old_size
, 0, sizeof (HashBucket
*) * old_size
);
795 * reloc pointers - this part would be also needed, if we
796 * allocate hash memory from GC movable memory, and then
797 * also the free_list needs updating (this is empty now,
798 * as expand_hash is only called for that case).
801 for (i
= 0; i
< old_size
; ++i
) {
802 HashBucket
**next_p
= new_bi
+ i
;
804 *next_p
= (HashBucket
*)((char *)*next_p
+ offset
);
811 /* recalc bucket index */
812 for (i
= 0; i
< old_size
; ++i
) {
813 HashBucket
**next_p
= new_bi
+ i
;
816 /* rehash the bucket */
817 new_loc
= (hash
->hash_val
)(interp
, b
->key
, hash
->seed
) &
822 b
->next
= new_bi
[new_loc
];
830 /* add new buckets to free_list in reverse order
831 * lowest bucket is top on free list and will be used first */
832 for (i
= 0, b
= (HashBucket
*)new_bi
- 1; i
< old_nb
; ++i
, --b
) {
833 b
->next
= hash
->free_list
;
834 b
->key
= b
->value
= NULL
;
842 =item C<Hash* parrot_new_hash(PARROT_INTERP)>
844 Creates a new Parrot STRING hash.
851 PARROT_CANNOT_RETURN_NULL
853 parrot_new_hash(PARROT_INTERP
)
855 ASSERT_ARGS(parrot_new_hash
)
856 return parrot_create_hash(interp
,
858 Hash_key_type_STRING
,
860 (hash_hash_key_fn
)key_hash_STRING
);
866 =item C<Hash* parrot_new_cstring_hash(PARROT_INTERP)>
868 Creates a new C string hash in C<hptr>.
875 PARROT_CANNOT_RETURN_NULL
877 parrot_new_cstring_hash(PARROT_INTERP
)
879 ASSERT_ARGS(parrot_new_cstring_hash
)
880 return parrot_create_hash(interp
,
882 Hash_key_type_cstring
,
883 (hash_comp_fn
)cstring_compare
,
884 (hash_hash_key_fn
)key_hash_cstring
);
890 =item C<Hash * parrot_new_pointer_hash(PARROT_INTERP)>
892 Create and return a new hash with void * keys and values.
899 PARROT_CANNOT_RETURN_NULL
901 parrot_new_pointer_hash(PARROT_INTERP
)
903 ASSERT_ARGS(parrot_new_pointer_hash
)
904 return parrot_create_hash(interp
,
914 =item C<Hash* parrot_new_intval_hash(PARROT_INTERP)>
916 Creates and returns new Hash PMC with INTVAL keys and values. C<flags> can be
917 C<PObj_constant_FLAG> or 0.
925 PARROT_WARN_UNUSED_RESULT
926 PARROT_CANNOT_RETURN_NULL
928 parrot_new_intval_hash(PARROT_INTERP
)
930 ASSERT_ARGS(parrot_new_intval_hash
)
931 return parrot_create_hash(interp
,
940 =item C<Hash * parrot_create_hash(PARROT_INTERP, PARROT_DATA_TYPE val_type,
941 Hash_key_type hkey_type, hash_comp_fn compare, hash_hash_key_fn keyhash)>
943 Creates and initializes a hash. Function pointers determine its behaviors.
944 The container passed in is the address of the hash PMC that is using it. The
945 hash and the PMC point to each other.
947 Memory from this function must be freed.
953 PARROT_CANNOT_RETURN_NULL
954 PARROT_WARN_UNUSED_RESULT
957 parrot_create_hash(PARROT_INTERP
, PARROT_DATA_TYPE val_type
, Hash_key_type hkey_type
,
958 ARGIN(hash_comp_fn compare
), ARGIN(hash_hash_key_fn keyhash
))
960 ASSERT_ARGS(parrot_create_hash
)
962 void *alloc
= mem_sys_allocate(sizeof (Hash
) + HASH_ALLOC_SIZE(INITIAL_BUCKETS
));
963 Hash
* const hash
= (Hash
*)alloc
;
966 PARROT_ASSERT(INITIAL_BUCKETS
% 4 == 0);
968 hash
->compare
= compare
;
969 hash
->hash_val
= keyhash
;
970 hash
->entry_type
= val_type
;
971 hash
->key_type
= hkey_type
;
972 hash
->seed
= interp
->hash_seed
;
973 hash
->mask
= INITIAL_BUCKETS
- 1;
975 hash
->container
= PMCNULL
;
978 * TODO if we have a significant amount of small hashes:
979 * - allocate a bigger hash structure e.g. 128 byte
980 * - use the bucket store and bi inside this structure
981 * - when reallocate copy this part
983 bp
= (HashBucket
*)((char *)alloc
+ sizeof (Hash
));
984 hash
->free_list
= NULL
;
986 /* fill free_list from hi addresses so that we can use
987 * buckets[i] directly in an OrderedHash, *if* nothing
991 bp
+= N_BUCKETS(INITIAL_BUCKETS
);
992 hash
->bi
= (HashBucket
**)bp
;
994 for (i
= 0, --bp
; i
< N_BUCKETS(INITIAL_BUCKETS
); ++i
, --bp
) {
995 bp
->next
= hash
->free_list
;
998 hash
->free_list
= bp
;
1001 for (i
= 0; i
< INITIAL_BUCKETS
; ++i
)
1010 =item C<void parrot_hash_destroy(PARROT_INTERP, Hash *hash)>
1012 Frees the memory allocated to the specified hash and its bucket store. Used by
1013 parrot_chash_destroy.
1021 parrot_hash_destroy(SHIM_INTERP
, ARGMOD(Hash
*hash
))
1023 ASSERT_ARGS(parrot_hash_destroy
)
1024 HashBucket
*bp
= (HashBucket
*)((char*)hash
+ sizeof (Hash
));
1026 mem_sys_free(hash
->bs
);
1033 =item C<void parrot_chash_destroy(PARROT_INTERP, Hash *hash)>
1035 Deletes the specified hash by freeing the memory allocated to all the key-value
1036 pairs, and finally the hash itself.
1043 parrot_chash_destroy(PARROT_INTERP
, ARGMOD(Hash
*hash
))
1045 ASSERT_ARGS(parrot_chash_destroy
)
1048 for (i
= 0; i
<= hash
->mask
; i
++) {
1049 HashBucket
*bucket
= hash
->bi
[i
];
1051 mem_sys_free(bucket
->key
);
1052 mem_sys_free(bucket
->value
);
1053 bucket
= bucket
->next
;
1057 parrot_hash_destroy(interp
, hash
);
1063 =item C<void parrot_chash_destroy_values(PARROT_INTERP, Hash *hash, value_free
1066 Deletes the specified hash by freeing the memory allocated to all the key-value
1067 pairs, calling the provided callback to free the values, and finally the hash
1070 The callback returns C<void> and takes a C<void *>.
1077 parrot_chash_destroy_values(PARROT_INTERP
, ARGMOD(Hash
*hash
),
1078 ARGIN(value_free func
))
1080 ASSERT_ARGS(parrot_chash_destroy_values
)
1083 for (i
= 0; i
<= hash
->mask
; i
++) {
1084 HashBucket
*bucket
= hash
->bi
[i
];
1086 mem_sys_free(bucket
->key
);
1087 func(bucket
->value
);
1088 bucket
= bucket
->next
;
1092 parrot_hash_destroy(interp
, hash
);
1098 =item C<INTVAL parrot_hash_size(PARROT_INTERP, const Hash *hash)>
1100 Returns the number of used entries in the hash.
1107 PARROT_WARN_UNUSED_RESULT
1108 PARROT_PURE_FUNCTION
1110 parrot_hash_size(SHIM_INTERP
, ARGIN(const Hash
*hash
))
1112 ASSERT_ARGS(parrot_hash_size
)
1114 return hash
->entries
;
1120 =item C<void * parrot_hash_get_idx(PARROT_INTERP, const Hash *hash, PMC *key)>
1122 Finds the next index into the hash's internal storage for the given Key. Used
1130 PARROT_WARN_UNUSED_RESULT
1131 PARROT_CAN_RETURN_NULL
1133 parrot_hash_get_idx(PARROT_INTERP
, ARGIN(const Hash
*hash
), ARGMOD(PMC
*key
))
1135 ASSERT_ARGS(parrot_hash_get_idx
)
1138 INTVAL i
= VTABLE_get_integer(interp
, key
);
1142 /* idx directly in the bucket store, which is at negative
1143 * address from the data pointer */
1144 /* locate initial */
1145 const INTVAL size
= (INTVAL
)N_BUCKETS(hash
->mask
+ 1);
1147 GETATTR_Key_next_key(interp
, key
, fake_bi
);
1148 bi
= (BucketIndex
)fake_bi
;
1150 if (bi
== INITBucketIndex
) {
1152 SETATTR_Key_next_key(interp
, key
, NULL
);
1154 else if (i
>= size
|| i
< 0) {
1155 /* NOTE: These instances of SETATTR_Key_int_key can't be VTABLE
1156 * functions because of the "special" way hash iterators work. */
1157 SETATTR_Key_int_key(interp
, key
, -1);
1163 for (b
= hash
->bs
+ i
; i
< size
; ++i
, ++b
) {
1164 /* XXX int keys may be zero - use different iterator */
1169 /* found next key - FIXME hash iter does auto next */
1178 SETATTR_Key_int_key(interp
, key
, i
);
1186 =item C<HashBucket * parrot_hash_get_bucket(PARROT_INTERP, const Hash *hash,
1189 Returns the bucket for C<key>, if found, and NULL otherwise.
1196 PARROT_WARN_UNUSED_RESULT
1197 PARROT_CAN_RETURN_NULL
1199 parrot_hash_get_bucket(PARROT_INTERP
, ARGIN(const Hash
*hash
), ARGIN_NULLOK(const void *key
))
1201 ASSERT_ARGS(parrot_hash_get_bucket
)
1203 if (hash
->entries
<= 0)
1206 /* a very fast search for very small hashes */
1207 if (hash
->entries
<= SMALL_HASH_SIZE
) {
1208 const UINTVAL entries
= hash
->entries
;
1211 for (i
= 0; i
< entries
; i
++) {
1212 HashBucket
*bucket
= hash
->bs
+ i
;
1214 /* the hash->compare cost is too high for this fast path */
1215 if (bucket
->key
== key
)
1220 /* if the fast search didn't work, try the normal hashing search */
1222 const UINTVAL hashval
= (hash
->hash_val
)(interp
, key
, hash
->seed
);
1223 HashBucket
*bucket
= hash
->bi
[hashval
& hash
->mask
];
1226 /* key equality is always a match, so it's worth checking */
1227 if (bucket
->key
== key
1229 /* ... but the slower comparison is more accurate */
1230 || ((hash
->compare
)(interp
, key
, bucket
->key
) == 0))
1232 bucket
= bucket
->next
;
1242 =item C<void * parrot_hash_get(PARROT_INTERP, Hash *hash, const void *key)>
1244 Returns the value keyed by C<key>, or C<NULL> if no bucket is found.
1251 PARROT_WARN_UNUSED_RESULT
1252 PARROT_CAN_RETURN_NULL
1254 parrot_hash_get(PARROT_INTERP
, ARGIN(Hash
*hash
), ARGIN(const void *key
))
1256 ASSERT_ARGS(parrot_hash_get
)
1257 const HashBucket
* const bucket
= parrot_hash_get_bucket(interp
, hash
, key
);
1258 return bucket
? bucket
->value
: NULL
;
1264 =item C<INTVAL parrot_hash_exists(PARROT_INTERP, Hash *hash, void *key)>
1266 Returns whether the key exists in the hash.
1273 PARROT_WARN_UNUSED_RESULT
1275 parrot_hash_exists(PARROT_INTERP
, ARGIN(Hash
*hash
), ARGIN(void *key
))
1277 ASSERT_ARGS(parrot_hash_exists
)
1278 const HashBucket
* const bucket
= parrot_hash_get_bucket(interp
, hash
, key
);
1279 return bucket
? 1 : 0;
1285 =item C<HashBucket* parrot_hash_put(PARROT_INTERP, Hash *hash, void *key, void
1288 Puts the key and value into the hash. Note that C<key> is B<not> copied.
1295 PARROT_IGNORABLE_RESULT
1296 PARROT_CANNOT_RETURN_NULL
1298 parrot_hash_put(PARROT_INTERP
, ARGMOD(Hash
*hash
),
1299 ARGIN_NULLOK(void *key
), ARGIN_NULLOK(void *value
))
1301 ASSERT_ARGS(parrot_hash_put
)
1302 const UINTVAL hashval
= (hash
->hash_val
)(interp
, key
, hash
->seed
);
1303 HashBucket
*bucket
= hash
->bi
[hashval
& hash
->mask
];
1305 /* When the hash is constant, check that the key and value are also
1307 if (!PMC_IS_NULL(hash
->container
)
1308 && PObj_constant_TEST(hash
->container
)) {
1309 if (hash
->key_type
== Hash_key_type_STRING
1310 && !PObj_constant_TEST((PObj
*)key
))
1311 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_INVALID_OPERATION
,
1312 "Used non-constant key in constant hash.");
1313 if (((hash
->entry_type
== enum_type_PMC
) || (hash
->entry_type
== enum_type_STRING
))
1314 && !PObj_constant_TEST((PObj
*)value
))
1315 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_INVALID_OPERATION
,
1316 "Used non-constant value in constant hash.");
1320 /* store hash_val or not */
1321 if ((hash
->compare
)(interp
, key
, bucket
->key
) == 0)
1323 bucket
= bucket
->next
;
1327 bucket
->value
= value
;
1330 bucket
= hash
->free_list
;
1333 expand_hash(interp
, hash
);
1334 bucket
= hash
->free_list
;
1338 hash
->free_list
= bucket
->next
;
1340 bucket
->value
= value
;
1341 bucket
->next
= hash
->bi
[hashval
& hash
->mask
];
1342 hash
->bi
[hashval
& hash
->mask
] = bucket
;
1351 =item C<void parrot_hash_delete(PARROT_INTERP, Hash *hash, void *key)>
1353 Deletes the key from the hash.
1361 parrot_hash_delete(PARROT_INTERP
, ARGMOD(Hash
*hash
), ARGIN(void *key
))
1363 ASSERT_ARGS(parrot_hash_delete
)
1365 HashBucket
*prev
= NULL
;
1366 const UINTVAL hashval
= (hash
->hash_val
)(interp
, key
, hash
->seed
) & hash
->mask
;
1368 for (bucket
= hash
->bi
[hashval
]; bucket
; bucket
= bucket
->next
) {
1369 if ((hash
->compare
)(interp
, key
, bucket
->key
) == 0) {
1372 prev
->next
= bucket
->next
;
1374 hash
->bi
[hashval
] = bucket
->next
;
1377 bucket
->next
= hash
->free_list
;
1379 hash
->free_list
= bucket
;
1391 =item C<void parrot_hash_clone(PARROT_INTERP, const Hash *hash, Hash *dest)>
1393 Clones C<hash> to C<dest>.
1401 parrot_hash_clone(PARROT_INTERP
, ARGIN(const Hash
*hash
), ARGOUT(Hash
*dest
))
1403 ASSERT_ARGS(parrot_hash_clone
)
1404 UINTVAL entries
= hash
->entries
;
1407 for (i
= 0; i
< entries
; i
++) {
1409 HashBucket
*b
= hash
->bs
+i
;
1410 void * const key
= b
->key
;
1412 switch (hash
->entry_type
) {
1413 case enum_type_undef
:
1415 case enum_type_INTVAL
:
1416 valtmp
= (void *)b
->value
;
1419 case enum_type_STRING
:
1420 valtmp
= (void *)Parrot_str_copy(interp
, (STRING
*)b
->value
);
1424 if (PMC_IS_NULL((PMC
*)b
->value
))
1425 valtmp
= (void *)PMCNULL
;
1427 valtmp
= (void *)VTABLE_clone(interp
, (PMC
*)b
->value
);
1431 valtmp
= NULL
; /* avoid warning */
1432 Parrot_ex_throw_from_c_args(interp
, NULL
, -1,
1433 "hash corruption: type = %d\n", hash
->entry_type
);
1437 parrot_hash_put(interp
, dest
, key
, valtmp
);
1444 =item C<PMC* get_integer_pmc(PARROT_INTERP, INTVAL value)>
1446 Lookup the PMC type which is used for storing native integers.
1452 PARROT_CANNOT_RETURN_NULL
1454 get_integer_pmc(PARROT_INTERP
, INTVAL value
)
1456 ASSERT_ARGS(get_integer_pmc
)
1457 PMC
* const ret
= pmc_new(interp
, Parrot_get_ctx_HLL_type(interp
, enum_class_Integer
));
1458 VTABLE_set_integer_native(interp
, ret
, value
);
1465 =item C<PMC* get_number_pmc(PARROT_INTERP, FLOATVAL value)>
1467 Lookup the PMC type which is used for floating point numbers.
1473 PARROT_CANNOT_RETURN_NULL
1475 get_number_pmc(PARROT_INTERP
, FLOATVAL value
)
1477 ASSERT_ARGS(get_number_pmc
)
1478 PMC
* const ret
= pmc_new(interp
, Parrot_get_ctx_HLL_type(interp
, enum_class_Float
));
1479 VTABLE_set_number_native(interp
, ret
, value
);
1485 =item C<PMC * get_string_pmc(PARROT_INTERP, STRING *value)>
1487 Lookup the PMC type which is used for storing strings.
1493 PARROT_CANNOT_RETURN_NULL
1495 get_string_pmc(PARROT_INTERP
, ARGIN(STRING
*value
))
1497 ASSERT_ARGS(get_string_pmc
)
1498 PMC
* const ret
= pmc_new(interp
, Parrot_get_ctx_HLL_type(interp
, enum_class_String
));
1499 VTABLE_set_string_native(interp
, ret
, value
);
1506 Poor-man polymorphic functions to convert something to something.
1508 There is bunch of functions to convert from passed value to stored keys type and to/from
1511 void *hash_key_from_TYPE convert to keys type.
1512 TYPE hash_key_to_TYPE convert from keys type.
1513 void *hash_value_from_TYPE convert to values type.
1514 TYPE hash_value_to_TYPE convert from values type.
1520 =item C<void* hash_key_from_int(PARROT_INTERP, const Hash * const hash, INTVAL
1523 Cast INTVAL to hash key.
1529 PARROT_CAN_RETURN_NULL
1531 hash_key_from_int(PARROT_INTERP
, ARGIN(const Hash
* const hash
), INTVAL key
)
1533 ASSERT_ARGS(hash_key_from_int
)
1535 switch (hash
->key_type
) {
1536 case Hash_key_type_int
:
1539 /* Currently PMCs are stringified */
1540 case Hash_key_type_PMC
:
1541 ret
= (void *)get_integer_pmc(interp
, key
);
1543 case Hash_key_type_STRING
:
1544 ret
= (void *)Parrot_str_from_int(interp
, key
);
1547 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1548 "Hash: unsupported key_type");
1555 =item C<void* hash_key_from_string(PARROT_INTERP, const Hash * const hash,
1558 Cast STRING to hash key.
1564 PARROT_CAN_RETURN_NULL
1566 hash_key_from_string(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN(STRING
*key
))
1568 ASSERT_ARGS(hash_key_from_string
)
1570 switch (hash
->key_type
) {
1571 case Hash_key_type_int
:
1573 /* Pacify compiler about casting INVTAL to void */
1574 const INTVAL int_key
= Parrot_str_to_int(interp
, key
);
1575 ret
= INTVAL2PTR(void *, int_key
);
1579 case Hash_key_type_PMC
:
1580 ret
= get_string_pmc(interp
, key
);
1583 case Hash_key_type_STRING
:
1588 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1589 "Hash: unsupported key_type");
1596 =item C<void* hash_key_from_pmc(PARROT_INTERP, const Hash * const hash, PMC
1599 Cast PMC* to hash key.
1605 PARROT_CAN_RETURN_NULL
1607 hash_key_from_pmc(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN(PMC
*key
))
1609 ASSERT_ARGS(hash_key_from_pmc
)
1611 switch (hash
->key_type
) {
1612 case Hash_key_type_int
:
1614 const INTVAL int_key
= VTABLE_get_integer(interp
, key
);
1615 ret
= INTVAL2PTR(void *, int_key
);
1618 case Hash_key_type_PMC
:
1620 /* Extract real value from Key (and box it if nessary) */
1621 if (key
->vtable
->base_type
== enum_class_Key
)
1622 switch (key_type(interp
, key
)) {
1623 case KEY_integer_FLAG
:
1624 key
= get_integer_pmc(interp
, key_integer(interp
, key
));
1626 case KEY_string_FLAG
:
1627 key
= get_string_pmc(interp
, key_string(interp
, key
));
1629 case KEY_number_FLAG
:
1630 key
= get_number_pmc(interp
, key_number(interp
, key
));
1633 key
= key_pmc(interp
, key
);
1636 /* It's impossible if Keys are same (and they are not) */
1637 /* So throw exception */
1638 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_INVALID_OPERATION
,
1639 "hash: unexpected type of Key");
1646 case Hash_key_type_STRING
:
1648 STRING
* const tmp
= VTABLE_get_string(interp
, key
);
1650 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNEXPECTED_NULL
,
1651 "hash: can't use null as key");
1656 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1657 "Hash: unsupported key_type");
1664 =item C<INTVAL hash_key_to_int(PARROT_INTERP, const Hash * const hash, void
1667 Cast hash key to INTVAL.
1674 hash_key_to_int(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN_NULLOK(void *key
))
1676 ASSERT_ARGS(hash_key_to_int
)
1678 switch (hash
->key_type
) {
1679 case Hash_key_type_int
:
1682 case Hash_key_type_PMC
:
1683 ret
= VTABLE_get_integer(interp
, (PMC
*)key
);
1685 case Hash_key_type_STRING
:
1686 ret
= Parrot_str_to_int(interp
, (STRING
*)key
);
1689 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1690 "Hash: unsupported key_type");
1697 =item C<STRING* hash_key_to_string(PARROT_INTERP, const Hash * const hash, void
1700 Cast hash key to STRING.
1706 PARROT_CANNOT_RETURN_NULL
1708 hash_key_to_string(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN_NULLOK(void *key
))
1710 ASSERT_ARGS(hash_key_to_string
)
1712 switch (hash
->key_type
) {
1713 case Hash_key_type_int
:
1714 ret
= Parrot_str_from_int(interp
, (INTVAL
)key
);
1717 case Hash_key_type_PMC
:
1718 ret
= VTABLE_get_string(interp
, (PMC
*)key
);
1721 case Hash_key_type_STRING
:
1722 ret
= (STRING
*)key
;
1726 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1727 "Hash: unsupported key_type");
1734 =item C<PMC* hash_key_to_pmc(PARROT_INTERP, const Hash * const hash, void *key)>
1736 Cast hash key to PMC*.
1742 PARROT_CANNOT_RETURN_NULL
1744 hash_key_to_pmc(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN(void *key
))
1746 ASSERT_ARGS(hash_key_to_pmc
)
1748 switch (hash
->key_type
) {
1749 case Hash_key_type_int
:
1750 ret
= get_integer_pmc(interp
, (INTVAL
)key
);
1752 case Hash_key_type_PMC
:
1755 case Hash_key_type_STRING
:
1756 ret
= get_string_pmc(interp
, (STRING
*)key
);
1759 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1760 "Hash: unsupported key_type");
1765 /* Second part - convert from stored void* to real type */
1766 /* TODO: FLOATVALs converted into Float PMC for now */
1770 =item C<void* hash_value_from_int(PARROT_INTERP, const Hash * const hash, INTVAL
1773 Cast INTVAL to hash value.
1779 PARROT_CAN_RETURN_NULL
1781 hash_value_from_int(PARROT_INTERP
, ARGIN(const Hash
* const hash
), INTVAL value
)
1783 ASSERT_ARGS(hash_value_from_int
)
1785 switch (hash
->entry_type
) {
1786 case enum_type_INTVAL
:
1787 ret
= INTVAL2PTR(void *, value
);
1791 PMC
* const tmp
= get_integer_pmc(interp
, value
);
1795 case enum_type_STRING
:
1796 ret
= (void *)Parrot_str_from_int(interp
, value
);
1799 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1800 "Hash: unsupported entry_type");
1807 =item C<void* hash_value_from_string(PARROT_INTERP, const Hash * const hash,
1810 Cast STRING to hash value.
1816 PARROT_CAN_RETURN_NULL
1818 hash_value_from_string(PARROT_INTERP
, ARGIN(const Hash
* const hash
),
1819 ARGIN_NULLOK(STRING
*value
))
1821 ASSERT_ARGS(hash_value_from_string
)
1823 switch (hash
->entry_type
) {
1824 case enum_type_INTVAL
:
1826 const INTVAL int_val
= STRING_IS_NULL(value
) ?
1827 (INTVAL
) 0 : Parrot_str_to_int(interp
, value
);
1828 ret
= INTVAL2PTR(void *, int_val
);
1831 case enum_type_STRING
:
1832 ret
= (void *)value
;
1836 PMC
* const s
= STRING_IS_NULL(value
) ?
1837 PMCNULL
: get_string_pmc(interp
, value
);
1842 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1843 "Hash: unsupported entry_type");
1850 =item C<void* hash_value_from_pmc(PARROT_INTERP, const Hash * const hash, PMC
1853 Cast PMC to hash value.
1859 PARROT_CAN_RETURN_NULL
1861 hash_value_from_pmc(PARROT_INTERP
, ARGIN(const Hash
* const hash
),
1862 ARGIN_NULLOK(PMC
*value
))
1864 ASSERT_ARGS(hash_value_from_pmc
)
1866 switch (hash
->entry_type
) {
1867 case enum_type_INTVAL
:
1869 const INTVAL int_val
= PMC_IS_NULL(value
) ?
1870 (INTVAL
) 0 : VTABLE_get_integer(interp
, value
);
1871 ret
= INTVAL2PTR(void *, int_val
);
1874 case enum_type_STRING
:
1875 ret
= PMC_IS_NULL(value
) ?
1876 PMCNULL
: (void *)VTABLE_get_string(interp
, value
);
1879 ret
= (void *)value
;
1882 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1883 "Hash: unsupported entry_type");
1890 =item C<void* hash_value_from_number(PARROT_INTERP, const Hash * const hash,
1893 Cast FLOATVAL to hash value.
1899 PARROT_CAN_RETURN_NULL
1901 hash_value_from_number(PARROT_INTERP
, ARGIN(const Hash
* const hash
), FLOATVAL value
)
1903 ASSERT_ARGS(hash_value_from_number
)
1905 switch (hash
->entry_type
) {
1906 case enum_type_INTVAL
:
1908 const INTVAL tmp
= value
;
1912 case enum_type_STRING
:
1913 ret
= (void *)Parrot_str_from_num(interp
, value
);
1917 PMC
* const tmp
= get_number_pmc(interp
, value
);
1922 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1923 "Hash: unsupported entry_type");
1930 =item C<INTVAL hash_value_to_int(PARROT_INTERP, const Hash * const hash, void
1933 Cast hash value to INTVAL.
1940 hash_value_to_int(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN_NULLOK(void *value
))
1942 ASSERT_ARGS(hash_value_to_int
)
1944 switch (hash
->entry_type
) {
1946 case enum_type_INTVAL
:
1947 ret
= (INTVAL
)value
;
1949 case enum_type_STRING
:
1950 ret
= Parrot_str_to_int(interp
, (STRING
*)value
);
1953 ret
= VTABLE_get_integer(interp
, (PMC
*)value
);
1956 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1957 "Hash: unsupported entry_type");
1964 =item C<STRING* hash_value_to_string(PARROT_INTERP, const Hash * const hash,
1967 Cast hash value to STRING.
1973 PARROT_CANNOT_RETURN_NULL
1975 hash_value_to_string(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN_NULLOK(void *value
))
1977 ASSERT_ARGS(hash_value_to_string
)
1979 switch (hash
->entry_type
) {
1980 case enum_type_INTVAL
:
1981 ret
= Parrot_str_from_int(interp
, (INTVAL
)value
);
1983 case enum_type_STRING
:
1984 ret
= (STRING
*)value
;
1987 ret
= VTABLE_get_string(interp
, (PMC
*)value
);
1990 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
1991 "Hash: unsupported entry_type");
1998 =item C<PMC* hash_value_to_pmc(PARROT_INTERP, const Hash * const hash, void
2001 Cast hash value to PMC.
2007 PARROT_CANNOT_RETURN_NULL
2009 hash_value_to_pmc(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN_NULLOK(void *value
))
2011 ASSERT_ARGS(hash_value_to_pmc
)
2013 switch (hash
->entry_type
) {
2014 case enum_type_INTVAL
:
2015 ret
= get_integer_pmc(interp
, (INTVAL
)value
);
2017 case enum_type_STRING
:
2018 ret
= get_string_pmc(interp
, (STRING
*)value
);
2024 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
2025 "Hash: unsupported entry_type");
2032 =item C<FLOATVAL hash_value_to_number(PARROT_INTERP, const Hash * const hash,
2035 Cast hash value to FLOATVAL.
2042 hash_value_to_number(PARROT_INTERP
, ARGIN(const Hash
* const hash
), ARGIN_NULLOK(void *value
))
2044 ASSERT_ARGS(hash_value_to_number
)
2046 switch (hash
->entry_type
) {
2047 case enum_type_INTVAL
:
2049 /* Pacify compiler about casting */
2050 const INTVAL tmp
= (INTVAL
)value
;
2054 case enum_type_STRING
:
2055 ret
= Parrot_str_to_num(interp
, (STRING
*)value
);
2058 ret
= VTABLE_get_number(interp
, (PMC
*)value
);
2061 Parrot_ex_throw_from_c_args(interp
, NULL
, EXCEPTION_UNIMPLEMENTED
,
2062 "Hash: unsupported entry_type");
2073 F<docs/pdds/pdd08_keys.pod>.
2077 Future optimizations:
2081 =item * Stop reallocating the bucket pool, and instead add chunks on.
2082 (Saves pointer fixups and copying during C<realloc>.)
2084 =item * Hash contraction (don't if it's worth it)
2095 * c-file-style: "parrot"
2097 * vim: expandtab shiftwidth=4: