LCOV - code coverage report
Current view: top level - basic - bitmap.c (source / functions) Hit Total Coverage
Test: systemd test coverage Lines: 67 81 82.7 %
Date: 2015-07-29 18:47:03 Functions: 9 10 90.0 %

          Line data    Source code
       1             : /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
       2             : 
       3             : /***
       4             :   This file is part of systemd.
       5             : 
       6             :   Copyright 2015 Tom Gundersen
       7             : 
       8             :   systemd is free software; you can redistribute it and/or modify it
       9             :   under the terms of the GNU Lesser General Public License as published by
      10             :   the Free Software Foundation; either version 2.1 of the License, or
      11             :   (at your option) any later version.
      12             : 
      13             :   systemd is distributed in the hope that it will be useful, but
      14             :   WITHOUT ANY WARRANTY; without even the implied warranty of
      15             :   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
      16             :   Lesser General Public License for more details.
      17             : 
      18             :   You should have received a copy of the GNU Lesser General Public License
      19             :   along with systemd; If not, see <http://www.gnu.org/licenses/>.
      20             : ***/
      21             : 
      22             : #include "util.h"
      23             : 
      24             : #include "bitmap.h"
      25             : 
      26             : struct Bitmap {
      27             :         uint64_t *bitmaps;
      28             :         size_t n_bitmaps;
      29             :         size_t bitmaps_allocated;
      30             : };
      31             : 
      32             : /* Bitmaps are only meant to store relatively small numbers
      33             :  * (corresponding to, say, an enum), so it is ok to limit
      34             :  * the max entry. 64k should be plenty. */
      35             : #define BITMAPS_MAX_ENTRY 0xffff
      36             : 
      37             : /* This indicates that we reached the end of the bitmap */
      38             : #define BITMAP_END ((unsigned) -1)
      39             : 
      40             : #define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(uint64_t) * 8))
      41             : #define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(uint64_t) * 8))
      42             : #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
      43             : 
      44           2 : Bitmap *bitmap_new(void) {
      45           2 :         return new0(Bitmap, 1);
      46             : }
      47             : 
      48           2 : void bitmap_free(Bitmap *b) {
      49           2 :         if (!b)
      50           0 :                 return;
      51             : 
      52           2 :         free(b->bitmaps);
      53           2 :         free(b);
      54             : }
      55             : 
      56           2 : int bitmap_ensure_allocated(Bitmap **b) {
      57             :         Bitmap *a;
      58             : 
      59           2 :         assert(b);
      60             : 
      61           2 :         if (*b)
      62           1 :                 return 0;
      63             : 
      64           1 :         a = bitmap_new();
      65           1 :         if (!a)
      66           0 :                 return -ENOMEM;
      67             : 
      68           1 :         *b = a;
      69             : 
      70           1 :         return 0;
      71             : }
      72             : 
      73           8 : int bitmap_set(Bitmap *b, unsigned n) {
      74             :         uint64_t bitmask;
      75             :         unsigned offset;
      76             : 
      77           8 :         assert(b);
      78             : 
      79             :         /* we refuse to allocate huge bitmaps */
      80           8 :         if (n > BITMAPS_MAX_ENTRY)
      81           1 :                 return -ERANGE;
      82             : 
      83           7 :         offset = BITMAP_NUM_TO_OFFSET(n);
      84             : 
      85           7 :         if (offset >= b->n_bitmaps) {
      86           2 :                 if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
      87           0 :                         return -ENOMEM;
      88             : 
      89           2 :                 b->n_bitmaps = offset + 1;
      90             :         }
      91             : 
      92           7 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
      93             : 
      94           7 :         b->bitmaps[offset] |= bitmask;
      95             : 
      96           7 :         return 0;
      97             : }
      98             : 
      99           5 : void bitmap_unset(Bitmap *b, unsigned n) {
     100             :         uint64_t bitmask;
     101             :         unsigned offset;
     102             : 
     103           5 :         if (!b)
     104           0 :                 return;
     105             : 
     106           5 :         offset = BITMAP_NUM_TO_OFFSET(n);
     107             : 
     108           5 :         if (offset >= b->n_bitmaps)
     109           0 :                 return;
     110             : 
     111           5 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
     112             : 
     113           5 :         b->bitmaps[offset] &= ~bitmask;
     114             : }
     115             : 
     116          10 : bool bitmap_isset(Bitmap *b, unsigned n) {
     117             :         uint64_t bitmask;
     118             :         unsigned offset;
     119             : 
     120          10 :         if (!b)
     121           0 :                 return false;
     122             : 
     123          10 :         offset = BITMAP_NUM_TO_OFFSET(n);
     124             : 
     125          10 :         if (offset >= b->n_bitmaps)
     126           3 :                 return false;
     127             : 
     128           7 :         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
     129             : 
     130           7 :         return !!(b->bitmaps[offset] & bitmask);
     131             : }
     132             : 
     133           8 : bool bitmap_isclear(Bitmap *b) {
     134             :         unsigned i;
     135             : 
     136           8 :         assert(b);
     137             : 
     138          19 :         for (i = 0; i < b->n_bitmaps; i++)
     139          14 :                 if (b->bitmaps[i] != 0)
     140           3 :                         return false;
     141             : 
     142           5 :         return true;
     143             : }
     144             : 
     145           1 : void bitmap_clear(Bitmap *b) {
     146           1 :         assert(b);
     147             : 
     148           1 :         b->n_bitmaps = 0;
     149           1 : }
     150             : 
     151           9 : bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
     152             :         uint64_t bitmask;
     153             :         unsigned offset, rem;
     154             : 
     155           9 :         assert(i);
     156           9 :         assert(n);
     157             : 
     158           9 :         if (!b || i->idx == BITMAP_END)
     159           1 :                 return false;
     160             : 
     161           8 :         offset = BITMAP_NUM_TO_OFFSET(i->idx);
     162           8 :         rem = BITMAP_NUM_TO_REM(i->idx);
     163           8 :         bitmask = UINT64_C(1) << rem;
     164             : 
     165          18 :         for (; offset < b->n_bitmaps; offset ++) {
     166          16 :                 if (b->bitmaps[offset]) {
     167         260 :                         for (; bitmask; bitmask <<= 1, rem ++) {
     168         256 :                                 if (b->bitmaps[offset] & bitmask) {
     169           6 :                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
     170           6 :                                         i->idx = *n + 1;
     171             : 
     172           6 :                                         return true;
     173             :                                 }
     174             :                         }
     175             :                 }
     176             : 
     177          10 :                 rem = 0;
     178          10 :                 bitmask = 1;
     179             :         }
     180             : 
     181           2 :         i->idx = BITMAP_END;
     182             : 
     183           2 :         return false;
     184             : }
     185             : 
     186           0 : bool bitmap_equal(Bitmap *a, Bitmap *b) {
     187             : 
     188           0 :         if (!a ^ !b)
     189           0 :                 return false;
     190             : 
     191           0 :         if (!a)
     192           0 :                 return true;
     193             : 
     194           0 :         if (a->n_bitmaps != b->n_bitmaps)
     195           0 :                 return false;
     196             : 
     197           0 :         return memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * a->n_bitmaps) == 0;
     198             : }

Generated by: LCOV version 1.11