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
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include <errno.h>
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include <stddef.h>
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include <stdint.h>
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include <stdlib.h>
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include <string.h>
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen
b5efdb8af40ea759a1ea584c1bc44ecc81dd00ceLennart Poettering#include "alloc-util.h"
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen#include "bitmap.h"
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include "hashmap.h"
11c3a36649e5e5e77db499c92f3cdcbd619efd3aThomas Hindoe Paaboel Andersen#include "macro.h"
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenstruct Bitmap {
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack uint64_t *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
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack#define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(uint64_t) * 8))
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack#define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(uint64_t) * 8))
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack#define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 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
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering assert(b);
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering
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) {
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack uint64_t 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
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering bitmask = UINT64_C(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) {
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack uint64_t bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen unsigned offset;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering if (!b)
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering return;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen offset = BITMAP_NUM_TO_OFFSET(n);
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen if (offset >= b->n_bitmaps)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering bitmask = UINT64_C(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) {
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack uint64_t bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen unsigned offset;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering if (!b)
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
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering bitmask = UINT64_C(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
0b8086379f0a062582c20471d6cd2646a6d22e93Lennart Poettering if (!b)
0b8086379f0a062582c20471d6cd2646a6d22e93Lennart Poettering return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen for (i = 0; i < b->n_bitmaps; i++)
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering if (b->bitmaps[i] != 0)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersenvoid bitmap_clear(Bitmap *b) {
0b8086379f0a062582c20471d6cd2646a6d22e93Lennart Poettering
0b8086379f0a062582c20471d6cd2646a6d22e93Lennart Poettering if (!b)
0b8086379f0a062582c20471d6cd2646a6d22e93Lennart Poettering return;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
a1e58e8ee1c84b633d6d6d651d5328d4dd4eba5bLennart Poettering b->bitmaps = mfree(b->bitmaps);
05fb03beeecd730e5525253b9c3c8706e1834b09Lennart Poettering b->n_bitmaps = 0;
951c3eefacedcdbdb2cebf245f043aa3e81fb483Martin Mikkelsen b->bitmaps_allocated = 0;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
cb57dd41595adddb08095298bb1ed258c8ea4877Tom Gundersenbool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
848d08b74eb0272774b1f8eff688d00ed9b63d9dDaniel Mack uint64_t bitmask;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen unsigned offset, rem;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering assert(i);
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering assert(n);
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering
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);
370a2172ac0f455863a1ac8e7a9b0a284d810fd4Lennart Poettering bitmask = UINT64_C(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) {
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen size_t common_n_bitmaps;
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen Bitmap *c;
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen unsigned i;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
7d7fa31c62242e11494ace491a8c98fb070d4e8aLennart Poettering if (a == b)
7d7fa31c62242e11494ace491a8c98fb070d4e8aLennart Poettering return true;
7d7fa31c62242e11494ace491a8c98fb070d4e8aLennart Poettering
7d7fa31c62242e11494ace491a8c98fb070d4e8aLennart Poettering if (!a != !b)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen if (!a)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen return false;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen c = a->n_bitmaps > b->n_bitmaps ? a : b;
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen if (c->bitmaps[i] != 0)
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen return false;
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen
d5fa81995849cb263ecfcd0aa6ab661360d9213eMartin Mikkelsen return true;
5ffa42cb8028833440040c2e240e0d788f11c112Tom Gundersen}