src/basic/bitmap.c

	bitmap.c revision 5ffa42cb8028833440040c2e240e0d788f11c112
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen/***
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  This file is part of systemd.
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  Copyright 2015 Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  systemd is free software; you can redistribute it and/or modify it
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  under the terms of the GNU Lesser General Public License as published by
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  the Free Software Foundation; either version 2.1 of the License, or
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  (at your option) any later version.
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  systemd is distributed in the hope that it will be useful, but
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  WITHOUT ANY WARRANTY; without even the implied warranty of
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  Lesser General Public License for more details.
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  You should have received a copy of the GNU Lesser General Public License
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen  along with systemd; If not, see <http://www.gnu.org/licenses/>.
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen***/
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#include "util.h"
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#include "bitmap.h"
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenstruct Bitmap {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        long long unsigned *bitmaps;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        size_t n_bitmaps;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        size_t bitmaps_allocated;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned next_entry;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen};
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen/* Bitmaps are only meant to store relatively small numbers
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen * (corresponding to, say, an enum), so it is ok to limit
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen * the max entry. 64k should be plenty. */
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#define BITMAPS_MAX_ENTRY 0xffff
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen/* This indicates that we reached the end of the bitmap */
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#define BITMAP_END ((unsigned) -1)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(long long unsigned) * 8))
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(long long unsigned) * 8))
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(long long unsigned) * 8 + (rem))
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom GundersenBitmap *bitmap_new(void) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return new0(Bitmap, 1);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenvoid bitmap_free(Bitmap *b) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!b)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        free(b->bitmaps);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        free(b);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenint bitmap_ensure_allocated(Bitmap **b) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        Bitmap *a;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (*b)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        a = bitmap_new();
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!a)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return -ENOMEM;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        *b = a;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenint bitmap_set(Bitmap *b, unsigned n) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        long long bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned offset;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        assert(b);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        /* we refuse to allocate huge bitmaps */
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (n > BITMAPS_MAX_ENTRY)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return -ERANGE;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        offset = BITMAP_NUM_TO_OFFSET(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (offset >= b->n_bitmaps) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                        return -ENOMEM;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                b->n_bitmaps = offset + 1;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        }
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        bitmask = 1 << BITMAP_NUM_TO_REM(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        b->bitmaps[offset] |= bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenvoid bitmap_unset(Bitmap *b, unsigned n) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        long long bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned offset;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        assert(b);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        offset = BITMAP_NUM_TO_OFFSET(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (offset >= b->n_bitmaps)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        bitmask = 1 << BITMAP_NUM_TO_REM(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        b->bitmaps[offset] &= ~bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenbool bitmap_isset(Bitmap *b, unsigned n) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        long long bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned offset;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!b || !b->bitmaps)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        offset = BITMAP_NUM_TO_OFFSET(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (offset >= b->n_bitmaps)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        bitmask = 1 << BITMAP_NUM_TO_REM(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return !!(b->bitmaps[offset] & bitmask);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenbool bitmap_isclear(Bitmap *b) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned i;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        assert(b);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        for (i = 0; i < b->n_bitmaps; i++)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                if (b->bitmaps[i])
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                        return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenvoid bitmap_clear(Bitmap *b) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned i;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        assert(b);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        for (i = 0; i < b->n_bitmaps; i++)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                b->bitmaps[i] = 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenvoid bitmap_rewind(Bitmap *b) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!b)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        b->next_entry = 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenbool bitmap_next(Bitmap *b, unsigned *n) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        long long bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned offset, rem;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!b && b->next_entry == BITMAP_END)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        offset = BITMAP_NUM_TO_OFFSET(b->next_entry);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        rem = BITMAP_NUM_TO_REM(b->next_entry);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        bitmask = 1 << rem;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        for (; offset < b->n_bitmaps; offset ++) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                if (b->bitmaps[offset]) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                        for (; bitmask; bitmask <<= 1, rem ++) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                                if (b->bitmaps[offset] & bitmask) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                                        *n = BITMAP_OFFSET_TO_NUM(offset, rem);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                                        b->next_entry = *n + 1;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                                        return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                                }
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                        }
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                }
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                rem = 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                bitmask = 1;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        }
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        b->next_entry = BITMAP_END;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenbool bitmap_equal(Bitmap *a, Bitmap *b) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        unsigned i;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!a ^ !b)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (!a)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        if (a->n_bitmaps != b->n_bitmaps)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        for (i = 0; i < a->n_bitmaps; i++)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                if (a->bitmaps[i] != b->bitmaps[i])
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen                        return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen        return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}