bitmap.c revision 22cedfe15fda59106b890ae2c646de96aa18a5eb
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};
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
cb57dd41595adddb08095298bb1ed258c8ea4877Tom Gundersenbool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen long long bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen unsigned offset, rem;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
22cedfe15fda59106b890ae2c646de96aa18a5ebDavid Herrmann if (!b || i->idx == BITMAP_END)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
cb57dd41595adddb08095298bb1ed258c8ea4877Tom Gundersen offset = BITMAP_NUM_TO_OFFSET(i->idx);
cb57dd41595adddb08095298bb1ed258c8ea4877Tom Gundersen rem = BITMAP_NUM_TO_REM(i->idx);
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);
cb57dd41595adddb08095298bb1ed258c8ea4877Tom Gundersen i->idx = *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
cb57dd41595adddb08095298bb1ed258c8ea4877Tom Gundersen i->idx = 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}