Branch data     Line data    Source code

       1                 :            : /*
       2                 :            :  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.  
       3                 :            :  * Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved.
       4                 :            :  *
       5                 :            :  * This file is part of the device-mapper userspace tools.
       6                 :            :  *
       7                 :            :  * This copyrighted material is made available to anyone wishing to use,
       8                 :            :  * modify, copy, or redistribute it subject to the terms and conditions
       9                 :            :  * of the GNU Lesser General Public License v.2.1.
      10                 :            :  *
      11                 :            :  * You should have received a copy of the GNU Lesser General Public License
      12                 :            :  * along with this program; if not, write to the Free Software Foundation,
      13                 :            :  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "dmlib.h"
      17                 :            : 
      18                 :            : /* FIXME: calculate this. */
      19                 :            : #define INT_SHIFT 5
      20                 :            : 
      21                 :      31527 : dm_bitset_t dm_bitset_create(struct dm_pool *mem, unsigned num_bits)
      22                 :            : {
      23                 :      31527 :         unsigned n = (num_bits / DM_BITS_PER_INT) + 2;
      24                 :      31527 :         size_t size = sizeof(int) * n;
      25                 :            :         dm_bitset_t bs;
      26                 :            :         
      27         [ +  - ]:      31527 :         if (mem)
      28                 :      31527 :                 bs = dm_pool_zalloc(mem, size);
      29                 :            :         else
      30                 :          0 :                 bs = dm_malloc(size);
      31                 :            : 
      32         [ -  + ]:      31527 :         if (!bs)
      33                 :          0 :                 return NULL;
      34                 :            : 
      35                 :      31527 :         *bs = num_bits;
      36                 :            : 
      37         [ -  + ]:      31527 :         if (!mem)
      38                 :          0 :                 dm_bit_clear_all(bs);
      39                 :            : 
      40                 :      31527 :         return bs;
      41                 :            : }
      42                 :            : 
      43                 :          0 : void dm_bitset_destroy(dm_bitset_t bs)
      44                 :            : {
      45                 :          0 :         dm_free(bs);
      46                 :          0 : }
      47                 :            : 
      48                 :   53106137 : void dm_bit_union(dm_bitset_t out, dm_bitset_t in1, dm_bitset_t in2)
      49                 :            : {
      50                 :            :         int i;
      51         [ +  + ]:         -1 :         for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--)
      52                 :         -1 :                 out[i] = in1[i] | in2[i];
      53                 :   53106137 : }
      54                 :            : 
      55                 :            : /*
      56                 :            :  * FIXME: slow
      57                 :            :  */
      58                 :  136910336 : static inline int _test_word(uint32_t test, int bit)
      59                 :            : {
      60         [ +  + ]: 1364958720 :         while (bit < (int) DM_BITS_PER_INT) {
      61         [ +  + ]: 1336442880 :                 if (test & (0x1 << bit))
      62                 :  108394496 :                         return bit;
      63                 : 1228048384 :                 bit++;
      64                 :            :         }
      65                 :            : 
      66                 :  136910336 :         return -1;
      67                 :            : }
      68                 :            : 
      69                 :  108596736 : int dm_bit_get_next(dm_bitset_t bs, int last_bit)
      70                 :            : {
      71                 :            :         int bit, word;
      72                 :            :         uint32_t test;
      73                 :            : 
      74                 :  108596736 :         last_bit++;             /* otherwise we'll return the same bit again */
      75                 :            : 
      76                 :            :         /*
      77                 :            :          * bs[0] holds number of bits
      78                 :            :          */
      79         [ +  + ]:  137112576 :         while (last_bit < (int) bs[0]) {
      80                 :  136910336 :                 word = last_bit >> INT_SHIFT;
      81                 :  136910336 :                 test = bs[word + 1];
      82                 :  136910336 :                 bit = last_bit & (DM_BITS_PER_INT - 1);
      83                 :            : 
      84         [ +  + ]:  136910336 :                 if ((bit = _test_word(test, bit)) >= 0)
      85                 :  108394496 :                         return (word * DM_BITS_PER_INT) + bit;
      86                 :            : 
      87                 :   28515840 :                 last_bit = last_bit - (last_bit & (DM_BITS_PER_INT - 1)) +
      88                 :            :                     DM_BITS_PER_INT;
      89                 :            :         }
      90                 :            : 
      91                 :  108596736 :         return -1;
      92                 :            : }
      93                 :            : 
      94                 :     202240 : int dm_bit_get_first(dm_bitset_t bs)
      95                 :            : {
      96                 :     202240 :         return dm_bit_get_next(bs, -1);
      97                 :            : }