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