[linux-2.6-block.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)

extern struct kmem_cache *btrfs_bit_radix_cachep;
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 = kmem_cache_alloc(btrfs_bit_radix_cachep, GFP_NOFS);
		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;
	}
	ret = test_and_set_bit(bit_slot, bits + 1);
	if (ret < 0)
		ret = 1;
	return ret;
}

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);
		kmem_cache_free(btrfs_bit_radix_cachep, bits);
	}
	return 0;
}

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

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