Home | History | Annotate | Line # | Download | only in datastruct 
      1 /*	$NetBSD: bitset.c,v 1.1.1.1 2008/12/22 00:18:36 haad Exp $	*/
      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 }
    100