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