/*
Copyright (C) 2001-2011, Parrot Foundation.
=head1 NAME
src/pmc/orderedhash.pmc - Ordered Hash
=head1 DESCRIPTION
C<OrderedHash> provide the interfaces of C<array> and
C<hash>.
Some limitations:
=over 4
=item *
Keys are always STRING*.
=item *
Values are always PMC*.
=back
To archive ordering for each item we store:
=over 4
=item * C<key>
Original key
=item * C<value>
Original value
=item * C<next>
Pointer to next C<item>
=item * C<prev>
Pointer to previous C<item>
=back
OrderedHash stores next things:
=over 4
=item * C<hash>
Lookup hash for values.
=item * C<first>
Pointer to first inserted value.
=item * C<last>
Pointer to last inserter value.
=back
See F<t/pmc/orderedhash.t> for test cases.
Overall design heavily inspired by C<Tie::StoredOrderHash>.
=head2 Methods
=over 4
=cut
*/
/* HEADERIZER HFILE: none */
/* HEADERIZER BEGIN: static */
/* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
PARROT_CANNOT_RETURN_NULL
PARROT_WARN_UNUSED_RESULT
static PMC* box_integer(PARROT_INTERP, INTVAL val)
__attribute__nonnull__(1);
PARROT_CANNOT_RETURN_NULL
PARROT_WARN_UNUSED_RESULT
static PMC* box_number(PARROT_INTERP, FLOATVAL val)
__attribute__nonnull__(1);
static void find_bounds(PARROT_INTERP,
ARGIN(PMC *pmc_hash),
ARGMOD(PMC **first),
ARGMOD(PMC **last))
__attribute__nonnull__(1)
__attribute__nonnull__(2)
__attribute__nonnull__(3)
__attribute__nonnull__(4)
FUNC_MODIFIES(*first)
FUNC_MODIFIES(*last);
PARROT_WARN_UNUSED_RESULT
PARROT_CAN_RETURN_NULL
static PMC* get_list_item(PARROT_INTERP, ARGIN(PMC *self), INTVAL idx)
__attribute__nonnull__(1)
__attribute__nonnull__(2);
#define ASSERT_ARGS_box_integer __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
PARROT_ASSERT_ARG(interp))
#define ASSERT_ARGS_box_number __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
PARROT_ASSERT_ARG(interp))
#define ASSERT_ARGS_find_bounds __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
PARROT_ASSERT_ARG(interp) \
, PARROT_ASSERT_ARG(pmc_hash) \
, PARROT_ASSERT_ARG(first) \
, PARROT_ASSERT_ARG(last))
#define ASSERT_ARGS_get_list_item __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
PARROT_ASSERT_ARG(interp) \
, PARROT_ASSERT_ARG(self))
/* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
/* HEADERIZER END: static */
/*
=item C<static PMC* get_list_item(PARROT_INTERP, PMC *self, INTVAL idx)>
Get list_item by index
XXX Can this actually return NULL or not?
=cut
*/
PARROT_WARN_UNUSED_RESULT
PARROT_CAN_RETURN_NULL
static PMC*
get_list_item(PARROT_INTERP, ARGIN(PMC *self), INTVAL idx)
{
ASSERT_ARGS(get_list_item)
const Parrot_OrderedHash_attributes * const attrs = PARROT_ORDEREDHASH(self);
const INTVAL n = VTABLE_elements(interp, attrs->hash);
INTVAL pos;
PMC *list_entry = attrs->first;
if (idx < -n)
idx = -idx - n - 1;
else if (idx < 0)
idx += n;
/* Iterate over linked list to get list_item */
for (pos = 0; pos < idx; ++pos) {
list_entry = VTABLE_get_pmc_keyed_int(interp, list_entry, ORDERED_HASH_ITEM_NEXT);
}
return list_entry;
}
/*
=item C<static void find_bounds(PARROT_INTERP, PMC *pmc_hash, PMC **first, PMC
**last)>
Find first/last in cloned/thawed OrderedHash
Parameter C<pmc_hash> is Hash, not OrderedHash
=cut
*/
static void
find_bounds(PARROT_INTERP, ARGIN(PMC *pmc_hash), ARGMOD(PMC **first), ARGMOD(PMC **last))
{
ASSERT_ARGS(find_bounds)
PMC * const iter = VTABLE_get_iter(interp, pmc_hash);
while (VTABLE_get_bool(interp, iter)) {
PMC * const item = VTABLE_shift_pmc(interp, iter);
PMC * const entry = VTABLE_get_pmc_keyed(interp, pmc_hash, item);
/* First entry doesn't have prev */
PMC *tmp = VTABLE_get_pmc_keyed_int(interp, entry, ORDERED_HASH_ITEM_PREV);
if (PMC_IS_NULL(tmp))
*first = entry;
/* Last entry doesn't have next */
tmp = VTABLE_get_pmc_keyed_int(interp, entry, ORDERED_HASH_ITEM_NEXT);
if (PMC_IS_NULL(tmp))
*last = entry;
}
}
/* Helpers for boxing values */
/*
=item C<static PMC* box_integer(PARROT_INTERP, INTVAL val)>
Helper function to box INTVAL
=cut
*/
PARROT_CANNOT_RETURN_NULL
PARROT_WARN_UNUSED_RESULT
static PMC*
box_integer(PARROT_INTERP, INTVAL val)
{
ASSERT_ARGS(box_integer)
PMC * const ret = Parrot_pmc_new(interp, Parrot_hll_get_ctx_HLL_type(interp,
enum_class_Integer));
VTABLE_set_integer_native(interp, ret, val);
return ret;
}
/*
=item C<static PMC* box_number(PARROT_INTERP, FLOATVAL val)>
Helper function to box FLOATVAL
=cut
*/
PARROT_CANNOT_RETURN_NULL
PARROT_WARN_UNUSED_RESULT
static PMC*
box_number(PARROT_INTERP, FLOATVAL val)
{
ASSERT_ARGS(box_number)
PMC * const ret = Parrot_pmc_new(interp, Parrot_hll_get_ctx_HLL_type(interp,
enum_class_Float));
VTABLE_set_number_native(interp, ret, val);
return ret;
}
pmclass OrderedHash need_ext provides array provides hash auto_attrs {
ATTR PMC *hash; /* key to item tuple */
ATTR PMC *first; /* Pointer to first inserted value */
ATTR PMC *last; /* Pointer to last inserted value */
/*
=item C<void init()>
Create new instance of OrderedHash.
=cut
*/
VTABLE void init() {
Parrot_OrderedHash_attributes * const attrs =
(Parrot_OrderedHash_attributes*) PMC_data(SELF);
attrs->hash = Parrot_pmc_new(INTERP, enum_class_Hash);
attrs->first = PMCNULL;
attrs->last = PMCNULL;
PObj_custom_mark_destroy_SETALL(SELF);
}
/*
=item C<void mark()>
Marks the OrderedHash as live.
=cut
*/
VTABLE void mark() {
const Parrot_OrderedHash_attributes * const attrs =
PARROT_ORDEREDHASH(SELF);
if (attrs->hash)
Parrot_gc_mark_PMC_alive(INTERP, attrs->hash);
/* Don't mark C<first> and C<last>. They are in lookup hash anyway */
}
/*
=item C<PMC *get_iter()>
Return a new iterator
=cut
*/
VTABLE PMC *get_iter() {
return Parrot_pmc_new_init(INTERP, enum_class_OrderedHashIterator, SELF);
}
/*
=item C<INTVAL elements()>
=item C<INTVAL get_integer()>
=item C<FLOATVAL get_number()>
Returns the size of the hash.
=cut
*/
VTABLE INTVAL get_integer() {
return STATICSELF.elements();
}
VTABLE FLOATVAL get_number() {
return SELF.get_integer();
}
VTABLE INTVAL elements() {
return VTABLE_elements(INTERP, PARROT_ORDEREDHASH(SELF)->hash);
}
/*
=item C<set_pmc_keyed(PMC *key, PMC *value)>
Main set function.
=cut
*/
VTABLE void set_pmc_keyed(PMC *key, PMC *value) {
Parrot_OrderedHash_attributes * const attrs =
PARROT_ORDEREDHASH(SELF);
/* Check for old entry */
PMC *list_entry = VTABLE_get_pmc_keyed(INTERP, attrs->hash, key);
if (!PMC_IS_NULL(list_entry)) {
/* We have old entry. Just update value */
PMC * const nextkey = Parrot_key_next(INTERP, key);
if (nextkey) {
VTABLE_set_pmc_keyed(INTERP, value, nextkey, value);
}
else
VTABLE_set_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_VALUE, value);
return;
}
/* Create new entry */
list_entry = Parrot_pmc_new_init_int(INTERP,
enum_class_FixedPMCArray, ORDERED_HASH_ITEM_MAX);
VTABLE_set_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_VALUE, value);
VTABLE_set_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_KEY, key);
/* .. and link it */
if (!PMC_IS_NULL(attrs->last)) {
VTABLE_set_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_PREV, attrs->last);
VTABLE_set_pmc_keyed_int(INTERP, attrs->last, ORDERED_HASH_ITEM_NEXT, list_entry);
}
attrs->last = list_entry;
if (PMC_IS_NULL(attrs->first))
attrs->first = list_entry;
/* .. and store it */
VTABLE_set_pmc_keyed(INTERP, attrs->hash, key, list_entry);
}
/*
=item C<void set_integer_keyed(INTVAL key, INTVAL value)>
=item C<void set_number_keyed(INTVAL key, FLOATVAL value)>
=item C<void set_string_keyed(INTVAL key, STRING *value)>
Sets the PMC value of the element at index C<key> to C<val>.
=cut
*/
VTABLE void set_integer_keyed(PMC *key, INTVAL value) {
PMC * const v = box_integer(INTERP, value);
SELF.set_pmc_keyed(key, v);
}
VTABLE void set_number_keyed(PMC *key, FLOATVAL value) {
PMC * const v = box_number(INTERP, value);
SELF.set_pmc_keyed(key, v);
}
VTABLE void set_string_keyed(PMC *key, STRING *value) {
PMC * const v = Parrot_pmc_box_string(INTERP, value);
SELF.set_pmc_keyed(key, v);
}
/*
=item C<void set_pmc_keyed_str(STRING *key, PMC *val)>
Sets the PMC value of the element at index C<key> to C<val>.
=cut
*/
VTABLE void set_pmc_keyed_str(STRING *key, PMC *value) {
/* Wallpapering problem with HLL Strings as keys */
/* Apparently HLL registry in Parrot uses OrderedHash */
/* Now we have chicken and egg problem during freeze/thaw */
/* When we try to thaw OrderedHash which stores HLL mapping */
/* Reported by François Perrad */
PMC * const pkey = Parrot_pmc_new(INTERP, enum_class_String);
VTABLE_set_string_native(INTERP, pkey, key);
VTABLE_set_pmc_keyed(INTERP, SELF, pkey, value);
}
/*
=item C<PMC *get_pmc_keyed(PMC *key)>
=item C<PMC *get_pmc_keyed_int(INTVAL key)>
=item C<PMC *get_pmc_keyed_str(STRING *key)>
=cut
*/
VTABLE PMC *get_pmc_keyed_int(INTVAL idx) {
PMC * const list_entry = get_list_item(INTERP, SELF, idx);
if (PMC_IS_NULL(list_entry))
return PMCNULL;
return VTABLE_get_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_VALUE);
}
VTABLE PMC *get_pmc_keyed(PMC *key) {
PMC *item;
/* Access by integer index */
if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG)
return SELF.get_pmc_keyed_int(VTABLE_get_integer(INTERP, key));
item = VTABLE_get_pmc_keyed(INTERP, PARROT_ORDEREDHASH(SELF)->hash, key);
if (PMC_IS_NULL(item))
return PMCNULL;
return VTABLE_get_pmc_keyed_int(INTERP, item, ORDERED_HASH_ITEM_VALUE);
}
VTABLE PMC *get_pmc_keyed_str(STRING *key) {
PMC * const item = VTABLE_get_pmc_keyed_str(INTERP,
PARROT_ORDEREDHASH(SELF)->hash, key);
if (PMC_IS_NULL(item))
return PMCNULL;
return VTABLE_get_pmc_keyed_int(INTERP, item, ORDERED_HASH_ITEM_VALUE);
}
/*
=item C<STRING *get_string_keyed(PMC *key)>
=item C<STRING *get_string_keyed_int(INTVAL key)>
=item C<STRING *get_string_keyed_str(STRING *key)>
=cut
*/
VTABLE STRING *get_string_keyed_int(INTVAL idx) {
PMC * const item = VTABLE_get_pmc_keyed_int(INTERP, SELF, idx);
return VTABLE_get_string(INTERP, item);
}
VTABLE STRING *get_string_keyed(PMC *key) {
PMC * const item = VTABLE_get_pmc_keyed(INTERP, SELF, key);
return VTABLE_get_string(INTERP, item);
}
/*
=item C<INTVAL get_integer_keyed(PMC *key)>
=item C<INTVAL get_integer_keyed_str(STRING *key)>
=item C<INTVAL get_integer_keyed_int(INTVAL key)>
Returns the integer value associated with C<key>.
=cut
*/
VTABLE INTVAL get_integer_keyed_int(INTVAL idx) {
PMC * const item = VTABLE_get_pmc_keyed_int(INTERP, SELF, idx);
return VTABLE_get_integer(INTERP, item);
}
VTABLE INTVAL get_integer_keyed(PMC *key) {
PMC * const item = VTABLE_get_pmc_keyed(INTERP, SELF, key);
return VTABLE_get_integer(INTERP, item);
}
/*
=item C<FLOATVAL get_number_keyed(PMC *key)>
=item C<FLOATVAL get_number_keyed_int(INTVAL key)>
=item C<FLOATVAL get_number_keyed_str(STRING *key)>
Returns the floating-point value for the element at C<key>.
=cut
*/
VTABLE FLOATVAL get_number_keyed_int(INTVAL idx) {
PMC * const item = VTABLE_get_pmc_keyed_int(INTERP, SELF, idx);
return VTABLE_get_number(INTERP, item);
}
VTABLE FLOATVAL get_number_keyed(PMC *key) {
PMC * const item = VTABLE_get_pmc_keyed(INTERP, SELF, key);
return VTABLE_get_number(INTERP, item);
}
/*
=item C<void set_pmc_keyed_int(INTVAL idx, PMC *val)>
=item C<void set_integer_keyed_int(INTVAL key, INTVAL value)>
=item C<void set_number_keyed_int(INTVAL key, FLOATVAL value)>
=item C<void set_string_keyed_int(INTVAL key, STRING *value)>
Sets the PMC value of the element at index C<key> to C<val>.
The created key = "\1idx".
=cut
*/
VTABLE void set_pmc_keyed_int(INTVAL idx, PMC *val) {
const INTVAL n = STATICSELF.elements();
if (idx < -n)
idx = -idx - n - 1;
else if (idx < 0)
idx += n;
if (idx >= n) {
/* TODO warn or fill if there are holes */
STRING * const fmt = CONST_STRING(INTERP, "\1%d");
STRING * const key = Parrot_sprintf_s(INTERP, fmt, idx);
SELF.set_pmc_keyed_str(key, val);
}
else {
PMC * const list_entry = get_list_item(INTERP, SELF, idx);
PARROT_ASSERT(!PMC_IS_NULL(list_entry));
VTABLE_set_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_VALUE, val);
}
}
VTABLE void set_integer_keyed_int(INTVAL idx, INTVAL value) {
PMC * const v = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP,
enum_class_Integer));
VTABLE_set_integer_native(INTERP, v, value);
SELF.set_pmc_keyed_int(idx, v);
}
VTABLE void set_number_keyed_int(INTVAL idx, FLOATVAL value) {
PMC * const v = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP,
enum_class_Float));
VTABLE_set_number_native(INTERP, v, value);
SELF.set_pmc_keyed_int(idx, v);
}
VTABLE void set_string_keyed_int(INTVAL idx, STRING *value) {
PMC * const v = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP,
enum_class_String));
VTABLE_set_string_native(INTERP, v, value);
SELF.set_pmc_keyed_int(idx, v);
}
/*
=item C<void push_float(FLOATVAL value)>
=item C<void push_integer(INTVAL value)>
=item C<void push_pmc(PMC *value)>
=item C<void push_string(STRING *value)>
=cut
*/
VTABLE void push_pmc(PMC *value) {
const INTVAL n = SELF.elements();
SELF.set_pmc_keyed_int(n, value);
}
VTABLE void push_float(FLOATVAL value) {
const INTVAL n = SELF.elements();
SELF.set_number_keyed_int(n, value);
}
VTABLE void push_integer(INTVAL value) {
const INTVAL n = SELF.elements();
SELF.set_integer_keyed_int(n, value);
}
VTABLE void push_string(STRING *value) {
const INTVAL n = SELF.elements();
SELF.set_string_keyed_int(n, value);
}
/*
=item C<INTVAL exists_keyed(PMC *key)>
=item C<INTVAL exists_keyed_str(STRING *key)>
=item C<INTVAL exists_keyed_int(INTVAL key)>
=cut
*/
VTABLE INTVAL exists_keyed_int(INTVAL idx) {
return (idx >= 0) && (idx < STATICSELF.elements());
}
VTABLE INTVAL exists_keyed(PMC *key) {
if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG) {
/* Don't fetch item prematurely. It's costy */
const INTVAL intval = VTABLE_get_integer(INTERP, key);
PMC * const next = VTABLE_shift_pmc(INTERP, key);
if (!next)
return STATICSELF.exists_keyed_int(intval);
return VTABLE_exists_keyed(INTERP, STATICSELF.get_pmc_keyed_int(intval), next);
}
return VTABLE_exists_keyed_str(INTERP, SELF, VTABLE_get_string(INTERP, key));
}
VTABLE INTVAL exists_keyed_str(STRING *key) {
return VTABLE_exists_keyed_str(INTERP, PARROT_ORDEREDHASH(SELF)->hash, key);
}
/*
=item C<INTVAL defined_keyed(PMC *key)>
=item C<INTVAL defined_keyed_int(INTVAL key)>
=cut
*/
VTABLE INTVAL defined_keyed(PMC *key) {
/* We store list_item (which is defined). So fetch original PMC and check it */
PMC * const item = STATICSELF.get_pmc_keyed(key);
if (PMC_IS_NULL(item))
return 0;
return VTABLE_defined(INTERP, item);
}
VTABLE INTVAL defined_keyed_int(INTVAL idx) {
PMC * item;
/* If item doesn't exists it's undefined */
if (!STATICSELF.exists_keyed_int(idx))
return 0;
/* Null is undefined */
item = STATICSELF.get_pmc_keyed_int(idx);
if (PMC_IS_NULL(item))
return 0;
return VTABLE_defined(INTERP, item);
}
/*
=item C<void delete_keyed(PMC *key)>
=item C<void delete_keyed_int(INTVAL key)>
Deletes the key C<*key> from the hash.
=cut
*/
VTABLE void delete_keyed(PMC *key) {
Parrot_OrderedHash_attributes * const attrs = PARROT_ORDEREDHASH(SELF);
PMC *list_entry, *prev, *next;
if ((PObj_get_FLAGS(key) & KEY_type_FLAGS) == KEY_integer_FLAG) {
const INTVAL intval = VTABLE_get_integer(INTERP, key);
PMC * const next = VTABLE_shift_pmc(INTERP, key);
if (next)
VTABLE_delete_keyed(INTERP, STATICSELF.get_pmc_keyed_int(intval), next);
else
STATICSELF.delete_keyed_int(intval);
return;
}
list_entry = VTABLE_get_pmc_keyed(INTERP, attrs->hash, key);
if (PMC_IS_NULL(list_entry))
return;
/* Unlink entry */
next = VTABLE_get_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_NEXT);
prev = VTABLE_get_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_PREV);
if (attrs->first == list_entry)
attrs->first = next;
if (attrs->last == list_entry)
attrs->last = prev;
/* C<prev> and C<next> are list entries (FPA) */
if (!PMC_IS_NULL(prev))
VTABLE_set_pmc_keyed_int(INTERP, prev, ORDERED_HASH_ITEM_NEXT, next);
if (!PMC_IS_NULL(next))
VTABLE_set_pmc_keyed_int(INTERP, next, ORDERED_HASH_ITEM_PREV, prev);
/* And finally delete it */
VTABLE_delete_keyed(INTERP, PARROT_ORDEREDHASH(SELF)->hash, key);
}
VTABLE void delete_keyed_int(INTVAL idx) {
if (STATICSELF.exists_keyed_int(idx)) {
PMC * const list_entry = get_list_item(INTERP, SELF, idx);
STATICSELF.delete_keyed(
VTABLE_get_pmc_keyed_int(INTERP, list_entry, ORDERED_HASH_ITEM_KEY));
}
return;
}
/*
=item C<PMC *clone()>
Create a clone of the OrderedHash. Non-existent keys are compacted. Accessing
the clone via integers has different indices, if items were deleted.
=cut
*/
VTABLE PMC *clone() {
PMC * const dest = Parrot_pmc_new(INTERP, SELF->vtable->base_type);
Parrot_OrderedHash_attributes *clone_attrs =
PARROT_ORDEREDHASH(dest);
clone_attrs->hash = VTABLE_clone(INTERP, PARROT_ORDEREDHASH(SELF)->hash);
find_bounds(INTERP, clone_attrs->hash, &clone_attrs->first, &clone_attrs->last);
return dest;
}
/*
=item C<void visit(PMC *info)>
Used during archiving to visit the elements in the hash.
=item C<void freeze(PMC *info)>
Used to archive the hash.
=item C<void thaw(PMC *info)>
Used to unarchive the hash.
=cut
*/
VTABLE void visit(PMC *info) {
VISIT_PMC_ATTR(INTERP, info, SELF, OrderedHash, hash);
SUPER(info);
}
VTABLE void thawfinish(PMC *info) {
Parrot_OrderedHash_attributes * const attrs = PARROT_ORDEREDHASH(SELF);
find_bounds(INTERP, attrs->hash, &attrs->first, &attrs->last);
SUPER(info);
}
/*
=item C<get_pmc()>
Get underlying regular Hash. Used in UnManagedStruct.
=cut
*/
VTABLE PMC* get_pmc() {
PMC *hash;
GET_ATTR_hash(INTERP, SELF, hash);
return hash;
}
}
/*
=back
=head1 SEE ALSO
F<docs/pdds/pdd08_keys.pod>.
=cut
*/
/*
* Local variables:
* c-file-style: "parrot"
* End:
* vim: expandtab shiftwidth=4 cinoptions='\:2=2' :
*/