Line data    Source code

       1             : /* SPDX-License-Identifier: LGPL-2.1+ */
       2             : 
       3             : #include <errno.h>
       4             : #include <stddef.h>
       5             : #include <stdint.h>
       6             : #include <stdlib.h>
       7             : #include <string.h>
       8             : 
       9             : #include "alloc-util.h"
      10             : #include "bitmap.h"
      11             : #include "hashmap.h"
      12             : #include "macro.h"
      13             : #include "memory-util.h"
      14             : 
      15             : /* Bitmaps are only meant to store relatively small numbers
      16             :  * (corresponding to, say, an enum), so it is ok to limit
      17             :  * the max entry. 64k should be plenty. */
      18             : #define BITMAPS_MAX_ENTRY 0xffff
      19             : 
      20             : /* This indicates that we reached the end of the bitmap */
      21             : #define BITMAP_END ((unsigned) -1)
      22             : 
      23             : #define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(uint64_t) * 8))
      24             : #define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(uint64_t) * 8))
      25             : #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
      26             : 
      27          54 : Bitmap *bitmap_new(void) {
      28          54 :         return new0(Bitmap, 1);
      29             : }
      30             : 
      31          25 : Bitmap *bitmap_copy(Bitmap *b) {
      32             :         Bitmap *ret;
      33             : 
      34          25 :         ret = bitmap_new();
      35          25 :         if (!ret)
      36           0 :                 return NULL;
      37             : 
      38          25 :         ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps);
      39          25 :         if (!ret->bitmaps)
      40           0 :                 return mfree(ret);
      41             : 
      42          25 :         ret->n_bitmaps = ret->bitmaps_allocated = b->n_bitmaps;
      43          25 :         return ret;
      44             : }
      45             : 
      46          55 : void bitmap_free(Bitmap *b) {
      47          55 :         if (!b)
      48           1 :                 return;
      49             : 
      50          54 :         free(b->bitmaps);
      51          54 :         free(b);
      52             : }
      53             : 
      54          28 : int bitmap_ensure_allocated(Bitmap **b) {
      55             :         Bitmap *a;
      56             : 
      57          28 :         assert(b);
      58             : 
      59          28 :         if (*b)
      60           1 :                 return 0;
      61             : 
      62          27 :         a = bitmap_new();
      63          27 :         if (!a)
      64           0 :                 return -ENOMEM;
      65             : 
      66          27 :         *b = a;
      67             : 
      68          27 :         return 0;
      69             : }
      70             : 
      71         161 : int bitmap_set(Bitmap *b, unsigned n) {
      72             :         uint64_t bitmask;
      73             :         unsigned offset;
      74             : 
      75         161 :         assert(b);
      76             : 
      77             :         /* we refuse to allocate huge bitmaps */
      78         161 :         if (n > BITMAPS_MAX_ENTRY)
      79           1 :                 return -ERANGE;
      80             : 
      81         160 :         offset = BITMAP_NUM_TO_OFFSET(n);
      82             : 
      83         160 :         if (offset >= b->n_bitmaps) {
      84          35 :                 if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
      85           0 :                         return -ENOMEM;
      86             : 
      87          35 :                 b->n_bitmaps = offset + 1;
      88             :         }
      89             : 
      90         160 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
      91             : 
      92         160 :         b->bitmaps[offset] |= bitmask;
      93             : 
      94         160 :         return 0;
      95             : }
      96             : 
      97           6 : void bitmap_unset(Bitmap *b, unsigned n) {
      98             :         uint64_t bitmask;
      99             :         unsigned offset;
     100             : 
     101           6 :         if (!b)
     102           0 :                 return;
     103             : 
     104           6 :         offset = BITMAP_NUM_TO_OFFSET(n);
     105             : 
     106           6 :         if (offset >= b->n_bitmaps)
     107           0 :                 return;
     108             : 
     109           6 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
     110             : 
     111           6 :         b->bitmaps[offset] &= ~bitmask;
     112             : }
     113             : 
     114          10 : bool bitmap_isset(const Bitmap *b, unsigned n) {
     115             :         uint64_t bitmask;
     116             :         unsigned offset;
     117             : 
     118          10 :         if (!b)
     119           0 :                 return false;
     120             : 
     121          10 :         offset = BITMAP_NUM_TO_OFFSET(n);
     122             : 
     123          10 :         if (offset >= b->n_bitmaps)
     124           3 :                 return false;
     125             : 
     126           7 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
     127             : 
     128           7 :         return !!(b->bitmaps[offset] & bitmask);
     129             : }
     130             : 
     131          42 : bool bitmap_isclear(const Bitmap *b) {
     132             :         unsigned i;
     133             : 
     134          42 :         if (!b)
     135           0 :                 return true;
     136             : 
     137          53 :         for (i = 0; i < b->n_bitmaps; i++)
     138          14 :                 if (b->bitmaps[i] != 0)
     139           3 :                         return false;
     140             : 
     141          39 :         return true;
     142             : }
     143             : 
     144         278 : void bitmap_clear(Bitmap *b) {
     145         278 :         if (!b)
     146           0 :                 return;
     147             : 
     148         278 :         b->bitmaps = mfree(b->bitmaps);
     149         278 :         b->n_bitmaps = 0;
     150         278 :         b->bitmaps_allocated = 0;
     151             : }
     152             : 
     153         358 : bool bitmap_iterate(const Bitmap *b, Iterator *i, unsigned *n) {
     154             :         uint64_t bitmask;
     155             :         unsigned offset, rem;
     156             : 
     157         358 :         assert(i);
     158         358 :         assert(n);
     159             : 
     160         358 :         if (!b || i->idx == BITMAP_END)
     161           2 :                 return false;
     162             : 
     163         356 :         offset = BITMAP_NUM_TO_OFFSET(i->idx);
     164         356 :         rem = BITMAP_NUM_TO_REM(i->idx);
     165         356 :         bitmask = UINT64_C(1) << rem;
     166             : 
     167        2470 :         for (; offset < b->n_bitmaps; offset ++) {
     168        2418 :                 if (b->bitmaps[offset]) {
     169        4160 :                         for (; bitmask; bitmask <<= 1, rem ++) {
     170        4096 :                                 if (b->bitmaps[offset] & bitmask) {
     171         304 :                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
     172         304 :                                         i->idx = *n + 1;
     173             : 
     174         304 :                                         return true;
     175             :                                 }
     176             :                         }
     177             :                 }
     178             : 
     179        2114 :                 rem = 0;
     180        2114 :                 bitmask = 1;
     181             :         }
     182             : 
     183          52 :         i->idx = BITMAP_END;
     184             : 
     185          52 :         return false;
     186             : }
     187             : 
     188          34 : bool bitmap_equal(const Bitmap *a, const Bitmap *b) {
     189             :         size_t common_n_bitmaps;
     190             :         const Bitmap *c;
     191             :         unsigned i;
     192             : 
     193          34 :         if (a == b)
     194           2 :                 return true;
     195             : 
     196          32 :         if (!a != !b)
     197           2 :                 return false;
     198             : 
     199          30 :         if (!a)
     200           0 :                 return true;
     201             : 
     202          30 :         common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
     203          30 :         if (memcmp_safe(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
     204           0 :                 return false;
     205             : 
     206          30 :         c = a->n_bitmaps > b->n_bitmaps ? a : b;
     207          31 :         for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
     208           2 :                 if (c->bitmaps[i] != 0)
     209           1 :                         return false;
     210             : 
     211          29 :         return true;
     212             : }