nasm/nasmlib/raa.c

/* SPDX-License-Identifier: BSD-2-Clause */
/* Copyright 1996-2018 The NASM Authors - All Rights Reserved */

#include "nasmlib.h"
#include "raa.h"
#include "ilog2.h"

/*
 * Routines to manage a dynamic random access array of int64_ts which
 * may grow in size to be more than the largest single malloc'able
 * chunk.
 */

#define RAA_LAYERSHIFT	11      /* 2^this many items per layer */
#define RAA_LAYERSIZE	((size_t)1 << RAA_LAYERSHIFT)
#define RAA_LAYERMASK	(RAA_LAYERSIZE-1)

typedef struct RAA RAA;
typedef union RAA_UNION RAA_UNION;
typedef struct RAA_LEAF RAA_LEAF;
typedef struct RAA_BRANCH RAA_BRANCH;

struct RAA {
    /* Last position in this RAA */
    raaindex endposn;

    /*
     * Number of layers below this one to get to the real data. 0
     * means this structure is a leaf, holding RAA_LAYERSIZE real
     * data items; 1 and above mean it's a branch, holding
     * RAA_LAYERSIZE pointers to the next level branch or leaf
     * structures.
     */
    unsigned int layers;

    /*
     * Number of real data items spanned by one position in the
     * `data' array at this level. This number is 0 trivially, for
     * a leaf (level 0): for a level n branch it should be
     * n*RAA_LAYERSHIFT.
     */
    unsigned int shift;

    /*
     * The actual data
     */
    union RAA_UNION {
        struct RAA_LEAF {
            union intorptr data[RAA_LAYERSIZE];
        } l;
        struct RAA_BRANCH {
            struct RAA *data[RAA_LAYERSIZE];
        } b;
    } u;
};

#define LEAFSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_LEAF))
#define BRANCHSIZ (sizeof(RAA)-sizeof(RAA_UNION)+sizeof(RAA_BRANCH))

static struct RAA *raa_init_layer(raaindex posn, unsigned int layers)
{
    struct RAA *r;
    raaindex posmask;

    r = nasm_zalloc((layers == 0) ? LEAFSIZ : BRANCHSIZ);
    r->shift = layers * RAA_LAYERSHIFT;
    r->layers    = layers;
    posmask = ((raaindex)RAA_LAYERSIZE << r->shift) - 1;
    r->endposn   = posn | posmask;
    return r;
}

void raa_free(struct RAA *r)
{
    if (!r)
        return;

    if (r->layers) {
        struct RAA **p = r->u.b.data;
        size_t i;
        for (i = 0; i < RAA_LAYERSIZE; i++)
            raa_free(*p++);
    }
    nasm_free(r);
}

static const union intorptr * pure_func
real_raa_read(struct RAA *r, raaindex posn)
{
    nasm_assert(posn <= (~(raaindex)0 >> 1));

    if (unlikely(!r || posn > r->endposn))
        return NULL;            /* Beyond the end */

    while (r->layers) {
        size_t l = (posn >> r->shift) & RAA_LAYERMASK;
        r = r->u.b.data[l];
        if (!r)
            return NULL;        /* Not present */
    }
    return &r->u.l.data[posn & RAA_LAYERMASK];
}

int64_t raa_read(struct RAA *r, raaindex pos)
{
    const union intorptr *ip;

    ip = real_raa_read(r, pos);
    return ip ? ip->i : 0;
}

void *raa_read_ptr(struct RAA *r, raaindex pos)
{
    const union intorptr *ip;

    ip = real_raa_read(r, pos);
    return ip ? ip->p : NULL;
}


static struct RAA *
real_raa_write(struct RAA *r, raaindex posn, union intorptr value)
{
    struct RAA *result;

    nasm_assert(posn <= (~(raaindex)0 >> 1));

    if (unlikely(!r)) {
        /* Create a new top-level RAA */
        r = raa_init_layer(posn, ilog2_64(posn)/RAA_LAYERSHIFT);
    } else {
        while (unlikely(r->endposn < posn)) {
            /* We need to add layers to an existing RAA */
            struct RAA *s = raa_init_layer(r->endposn, r->layers + 1);
            s->u.b.data[0] = r;
            r = s;
        }
    }

    result = r;

    while (r->layers) {
        struct RAA **s;
        size_t l = (posn >> r->shift) & RAA_LAYERMASK;
        s = &r->u.b.data[l];
        if (unlikely(!*s))
            *s = raa_init_layer(posn, r->layers - 1);
        r = *s;
    }
    r->u.l.data[posn & RAA_LAYERMASK] = value;

    return result;
}

struct RAA *raa_write(struct RAA *r, raaindex posn, int64_t value)
{
    union intorptr ip;

    ip.i = value;
    return real_raa_write(r, posn, ip);
}

struct RAA *raa_write_ptr(struct RAA *r, raaindex posn, void *value)
{
    union intorptr ip;

    ip.p = value;
    return real_raa_write(r, posn, ip);
}