~ubuntu-branches/ubuntu/wily/btrfs-tools/wily

/*

 * Copyright (C) 2007 Oracle.  All rights reserved.

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public

 * License v2 as published by the Free Software Foundation.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * General Public License for more details.

 *

 * You should have received a copy of the GNU General Public

 * License along with this program; if not, write to the

 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

 * Boston, MA 021110-1307, USA.

 */

#include "kerncompat.h"

#include "radix-tree.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 = malloc(BIT_ARRAY_BYTES);

		if (!bits)

			return -ENOMEM;

		memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));

		bits[0] = slot;

		radix_tree_preload(GFP_NOFS);

		ret = radix_tree_insert(radix, slot, bits);

		radix_tree_preload_end();

		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);

		free(bits);

	}

	return 0;

}

#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)

/**

 * __ffs - find first bit in word.

 * @word: The word to search

 *

 * Undefined if no bit exists, so code should check against 0 first.

 */

static unsigned long __ffs(unsigned long word)

{

	int num = 0;

	if (sizeof(long) == 8 && (word & 0xffffffff) == 0) {

		num += 32;

		word >>= sizeof(long) * 4;

	}

	if ((word & 0xffff) == 0) {

		num += 16;

		word >>= 16;

	}

	if ((word & 0xff) == 0) {

		num += 8;

		word >>= 8;

	}

	if ((word & 0xf) == 0) {

		num += 4;

		word >>= 4;

	}

	if ((word & 0x3) == 0) {

		num += 2;

		word >>= 2;

	}

	if ((word & 0x1) == 0)

		num += 1;

	return num;

}

/**

 * find_next_bit - find the next set bit in a memory region

 * @addr: The address to base the search on

 * @offset: The bitnumber to start searching at

 * @size: The maximum size to search

 */

unsigned long find_next_bit(const unsigned long *addr, unsigned long size,

		unsigned long offset)

{

	const unsigned long *p = addr + BITOP_WORD(offset);

	unsigned long result = offset & ~(BITS_PER_LONG-1);

	unsigned long tmp;

	if (offset >= size)

		return size;

	size -= result;

	offset %= BITS_PER_LONG;

	if (offset) {

		tmp = *(p++);

		tmp &= (~0UL << offset);

		if (size < BITS_PER_LONG)

			goto found_first;

		if (tmp)

			goto found_middle;

		size -= BITS_PER_LONG;

		result += BITS_PER_LONG;

	}

	while (size & ~(BITS_PER_LONG-1)) {

		if ((tmp = *(p++)))

			goto found_middle;

		result += BITS_PER_LONG;

		size -= BITS_PER_LONG;

	}

	if (!size)

		return result;

	tmp = *p;

found_first:

	tmp &= (~0UL >> (BITS_PER_LONG - size));

	if (tmp == 0UL)		/* Are any bits set? */

		return result + size;	/* Nope. */

found_middle:

	return result + __ffs(tmp);

}

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;

}