src/basic/bitmap.c

	bitmap.c revision 951c3eefacedcdbdb2cebf245f043aa3e81fb483
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering/***
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  This file is part of systemd.
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  Copyright 2015 Tom Gundersen
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  systemd is free software; you can redistribute it and/or modify it
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  under the terms of the GNU Lesser General Public License as published by
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  the Free Software Foundation; either version 2.1 of the License, or
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  (at your option) any later version.
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  systemd is distributed in the hope that it will be useful, but
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  WITHOUT ANY WARRANTY; without even the implied warranty of
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  Lesser General Public License for more details.
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  You should have received a copy of the GNU Lesser General Public License
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering  along with systemd; If not, see <http://www.gnu.org/licenses/>.
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering***/
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering#include "util.h"
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering#include "bitmap.h"
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poetteringstruct Bitmap {
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering        uint64_t *bitmaps;
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering        size_t n_bitmaps;
34e5a31ec5897de8ba1436dad53df99637569d0aLennart Poettering        size_t bitmaps_allocated;
34e5a31ec5897de8ba1436dad53df99637569d0aLennart Poettering};
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering
34e5a31ec5897de8ba1436dad53df99637569d0aLennart Poettering/* Bitmaps are only meant to store relatively small numbers
2e3d069236777cd62f755a02f4a239306b4ad21aLennart Poettering * (corresponding to, say, an enum), so it is ok to limit
 * the max entry. 64k should be plenty. */
#define BITMAPS_MAX_ENTRY 0xffff

/* This indicates that we reached the end of the bitmap */
#define BITMAP_END ((unsigned) -1)

#define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(uint64_t) * 8))
#define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(uint64_t) * 8))
#define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))

Bitmap *bitmap_new(void) {
        return new0(Bitmap, 1);
}

void bitmap_free(Bitmap *b) {
        if (!b)
                return;

        free(b->bitmaps);
        free(b);
}

int bitmap_ensure_allocated(Bitmap **b) {
        Bitmap *a;

        assert(b);

        if (*b)
                return 0;

        a = bitmap_new();
        if (!a)
                return -ENOMEM;

        *b = a;

        return 0;
}

int bitmap_set(Bitmap *b, unsigned n) {
        uint64_t bitmask;
        unsigned offset;

        assert(b);

        /* we refuse to allocate huge bitmaps */
        if (n > BITMAPS_MAX_ENTRY)
                return -ERANGE;

        offset = BITMAP_NUM_TO_OFFSET(n);

        if (offset >= b->n_bitmaps) {
                if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
                        return -ENOMEM;

                b->n_bitmaps = offset + 1;
        }

        bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);

        b->bitmaps[offset] |= bitmask;

        return 0;
}

void bitmap_unset(Bitmap *b, unsigned n) {
        uint64_t bitmask;
        unsigned offset;

        if (!b)
                return;

        offset = BITMAP_NUM_TO_OFFSET(n);

        if (offset >= b->n_bitmaps)
                return;

        bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);

        b->bitmaps[offset] &= ~bitmask;
}

bool bitmap_isset(Bitmap *b, unsigned n) {
        uint64_t bitmask;
        unsigned offset;

        if (!b)
                return false;

        offset = BITMAP_NUM_TO_OFFSET(n);

        if (offset >= b->n_bitmaps)
                return false;

        bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);

        return !!(b->bitmaps[offset] & bitmask);
}

bool bitmap_isclear(Bitmap *b) {
        unsigned i;

        assert(b);

        for (i = 0; i < b->n_bitmaps; i++)
                if (b->bitmaps[i] != 0)
                        return false;

        return true;
}

void bitmap_clear(Bitmap *b) {
        assert(b);

        free(b->bitmaps);
        b->bitmaps = NULL;
        b->n_bitmaps = 0;
        b->bitmaps_allocated = 0;
}

bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
        uint64_t bitmask;
        unsigned offset, rem;

        assert(i);
        assert(n);

        if (!b || i->idx == BITMAP_END)
                return false;

        offset = BITMAP_NUM_TO_OFFSET(i->idx);
        rem = BITMAP_NUM_TO_REM(i->idx);
        bitmask = UINT64_C(1) << rem;

        for (; offset < b->n_bitmaps; offset ++) {
                if (b->bitmaps[offset]) {
                        for (; bitmask; bitmask <<= 1, rem ++) {
                                if (b->bitmaps[offset] & bitmask) {
                                        *n = BITMAP_OFFSET_TO_NUM(offset, rem);
                                        i->idx = *n + 1;

                                        return true;
                                }
                        }
                }

                rem = 0;
                bitmask = 1;
        }

        i->idx = BITMAP_END;

        return false;
}

bool bitmap_equal(Bitmap *a, Bitmap *b) {
        size_t common_n_bitmaps;
        Bitmap *c;
        unsigned i;

        if (!a ^ !b)
                return false;

        if (!a)
                return true;

        common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
        if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
                return false;

        c = a->n_bitmaps > b->n_bitmaps ? a : b;
        for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
                if (c->bitmaps[i] != 0)
                        return false;

        return true;
}