Branch data     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                 :        216 : Bitmap *bitmap_new(void) {
      28                 :        216 :         return new0(Bitmap, 1);
      29                 :            : }
      30                 :            : 
      31                 :        100 : Bitmap *bitmap_copy(Bitmap *b) {
      32                 :            :         Bitmap *ret;
      33                 :            : 
      34                 :        100 :         ret = bitmap_new();
      35         [ -  + ]:        100 :         if (!ret)
      36                 :          0 :                 return NULL;
      37                 :            : 
      38                 :        100 :         ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps);
      39         [ -  + ]:        100 :         if (!ret->bitmaps)
      40                 :          0 :                 return mfree(ret);
      41                 :            : 
      42                 :        100 :         ret->n_bitmaps = ret->bitmaps_allocated = b->n_bitmaps;
      43                 :        100 :         return ret;
      44                 :            : }
      45                 :            : 
      46                 :        220 : void bitmap_free(Bitmap *b) {
      47         [ +  + ]:        220 :         if (!b)
      48                 :          4 :                 return;
      49                 :            : 
      50                 :        216 :         free(b->bitmaps);
      51                 :        216 :         free(b);
      52                 :            : }
      53                 :            : 
      54                 :        112 : int bitmap_ensure_allocated(Bitmap **b) {
      55                 :            :         Bitmap *a;
      56                 :            : 
      57         [ -  + ]:        112 :         assert(b);
      58                 :            : 
      59         [ +  + ]:        112 :         if (*b)
      60                 :          4 :                 return 0;
      61                 :            : 
      62                 :        108 :         a = bitmap_new();
      63         [ -  + ]:        108 :         if (!a)
      64                 :          0 :                 return -ENOMEM;
      65                 :            : 
      66                 :        108 :         *b = a;
      67                 :            : 
      68                 :        108 :         return 0;
      69                 :            : }
      70                 :            : 
      71                 :        644 : int bitmap_set(Bitmap *b, unsigned n) {
      72                 :            :         uint64_t bitmask;
      73                 :            :         unsigned offset;
      74                 :            : 
      75         [ -  + ]:        644 :         assert(b);
      76                 :            : 
      77                 :            :         /* we refuse to allocate huge bitmaps */
      78         [ +  + ]:        644 :         if (n > BITMAPS_MAX_ENTRY)
      79                 :          4 :                 return -ERANGE;
      80                 :            : 
      81                 :        640 :         offset = BITMAP_NUM_TO_OFFSET(n);
      82                 :            : 
      83         [ +  + ]:        640 :         if (offset >= b->n_bitmaps) {
      84         [ -  + ]:        140 :                 if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
      85                 :          0 :                         return -ENOMEM;
      86                 :            : 
      87                 :        140 :                 b->n_bitmaps = offset + 1;
      88                 :            :         }
      89                 :            : 
      90                 :        640 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
      91                 :            : 
      92                 :        640 :         b->bitmaps[offset] |= bitmask;
      93                 :            : 
      94                 :        640 :         return 0;
      95                 :            : }
      96                 :            : 
      97                 :         24 : void bitmap_unset(Bitmap *b, unsigned n) {
      98                 :            :         uint64_t bitmask;
      99                 :            :         unsigned offset;
     100                 :            : 
     101         [ -  + ]:         24 :         if (!b)
     102                 :          0 :                 return;
     103                 :            : 
     104                 :         24 :         offset = BITMAP_NUM_TO_OFFSET(n);
     105                 :            : 
     106         [ -  + ]:         24 :         if (offset >= b->n_bitmaps)
     107                 :          0 :                 return;
     108                 :            : 
     109                 :         24 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
     110                 :            : 
     111                 :         24 :         b->bitmaps[offset] &= ~bitmask;
     112                 :            : }
     113                 :            : 
     114                 :         40 : bool bitmap_isset(const Bitmap *b, unsigned n) {
     115                 :            :         uint64_t bitmask;
     116                 :            :         unsigned offset;
     117                 :            : 
     118         [ -  + ]:         40 :         if (!b)
     119                 :          0 :                 return false;
     120                 :            : 
     121                 :         40 :         offset = BITMAP_NUM_TO_OFFSET(n);
     122                 :            : 
     123         [ +  + ]:         40 :         if (offset >= b->n_bitmaps)
     124                 :         12 :                 return false;
     125                 :            : 
     126                 :         28 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
     127                 :            : 
     128                 :         28 :         return !!(b->bitmaps[offset] & bitmask);
     129                 :            : }
     130                 :            : 
     131                 :        168 : bool bitmap_isclear(const Bitmap *b) {
     132                 :            :         unsigned i;
     133                 :            : 
     134         [ -  + ]:        168 :         if (!b)
     135                 :          0 :                 return true;
     136                 :            : 
     137         [ +  + ]:        212 :         for (i = 0; i < b->n_bitmaps; i++)
     138         [ +  + ]:         56 :                 if (b->bitmaps[i] != 0)
     139                 :         12 :                         return false;
     140                 :            : 
     141                 :        156 :         return true;
     142                 :            : }
     143                 :            : 
     144                 :       1112 : void bitmap_clear(Bitmap *b) {
     145         [ -  + ]:       1112 :         if (!b)
     146                 :          0 :                 return;
     147                 :            : 
     148                 :       1112 :         b->bitmaps = mfree(b->bitmaps);
     149                 :       1112 :         b->n_bitmaps = 0;
     150                 :       1112 :         b->bitmaps_allocated = 0;
     151                 :            : }
     152                 :            : 
     153                 :       1432 : bool bitmap_iterate(const Bitmap *b, Iterator *i, unsigned *n) {
     154                 :            :         uint64_t bitmask;
     155                 :            :         unsigned offset, rem;
     156                 :            : 
     157         [ -  + ]:       1432 :         assert(i);
     158         [ -  + ]:       1432 :         assert(n);
     159                 :            : 
     160   [ +  +  -  + ]:       1432 :         if (!b || i->idx == BITMAP_END)
     161                 :          8 :                 return false;
     162                 :            : 
     163                 :       1424 :         offset = BITMAP_NUM_TO_OFFSET(i->idx);
     164                 :       1424 :         rem = BITMAP_NUM_TO_REM(i->idx);
     165                 :       1424 :         bitmask = UINT64_C(1) << rem;
     166                 :            : 
     167         [ +  + ]:       9880 :         for (; offset < b->n_bitmaps; offset ++) {
     168         [ +  + ]:       9672 :                 if (b->bitmaps[offset]) {
     169         [ +  + ]:      16640 :                         for (; bitmask; bitmask <<= 1, rem ++) {
     170         [ +  + ]:      16384 :                                 if (b->bitmaps[offset] & bitmask) {
     171                 :       1216 :                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
     172                 :       1216 :                                         i->idx = *n + 1;
     173                 :            : 
     174                 :       1216 :                                         return true;
     175                 :            :                                 }
     176                 :            :                         }
     177                 :            :                 }
     178                 :            : 
     179                 :       8456 :                 rem = 0;
     180                 :       8456 :                 bitmask = 1;
     181                 :            :         }
     182                 :            : 
     183                 :        208 :         i->idx = BITMAP_END;
     184                 :            : 
     185                 :        208 :         return false;
     186                 :            : }
     187                 :            : 
     188                 :        136 : bool bitmap_equal(const Bitmap *a, const Bitmap *b) {
     189                 :            :         size_t common_n_bitmaps;
     190                 :            :         const Bitmap *c;
     191                 :            :         unsigned i;
     192                 :            : 
     193         [ +  + ]:        136 :         if (a == b)
     194                 :          8 :                 return true;
     195                 :            : 
     196         [ +  + ]:        128 :         if (!a != !b)
     197                 :          8 :                 return false;
     198                 :            : 
     199         [ -  + ]:        120 :         if (!a)
     200                 :          0 :                 return true;
     201                 :            : 
     202                 :        120 :         common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
     203         [ -  + ]:        120 :         if (memcmp_safe(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
     204                 :          0 :                 return false;
     205                 :            : 
     206         [ +  + ]:        120 :         c = a->n_bitmaps > b->n_bitmaps ? a : b;
     207         [ +  + ]:        124 :         for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
     208         [ +  + ]:          8 :                 if (c->bitmaps[i] != 0)
     209                 :          4 :                         return false;
     210                 :            : 
     211                 :        116 :         return true;
     212                 :            : }