external/gpl2/lvm2/dist/libdm/datastruct/bitset.c

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