libdm/datastruct/bitset.c

   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 dm_bitset_t dm_bitset_create(struct dm_pool *mem, unsigned num_bits)
  22 {
  23         unsigned n = (num_bits / DM_BITS_PER_INT) + 2;
  24         size_t size = sizeof(int) * n;
  25         dm_bitset_t bs;
  26
  27         if (mem)
  28                 bs = dm_pool_zalloc(mem, size);
  29         else
  30                 bs = dm_zalloc(size);
  31
  32         if (!bs)
  33                 return NULL;
  34
  35         *bs = num_bits;
  36
  37         return bs;
  38 }
  39
  40 void dm_bitset_destroy(dm_bitset_t bs)
  41 {
  42         dm_free(bs);
  43 }
  44
  45 int dm_bitset_equal(dm_bitset_t in1, dm_bitset_t in2)
  46 {
  47         int i;
  48
  49         for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--)
  50                 if (in1[i] != in2[i])
  51                         return 0;
  52
  53         return 1;
  54 }
  55
  56 void dm_bit_and(dm_bitset_t out, dm_bitset_t in1, dm_bitset_t in2)
  57 {
  58         int i;
  59
  60         for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--)
  61                 out[i] = in1[i] & in2[i];
  62 }
  63 void dm_bit_union(dm_bitset_t out, dm_bitset_t in1, dm_bitset_t in2)
  64 {
  65         int i;
  66         for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--)
  67                 out[i] = in1[i] | in2[i];
  68 }
  69
  70 static int _test_word(uint32_t test, int bit)
  71 {
  72         uint32_t tb = test >> bit;
  73
  74         return (tb ? ffs(tb) + bit - 1 : -1);
  75 }
  76
  77 int dm_bit_get_next(dm_bitset_t bs, int last_bit)
  78 {
  79         int bit, word;
  80         uint32_t test;
  81
  82         last_bit++;             /* otherwise we'll return the same bit again */
  83
  84         /*
  85          * bs[0] holds number of bits
  86          */
  87         while (last_bit < (int) bs[0]) {
  88                 word = last_bit >> INT_SHIFT;
  89                 test = bs[word + 1];
  90                 bit = last_bit & (DM_BITS_PER_INT - 1);
  91
  92                 if ((bit = _test_word(test, bit)) >= 0)
  93                         return (word * DM_BITS_PER_INT) + bit;
  94
  95                 last_bit = last_bit - (last_bit & (DM_BITS_PER_INT - 1)) +
  96                     DM_BITS_PER_INT;
  97         }
  98
  99         return -1;
 100 }
 101
 102 int dm_bit_get_first(dm_bitset_t bs)
 103 {
 104         return dm_bit_get_next(bs, -1);
 105 }