Ancient

 view release on metacpan or  search on metacpan

xs/heap/heap.c  view on Meta::CPAN

            return (NumericHeap*)mg->mg_ptr;
        }
        mg = mg->mg_moremagic;
    }
    return NULL;
}

/* ============================================
   PART 1: RAW ARRAY API (fastest)
   Operates directly on Perl arrays
   ============================================ */

/* Sift up for raw array - min heap */
static void raw_sift_up_min(pTHX_ AV *av, IV idx) {
    SV **arr = AvARRAY(av);
    SV *val = arr[idx];
    NV val_nv = SvNV(val);

    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        NV parent_nv = SvNV(arr[parent]);
        if (val_nv < parent_nv) {
            arr[idx] = arr[parent];
            idx = parent;
        } else {
            break;
        }
    }
    arr[idx] = val;
}

/* Sift up for raw array - max heap */
static void raw_sift_up_max(pTHX_ AV *av, IV idx) {
    SV **arr = AvARRAY(av);
    SV *val = arr[idx];
    NV val_nv = SvNV(val);

    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        NV parent_nv = SvNV(arr[parent]);
        if (val_nv > parent_nv) {
            arr[idx] = arr[parent];
            idx = parent;
        } else {
            break;
        }
    }
    arr[idx] = val;
}

/* Sift down for raw array - min heap */
static void raw_sift_down_min(pTHX_ AV *av, IV idx, IV size) {
    SV **arr = AvARRAY(av);
    SV *val = arr[idx];
    NV val_nv = SvNV(val);
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = SvNV(arr[left]);

        if (right < size) {
            NV right_nv = SvNV(arr[right]);
            if (right_nv < best_nv) {
                best = right;
                best_nv = right_nv;
            }
        }

        if (best_nv < val_nv) {
            arr[idx] = arr[best];
            idx = best;
        } else {
            break;
        }
    }
    arr[idx] = val;
}

/* Sift down for raw array - max heap */
static void raw_sift_down_max(pTHX_ AV *av, IV idx, IV size) {
    SV **arr = AvARRAY(av);
    SV *val = arr[idx];
    NV val_nv = SvNV(val);
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = SvNV(arr[left]);

        if (right < size) {
            NV right_nv = SvNV(arr[right]);
            if (right_nv > best_nv) {
                best = right;
                best_nv = right_nv;
            }
        }

        if (best_nv > val_nv) {
            arr[idx] = arr[best];
            idx = best;
        } else {
            break;
        }
    }
    arr[idx] = val;
}

/* push_heap_min(\@array, $value) */
XS_EXTERNAL(XS_push_heap_min) {
    dXSARGS;
    AV *av;
    SV *val;
    IV size;

    if (items != 2) croak("Usage: push_heap_min(\\@array, $value)");
    if (!SvROK(ST(0)) || SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
        croak("First argument must be an array reference");
    }

    av = (AV*)SvRV(ST(0));
    val = newSVsv(ST(1));

    av_push(av, val);
    size = av_len(av) + 1;
    raw_sift_up_min(aTHX_ av, size - 1);

    XSRETURN_EMPTY;
}

/* push_heap_max(\@array, $value) */
XS_EXTERNAL(XS_push_heap_max) {
    dXSARGS;
    AV *av;
    SV *val;
    IV size;

    if (items != 2) croak("Usage: push_heap_max(\\@array, $value)");
    if (!SvROK(ST(0)) || SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
        croak("First argument must be an array reference");
    }

    av = (AV*)SvRV(ST(0));
    val = newSVsv(ST(1));

    av_push(av, val);
    size = av_len(av) + 1;
    raw_sift_up_max(aTHX_ av, size - 1);

    XSRETURN_EMPTY;
}

/* pop_heap_min(\@array) */
XS_EXTERNAL(XS_pop_heap_min) {
    dXSARGS;
    AV *av;
    IV size;
    SV *result;
    SV **arr;

    if (items != 1) croak("Usage: pop_heap_min(\\@array)");

xs/heap/heap.c  view on Meta::CPAN

    XSRETURN_EMPTY;
}

/* ============================================
   PART 2: NUMERIC HEAP (stores NV directly)
   ============================================ */

static void nv_ensure_capacity(NumericHeap *h, IV needed) {
    if (needed > h->capacity) {
        IV new_cap = h->capacity ? h->capacity * 2 : 16;
        while (new_cap < needed) new_cap *= 2;
        Renew(h->data, new_cap, NV);
        h->capacity = new_cap;
    }
}

