Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
tag: RELEASE_0_4_5
Fetching contributors…

Cannot retrieve contributors at this time

639 lines (495 sloc) 15.706 kB
/*
Copyright (C) 2001-2003, The Perl Foundation.
$Id$
=head1 NAME
src/pmc/orderedhash.pmc - Ordered Hash
=head1 DESCRIPTION
C<OrderedHash> extends C<Hash> to provide the interfaces of
C<array> and C<hash>. To achieve the functionality of an ordered
hash there are a few restrictions though: C<delete_keyed> never removes
items, they are just nulled.
Please note that if values are set via integer idx, these indices
have to be in strict order. Using C<push_xx> simplifies this task.
This creates a key "\1idx" for C<idx> and is therefore not fully transparent.
There are 2 iterator interfaces:
=over 4
=item * retrieve values (in creation order)
Please note that after a C<delete_keyed> operation, iterating over
values doesn't work any more, you'll get an error 'No such key'.
=item * retrieve keys (in creation order)
=back
See F<t/pmc/orderedhash.t>.
=head2 Methods
=over 4
=cut
*/
#include "parrot/parrot.h"
#include "pmc_hash.h"
pmclass OrderedHash extends Hash need_ext does array does hash {
/*
=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
*/
PMC* get_pmc_keyed_int (INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
real_exception(INTERP, NULL, KEY_NOT_FOUND,
"OrderedHash: index out of bounds!");
}
b = h->bs + idx;
if (b->key)
return (PMC*) b->value;
real_exception(INTERP, NULL, KEY_NOT_FOUND,
"OrderedHash: No such key");
return PMCNULL;
}
PMC* get_pmc_keyed (PMC* key) {
PMC *item, *next;
switch (PObj_get_FLAGS(key) & KEY_type_FLAGS) {
case KEY_hash_iterator_FLAGS:
return SUPER(key);
case KEY_integer_FLAG:
item = SELF.get_pmc_keyed_int(key_integer(INTERP, key));
next = key_next(INTERP, key);
if (!next)
return item;
return VTABLE_get_pmc_keyed(INTERP, item, next);
default:
return SUPER(key);
}
}
/*
=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
*/
STRING* get_string_keyed_int (INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
real_exception(INTERP, NULL, KEY_NOT_FOUND,
"OrderedHash: index out of bounds!");
}
b = h->bs + idx;
if (b->key)
return VTABLE_get_string(INTERP, (PMC*) b->value);
real_exception(INTERP, NULL, KEY_NOT_FOUND,
"OrderedHash: No such key");
return NULL;
}
STRING* get_string_keyed (PMC* key) {
PMC *item, *next;
switch (PObj_get_FLAGS(key) & KEY_type_FLAGS) {
case KEY_hash_iterator_FLAGS:
return SUPER(key);
case KEY_integer_FLAG:
item = SELF.get_pmc_keyed_int(key_integer(INTERP, key));
next = key_next(INTERP, key);
if (!next)
return VTABLE_get_string(INTERP, item);
return VTABLE_get_string_keyed(INTERP, item, next);
default:
return SUPER(key);
}
}
/*
=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
*/
INTVAL get_integer_keyed_int (INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
real_exception(INTERP, NULL, OUT_OF_BOUNDS,
"OrderedHash: index out of bounds!");
}
b = h->bs + idx;
if (b->key)
return VTABLE_get_integer(INTERP, (PMC*) b->value);
real_exception(INTERP, NULL, KEY_NOT_FOUND,
"OrderedHash: No such key");
return 0;
}
INTVAL get_integer_keyed (PMC* key) {
PMC *item, *next;
switch (PObj_get_FLAGS(key) & KEY_type_FLAGS) {
case KEY_hash_iterator_FLAGS:
return SUPER(key);
case KEY_integer_FLAG:
item = SELF.get_pmc_keyed_int(key_integer(INTERP, key));
next = key_next(INTERP, key);
if (!next)
return VTABLE_get_integer(INTERP, item);
return VTABLE_get_integer_keyed(INTERP, item, next);
default:
return SUPER(key);
}
}
/*
=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
*/
FLOATVAL get_number_keyed_int (INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
real_exception(INTERP, NULL, OUT_OF_BOUNDS,
"OrderedHash: index out of bounds!");
}
b = h->bs + idx;
if (b->key)
return VTABLE_get_number(INTERP, (PMC*) b->value);
real_exception(INTERP, NULL, KEY_NOT_FOUND,
"OrderedHash: No such key");
return 0.0;
}
FLOATVAL get_number_keyed (PMC* key) {
PMC *item, *next;
switch (PObj_get_FLAGS(key) & KEY_type_FLAGS) {
case KEY_hash_iterator_FLAGS:
return SUPER(key);
case KEY_integer_FLAG:
item = SELF.get_pmc_keyed_int(key_integer(INTERP, key));
next = key_next(INTERP, key);
if (!next)
return VTABLE_get_number(INTERP, item);
return VTABLE_get_number_keyed(INTERP, item, next);
default:
return SUPER(key);
}
}
/*
=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
*/
void set_pmc_keyed_int (INTVAL idx, PMC* val) {
STRING *key, *fmt;
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < -n)
idx = -idx - n - 1;
else if (idx < 0)
idx += n;
fmt = CONST_STRING(INTERP, "\1%d");
if (idx >= n) {
/* TODO warn or fill if there are holes */
key = Parrot_sprintf_s(INTERP, fmt, idx);
DYNSELF.set_pmc_keyed_str(key, val);
}
else {
b = h->bs + idx;
if (!b->key) {
b->key = Parrot_sprintf_s(INTERP, fmt, idx);
}
b->value = val;
}
}
void set_integer_keyed_int (INTVAL idx, INTVAL value) {
PMC *v = pmc_new(INTERP, Parrot_get_ctx_HLL_type(INTERP,
enum_class_Integer));
VTABLE_set_integer_native(INTERP, v, value);
SELF.set_pmc_keyed_int(idx, v);
}
void set_number_keyed_int (INTVAL idx, FLOATVAL value) {
PMC *v = pmc_new(INTERP, Parrot_get_ctx_HLL_type(INTERP,
enum_class_Float));
VTABLE_set_number_native(INTERP, v, value);
SELF.set_pmc_keyed_int(idx, v);
}
void set_string_keyed_int (INTVAL idx, STRING* value) {
PMC *v = pmc_new(INTERP, Parrot_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
*/
void push_pmc(PMC* value) {
INTVAL n = DYNSELF.elements();
SELF.set_pmc_keyed_int(n, value);
}
void push_float(FLOATVAL value) {
INTVAL n = DYNSELF.elements();
SELF.set_number_keyed_int(n, value);
}
void push_integer(INTVAL value) {
INTVAL n = DYNSELF.elements();
SELF.set_integer_keyed_int(n, value);
}
void push_string(STRING* value) {
INTVAL n = DYNSELF.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
*/
INTVAL exists_keyed_int(INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
return 0;
}
b = h->bs + idx;
if (b->key)
return 1;
return 0;
}
INTVAL exists_keyed(PMC* key) {
PMC *item, *next;
if (PObj_get_FLAGS(key) & KEY_integer_FLAG) {
Hash *h = PMC_struct_val(SELF);
INTVAL n, idx;
HashBucket *b;
idx = key_integer(INTERP, key);
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
return 0;
}
b = h->bs + idx;
if (!b->key)
return 0;
item = b->value;
next = key_next(INTERP, key);
if (!next)
return 1;
return VTABLE_exists_keyed(INTERP, item, next);
}
else {
return SUPER(key);
}
}
INTVAL exists_keyed_str(STRING* key) {
Hash *h = PMC_struct_val(SELF);
HashBucket *b;
b = parrot_hash_get_bucket(INTERP, h, key);
if (b && b->key)
return 1;
return 0;
}
/*
=item C<INTVAL defined_keyed(PMC *key)>
=item C<INTVAL defined_keyed_str(STRING *key)>
=item C<INTVAL defined_keyed_int(INTVAL key)>
=cut
*/
INTVAL defined_keyed(PMC *key) {
PMC *item, *next;
if (PObj_get_FLAGS(key) & KEY_integer_FLAG) {
Hash *h = PMC_struct_val(SELF);
INTVAL n, idx;
HashBucket *b;
idx = key_integer(INTERP, key);
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
/* XXX non-existant is undefined - is this correct */
return 0;
}
b = h->bs + idx;
if (!b->key)
return 0;
item = b->value;
next = key_next(INTERP, key);
if (!next)
return VTABLE_defined(INTERP, item);
return VTABLE_defined_keyed(INTERP, item, next);
}
return SUPER(key);
}
INTVAL defined_keyed_int(INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
return 0;
}
b = h->bs + idx;
if (b->key)
return VTABLE_defined(INTERP, (PMC*)b->value);
return 0;
}
/*
=item C<void delete_keyed(PMC *key)>
=item C<void delete_keyed_str(STRING *key)>
=item C<void delete_keyed_int(INTVAL key)>
Deletes the key C<*key> from the hash.
=cut
*/
void delete_keyed(PMC* key) {
PMC *item, *next;
next = key_next(INTERP, key);
if (PObj_get_FLAGS(key) & KEY_integer_FLAG) {
if (next) {
item = SELF.get_pmc_keyed_int(key_integer(INTERP, key));
VTABLE_delete_keyed(INTERP, item, next);
return;
}
SELF.delete_keyed_int(key_integer(INTERP, key));
}
else {
if (next) {
item = DYNSELF.get_pmc_keyed_str(key_string(INTERP, key));
VTABLE_delete_keyed(INTERP, item, next);
return;
}
SELF.delete_keyed_str(key_string(INTERP, key));
}
}
void delete_keyed_int(INTVAL idx) {
Hash *h = PMC_struct_val(SELF);
INTVAL n;
HashBucket *b;
n = h->entries;
if (idx < 0)
idx += n;
if (idx < 0 || idx >= n) {
return;
}
b = h->bs + idx;
if (b)
b->key = NULL;
}
void delete_keyed_str(STRING* key) {
Hash *h = PMC_struct_val(SELF);
HashBucket *b;
b = parrot_hash_get_bucket(INTERP, h, key);
if (b)
b->key = NULL;
}
/*
=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
*/
PMC* clone() {
PMC *dest;
Hash *hash = PMC_struct_val(SELF), *h_dest;
UINTVAL i;
HashBucket *b;
void *key;
void *valtmp;
dest = pmc_new_noinit(INTERP, SELF->vtable->base_type);
parrot_new_pmc_hash_x(INTERP, dest, hash->entry_type,
hash->key_type, hash->compare, hash->hash_val);
h_dest = PMC_struct_val(dest);
for (i = 0; i <= hash->mask; i++) {
b = hash->bs + i;
key = b->key;
if (!key)
continue;
valtmp = VTABLE_clone(INTERP, (PMC*)b->value);
parrot_hash_put(INTERP, h_dest, key, valtmp);
}
return dest;
}
/*
=item C<void visit(visit_info *info)>
Used during archiving to visit the elements in the hash.
=item C<void freeze(visit_info *info)>
Used to archive the hash.
=item C<void thaw(visit_info *info)>
Used to unarchive the hash.
Freeze/thaw are inherited from hash, onyl thaw.visit is special, as
we have to preserver key/value order.
=cut
*/
void visit(visit_info *info) {
UINTVAL i;
HashBucket *b;
void *key;
IMAGE_IO *io = info->image_io;
Hash *hash = (Hash *)PMC_struct_val(SELF);
info->container = SELF;
switch (info->what) {
case VISIT_THAW_NORMAL:
case VISIT_THAW_CONSTANTS:
SUPER(info);
break;
case VISIT_FREEZE_NORMAL:
case VISIT_FREEZE_AT_DESTRUCT:
for (i = 0; i <= hash->mask; i++) {
b = hash->bs + i;
key = b->key;
if (!key)
continue;
io->vtable->push_string(interpreter, io, key);
(info->visit_pmc_now)(interpreter, b->value, info);
}
break;
default:
real_exception(interpreter, NULL, E_Exception,
"unhandled visit action (%d)",
info->what);
}
}
}
/*
=back
=head1 SEE ALSO
F<docs/pdds/pdd08_keys.pod>.
=head1 HISTORY
Initial rev by leo 2003-08-21.
=cut
*/
/*
* Local variables:
* c-indentation-style: bsd
* c-basic-offset: 4
* indent-tabs-mode: nil
* End:
*
* vim: expandtab shiftwidth=4:
*/
Jump to Line
Something went wrong with that request. Please try again.