Add SPDX license identifiers to source files under the LGPL

[thirdparty/systemd.git] / src / basic / bitmap.c

diff --git a/src/basic/bitmap.c b/src/basic/bitmap.c
index d865e2fc6ed1d5508ffd7e001e8e8116fb084272..f1aa7c5e51a48884e3867ec1e2fa1df77ed7ec71 100644 (file)
--- a/src/basic/bitmap.c
+++ b/src/basic/bitmap.c
@@ -1,5 +1,4 @@
-/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
-
+/* SPDX-License-Identifier: LGPL-2.1+ */
 /***
   This file is part of systemd.
 
@@ -19,15 +18,21 @@
   along with systemd; If not, see <http://www.gnu.org/licenses/>.
 ***/
 
-#include "util.h"
+#include <errno.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
 
+#include "alloc-util.h"
 #include "bitmap.h"
+#include "hashmap.h"
+#include "macro.h"
 
 struct Bitmap {
-        long long unsigned *bitmaps;
+        uint64_t *bitmaps;
         size_t n_bitmaps;
         size_t bitmaps_allocated;
-        unsigned next_entry;
 };
 
 /* Bitmaps are only meant to store relatively small numbers
@@ -38,14 +43,29 @@ struct Bitmap {
 /* This indicates that we reached the end of the bitmap */
 #define BITMAP_END ((unsigned) -1)
 
-#define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(long long unsigned) * 8))
-#define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(long long unsigned) * 8))
-#define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(long long unsigned) * 8 + (rem))
+#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);
 }
 
+Bitmap *bitmap_copy(Bitmap *b) {
+        Bitmap *ret;
+
+        ret = bitmap_new();
+        if (!ret)
+                return NULL;
+
+        ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps);
+        if (!ret->bitmaps)
+                return mfree(ret);
+
+        ret->n_bitmaps = ret->bitmaps_allocated = b->n_bitmaps;
+        return ret;
+}
+
 void bitmap_free(Bitmap *b) {
         if (!b)
                 return;
@@ -57,6 +77,8 @@ void bitmap_free(Bitmap *b) {
 int bitmap_ensure_allocated(Bitmap **b) {
         Bitmap *a;
 
+        assert(b);
+
         if (*b)
                 return 0;
 
@@ -70,7 +92,7 @@ int bitmap_ensure_allocated(Bitmap **b) {
 }
 
 int bitmap_set(Bitmap *b, unsigned n) {
-        long long bitmask;
+        uint64_t bitmask;
         unsigned offset;
 
         assert(b);
@@ -88,7 +110,7 @@ int bitmap_set(Bitmap *b, unsigned n) {
                 b->n_bitmaps = offset + 1;
         }
 
-        bitmask = 1 << BITMAP_NUM_TO_REM(n);
+        bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 
         b->bitmaps[offset] |= bitmask;
 
@@ -96,26 +118,27 @@ int bitmap_set(Bitmap *b, unsigned n) {
 }
 
 void bitmap_unset(Bitmap *b, unsigned n) {
-        long long bitmask;
+        uint64_t bitmask;
         unsigned offset;
 
-        assert(b);
+        if (!b)
+                return;
 
         offset = BITMAP_NUM_TO_OFFSET(n);
 
         if (offset >= b->n_bitmaps)
                 return;
 
-        bitmask = 1 << BITMAP_NUM_TO_REM(n);
+        bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 
         b->bitmaps[offset] &= ~bitmask;
 }
 
 bool bitmap_isset(Bitmap *b, unsigned n) {
-        long long bitmask;
+        uint64_t bitmask;
         unsigned offset;
 
-        if (!b || !b->bitmaps)
+        if (!b)
                 return false;
 
         offset = BITMAP_NUM_TO_OFFSET(n);
@@ -123,7 +146,7 @@ bool bitmap_isset(Bitmap *b, unsigned n) {
         if (offset >= b->n_bitmaps)
                 return false;
 
-        bitmask = 1 << BITMAP_NUM_TO_REM(n);
+        bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 
         return !!(b->bitmaps[offset] & bitmask);
 }
@@ -131,48 +154,46 @@ bool bitmap_isset(Bitmap *b, unsigned n) {
 bool bitmap_isclear(Bitmap *b) {
         unsigned i;
 
-        assert(b);
+        if (!b)
+                return true;
 
         for (i = 0; i < b->n_bitmaps; i++)
-                if (b->bitmaps[i])
+                if (b->bitmaps[i] != 0)
                         return false;
 
         return true;
 }
 
 void bitmap_clear(Bitmap *b) {
-        unsigned i;
-
-        assert(b);
 
-        for (i = 0; i < b->n_bitmaps; i++)
-                b->bitmaps[i] = 0;
-}
-
-void bitmap_rewind(Bitmap *b) {
         if (!b)
                 return;
 
-        b->next_entry = 0;
+        b->bitmaps = mfree(b->bitmaps);
+        b->n_bitmaps = 0;
+        b->bitmaps_allocated = 0;
 }
 
-bool bitmap_next(Bitmap *b, unsigned *n) {
-        long long bitmask;
+bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
+        uint64_t bitmask;
         unsigned offset, rem;
 
-        if (!b && b->next_entry == BITMAP_END)
+        assert(i);
+        assert(n);
+
+        if (!b || i->idx == BITMAP_END)
                 return false;
 
-        offset = BITMAP_NUM_TO_OFFSET(b->next_entry);
-        rem = BITMAP_NUM_TO_REM(b->next_entry);
-        bitmask = 1 << rem;
+        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);
-                                        b->next_entry = *n + 1;
+                                        i->idx = *n + 1;
 
                                         return true;
                                 }
@@ -183,25 +204,32 @@ bool bitmap_next(Bitmap *b, unsigned *n) {
                 bitmask = 1;
         }
 
-        b->next_entry = BITMAP_END;
+        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)
+        if (a == b)
+                return true;
+
+        if (!a != !b)
                 return false;
 
         if (!a)
                 return true;
 
-        if (a->n_bitmaps != b->n_bitmaps)
+        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;
 
-        for (i = 0; i < a->n_bitmaps; i++)
-                if (a->bitmaps[i] != b->bitmaps[i])
+        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;