/* Sift up for NV min-heap */
static void nv_sift_up_min(NumericHeap *h, IV idx) {
    NV *data = h->data;
    NV val = data[idx];

    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        if (val < data[parent]) {
            data[idx] = data[parent];
            idx = parent;
        } else {
            break;
        }
    }
    data[idx] = val;
}

/* Sift up for NV max-heap */
static void nv_sift_up_max(NumericHeap *h, IV idx) {
    NV *data = h->data;
    NV val = data[idx];

    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        if (val > data[parent]) {
            data[idx] = data[parent];
            idx = parent;
        } else {
            break;
        }
    }
    data[idx] = val;
}

/* Sift down for NV min-heap */
static void nv_sift_down_min(NumericHeap *h, IV idx) {
    NV *data = h->data;
    IV size = h->size;
    NV val = data[idx];
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = data[left];

        if (right < size && data[right] < best_nv) {
            best = right;
            best_nv = data[right];
        }

        if (best_nv < val) {
            data[idx] = data[best];
            idx = best;
        } else {
            break;
        }
    }
    data[idx] = val;
}

/* Sift down for NV max-heap */
static void nv_sift_down_max(NumericHeap *h, IV idx) {
    NV *data = h->data;
    IV size = h->size;
    NV val = data[idx];
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = data[left];

        if (right < size && data[right] > best_nv) {
            best = right;
            best_nv = data[right];
        }

        if (best_nv > val) {
            data[idx] = data[best];
            idx = best;
        } else {
            break;
        }
    }
    data[idx] = val;
}

static int numeric_heap_free(pTHX_ SV *sv, MAGIC *mg) {
    NumericHeap *h = (NumericHeap*)mg->mg_ptr;
    PERL_UNUSED_ARG(sv);
    if (h->data) Safefree(h->data);
    Safefree(h);
    return 0;
}

/* heap::new_nv($type) - create numeric heap */
XS_EXTERNAL(XS_heap_new_nv) {
    dXSARGS;
    NumericHeap *h;
    SV *obj_sv, *rv;
    HV *stash;
    HeapType type = HEAP_MIN;
    int arg_offset = 0;

    if (items >= 1 && SvPOK(ST(0))) {
        STRLEN len;
        const char *str = SvPV(ST(0), len);
        if (len == 4 && strEQ(str, "heap")) {
            arg_offset = 1;
        } else if (len == 3 && (strEQ(str, "min") || strEQ(str, "max"))) {
            arg_offset = 0;
        } else {
            arg_offset = 1;
        }
    }

    if (items > arg_offset) {
        STRLEN len;
        const char *type_str = SvPV(ST(arg_offset), len);
        if (len == 3 && strEQ(type_str, "max")) {
            type = HEAP_MAX;
        }
    }

    Newxz(h, 1, NumericHeap);
    h->type = type;
    h->size = 0;
    h->capacity = 16;
    Newx(h->data, 16, NV);

    obj_sv = newSV(0);
    sv_magicext(obj_sv, NULL, PERL_MAGIC_ext, &numeric_heap_vtbl, (char*)h, 0);

    rv = newRV_noinc(obj_sv);
    stash = gv_stashpvn("heap::nv", 8, GV_ADD);
    sv_bless(rv, stash);

    ST(0) = sv_2mortal(rv);
    XSRETURN(1);
}

xs/heap/heap.c  view on Meta::CPAN

}

/* ============================================
   PART 3: STANDARD HEAP (original OO API)
   ============================================ */

static void heap_ensure_capacity(Heap *h, IV needed) {
    if (needed > h->capacity) {
        IV new_cap = h->capacity ? h->capacity * 2 : 16;
        while (new_cap < needed) new_cap *= 2;
        Renew(h->data, new_cap, SV*);
        h->capacity = new_cap;
    }
}

/* Sift functions for standard heap */
static void heap_sift_up_min(Heap *h, IV idx) {
    SV **data = h->data;
    SV *val = data[idx];
    NV val_nv = SvNV(val);

    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        if (val_nv < SvNV(data[parent])) {
            data[idx] = data[parent];
            idx = parent;
        } else {
            break;
        }
    }
    data[idx] = val;
}

static void heap_sift_up_max(Heap *h, IV idx) {
    SV **data = h->data;
    SV *val = data[idx];
    NV val_nv = SvNV(val);

    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        if (val_nv > SvNV(data[parent])) {
            data[idx] = data[parent];
            idx = parent;
        } else {
            break;
        }
    }
    data[idx] = val;
}

