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