idpool.c

Go to the documentation of this file.

// SPDX-FileCopyrightText: 2017-2020 condret <condr3t@protonmail.com>
// SPDX-License-Identifier: LGPL-3.0-only
 
#include <rz_util.h>
#include <rz_types.h>
#include <string.h>
#include <stdlib.h>
#if __WINDOWS__
#include <search.h>
#endif
 
static ut32 get_msb(ut32 v) {
    int i;
    for (i = 31; i > (-1); i--) {
        if (v & (0x1U << i)) {
            return (v & (0x1U << i));
        }
    }
    return 0;
}
 
RZ_API RzIDPool *rz_id_pool_new(ut32 start_id, ut32 last_id) {
    RzIDPool *pool = NULL;
    if (start_id < last_id) {
        pool = RZ_NEW0(RzIDPool);
        if (pool) {
            pool->next_id = pool->start_id = start_id;
            pool->last_id = last_id;
        }
    }
    return pool;
}
 
RZ_API bool rz_id_pool_grab_id(RzIDPool *pool, ut32 *grabber) {
    rz_return_val_if_fail(pool && grabber, false);
 
    *grabber = UT32_MAX;
    if (pool->freed_ids) {
        rz_vector_pop_front(pool->freed_ids, grabber);
        if (rz_vector_empty(pool->freed_ids)) {
            RZ_FREE_CUSTOM(pool->freed_ids, rz_vector_free);
        }
        return true;
    }
    if (pool->next_id < pool->last_id) {
        *grabber = pool->next_id;
        pool->next_id++;
        return true;
    }
    return false;
}
 
RZ_API bool rz_id_pool_kick_id(RzIDPool *pool, ut32 kick) {
    if (!pool || (kick < pool->start_id) || (pool->start_id == pool->next_id)) {
        return false;
    }
    if (kick == (pool->next_id - 1)) {
        pool->next_id--;
        return true;
    }
    if (!pool->freed_ids) {
        pool->freed_ids = rz_vector_new(sizeof(ut32), NULL, NULL);
        if (!pool->freed_ids) {
            return false;
        }
        rz_vector_reserve(pool->freed_ids, 2);
    }
    rz_vector_push(pool->freed_ids, &kick);
    return true;
}
 
RZ_API void rz_id_pool_free(RzIDPool *pool) {
    if (!pool) {
        return;
    }
    rz_vector_free(pool->freed_ids);
    free(pool);
}
 
RZ_API RzIDStorage *rz_id_storage_new(ut32 start_id, ut32 last_id) {
    RzIDStorage *storage = NULL;
    RzIDPool *pool = rz_id_pool_new(start_id, last_id);
    if (pool) {
        storage = RZ_NEW0(RzIDStorage);
        if (!storage) {
            rz_id_pool_free(pool);
            return NULL;
        }
        storage->pool = pool;
    }
    return storage;
}
 
static bool id_storage_reallocate(RzIDStorage *storage, ut32 size) {
    if (!storage) {
        return false;
    }
    void **data = realloc(storage->data, size * sizeof(void *));
    if (!data) {
        return false;
    }
    if (size > storage->size) {
        memset(data + storage->size, 0, (size - storage->size) * sizeof(void *));
    }
    storage->data = data;
    storage->size = size;
    return true;
}
 
static bool oid_storage_preallocate(ROIDStorage *st, ut32 size) {
    ut32 *permutation;
    if (!st) {
        return false;
    }
    if (!size) {
        RZ_FREE(st->permutation);
        st->psize = 0;
    }
    permutation = realloc(st->permutation, size * sizeof(ut32));
    if (!permutation) {
        return false;
    }
    if (size > st->psize) {
        memset(permutation + st->psize, 0, (size - st->psize) * sizeof(ut32));
    }
    st->permutation = permutation;
    st->psize = size;
    return true;
}
 
RZ_API bool rz_id_storage_set(RzIDStorage *storage, void *data, ut32 id) {
    ut32 n;
    if (!storage || !storage->pool || (id >= storage->pool->next_id)) {
        return false;
    }
    n = get_msb(id + 1);
    if (n > ((storage->size / 2) + (storage->size / 4))) {
        if ((n * 2) < storage->pool->last_id) {
            if (!id_storage_reallocate(storage, n * 2)) {
                return false;
            }
        } else if (n != (storage->pool->last_id)) {
            if (!id_storage_reallocate(storage, storage->pool->last_id)) {
                return false;
            }
        }
    }
    storage->data[id] = data;
    if (id > storage->top_id) {
        storage->top_id = id;
    }
    return true;
}
 
RZ_API bool rz_id_storage_add(RzIDStorage *storage, void *data, ut32 *id) {
    if (!storage || !rz_id_pool_grab_id(storage->pool, id)) {
        return false;
    }
    return rz_id_storage_set(storage, data, *id);
}
 