static void heap_sift_down_min(Heap *h, IV idx) {
    SV **data = h->data;
    IV size = h->size;
    SV *val = data[idx];
    NV val_nv = SvNV(val);
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = SvNV(data[left]);

        if (right < size) {
            NV right_nv = SvNV(data[right]);
            if (right_nv < best_nv) {
                best = right;
                best_nv = right_nv;
            }
        }

        if (best_nv < val_nv) {
            data[idx] = data[best];
            idx = best;
        } else {
            break;
        }
    }
    data[idx] = val;
}

static void heap_sift_down_max(Heap *h, IV idx) {
    SV **data = h->data;
    IV size = h->size;
    SV *val = data[idx];
    NV val_nv = SvNV(val);
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = SvNV(data[left]);

        if (right < size) {
            NV right_nv = SvNV(data[right]);
            if (right_nv > best_nv) {
                best = right;
                best_nv = right_nv;
            }
        }

        if (best_nv > val_nv) {
            data[idx] = data[best];
            idx = best;
        } else {
            break;
        }
    }
    data[idx] = val;
}

/* Custom comparator sift operations */
static bool heap_compare_custom(pTHX_ Heap *h, SV *a, SV *b) {
    dSP;
    IV result;
    int count;

    ENTER; SAVETMPS;
    PUSHMARK(SP);
    XPUSHs(a);
    XPUSHs(b);
    PUTBACK;

    count = call_sv(h->comparator, G_SCALAR);

    SPAGAIN;
    if (count != 1) croak("Comparator must return exactly one value");
    result = POPi;
    PUTBACK;
    FREETMPS; LEAVE;

    return h->type == HEAP_MIN ? result < 0 : result > 0;
}

static void heap_sift_up_custom(pTHX_ Heap *h, IV idx) {
    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        if (heap_compare_custom(aTHX_ h, h->data[idx], h->data[parent])) {
            SV *tmp = h->data[idx];
            h->data[idx] = h->data[parent];
            h->data[parent] = tmp;
            idx = parent;
        } else {
            break;
        }
    }
}

static void heap_sift_down_custom(pTHX_ Heap *h, IV idx) {
    while (1) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = idx;

        if (left < h->size && heap_compare_custom(aTHX_ h, h->data[left], h->data[best])) {
            best = left;
        }
        if (right < h->size && heap_compare_custom(aTHX_ h, h->data[right], h->data[best])) {
            best = right;
        }

        if (best != idx) {
            SV *tmp = h->data[idx];
            h->data[idx] = h->data[best];
            h->data[best] = tmp;
            idx = best;
        } else {
            break;
        }
    }
}

static void heap_sift_up(pTHX_ Heap *h, IV idx) {
    if (h->comparator) {
        heap_sift_up_custom(aTHX_ h, idx);
    } else if (h->type == HEAP_MIN) {
        heap_sift_up_min(h, idx);
    } else {
        heap_sift_up_max(h, idx);
    }
}

static void heap_sift_down(pTHX_ Heap *h, IV idx) {
    if (h->comparator) {
        heap_sift_down_custom(aTHX_ h, idx);
    } else if (h->type == HEAP_MIN) {
        heap_sift_down_min(h, idx);
    } else {
        heap_sift_down_max(h, idx);
    }
}

static int heap_free(pTHX_ SV *sv, MAGIC *mg) {
    Heap *h = (Heap*)mg->mg_ptr;
    IV i;
    PERL_UNUSED_ARG(sv);

    for (i = 0; i < h->size; i++) {
        if (h->data[i]) SvREFCNT_dec(h->data[i]);
    }
    if (h->comparator) SvREFCNT_dec(h->comparator);
    if (h->data) Safefree(h->data);
    Safefree(h);
    return 0;
}

/* Custom OP implementations - handle both regular and numeric heaps */
static OP* pp_heap_push(pTHX) {
    dSP;
    SV *val_sv = POPs;
    SV *heap_sv = TOPs;

    /* Check for numeric heap first */
    NumericHeap *nh = try_get_numeric_heap(aTHX_ heap_sv);
    if (nh) {
        NV val = SvNV(val_sv);
        nv_ensure_capacity(nh, nh->size + 1);
        nh->data[nh->size] = val;
        nh->size++;
        if (nh->type == HEAP_MIN) {
            nv_sift_up_min(nh, nh->size - 1);
        } else {
            nv_sift_up_max(nh, nh->size - 1);
        }
        RETURN;
    }