Heap-Simple-XS
view release on metacpan or search on metacpan
NV k;
int val_copied;
if (MAGIC && SvGMAGICAL(value)) {
value = MORTALCOPY(value);
val_copied = 1;
} else val_copied = 0;
/* SvNV will handle get magic (though sv_2nv) */
if (h->order == LESS) k = SvNV(key);
else if (h->order == MORE) k = -SvNV(key);
else croak("No fast %s order", order_name(h));
FKEY(NV, h, h->used) = k;
if (h->has_values)
h->values[h->used] =
val_copied ? SvREFCNT_inc(value) : newSVsv(value);
} else {
int val_copied, key_copied;
if (MAGIC && SvGMAGICAL(value)) {
value = MORTALCOPY(value);
val_copied = 1;
} else val_copied = 0;
if (MAGIC && SvGMAGICAL(key)) {
key = MORTALCOPY(key);
key_copied = 1;
} else key_copied = 0;
h->values[h->used] =
val_copied ? SvREFCNT_inc(value) : newSVsv(value);
/* Assume newSVsv can't die since key will already
have been (mortal)copied in case it's magic */
h->keys[h->used] = key_copied ?
SvREFCNT_inc(key) : newSVsv(key);
}
h->used++;
}
multi_insert(aTHX_ h, first);
}
for (; i<items; i++) {
pair = ST(i);
if (MAGIC) SvGETMAGIC(pair);
if (!SvROK(pair)) croak("pair is not a reference");
av = (AV*) SvRV(pair);
if (SvTYPE(av) != SVt_PVAV) croak("pair is not an ARRAY reference");
key_ref = av_fetch(av, 0, 0);
if (!key_ref) croak("No key in the element array");
val_ref = av_fetch(av, 1, 0);
if (!val_ref) croak("No value in the element array");
key_insert(aTHX_ h, *key_ref, *val_ref);
}
XSRETURN_EMPTY;
void
extract_top(heap h)
ALIAS:
Heap::Simple::XS::extract_min = 1
Heap::Simple::XS::extract_first = 2
PPCODE:
if (h->used <= 2) {
if (h->used < 2) {
if (ix != 2) croak("Empty heap");
XSRETURN_EMPTY;
}
if (h->locked) croak("recursive heap change");
SAVEINT(h->locked);
h->locked = 1;
--h->used;
if (h->wrapped && !h->fast) SvREFCNT_dec(h->keys[h->used]);
if (h->has_values) PUSHs(sv_2mortal(h->values[h->used]));
else if (h->order == LESS) XSRETURN_NV( FKEY(NV, h, 1));
else if (h->order == MORE) XSRETURN_NV(-FKEY(NV, h, 1));
else croak("No fast %s order", order_name(h));
} else {
PUTBACK;
if (h->locked) croak("recursive heap change");
SAVEINT(h->locked);
h->locked = 1;
PUSHs(sv_2mortal(extract_top(aTHX_ h)));
}
void
extract_upto(heap h, SV *border)
PPCODE:
/* special case, avoid uneeded access to border */
if (h->used < 2) return;
if (h->locked) croak("recursive heap change");
SAVEINT(h->locked);
h->locked = 1;
if (h->fast) {
NV b;
if (h->order == LESS) b = SvNV(border);
else if (h->order == MORE) b = -SvNV(border);
else croak("No fast %s order", order_name(h));
while (FKEY(NV, h, 1) <= b) {
/* No PUTBACK/SPAGAIN needed since fast extract top
won't change the stack */
XPUSHs(sv_2mortal(extract_top(aTHX_ h)));
if (h->used < 2) break;
}
} else {
if (MAGIC && SvGMAGICAL(border)) border = MORTALCOPY(border);
while (1) {
SV *top;
PUTBACK;
if (less(aTHX_ h, border, KEY(h, 1))) {
SPAGAIN;
break;
}
top = extract_top(aTHX_ h);
SPAGAIN;
XPUSHs(sv_2mortal(top));
if (h->used < 2) break;
}
}
if ((h->used+4)*4 < h->allocated) extend(h, 0); /* shrink really */
void
extract_all(heap h)
PPCODE:
if (h->locked) croak("recursive heap change");
SAVEINT(h->locked);
h->locked = 1;
/* Extends one too much. Who cares... */
EXTEND(SP, h->used);
EXTEND_MORTAL(h->used);
if (h->fast) {
/* No PUTBACK/SPAGAIN needed since fast extract top
won't change the stack */
while (h->used > 1) XPUSHs(sv_2mortal(extract_top(aTHX_ h)));
} else while (h->used > 1) {
SV *top;
PUTBACK;
top = extract_top(aTHX_ h);
SPAGAIN;
XPUSHs(sv_2mortal(top));
}
if ((1+4)*4 < h->allocated) extend(h, 0); /* shrink really */
void
top(heap h)
ALIAS:
Heap::Simple::XS::first = 1
PPCODE:
if (h->used < 2) {
if (ix != 1) croak("Empty heap");
XSRETURN_EMPTY;
}
if (h->has_values) PUSHs(sv_2mortal(SvREFCNT_inc(h->values[1])));
else if (h->order == LESS) XSRETURN_NV( FKEY(NV, h, 1));
else if (h->order == MORE) XSRETURN_NV(-FKEY(NV, h, 1));
else croak("No fast %s order", order_name(h));
void
top_key(heap h)
ALIAS:
Heap::Simple::XS::min_key = 1
Heap::Simple::XS::first_key = 2
PPCODE:
if (h->used < 2) {
if (ix == 2) XSRETURN_EMPTY;
if (!h->infinity || !SvOK(h->infinity)) croak("Empty heap");
PUSHs(sv_2mortal(SvREFCNT_inc(h->infinity)));
} else if (h->fast) {
if (h->order== LESS) XSRETURN_NV( FKEY(NV, h, 1));
else if (h->order== MORE) XSRETURN_NV(-FKEY(NV, h, 1));
else croak("No fast %s order", order_name(h));
} else PUSHs(sv_2mortal(SvREFCNT_inc(KEY(h, 1))));
void
keys(heap h)
PREINIT:
/* you can actally modify the values through the return */
size_t i;
SV *key;
PPCODE:
/* Extends one too much. Who cares... */
EXTEND(SP, h->used);
EXTEND_MORTAL(h->used);
if (h->fast) {
if (h->order == LESS) for (i=1; i<h->used; i++)
PUSHs(sv_2mortal(newSVnv( FKEY(NV, h, i))));
else if (h->order == MORE) for (i=1; i<h->used; i++)
PUSHs(sv_2mortal(newSVnv(-FKEY(NV, h, i))));
else croak("No fast %s order", order_name(h));
} else {
for (i=1; i<h->used; i++) {
PUTBACK;
key = KEY(h, i);
SPAGAIN;
PUSHs(sv_2mortal(SvREFCNT_inc(key)));
}
}
void
values(heap h)
PREINIT:
/* you can actally modify the values through the return */
size_t i;
PPCODE:
/* Extends one too much. Who cares... */
EXTEND(SP, h->used);
EXTEND_MORTAL(h->used);
if (h->has_values) for (i=1; i<h->used; i++)
PUSHs(sv_2mortal(SvREFCNT_inc(h->values[i])));
else if (h->order == LESS) for (i=1; i<h->used; i++)
PUSHs(sv_2mortal(newSVnv( FKEY(NV, h, i))));
else if (h->order == MORE) for (i=1; i<h->used; i++)
PUSHs(sv_2mortal(newSVnv(-FKEY(NV, h, i))));
else croak("No fast %s order", order_name(h));
void
clear(heap h)
PREINIT:
SV *key, *value;
PPCODE:
if (h->locked) croak("recursive heap change");
SAVEINT(h->locked);
h->locked = 1;
if (h->fast || !h->wrapped) {
if (h->has_values)
while (h->used > 1) SvREFCNT_dec(h->values[--h->used]);
else h->used = 1;
} else {
while (h->used > 1) {
--h->used;
value = h->values[h->used];
key = h->keys [h->used];
SvREFCNT_dec(key);
SvREFCNT_dec(value);
}
}
if ((1+4)*4 < h->allocated) extend(h, 0); /* shrink really */
SV *
key(heap h, SV *value)
CODE:
if (h->fast) {
RETVAL = newSVnv(SvNV(fetch_key(aTHX_ h, value)));
} else {
RETVAL = SvREFCNT_inc(fetch_key(aTHX_ h, value));
}
OUTPUT:
RETVAL
void
_absorb(SV * heap1, SV *heap2)
PREINIT:
int copied2, one_by_one;
SV *heap1_ref, *value;
heap h1, h2;
PPCODE:
/* Helper for absorb, puts h1 into h2 */
h1 = C_HEAP(heap1, "heap1");
/* Keep argument alive for the duration */
heap1_ref = SvRV(heap1);
sv_2mortal(SvREFCNT_inc(heap1_ref));
if (h1->locked) croak("recursive heap change");
SAVEINT(h1->locked);
h1->locked = 1;
if (h1->used < 2) XSRETURN_EMPTY;
if (MAGIC && SvMAGICAL(heap2)) {
heap2 = MORTALCOPY(heap2);
copied2 = 1;
} else copied2 = 0;
/* If we are an XS heap, the argument (h2) probably is too */
h2 = TRY_C_HEAP(heap2);
if (h2) {
size_t more, first;
if (h1 == h2) croak("Self absorption");
PUTBACK;
/* Keep argument alive for the duration */
/* heap2 is now the object, not the object pointer */
if (!copied2) sv_2mortal(SvREFCNT_inc(heap2));
more = h1->used-1;
if (h2->used-1+more > h2->max_count)
more = h2->max_count-(h2->used-1);
if (more <= 1) one_by_one = 1;
else one_by_one = h2->can_die;
if (!one_by_one) {
SV *key;
if (h2->locked) croak("recursive heap change");
SAVEINT(h2->locked);
h2->locked = 1;
first = h2->used;
if (first+more > h2->allocated) extend(h2, more);
if (h2->fast) {
NV k;
while (more--) {
if (h1->has_values) value = h1->values[h1->used-1];
else if (h1->order == LESS)
value = newSVnv(FKEY(NV, h1, h1->used-1));
else if (h1->order == MORE)
value = newSVnv(-FKEY(NV, h1, h1->used-1));
else croak("No fast %s order", order_name(h1));
if (h2->has_values) h2->values[h2->used] = value;
else sv_2mortal(value);
h2->used++;
h1->used--;
if (h1->wrapped && !h1->fast)
SvREFCNT_dec(h1->keys[h1->used]);
key = fetch_key(aTHX_ h2, value);
/* SvNV will handle get magic (though sv_2nv) */
PUSHs(value);
PUTBACK;
count = call_method("insert", G_VOID);
SPAGAIN;
if (count) {
if (count < 0) croak("Forced void context call 'insert' succeeded in returning %d values. This is impossible", (int) count);
SP -= count;
}
h1->used--;
if (h1->has_values) SvREFCNT_dec(value);
if (h1->wrapped && !h1->fast) SvREFCNT_dec(h1->keys[h1->used]);
if ((h1->used+4)*4 < h1->allocated) extend(h1, 0); /* shrink really */
FREETMPS;
}
LEAVE;
} else {
size_t i;
EXTEND(SP, h1->used);
if (!h1->has_values) EXTEND_MORTAL(h1->used);
PUSHMARK(SP);
PUSHs(heap2);
for (i=1; i<h1->used; i++) {
if (h1->has_values) value = h1->values[i];
else {
if (h1->order == LESS)
value = newSVnv(FKEY(NV, h1, i));
else if (h1->order == MORE)
value = newSVnv(-FKEY(NV, h1, i));
else croak("No fast %s order", order_name(h1));
sv_2mortal(value);
}
PUSHs(value);
}
PUTBACK;
count = call_method("insert", G_VOID);
SPAGAIN;
if (count) {
if (count < 0) croak("Forced void context call 'insert' succeeded in returning %d values. This is impossible", (int) count);
SP -= count;
}
while (h1->used > 1) {
h1->used--;
if (h1->has_values) SvREFCNT_dec(h1->values[h1->used]);
if (h1->wrapped && !h1->fast) SvREFCNT_dec(h1->keys[h1->used]);
}
if ((h1->used+4)*4 < h1->allocated) extend(h1, 0); /* shrink really */
}
}
void
_key_absorb(SV * heap1, SV *heap2)
PREINIT:
int copied2;
SV *heap1_ref, *key, *value;
heap h1, h2;
int one_by_one;
PPCODE:
/* Helper for absorb, puts h1 into h2 */
h1 = C_HEAP(heap1, "heap1");
/* Keep arguments alive for the duration */
heap1_ref = SvRV(heap1);
sv_2mortal(SvREFCNT_inc(heap1_ref));
if (h1->locked) croak("recursive heap change");
SAVEINT(h1->locked);
h1->locked = 1;
if (h1->used < 2) XSRETURN_EMPTY;
if (MAGIC && SvMAGICAL(heap2)) {
heap2 = MORTALCOPY(heap2);
copied2 = 1;
} else copied2 = 0;
/* If we are an XS heap, the argument probably is too */
h2 = TRY_C_HEAP(heap2);
if (h2) {
size_t more, first;
if (h1 == h2) croak("Self absorption");
if (!h2->key_ops) croak("This heap type does not support key_insert");
PUTBACK;
/* Keep arguments alive for the duration */
/* heap2 is now the object, not the object pointer */
if (!copied2) sv_2mortal(SvREFCNT_inc(heap2));
more = h1->used-1;
if (h2->used-1+more > h2->max_count)
more = h2->max_count-(h2->used-1);
if (more <= 1) one_by_one = 1;
else one_by_one = h2->can_die;
if (!one_by_one) {
SV *key;
if (h2->locked) croak("recursive heap change");
SAVEINT(h2->locked);
h2->locked = 1;
first = h2->used;
if (first+more > h2->allocated) extend(h2, more);
if (h2->fast) {
NV k;
while (more--) {
if (!h1->fast) k = SvNV(KEY(h1, h1->used-1));
else if (h1->order== LESS)
k = FKEY(NV, h1, h1->used-1);
else if (h1->order== MORE)
k = -FKEY(NV, h1, h1->used-1);
else croak("No fast %s order", order_name(h1));
if (h2->order == LESS) FKEY(NV, h2, h2->used-1) = k;
else if (h2->order == MORE) FKEY(NV, h2, h2->used-1) = -k;
else croak("No fast %s order", order_name(h2));
if (h2->has_values) {
if (h1->has_values) value = h1->values[h1->used-1];
else if (h1->order == LESS)
SPAGAIN;
if (count) {
if (count < 0) croak("Forced void context call 'key_insert' succeeded in returning %d values. This is impossible", (int) count);
SP -= count;
}
while (h1->used > 1) {
h1->used--;
if (h1->has_values) SvREFCNT_dec(h1->values[h1->used]);
if (h1->wrapped && !h1->fast) SvREFCNT_dec(KEY(h1, h1->used));
}
if ((h1->used+4)*4 < h1->allocated) extend(h1, 0); /* shrink really */
}
}
void
absorb(SV *heap, ...)
PREINIT:
I32 count, i;
SV *heap2;
CODE:
for (i=1; i<items; i++) {
heap2 = ST(i);
if (MAGIC && SvMAGICAL(heap2)) heap2 = MORTALCOPY(heap2);
PUSHMARK(SP);
XPUSHs(heap2);
XPUSHs(heap);
PUTBACK;
count = call_method("_absorb", G_VOID);
/* Needed or the stack will remember and return the stuff we pushed */
SPAGAIN;
if (count) {
if (count < 0) croak("Forced void context call '_absorb' succeeded in returning %d values. This is impossible", (int) count);
SP -= count;
}
}
void
key_absorb(SV *heap, ...)
PREINIT:
I32 count, i;
SV *heap2;
CODE:
for (i=1; i<items; i++) {
heap2 = ST(i);
if (MAGIC && SvMAGICAL(heap2)) heap2 = MORTALCOPY(heap2);
PUSHMARK(SP);
XPUSHs(heap2);
XPUSHs(heap);
PUTBACK;
count = call_method("_key_absorb", G_VOID);
/* Needed or the stack will remember and return the stuff we pushed */
SPAGAIN;
if (count) {
if (count < 0) croak("Forced void context call '_key_absorb' succeeded in returning %d values. This is impossible", (int) count);
SP -= count;
}
}
void
infinity(heap h, SV *new_infinity=0)
PPCODE:
if (GIMME_V != G_VOID)
XPUSHs(h->infinity ?
sv_2mortal(SvREFCNT_inc(h->infinity)) : &PL_sv_undef);
if (new_infinity) {
if (h->infinity) sv_2mortal(h->infinity);
h->infinity = newSVsv(new_infinity);
}
IV
key_index(heap h)
CODE:
if (h->elements != ARRAY) croak("Heap elements are not of type 'Array'");
RETVAL = h->aindex;
OUTPUT:
RETVAL
SV *
key_name(heap h)
CODE:
if (h->elements != HASH) croak("Heap elements are not of type 'Hash'");
/* Make a copy instead of returning an lvalue
so that the cached aindex remains valid */
RETVAL = newSVsv(h->hkey);
OUTPUT:
RETVAL
SV *
key_method(heap h)
CODE:
if (h->elements != METHOD && h->elements != OBJECT)
croak("Heap elements are not of type 'Method' or 'Object'");
RETVAL = SvREFCNT_inc(h->hkey);
OUTPUT:
RETVAL
SV *
key_function(heap h)
CODE:
if (h->elements != FUNCTION && h->elements != ANY_ELEM)
croak("Heap elements are not of type 'Function' or 'Any'");
RETVAL = SvREFCNT_inc(h->hkey);
OUTPUT:
RETVAL
void
user_data(heap h, SV *new_user_data=0)
PPCODE:
if (GIMME_V != G_VOID)
PUSHs(h->user_data ? h->user_data : &PL_sv_undef);
if (new_user_data) {
if (h->user_data) sv_2mortal(h->user_data);
h->user_data = newSVsv(new_user_data);
}
void
order(heap h)
PPCODE:
PUSHs(h->order == CODE_ORDER ?
h->order_sv : sv_2mortal(newSVpv(order_name(h), 0)));
void
elements(heap h)
PPCODE:
XPUSHs(sv_2mortal(newSVpv(elements_name(h), 0)));
if (GIMME_V == G_ARRAY) switch(h->elements) {
case SCALAR:
break;
case ARRAY:
XPUSHs(sv_2mortal(newSViv(h->aindex)));
break;
case HASH:
case METHOD:
case OBJECT:
case FUNCTION:
case ANY_ELEM:
if (h->hkey) XPUSHs(sv_2mortal(newSVsv(h->hkey)));
break;
default:
croak("Assertion: unhandled element type %s", elements_name(h));
}
void
wrapped(heap h)
PPCODE:
if (h->key_ops) XSRETURN_YES;
if (GIMME_V == G_SCALAR) XSRETURN_NO;
XSRETURN_EMPTY;
void
dirty(heap h)
PPCODE:
if (h->dirty) XSRETURN_YES;
if (GIMME_V == G_SCALAR) XSRETURN_NO;
XSRETURN_EMPTY;
void
can_die(heap h)
PPCODE:
/* ->fast types are wrapped too really */
if (h->can_die) XSRETURN_YES;
if (GIMME_V == G_SCALAR) XSRETURN_NO;
XSRETURN_EMPTY;
void
max_count(heap h)
PPCODE:
if (h->max_count == MAX_SIZE) XSRETURN_NV(INFINITY);
XSRETURN_UV(h->max_count);
void
merge_arrays(heap h, ...)
PREINIT:
I32 i, j;
size_t l, filled, left, k0, k1, k2;
SV *value, **ptr, *key;
AV *av, *work_av;
merge *work_heap, here;
fast_merge *fast_work_heap, fast_here;
CODE:
filled = left = 0;
for (i=1; i<items; i++) {
value = ST(i);
if (MAGIC) SvGETMAGIC(value);
if (!SvROK(value))
croak("argument %u is not a reference", (unsigned int) i-1);
work_av = (AV*) SvRV(value);
if (MAGIC) SvGETMAGIC((SV *) work_av);
if (SvTYPE(work_av) != SVt_PVAV)
croak("argument %u is not an array reference", (unsigned int) i-1);
j = av_len(work_av);
if (j < 0) continue;
filled++;
left += j+1;
av = work_av;
}
work_av = newAV();
value = newRV_noinc((SV *) work_av);
ST(0) = sv_2mortal(value);
k2 = left;
if (h->max_count != MAX_SIZE && h->max_count < left)
left = h->max_count;
av_extend(work_av, (I32) left - 1);
switch(filled) {
case 0: break;
case 1:
for (k0= k2-left, k1=0; k1 < left; k0++, k1++) {
ptr = av_fetch(av, k0, 0);
if (ptr) {
value = newSVsv(*ptr);
if (!av_store(work_av, k1, value)) {
SvREFCNT_dec(value);
croak("Assertion: Could not store value");
}
}
}
break;
default:
if (h->fast) {
if (h->max_count < filled) {
filled = h->max_count;
New(__LINE__ % 1000, fast_work_heap, filled+1, struct fast_merge);
SAVEFREEPV(fast_work_heap);
k1 = 0;
ptr = av_fetch(av, j, 0);
if (ptr) {
value = newSVsv(*ptr);
--left;
if (!av_store(work_av, left, value)) {
SvREFCNT_dec(value);
croak("Assertion: Could not store value");
}
}
if (left == 0) break;
j--;
if (j >= 0) {
ptr = av_fetch(av, j, 0);
here.key = fetch_key(aTHX_ h, ptr ? *ptr : &PL_sv_undef);
here.array = av;
here.index = j;
} else {
here = work_heap[filled--];
if (filled <= 1) {
av = here.array;
for (j = here.index; j >= 0; j--) {
--left;
ptr = av_fetch(av, j, 0);
if (ptr) {
value = newSVsv(*ptr);
if (!av_store(work_av, left, value)) {
SvREFCNT_dec(value);
croak("Assertion: Could not store value");
}
}
if (left == 0) break;
}
if (left) croak("Not enough values the second time round");
break;
}
}
l = 2;
while (l < filled) {
if (less(aTHX_ h, here.key, work_heap[l].key)) {
if (less(aTHX_ h, work_heap[l].key, work_heap[l+1].key)) l++;
} else if (less(aTHX_ h, here.key, work_heap[l+1].key)) l++;
else break;
work_heap[l/2] = work_heap[l];
l *= 2;
}
if (l == filled && less(aTHX_ h, here.key, work_heap[l].key)) {
work_heap[l/2] = work_heap[l];
l *= 2;
}
work_heap[l/2] = here;
}
}
break;
}
XSRETURN(1);
void
DESTROY(heap h)
PREINIT:
SV *key, *value;
PPCODE:
/* Let's assume the module isn't buggy and it always increases the refcount
on the heap during modification.
That means that the user is explicitely calling DESTROY */
if (h->locked)
croak("Refusing explicit DESTROY call during heap modification");
h->locked = 1;
if (h->fast || !h->wrapped) {
if (h->has_values)
while (h->used > 1) SvREFCNT_dec(h->values[--h->used]);
} else {
while (h->used > 1) {
--h->used;
value = h->values[h->used];
key = h->keys [h->used];
SvREFCNT_dec(key);
SvREFCNT_dec(value);
}
}
if (h->hkey) {
key = h->hkey;
h->hkey = NULL;
SvREFCNT_dec(key);
}
if (h->infinity) {
key = h->infinity;
h->infinity = NULL;
SvREFCNT_dec(key);
}
if (h->user_data) {
key = h->user_data;
h->user_data = NULL;
SvREFCNT_dec(key);
}
if (h->order_sv) {
key = h->order_sv;
h->order_sv = NULL;
SvREFCNT_dec(key);
}
if (h->values) Safefree(h->values);
if (h->keys) Safefree(h->keys);
Safefree(h);
BOOT:
if (MAX_SIZE < 0) croak("signed size_t");
( run in 2.703 seconds using v1.01-cache-2.11-cpan-71847e10f99 )