RZ_API void *rz_id_storage_get(RzIDStorage *storage, ut32 id) {
    if (!storage || !storage->data || (storage->size <= id)) {
        return NULL;
    }
    return storage->data[id];
}
 
RZ_API bool rz_id_storage_get_lowest(RzIDStorage *storage, ut32 *id) {
    rz_return_val_if_fail(storage, false);
    ut32 i;
    for (i = 0; i < storage->size && !storage->data[i]; i++)
        ;
    *id = i;
    return i < storage->size;
}
 
RZ_API bool rz_id_storage_get_highest(RzIDStorage *storage, ut32 *id) {
    rz_return_val_if_fail(storage, false);
    size_t i = 0;
    if (storage->size > 0) {
        for (i = storage->size - 1; !storage->data[i] && i > 0; i--)
            ;
        *id = i;
        return storage->data[i] != NULL;
    }
    // *id = i;
    return false;
}
 
RZ_API bool rz_id_storage_get_next(RzIDStorage *storage, ut32 *idref) {
    rz_return_val_if_fail(idref && storage, false);
    ut32 id = *idref;
    if (storage->size < 1 || id >= storage->size || !storage->data) {
        return false;
    }
    for (id = *idref + 1; id < storage->size && !storage->data[id]; id++)
        ;
    if (id < storage->size) {
        *idref = id;
        return true;
    }
    return false;
}
 
RZ_API bool rz_id_storage_get_prev(RzIDStorage *storage, ut32 *idref) {
    rz_return_val_if_fail(idref && storage, false);
    ut32 id = *idref;
    if (id == 0 || id >= storage->size || storage->size < 1 || !storage->data) {
        return false;
    }
    for (id = *idref - 1; id > 0 && !storage->data[id]; id--)
        ;
    if (storage->data[id]) {
        *idref = id;
        return true;
    }
    return false;
}
 
RZ_API void rz_id_storage_delete(RzIDStorage *storage, ut32 id) {
    if (!storage || !storage->data || (storage->size <= id)) {
        return;
    }
    storage->data[id] = NULL;
    if (id == storage->top_id) {
        while (storage->top_id && !storage->data[storage->top_id]) {
            storage->top_id--;
        }
        if (!storage->top_id) {
            if (storage->data[storage->top_id]) {
                id_storage_reallocate(storage, 2);
            } else {
                RzIDPool *pool = rz_id_pool_new(storage->pool->start_id, storage->pool->last_id);
                RZ_FREE(storage->data);
                storage->size = 0;
                rz_id_pool_free(storage->pool);
                storage->pool = pool;
                return;
            }
        } else if ((storage->top_id + 1) < (storage->size / 4)) {
            id_storage_reallocate(storage, storage->size / 2);
        }
    }
    rz_id_pool_kick_id(storage->pool, id);
}
 
RZ_API void *rz_id_storage_take(RzIDStorage *storage, ut32 id) {
    void *ret = rz_id_storage_get(storage, id);
    rz_id_storage_delete(storage, id);
    return ret;
}
 
RZ_API bool rz_id_storage_foreach(RzIDStorage *storage, RzIDStorageForeachCb cb, void *user) {
    ut32 i;
    if (!cb || !storage || !storage->data) {
        return false;
    }
    for (i = 0; i < storage->top_id; i++) {
        if (storage->data[i] && !cb(user, storage->data[i], i)) {
            return false;
        }
    }
    if (storage->data[i]) {
        return cb(user, storage->data[i], i);
    }
    return true;
}
 
RZ_API void rz_id_storage_free(RzIDStorage *storage) {
    if (storage) {
        rz_id_pool_free(storage->pool);
        free(storage->data);
    }
    free(storage);
}
 
static bool _list(void *user, void *data, ut32 id) {
    rz_list_append(user, data);
    return true;
}
 
RZ_API RzList *rz_id_storage_list(RzIDStorage *s) { // remove this pls
    RzList *list = rz_list_newf(NULL);
    rz_id_storage_foreach(s, _list, list);
    return list;
}
 
RZ_API ROIDStorage *rz_oids_new(ut32 start_id, ut32 last_id) {
    ROIDStorage *storage = RZ_NEW0(ROIDStorage);
    if (!storage) {
        return NULL;
    }
    if (!(storage->data = rz_id_storage_new(start_id, last_id))) {
        free(storage);
        return NULL;
    }
    return storage;
}
 
RZ_API void *rz_oids_get(ROIDStorage *storage, ut32 id) {
    if (storage) {
        return rz_id_storage_get(storage->data, id);
    }
    return NULL;
}
 
