view release on metacpan or  search on metacpan

sortedset.h  view on Meta::CPAN

}

/* delete (score,member) from subtree nidx (known present); decrement counts;
   return 1 if nidx now underflows (num < SS_MIN) */
static int ss_delete_rec(SsHandle *h, uint32_t nidx, double score, int64_t member) {
    SsNode *nd = &h->nodes[nidx];
    if (nd->is_leaf) {
        int pos = 0;
        while (pos < nd->num && ss_key_cmp(nd->scores[pos], nd->members[pos], score, member) != 0) pos++;
        for (int i = pos; i+1 < nd->num; i++) { nd->scores[i] = nd->scores[i+1]; nd->members[i] = nd->members[i+1]; }
        nd->num--;
        return nd->num < SS_MIN;
    }
    int c = ss_child_index(nd, score, member);
    int under = ss_delete_rec(h, nd->children[c], score, member);
    nd->counts[c]--;
    if (under) ss_fix_underflow(h, nidx, c);
    return nd->num < SS_MIN;
}

static void ss_tree_del(SsHandle *h, double score, int64_t member) {
    SsHeader *hdr = h->hdr;
    ss_delete_rec(h, hdr->root, score, member);
    SsNode *root = &h->nodes[hdr->root];
    if (root->is_leaf) {
        if (root->num == 0) {
            ss_node_free(h, hdr->root);
            hdr->root = SS_NONE; hdr->leftmost = SS_NONE; hdr->rightmost = SS_NONE; hdr->height = 0;
        }
    } else if (root->num == 1) {
        uint32_t child = root->children[0];
        ss_node_free(h, hdr->root);
        hdr->root = child; h->nodes[child].parent = SS_NONE; hdr->height--;
    }
    hdr->count--;
}

/* add: 1 (new), 0 (existing -- score updated if changed), -1 (full) */
static int ss_add_locked(SsHandle *h, int64_t member, double score) {
    double old;
    if (ss_idx_get(h, member, &old)) {
        if (old != score) { ss_tree_del(h, old, member); ss_tree_add(h, score, member); ss_idx_set(h, member, score); }
        return 0;
    }
    if (h->hdr->count >= h->hdr->max_entries) return -1;
    ss_tree_add(h, score, member);
    ss_idx_set(h, member, score);
    return 1;
}

/* remove: 1 if removed, 0 if absent */
static int ss_remove_locked(SsHandle *h, int64_t member) {
    double old;
    if (!ss_idx_get(h, member, &old)) return 0;
    ss_tree_del(h, old, member);
    ss_idx_del(h, member);
    return 1;
}

/* incr by delta. *out = new score. returns 1 (created), 0 (updated), -1 (full),
   -2 (result is NaN) */
static int ss_incr_locked(SsHandle *h, int64_t member, double delta, double *out) {
    double old;
    if (ss_idx_get(h, member, &old)) {
        double ns = old + delta; *out = ns;
        if (ns != ns) return -2;
        if (ns != old) { ss_tree_del(h, old, member); ss_tree_add(h, ns, member); ss_idx_set(h, member, ns); }
        return 0;
    }
    if (h->hdr->count >= h->hdr->max_entries) return -1;
    *out = delta;
    if (delta != delta) return -2;
    ss_tree_add(h, delta, member); ss_idx_set(h, member, delta);
    return 1;
}

/* node indices stored in the mmap (children[], leftmost,
 * rightmost, leaf next/prev, free-list links) are attacker-controlled -- a
 * local peer can write the backing file. Bound every such index against the
 * node pool before using it to dereference h->nodes[]. A predictable
 * never-taken branch for valid data; on a bad index the caller stops/skips
 * instead of trapping. */
static inline int ss_node_ok(const SsHandle *h, uint32_t idx) {
    return idx < h->hdr->node_capacity;
}

/* pop the min (max=0) or max (max=1): 0 if empty, else 1 with *m,*s */
static int ss_pop_locked(SsHandle *h, int max, int64_t *m, double *s) {
    if (h->hdr->root == SS_NONE) return 0;
    uint32_t li = max ? h->hdr->rightmost : h->hdr->leftmost;
    if (!ss_node_ok(h, li)) return 0;                 /* corrupt leftmost/rightmost */
    SsNode *nd = &h->nodes[li];
    int pos = max ? nd->num - 1 : 0;
    *m = nd->members[pos]; *s = nd->scores[pos];
    ss_tree_del(h, *s, *m);
    ss_idx_del(h, *m);
    return 1;
}

/* ---- structural validator (debug / tests) ---- */
static long ss_check_rec(SsHandle *h, uint32_t nidx, int depth, int is_root,
                         double *ps, int64_t *pm, int *hp, int *leaf_depth) {
    if (!ss_node_ok(h, nidx)) return -1;              /* corrupt child index */
    SsNode *nd = &h->nodes[nidx];
    if (nd->num < 1 || nd->num > SS_ORDER) return -1;
    if (!is_root && nd->num < SS_MIN) return -1;
    if (nd->is_leaf) {
        if (*leaf_depth < 0) *leaf_depth = depth;
        else if (*leaf_depth != depth) return -1;
        for (int i = 0; i < nd->num; i++) {
            if (*hp && ss_key_cmp(*ps, *pm, nd->scores[i], nd->members[i]) >= 0) return -1;
            *ps = nd->scores[i]; *pm = nd->members[i]; *hp = 1;
        }
        return nd->num;
    }
    long total = 0;
    for (int i = 0; i < nd->num; i++) {
        long c = ss_check_rec(h, nd->children[i], depth + 1, 0, ps, pm, hp, leaf_depth);
        if (c < 0 || (uint32_t)c != nd->counts[i]) return -1;
        total += c;
    }