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