RZ_API void *rz_oids_oget(ROIDStorage *storage, ut32 od) {
    ut32 id;
    if (rz_oids_get_id(storage, od, &id)) {
        return rz_id_storage_get(storage->data, id);
    }
    return NULL;
}
 
RZ_API bool rz_oids_get_id(ROIDStorage *storage, ut32 od, ut32 *id) {
    if (storage && storage->permutation && (storage->ptop > od)) {
        *id = storage->permutation[od];
        return true;
    }
    return false;
}
 
RZ_API bool rz_oids_get_od(ROIDStorage *storage, ut32 id, ut32 *od) {
    if (storage && storage->permutation &&
        storage->data && (id < storage->data->pool->next_id)) {
        for (od[0] = 0; od[0] < storage->ptop; od[0]++) {
            if (id == storage->permutation[od[0]]) {
                return true;
            }
        }
    }
    return false;
}
 
RZ_API bool rz_oids_add(ROIDStorage *storage, void *data, ut32 *id, ut32 *od) {
    if (!storage || !id || !od) {
        return false;
    }
    if (!rz_id_storage_add(storage->data, data, id)) {
        return false;
    }
    if (!storage->permutation) {
        oid_storage_preallocate(storage, 4);
    } else if (storage->ptop > (storage->psize * 3 / 4)) {
        oid_storage_preallocate(storage, storage->psize * 2);
    }
    if (storage->psize <= storage->ptop) {
        rz_id_storage_delete(storage->data, *id);
        return false;
    }
    if (!storage->permutation) {
        return false;
    }
    *od = storage->ptop;
    storage->permutation[*od] = *id;
    storage->ptop++;
    return true;
}
 
RZ_API bool rz_oids_to_front(ROIDStorage *storage, const ut32 id) {
    ut32 od;
    if (!storage || !storage->permutation) {
        return false;
    }
    for (od = 0; od < storage->ptop; od++) {
        if (id == storage->permutation[od]) {
            break;
        }
    }
    if (od == storage->ptop) {
        return false;
    } else if (od == (storage->ptop - 1)) {
        return true;
    }
    memmove(&storage->permutation[od], &storage->permutation[od + 1],
        (storage->ptop - od - 1) * sizeof(ut32));
    storage->permutation[storage->ptop - 1] = id;
    return true;
}
 
RZ_API bool rz_oids_to_rear(ROIDStorage *storage, ut32 id) {
    ut32 od;
    if (!storage || !storage->permutation ||
        !storage->data || (id >= storage->data->pool->next_id)) {
        return false;
    }
    bool found = false;
    for (od = 0; od < storage->ptop; od++) {
        if (id == storage->permutation[od]) {
            found = true;
            break;
        }
    }
    if (od == storage->ptop) {
        return false;
    }
    if (!found) {
        return true;
    }
    memmove(&storage->permutation[1], &storage->permutation[0], od * sizeof(ut32));
    storage->permutation[0] = id;
    return true;
}
 
RZ_API void rz_oids_delete(ROIDStorage *storage, ut32 id) {
    if (!rz_oids_to_front(storage, id)) {
        return;
    }
    rz_id_storage_delete(storage->data, id);
    storage->ptop--;
    if (!storage->ptop) {
        RZ_FREE(storage->permutation);
        storage->psize = 0;
    } else if ((storage->ptop + 1) < (storage->psize / 4)) {
        oid_storage_preallocate(storage, storage->psize / 2);
    }
}
 
RZ_API void rz_oids_odelete(ROIDStorage *st, ut32 od) {
    ut32 n;
    if (!st || !st->permutation || od >= st->ptop) {
        return;
    }
    n = st->ptop - od - 1;
    rz_id_storage_delete(st->data, st->permutation[od]);
    memmove(&st->permutation[od], &st->permutation[od + 1], n * sizeof(ut32));
    st->ptop--;
    if (!st->ptop) {
        RZ_FREE(st->permutation);
        st->psize = 0;
    } else if ((st->ptop + 1) < (st->psize / 4)) {
        oid_storage_preallocate(st, st->psize / 2);
    }
}
 
RZ_API void *rz_oids_take(ROIDStorage *storage, ut32 id) {
    rz_return_val_if_fail(storage, NULL);
    void *ret = rz_id_storage_get(storage->data, id);
    rz_oids_delete(storage, id);
    return ret;
}
 
RZ_API void *rz_oids_otake(ROIDStorage *st, ut32 od) {
    void *ret = rz_oids_oget(st, od);
    rz_oids_odelete(st, od);
    return ret;
}
 
RZ_API void rz_oids_free(ROIDStorage *storage) {
    if (storage) {
        free(storage->permutation);
        rz_id_storage_free(storage->data);
    }
    free(storage);
}
 
