[deliverable/linux.git] / fs / btrfs / bit-radix.c

#include <linux/module.h>
#include "bit-radix.h"

#define BIT_ARRAY_BYTES 256
#define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)

int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
{
	unsigned long *bits;
	unsigned long slot;
	int bit_slot;
	int ret;

	slot = bit / BIT_RADIX_BITS_PER_ARRAY;
	bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;

	bits = radix_tree_lookup(radix, slot);
	if (!bits) {
		bits = kmalloc(BIT_ARRAY_BYTES, GFP_NOIO);
		if (!bits)
			return -ENOMEM;
		memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
		bits[0] = slot;
		ret = radix_tree_insert(radix, slot, bits);
		if (ret)
			return ret;
	}
	set_bit(bit_slot, bits + 1);
	return 0;
}

int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
{
	unsigned long *bits;
	unsigned long slot;
	int bit_slot;

	slot = bit / BIT_RADIX_BITS_PER_ARRAY;
	bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;

	bits = radix_tree_lookup(radix, slot);
	if (!bits)
		return 0;
	return test_bit(bit_slot, bits + 1);
}

int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
{
	unsigned long *bits;
	unsigned long slot;
	int bit_slot;
	int i;
	int empty = 1;

	slot = bit / BIT_RADIX_BITS_PER_ARRAY;
	bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;

	bits = radix_tree_lookup(radix, slot);
	if (!bits)
		return 0;
	clear_bit(bit_slot, bits + 1);

	for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
		if (bits[i]) {
			empty = 0;
			break;
		}
	}

	if (empty) {
		bits = radix_tree_delete(radix, slot);
		BUG_ON(!bits);
	}
	return 0;
}

int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
			 int nr)
{
	unsigned long *bits;
	unsigned long *gang[4];
	int found;
	int ret;
	int i;
	int total_found = 0;

	ret = radix_tree_gang_lookup(radix, (void *)&gang, 0, ARRAY_SIZE(gang));
	for (i = 0; i < ret && nr > 0; i++) {
		found = 0;
		bits = gang[i];
		while(nr > 0) {
			found = find_next_bit(bits + 1,
					      BIT_RADIX_BITS_PER_ARRAY,
					      found);
			if (found < BIT_RADIX_BITS_PER_ARRAY) {
				*retbits = bits[0] *
					BIT_RADIX_BITS_PER_ARRAY + found;
				retbits++;
				nr--;
				total_found++;
				found++;
			} else
				break;
		}
	}
	return total_found;
}
Commit	Line	Data
8ef97622 CM	1	#include <linux/module.h>
	2	#include "bit-radix.h"
	3
	4	#define BIT_ARRAY_BYTES 256
	5	#define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
	6
	7	int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
	8	{
	9	unsigned long *bits;
	10	unsigned long slot;
	11	int bit_slot;
	12	int ret;
	13
	14	slot = bit / BIT_RADIX_BITS_PER_ARRAY;
	15	bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
	16
	17	bits = radix_tree_lookup(radix, slot);
	18	if (!bits) {
	19	bits = kmalloc(BIT_ARRAY_BYTES, GFP_NOIO);
	20	if (!bits)
	21	return -ENOMEM;
	22	memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
	23	bits[0] = slot;
	24	ret = radix_tree_insert(radix, slot, bits);
	25	if (ret)
	26	return ret;
	27	}
	28	set_bit(bit_slot, bits + 1);
	29	return 0;
	30	}
	31
	32	int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
	33	{
	34	unsigned long *bits;
	35	unsigned long slot;
	36	int bit_slot;
	37
	38	slot = bit / BIT_RADIX_BITS_PER_ARRAY;
	39	bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
	40
	41	bits = radix_tree_lookup(radix, slot);
	42	if (!bits)
	43	return 0;
	44	return test_bit(bit_slot, bits + 1);
	45	}
	46
	47	int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
	48	{
	49	unsigned long *bits;
	50	unsigned long slot;
	51	int bit_slot;
	52	int i;
	53	int empty = 1;
	54
	55	slot = bit / BIT_RADIX_BITS_PER_ARRAY;
	56	bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
	57
	58	bits = radix_tree_lookup(radix, slot);
	59	if (!bits)
	60	return 0;
	61	clear_bit(bit_slot, bits + 1);
	62
	63	for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
	64	if (bits[i]) {
65	empty = 0;
66	break;
67	}
68	}
69
70	if (empty) {
71	bits = radix_tree_delete(radix, slot);
72	BUG_ON(!bits);
73	}
74	return 0;
75	}
76
77	int find_first_radix_bit(struct radix_tree_root radix, unsigned long retbits,
78	int nr)
79	{
80	unsigned long *bits;
81	unsigned long *gang[4];
82	int found;
83	int ret;
84	int i;
85	int total_found = 0;
86
87	ret = radix_tree_gang_lookup(radix, (void *)&gang, 0, ARRAY_SIZE(gang));
88	for (i = 0; i < ret && nr > 0; i++) {
89	found = 0;
90	bits = gang[i];
91	while(nr > 0) {
92	found = find_next_bit(bits + 1,
93	BIT_RADIX_BITS_PER_ARRAY,
94	found);
95	if (found < BIT_RADIX_BITS_PER_ARRAY) {
96	retbits = bits[0]
97	BIT_RADIX_BITS_PER_ARRAY + found;
98	retbits++;
99	nr--;
100	total_found++;
101	found++;
102	} else
103	break;
104	}
105	}
106	return total_found;
107	}