// returns the element with lowest order
RZ_API void *rz_oids_last(ROIDStorage *storage) {
    if (storage && storage->data && storage->data->data && storage->permutation) {
        return storage->data->data[storage->permutation[0]];
    }
    return NULL;
}
 
// return the element with highest order
RZ_API void *rz_oids_first(ROIDStorage *storage) {
    if (storage && storage->data && storage->data->data && storage->permutation) {
        return storage->data->data[storage->permutation[storage->ptop - 1]];
    }
    return NULL;
}
 
RZ_API bool rz_oids_foreach(ROIDStorage *storage, RzIDStorageForeachCb cb, void *user) {
    ut32 i;
    ut32 id;
    if (!cb || !storage || !storage->data || !storage->data->data || !storage->permutation) {
        return false;
    }
    for (i = storage->ptop - 1; i != 0; i--) {
        id = storage->permutation[i];
        if (!cb(user, storage->data->data[id], id)) {
            return false;
        }
    }
    id = storage->permutation[0];
    return cb(user, storage->data->data[id], id);
}
 
RZ_API bool rz_oids_foreach_prev(ROIDStorage *storage, RzIDStorageForeachCb cb, void *user) {
    ut32 i;
    ut32 id;
    if (!cb || !storage || !storage->data || !storage->data->data || !storage->permutation) {
        return false;
    }
    for (i = 0; i < storage->ptop; i++) {
        id = storage->permutation[i];
        if (!cb(user, storage->data->data[id], id)) {
            return false;
        }
    }
    return true;
}
 
bool oids_od_bfind(ROIDStorage *st, ut32 *od, void *incoming, void *user) {
    st64 high, low;
    int cmp_res;
    void *in;
 
    if (!st->ptop) {
        return false;
    }
 
    high = st->ptop - 1;
    low = 0;
 
    while (1) {
        if (high <= low) {
            od[0] = (ut32)low;
            in = rz_oids_oget(st, od[0]);
            // in - incoming
            if (!st->cmp(in, incoming, user, &cmp_res)) {
                return false;
            }
            if (cmp_res < 0) {
                od[0]++;
            }
            return true;
        }
 
        od[0] = (ut32)((low + high) / 2);
        in = rz_oids_oget(st, od[0]);
        if (!st->cmp(in, incoming, user, &cmp_res)) {
            return false;
        }
 
        if (cmp_res == 0) {
            return true;
        }
 
        if (cmp_res < 0) {
            low = od[0] + 1;
        } else {
            high = od[0];
            high--;
        }
    }
    return false;
}
 
bool oids_od_binsert(ROIDStorage *storage, ut32 id, ut32 *od, void *incoming, void *user) {
    if (!oids_od_bfind(storage, od, incoming, user)) {
        return false;
    }
    if (od[0] != storage->ptop) {
        memmove(&storage->permutation[od[0] + 1], &storage->permutation[od[0]], (storage->ptop - od[0]) * sizeof(ut32));
    }
    storage->ptop++;
    storage->permutation[od[0]] = id;
    return true;
}
 
RZ_API bool rz_oids_insert(ROIDStorage *storage, void *data, ut32 *id, ut32 *od, void *user) {
    if (!storage || !storage->cmp || !id || !od) {
        return false;
    }
    if (!storage->ptop) { // empty storage
        return rz_oids_add(storage, data, id, od);
    }
    if (!rz_id_storage_add(storage->data, data, id)) {
        return false;
    }
    if (storage->ptop > (storage->psize * 3 / 4)) {
        oid_storage_preallocate(storage, storage->psize * 2);
    }
    return oids_od_binsert(storage, id[0], od, data, user);
}
 
RZ_API bool rz_oids_sort(ROIDStorage *storage, void *user) {
    ut32 od, id, ptop, *permutation;
 
    if (!storage || !storage->ptop || !storage->cmp) {
        return false;
    }
    if (storage->ptop == 1) {
        return true;
    }
    permutation = storage->permutation;
    storage->permutation = RZ_NEWS0(ut32, storage->psize);
    if (!storage->permutation) {
        storage->permutation = permutation;
        return false;
    }
    storage->permutation[0] = permutation[0];
    ptop = storage->ptop;
    storage->ptop = 1;
    while (storage->ptop != ptop) {
        id = permutation[storage->ptop];
        void *incoming = rz_id_storage_get(storage->data, id);
        if (!oids_od_binsert(storage, id, &od, incoming, user)) {
            goto beach;
        }
    }
    free(permutation);
    return true;
 
beach:
    free(storage->permutation);
    storage->permutation = permutation;
    storage->ptop = ptop;
    return false;
}
 
RZ_API ut32 rz_oids_find(ROIDStorage *storage, void *incoming, void *user) {
    ut32 ret;
    return oids_od_bfind(storage, &ret, incoming, user) ? ret : storage->ptop;
}