/* -*- mode: c; c-basic-offset: 8; -*-
 * vim: noexpandtab sw=8 ts=8 sts=0:
 *
 * bitmap.c
 *
 * Basic bitmap routines for the OCFS2 userspace library.
 *
 * Copyright (C) 2004 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, version 2,  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.
 */

#define _XOPEN_SOURCE 600 /* Triggers magic in features.h */
#define _LARGEFILE64_SOURCE

#include <string.h>
#include <limits.h>
#include <inttypes.h>

#include "ocfs2/ocfs2.h"
#include "ocfs2/bitops.h"

#include "bitmap.h"


/* The public API */

void ocfs2_bitmap_free(ocfs2_bitmap *bitmap)
{
	struct rb_node *node;
	struct ocfs2_bitmap_region *br;

	/*
	 * If the bitmap needs to do extra cleanup of region,
	 * it should have done it in destroy_notify.  Same with the
	 * private pointers.
	 */
	if (bitmap->b_ops->destroy_notify)
		(*bitmap->b_ops->destroy_notify)(bitmap);

	while ((node = rb_first(&bitmap->b_regions)) != NULL) {
		br = rb_entry(node, struct ocfs2_bitmap_region, br_node);

		rb_erase(&br->br_node, &bitmap->b_regions);
		ocfs2_bitmap_free_region(br);
	}

	ocfs2_free(&bitmap->b_description);
	ocfs2_free(&bitmap);
}

errcode_t ocfs2_bitmap_set(ocfs2_bitmap *bitmap, uint64_t bitno,
			   int *oldval)
{
	errcode_t ret;
	int old_tmp;

	if (bitno >= bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	ret = (*bitmap->b_ops->set_bit)(bitmap, bitno, &old_tmp);
	if (ret)
		return ret;

	if (!old_tmp)
		bitmap->b_set_bits++;
	if (oldval)
		*oldval = old_tmp;

	return 0;
}

errcode_t ocfs2_bitmap_clear(ocfs2_bitmap *bitmap, uint64_t bitno,
			     int *oldval)
{
	errcode_t ret;
	int old_tmp;

	if (bitno >= bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	ret = (*bitmap->b_ops->clear_bit)(bitmap, bitno, &old_tmp);
	if (ret)
		return ret;

	if (old_tmp)
		bitmap->b_set_bits--;
	if (oldval)
		*oldval = old_tmp;

	return 0;
}

errcode_t ocfs2_bitmap_test(ocfs2_bitmap *bitmap, uint64_t bitno,
			    int *val)
{
	errcode_t ret;

	if (bitno >= bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	ret = (*bitmap->b_ops->test_bit)(bitmap, bitno, val);

	return ret;
}

errcode_t ocfs2_bitmap_find_next_set(ocfs2_bitmap *bitmap,
				     uint64_t start, 
				     uint64_t *found)
{
	if (start >= bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	return (*bitmap->b_ops->find_next_set)(bitmap, start, found);
}

errcode_t ocfs2_bitmap_find_next_clear(ocfs2_bitmap *bitmap,
				       uint64_t start, 
				       uint64_t *found)
{
	if (start >= bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	return (*bitmap->b_ops->find_next_clear)(bitmap, start, found);
}

/* kind of poorly named, but I couldn't come up with something nicer */
errcode_t ocfs2_bitmap_alloc_range(ocfs2_bitmap *bitmap, uint64_t min,
				   uint64_t len, uint64_t *first_bit,
				   uint64_t *bits_found)
{
	errcode_t ret;

	if (min == 0 || len == 0 || len >= bitmap->b_total_bits || min > len)
		return OCFS2_ET_INVALID_ARGUMENT;

	ret = (*bitmap->b_ops->alloc_range)(bitmap, min, len, first_bit,
					    bits_found);
	if (ret == 0 && *bits_found < min)
		abort();

	return ret;
}

errcode_t ocfs2_bitmap_clear_range(ocfs2_bitmap *bitmap, uint64_t len, 
				   uint64_t first_bit)
{
	if (len == 0 || len + first_bit > bitmap->b_total_bits)
		return OCFS2_ET_INVALID_ARGUMENT;

	return (*bitmap->b_ops->clear_range)(bitmap, len, first_bit);
}

errcode_t ocfs2_bitmap_read(ocfs2_bitmap *bitmap)
{
	if (!bitmap->b_ops->read_bitmap)
		return OCFS2_ET_INVALID_ARGUMENT;

	/* FIXME: Some sane error, or handle in ->read_bitmap() */
	if (rb_first(&bitmap->b_regions))
		return OCFS2_ET_INVALID_BIT;

	return (*bitmap->b_ops->read_bitmap)(bitmap);
}

errcode_t ocfs2_bitmap_write(ocfs2_bitmap *bitmap)
{
	if (!bitmap->b_ops->write_bitmap)
		return OCFS2_ET_INVALID_ARGUMENT;

	return (*bitmap->b_ops->write_bitmap)(bitmap);
}

uint64_t ocfs2_bitmap_get_set_bits(ocfs2_bitmap *bitmap)
{
	return bitmap->b_set_bits;
}

/*
 * The remaining functions are private to the library.
 */

/*
 * This function is private to the library.  Bitmap subtypes will
 * use this to allocate their structure, but their b_ops will
 * determine how they work.
 */
errcode_t ocfs2_bitmap_new(ocfs2_filesys *fs,
			   uint64_t total_bits,
			   const char *description,
			   struct ocfs2_bitmap_operations *ops,
			   void *private_data,
			   ocfs2_bitmap **ret_bitmap)
{
	errcode_t ret;
	ocfs2_bitmap *bitmap;

	if (!ops->set_bit || !ops->clear_bit || !ops->test_bit)
		return OCFS2_ET_INVALID_ARGUMENT;

	ret = ocfs2_malloc0(sizeof(struct _ocfs2_bitmap), &bitmap);
	if (ret)
		return ret;

	bitmap->b_fs = fs;
	bitmap->b_total_bits = total_bits;
	bitmap->b_ops = ops;
	bitmap->b_regions = RB_ROOT;
	bitmap->b_private = private_data;
	if (description) {
		ret = ocfs2_malloc0(sizeof(char) *
				    (strlen(description) + 1),
				    &bitmap->b_description);
		if (ret)
			goto out_free;

		strcpy(bitmap->b_description, description);
	}

	*ret_bitmap = bitmap;
	return 0;

out_free:
	ocfs2_free(&bitmap);

	return ret;
}

static size_t ocfs2_align_total(int total_bits)
{
	return (total_bits + 7) / 8;
}

errcode_t ocfs2_bitmap_alloc_region(ocfs2_bitmap *bitmap,
				    uint64_t start_bit,
				    int bitmap_start,
				    int total_bits,
				    struct ocfs2_bitmap_region **ret_br)
{
	errcode_t ret;
	struct ocfs2_bitmap_region *br;

	if (total_bits < 0)
		return OCFS2_ET_INVALID_BIT;

	ret = ocfs2_malloc0(sizeof(struct ocfs2_bitmap_region), &br);
	if (ret)
		return ret;


	br->br_start_bit = start_bit;
	br->br_bitmap_start = bitmap_start;
	br->br_valid_bits = total_bits;
	br->br_total_bits = total_bits + bitmap_start;
	br->br_bytes = ocfs2_align_total(br->br_total_bits);

	ret = ocfs2_malloc0(br->br_bytes, &br->br_bitmap);
	if (ret)
		ocfs2_free(&br);
	else
		*ret_br = br;

	return ret;
}

void ocfs2_bitmap_free_region(struct ocfs2_bitmap_region *br)
{
	if (br->br_bitmap)
		ocfs2_free(&br->br_bitmap);
	ocfs2_free(&br);
}

errcode_t ocfs2_bitmap_realloc_region(ocfs2_bitmap *bitmap,
				      struct ocfs2_bitmap_region *br,
				      int total_bits)
{
	errcode_t ret;
	size_t new_bytes;

	if ((br->br_start_bit + total_bits) > bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	new_bytes = ocfs2_align_total(total_bits + br->br_bitmap_start);

	if (new_bytes > br->br_bytes) {
		ret = ocfs2_realloc0(new_bytes, &br->br_bitmap, br->br_bytes);
		if (ret)
			return ret;
		br->br_bytes = new_bytes;
	}
	br->br_valid_bits = total_bits;
	br->br_total_bits = total_bits + br->br_bitmap_start;

	return 0;
}

errcode_t ocfs2_bitmap_foreach_region(ocfs2_bitmap *bitmap,
				      ocfs2_bitmap_foreach_func func,
				      void *private_data)
{
	struct ocfs2_bitmap_region *br;
	struct rb_node *node;
	errcode_t ret = 0;

	for (node = rb_first(&bitmap->b_regions); node; node = rb_next(node)) {
		br = rb_entry(node, struct ocfs2_bitmap_region, br_node);

		ret = func(br, private_data);
		if (ret == OCFS2_ET_ITERATION_COMPLETE) {
			ret = 0;
			break;
		}
		if (ret)
			break;
	}

	return ret;
}

/*
 * Attempt to merge two regions.  If the merge is successful, 0 will
 * be returned and prev will be the only valid region.  Next will
 * be freed.
 */
static errcode_t ocfs2_bitmap_merge_region(ocfs2_bitmap *bitmap,
					   struct ocfs2_bitmap_region *prev,
					   struct ocfs2_bitmap_region *next)
{
	errcode_t ret;
	uint64_t new_bits;
	size_t prev_bytes;
	uint8_t *pbm, *nbm, offset, diff;

	if ((prev->br_start_bit + prev->br_valid_bits) !=
	    next->br_start_bit)
		return OCFS2_ET_INVALID_BIT;

	if (bitmap->b_ops->merge_region &&
	    !(*bitmap->b_ops->merge_region)(bitmap, prev, next))
		return OCFS2_ET_INVALID_BIT;

	/* XXX: We don't support merge if the bitmap isn't aligned now. */
	if (prev->br_bitmap_start || next->br_bitmap_start)
		return OCFS2_ET_INVALID_BIT;

	new_bits = (uint64_t)(prev->br_total_bits) +
		(uint64_t)(next->br_total_bits);
	if (new_bits > INT_MAX)
		return OCFS2_ET_INVALID_BIT;

	/* grab before realloc changes them */
	prev_bytes = prev->br_bytes;
	offset = prev->br_total_bits % 8;

	ret = ocfs2_bitmap_realloc_region(bitmap, prev, (int)new_bits);
	if (ret)
		return ret;

	/* if prev's last bit ends on a byte boundary then we can just
	 * copy everything over */
	if (offset == 0) {
		memcpy(prev->br_bitmap + prev_bytes, next->br_bitmap, 
				next->br_bytes);
		goto done;
	}

	/* otherwise we have to shift next in.  we're about to free
	 * next, so we consume it as we go. */
	pbm = &prev->br_bitmap[prev_bytes - 1];
	nbm = &next->br_bitmap[0];
	diff = 8 - offset;
	while(next->br_bytes-- && next->br_total_bits > 0) {
		/* mask off just the offset bytes in the prev */
		*pbm &= ((1 << offset) - 1);
		/* move 'diff' LSB from next into prevs MSB */
		*pbm |= (*nbm & ((1 << diff) - 1)) << offset;
		pbm++;
		next->br_total_bits -= diff;

		if (next->br_total_bits > 0) {
			/* then set prev's LSB to the next offset MSB.  this relies
			 * on 0s being shifted into the MSB */
			*pbm = *nbm >> diff;
			nbm++;
			next->br_total_bits -= offset;
		}
	}

done:
	prev->br_set_bits = prev->br_set_bits + next->br_set_bits;
	rb_erase(&next->br_node, &bitmap->b_regions);
	ocfs2_bitmap_free_region(next);

	return 0;
}

/* 
 * Find a bitmap_region in the tree that intersects the bit region
 * that is passed in.  
 *
 * _p and _parent are set so that callers can use rb_link_node and 
 * rb_insert_color to insert a node after finding that their bit
 * wasn't found.
 *
 * _next is only used if a bitmap_region isn't found.  it is set
 * to the next node in the tree greater than the bitmap range
 * that was searched.
 */
static
struct ocfs2_bitmap_region *ocfs2_bitmap_lookup(ocfs2_bitmap *bitmap, 
						uint64_t bitno, 
						uint64_t total_bits, 
						struct rb_node ***ret_p,
						struct rb_node **ret_parent,
						struct rb_node **ret_next)
{
	struct rb_node **p = &bitmap->b_regions.rb_node;
	struct rb_node *parent = NULL, *last_left = NULL;
	struct ocfs2_bitmap_region *br = NULL;

	while (*p)
	{
		parent = *p;
		br = rb_entry(parent, struct ocfs2_bitmap_region, br_node);

		if (bitno + total_bits <= br->br_start_bit) {
			last_left = parent;
			p = &(*p)->rb_left;
			br = NULL;
		} else if (bitno >= (br->br_start_bit + br->br_valid_bits)) {
			p = &(*p)->rb_right;
			br = NULL;
		} else
			break;
	}
	if (ret_p != NULL)
		*ret_p = p;
	if (ret_parent != NULL)
		*ret_parent = parent;
	if (br == NULL && ret_next != NULL)
		*ret_next = last_left;
	return br;
}

errcode_t ocfs2_bitmap_insert_region(ocfs2_bitmap *bitmap,
				     struct ocfs2_bitmap_region *br)
{
	struct ocfs2_bitmap_region *br_tmp;
	struct rb_node **p, *parent, *node;

	if (br->br_start_bit > bitmap->b_total_bits)
		return OCFS2_ET_INVALID_BIT;

	/* we shouldn't find an existing region that intersects our new one */
	br_tmp = ocfs2_bitmap_lookup(bitmap, br->br_start_bit, 
				     br->br_valid_bits, &p, &parent, NULL);
	if (br_tmp)
		return OCFS2_ET_INVALID_BIT;

	rb_link_node(&br->br_node, parent, p);
	rb_insert_color(&br->br_node, &bitmap->b_regions);

	/* try to merge our new extent with its neighbours in the tree */

	node = rb_prev(&br->br_node);
	if (node) {
		br_tmp = rb_entry(node, struct ocfs2_bitmap_region, br_node);
		ocfs2_bitmap_merge_region(bitmap, br_tmp, br);
		br = br_tmp;
	}

	node = rb_next(&br->br_node);
	if (node != NULL) {
		br_tmp = rb_entry(node, struct ocfs2_bitmap_region, br_node);
		ocfs2_bitmap_merge_region(bitmap, br, br_tmp);
	}

	return 0;
}

static int set_generic_shared(ocfs2_bitmap *bitmap, 
			      struct ocfs2_bitmap_region *br,
			      uint64_t bitno)
{
	int old_tmp;

	old_tmp = ocfs2_set_bit(bitno - br->br_start_bit + br->br_bitmap_start,
				br->br_bitmap);
	if (!old_tmp) {
		br->br_set_bits++;
		if (bitmap->b_ops->bit_change_notify)
			(*bitmap->b_ops->bit_change_notify)(bitmap, br, bitno,
							    1);
	}
	return old_tmp;
}

/*
 * Helper functions for the most generic of bitmaps.  If there is no
 * memory allocated for the bit, it fails.
 */
errcode_t ocfs2_bitmap_set_generic(ocfs2_bitmap *bitmap, uint64_t bitno,
				   int *oldval)
{
	struct ocfs2_bitmap_region *br;
	int old_tmp;
	
	br = ocfs2_bitmap_lookup(bitmap, bitno, 1, NULL, NULL, NULL);
	if (!br)
		return OCFS2_ET_INVALID_BIT;

	old_tmp = set_generic_shared(bitmap, br, bitno);
	if (oldval)
		*oldval = old_tmp;

	return 0;
}

static int clear_generic_shared(ocfs2_bitmap *bitmap, 
				struct ocfs2_bitmap_region *br,
				uint64_t bitno)
{
	int old_tmp;

	old_tmp = ocfs2_clear_bit(bitno - br->br_start_bit +
				  br->br_bitmap_start,
				  br->br_bitmap);
	if (old_tmp) {
		br->br_set_bits--;
		if (bitmap->b_ops->bit_change_notify)
			(*bitmap->b_ops->bit_change_notify)(bitmap, br, bitno,
							    0);
	}

	return old_tmp;
}

errcode_t ocfs2_bitmap_clear_generic(ocfs2_bitmap *bitmap,
				     uint64_t bitno, int *oldval)
{
	struct ocfs2_bitmap_region *br;
	int old_tmp;
	
	br = ocfs2_bitmap_lookup(bitmap, bitno, 1, NULL, NULL, NULL);
	if (!br)
		return OCFS2_ET_INVALID_BIT;

	old_tmp = clear_generic_shared(bitmap, br, bitno);
	if (oldval)
		*oldval = old_tmp;

	return 0;
}

errcode_t ocfs2_bitmap_test_generic(ocfs2_bitmap *bitmap,
				    uint64_t bitno, int *val)
{
	struct ocfs2_bitmap_region *br;
	
	br = ocfs2_bitmap_lookup(bitmap, bitno, 1, NULL, NULL, NULL);
	if (!br)
		return OCFS2_ET_INVALID_BIT;

	*val = ocfs2_test_bit(bitno - br->br_start_bit + br->br_bitmap_start,
			      br->br_bitmap) ? 1 : 0;
	return 0;
}

errcode_t ocfs2_bitmap_find_next_set_generic(ocfs2_bitmap *bitmap,
					     uint64_t start,
					     uint64_t *found)
{
	struct ocfs2_bitmap_region *br;
	struct rb_node *node = NULL;
	int offset, ret;

	/* start from either the node whose's br contains the bit or 
	 * the next greatest node in the tree */
	br = ocfs2_bitmap_lookup(bitmap, start, 1, NULL, NULL, &node);
	if (br)
		node = &br->br_node;

	for (; node != NULL; node = rb_next(node)) {
		br = rb_entry(node, struct ocfs2_bitmap_region, br_node);

		if (start > br->br_start_bit)
			offset = start - br->br_start_bit;
		else
			offset = 0;

		ret = ocfs2_find_next_bit_set(br->br_bitmap,
					      br->br_total_bits,
					      offset + br->br_bitmap_start);
		if (ret != br->br_total_bits) {
			*found = br->br_start_bit + ret - br->br_bitmap_start;
			return 0;
		}
	}

	return OCFS2_ET_BIT_NOT_FOUND;
}

errcode_t ocfs2_bitmap_find_next_clear_generic(ocfs2_bitmap *bitmap,
					       uint64_t start,
					       uint64_t *found)
{
	struct ocfs2_bitmap_region *br;
	struct rb_node *node = NULL;
	int offset, ret;

	/* start from either the node whose's br contains the bit or 
	 * the next greatest node in the tree */
	br = ocfs2_bitmap_lookup(bitmap, start, 1, NULL, NULL, &node);
	if (br)
		node = &br->br_node;

	for (; node != NULL; node = rb_next(node)) {
		br = rb_entry(node, struct ocfs2_bitmap_region, br_node);

		if (start > br->br_start_bit)
			offset = start - br->br_start_bit;
		else
			offset = 0;

		ret = ocfs2_find_next_bit_clear(br->br_bitmap,
						br->br_total_bits,
						offset + br->br_bitmap_start);
		if (ret != br->br_total_bits) {
			*found = br->br_start_bit + ret - br->br_bitmap_start;
			return 0;
		}
	}

	return OCFS2_ET_BIT_NOT_FOUND;
}

struct alloc_range_args {
	ocfs2_bitmap	*ar_bitmap;
	uint64_t	ar_min_len;
	uint64_t	ar_len;
	uint64_t	ar_first_bit;
	uint64_t	ar_bits_found;
	errcode_t	ar_ret;
};

/* Our strategy here to aid discontiguous allocation is to track the
 * largest free regions (which still fit within ar_min_len) and if the
 * max allocation fails, fall back to returning one of those. */
static errcode_t alloc_range_func(struct ocfs2_bitmap_region *br,
				  void *private_data)
{
	struct alloc_range_args *ar = private_data;
	errcode_t ret = 0;
	uint64_t best_start = UINT64_MAX, best_len = 0;
	int start, end;

	if ((br->br_valid_bits - br->br_set_bits) < ar->ar_min_len)
		goto out;

	for (start = br->br_bitmap_start;
	     start + ar->ar_min_len <= br->br_total_bits;) {
		start = ocfs2_find_next_bit_clear(br->br_bitmap,
						  br->br_total_bits,
						  start);
		if (start == br->br_total_bits)
			break;

		/* avoiding start + 1 here so that start at total_bits - 1
		 * just works out */
		end = ocfs2_find_next_bit_set(br->br_bitmap,
					      br->br_total_bits,
					      start);

		/* We've found a region large enough to hold our max. */
		if ((end - start) >= ar->ar_len) {
			end = start + ar->ar_len;
			goto found;
		}

		if ((end - start) > best_len) {
			best_len = end - start;
			best_start = start;
		}

		start = end + 1;
	}

	/* Nothing found at all */
	if (best_start == UINT64_MAX || best_len < ar->ar_min_len)
		goto out;

	/* Best fit works */
	start = best_start;
	end = best_start + best_len;
found:
	ar->ar_first_bit = br->br_start_bit + start - br->br_bitmap_start;
	ar->ar_bits_found = end - start;

	for (; start < end; start++)
		set_generic_shared(ar->ar_bitmap, br,
				br->br_start_bit + start - br->br_bitmap_start);

	ar->ar_ret = 0;
	ret = OCFS2_ET_ITERATION_COMPLETE;
out:
	return ret;
}

errcode_t ocfs2_bitmap_alloc_range_generic(ocfs2_bitmap *bitmap,
					   uint64_t min_len,
					   uint64_t len,
					   uint64_t *first_bit,
					   uint64_t *bits_found)
{
	errcode_t ret;
	struct alloc_range_args ar = { 
		.ar_bitmap = bitmap,
		.ar_min_len = min_len,
		.ar_len = len,
		.ar_ret = OCFS2_ET_BIT_NOT_FOUND,
	};

	ret = ocfs2_bitmap_foreach_region(bitmap, alloc_range_func,
					  &ar);
	if (ret == 0)
		ret = ar.ar_ret;

	if (ret == 0) {
		*first_bit = ar.ar_first_bit;
		*bits_found = ar.ar_bits_found;
	}

	return ret;
}

errcode_t ocfs2_bitmap_clear_range_generic(ocfs2_bitmap *bitmap,
					   uint64_t len,
					   uint64_t first_bit)
{
	struct ocfs2_bitmap_region *br;
	uint64_t end;

	br = ocfs2_bitmap_lookup(bitmap, first_bit, len, NULL, NULL, NULL);
	if (!br)
		return OCFS2_ET_INVALID_BIT;

	for (end = first_bit + len; first_bit < end; first_bit++)
		clear_generic_shared(bitmap, br, first_bit);

	return 0;
}

/*
 * Helper functions for a bitmap with holes in it.
 * If a bit doesn't have memory allocated for it, we allocate.
 */
errcode_t ocfs2_bitmap_set_holes(ocfs2_bitmap *bitmap,
				 uint64_t bitno, int *oldval)
{
	errcode_t ret;
	struct ocfs2_bitmap_region *br;

	if (!ocfs2_bitmap_set_generic(bitmap, bitno, oldval))
		return 0;

	ret = ocfs2_bitmap_alloc_region(bitmap, bitno, 0, 1, &br);
	if (ret)
		return ret;

	ret = ocfs2_bitmap_insert_region(bitmap, br);
	if (ret)
		return ret;

	return ocfs2_bitmap_set_generic(bitmap, bitno, oldval);
}

errcode_t ocfs2_bitmap_clear_holes(ocfs2_bitmap *bitmap,
				   uint64_t bitno, int *oldval)
{
	errcode_t ret;
	struct ocfs2_bitmap_region *br;

	if (!ocfs2_bitmap_clear_generic(bitmap, bitno, oldval))
		return 0;

	ret = ocfs2_bitmap_alloc_region(bitmap, bitno, 0, 1, &br);
	if (ret)
		return ret;

	ret = ocfs2_bitmap_insert_region(bitmap, br);

	return ret;
}

errcode_t ocfs2_bitmap_test_holes(ocfs2_bitmap *bitmap,
				  uint64_t bitno, int *val)
{
	if (ocfs2_bitmap_test_generic(bitmap, bitno, val))
		*val = 0;

	return 0;
}

errcode_t ocfs2_bitmap_find_next_set_holes(ocfs2_bitmap *bitmap, 
					   uint64_t start,
					   uint64_t *found)
{
	return ocfs2_bitmap_find_next_set_generic(bitmap, start, found);
}

errcode_t ocfs2_bitmap_find_next_clear_holes(ocfs2_bitmap *bitmap,
					     uint64_t start,
					     uint64_t *found)
{
	struct ocfs2_bitmap_region *br;
	struct rb_node *node = NULL;
	uint64_t seen;
	int offset, ret;

	/* start from either the node whose's br contains the bit or 
	 * the next greatest node in the tree */
	br = ocfs2_bitmap_lookup(bitmap, start, 1, NULL, NULL, &node);
	if (br)
		node = &br->br_node;
	else if (!node) {
		/* There was nothing past start */
		*found = start;
		return 0;
	}

	seen = start;
	for (; node != NULL; node = rb_next(node)) {
		br = rb_entry(node, struct ocfs2_bitmap_region, br_node);

		/* Did we find a hole? */
		if (seen < br->br_start_bit) {
			*found = seen;
			return 0;
		}

		if (start > br->br_start_bit)
			offset = start - br->br_start_bit;
		else
			offset = 0;

		ret = ocfs2_find_next_bit_clear(br->br_bitmap,
						br->br_total_bits,
						offset + br->br_bitmap_start);
		if (ret != br->br_total_bits) {
			*found = br->br_start_bit + ret - br->br_bitmap_start;
			return 0;
		}
		seen = br->br_start_bit + br->br_valid_bits;
	}

	return OCFS2_ET_BIT_NOT_FOUND;
}

static struct ocfs2_bitmap_operations global_cluster_ops = {
	.set_bit		= ocfs2_bitmap_set_generic,
	.clear_bit		= ocfs2_bitmap_clear_generic,
	.test_bit		= ocfs2_bitmap_test_generic,
	.find_next_set		= ocfs2_bitmap_find_next_set_generic,
	.find_next_clear	= ocfs2_bitmap_find_next_clear_generic,
	.alloc_range		= ocfs2_bitmap_alloc_range_generic,
	.clear_range		= ocfs2_bitmap_clear_range_generic,
};

errcode_t ocfs2_cluster_bitmap_new(ocfs2_filesys *fs,
				   const char *description,
				   ocfs2_bitmap **ret_bitmap)
{
	errcode_t ret;
	ocfs2_bitmap *bitmap;
	uint64_t max_bits, num_bits, bitoff, alloc_bits;
	struct ocfs2_bitmap_region *br;

	num_bits = fs->fs_clusters;
	ret = ocfs2_bitmap_new(fs,
			       num_bits,
			       description ? description :
			       "Generic cluster bitmap",
			       &global_cluster_ops,
			       NULL,
			       &bitmap);
	if (ret)
		return ret;

	bitoff = 0;
	max_bits = INT_MAX - (fs->fs_clustersize - 1);
	while (bitoff < num_bits) {
		alloc_bits = num_bits;
		if (num_bits > max_bits)
			alloc_bits = max_bits;
		ret = ocfs2_bitmap_alloc_region(bitmap, bitoff, 0,
						alloc_bits, &br);
		if (ret) {
			ocfs2_bitmap_free(bitmap);
			return ret;
		}

		ret = ocfs2_bitmap_insert_region(bitmap, br);
		if (ret) {
			ocfs2_bitmap_free_region(br);
			ocfs2_bitmap_free(bitmap);
			return ret;
		}

		bitoff += alloc_bits;
	}

	*ret_bitmap = bitmap;

	return 0;
}


static struct ocfs2_bitmap_operations global_block_ops = {
	.set_bit		= ocfs2_bitmap_set_holes,
	.clear_bit		= ocfs2_bitmap_clear_holes,
	.test_bit		= ocfs2_bitmap_test_holes,
	.find_next_set		= ocfs2_bitmap_find_next_set_holes,
	.find_next_clear	= ocfs2_bitmap_find_next_clear_holes,
	/* XXX can't allocate a range yet, would need to fill holes and merge
	 * with adjacent */
};

errcode_t ocfs2_block_bitmap_new(ocfs2_filesys *fs,
				 const char *description,
				 ocfs2_bitmap **ret_bitmap)
{
	errcode_t ret;
	ocfs2_bitmap *bitmap;

	ret = ocfs2_bitmap_new(fs,
			       fs->fs_blocks,
			       description ? description :
			       "Generic block bitmap",
			       &global_block_ops,
			       NULL,
			       &bitmap);
	if (ret)
		return ret;

	*ret_bitmap = bitmap;

	return 0;
}


#ifdef DEBUG_EXE
#include <stdlib.h>
#include <getopt.h>
#include <limits.h>

static uint64_t read_number(const char *num)
{
	uint64_t val;
	char *ptr;

	val = strtoull(num, &ptr, 0);
	if (!ptr || *ptr)
		return 0;

	return val;
}

static void print_usage(void)
{
	fprintf(stderr,
		"debug_bitmap [-a] <filename>\n");
}

extern int opterr, optind;
extern char *optarg;

static void dump_regions(ocfs2_bitmap *bitmap)
{
	struct ocfs2_bitmap_region *br;
	struct rb_node *node;

	fprintf(stdout, "Bitmap \"%s\": total = %"PRIu64", set = %"PRIu64"\n",
		bitmap->b_description, bitmap->b_total_bits,
		bitmap->b_set_bits);

	for (node = rb_first(&bitmap->b_regions);node; node = rb_next(node)) {
		br = rb_entry(node, struct ocfs2_bitmap_region, br_node);

		fprintf(stdout,
			"(start: %"PRIu64", n: %d, set: %d)\n",
			br->br_start_bit, br->br_valid_bits,
			br->br_set_bits);
	}
}

static void print_bitmap(ocfs2_bitmap *bitmap)
{
	uint64_t bitno;
	uint64_t gap_start = 0;  /* GCC is dumb */
	errcode_t ret;
	int val, gap;

	gap = 0;
	for (bitno = 0; bitno < bitmap->b_total_bits; bitno++) {
		ret = ocfs2_bitmap_test(bitmap, bitno, &val);
		if (ret) {
			if (ret == OCFS2_ET_INVALID_BIT) {
				if (!gap) {
					gap = 1;
					gap_start = bitno;
				}
				continue;
			}
			com_err("print_bitmap", ret,
				"while testing bit %"PRIu64"\n", bitno);
			break;
		}
		if (gap) {
			fprintf(stdout,
				"\nGap of length %"PRIu64" at %"PRIu64"\n",
				bitno - gap_start, gap_start);
			gap = bitno % 72;
			gap += gap / 8;
			for (; gap; gap--)
				fprintf(stdout, " ");
			fflush(stdout);
		} else {
			if (bitno && !(bitno % 72))
				fprintf(stdout, "\n");
			else if (bitno && !(bitno % 8))
				fprintf(stdout, " ");
		}
		fprintf(stdout, "%d", val);
		fflush(stdout);
	}

	if ((bitno - 1) % 72)
		fprintf(stdout, "\n");
}

static int try_op(ocfs2_bitmap *bitmap,
		  errcode_t (*func)(ocfs2_bitmap *bitmap,
				    uint64_t bitno,
				    int *val),
		  char *bit_val, int *ret_val)
{
	errcode_t ret;
	uint64_t bitno;
	char *ptr;

	if (!bit_val) {
		fprintf(stderr, "You must provide a bit offset\n");
		return 1;
	}

	bitno = read_number(bit_val);
	if (!bitno) {
		for (ptr = bit_val; *ptr; ptr++) {
			if (*ptr != '0')
				break;
		}
		if ((ptr == bit_val) || *ptr) {
			fprintf(stderr, "Invalid bit offset: %s\n",
				bit_val);
			return 1;
		}
	}

	ret = (*func)(bitmap, bitno, ret_val);
	if (ret) {
		com_err("try_op", ret, "while setting bit %"PRIu64"\n", bitno);
		return 1;
	}

	return 0;
}

static int try_op64(ocfs2_bitmap *bitmap,
		    errcode_t (*func)(ocfs2_bitmap *bitmap,
				      uint64_t bitno,
				      uint64_t *val),
		    char *bit_val, uint64_t *ret_val)
{
	errcode_t ret;
	uint64_t bitno;
	char *ptr;

	if (!bit_val) {
		fprintf(stderr, "You must provide a bit offset\n");
		return 1;
	}

	bitno = read_number(bit_val);
	if (!bitno) {
		for (ptr = bit_val; *ptr; ptr++) {
			if (*ptr != '0')
				break;
		}
		if ((ptr == bit_val) || *ptr) {
			fprintf(stderr, "Invalid bit offset: %s\n",
				bit_val);
			return 1;
		}
	}

	ret = (*func)(bitmap, bitno, ret_val);
	if (ret) {
		com_err("try_op64", ret, "while setting bit %"PRIu64"\n", bitno);
		return 1;
	}

	return 0;
}


static void run_test(ocfs2_bitmap *bitmap)
{
	char buf[256];
	char *ptr, *cmd;
	uint64_t val64;
	int val;

	while (1) {
		fprintf(stdout, "Command: ");
		fflush(stdout);

		if (!fgets(buf, sizeof(buf), stdin))
			break;

		ptr = buf + strlen(buf) - 1;
		if (*ptr == '\n')
			*ptr = '\0';

		for (cmd = buf; (*cmd == ' ') || (*cmd == '\t'); cmd++);

		if (!(*cmd))
			continue;

		ptr = strchr(cmd, ' ');
		if (ptr) {
			*ptr = '\0';
			ptr++;
		}

		if (!strcmp(cmd, "set")) {
			try_op(bitmap, ocfs2_bitmap_set, ptr, NULL);
		} else if (!strcmp(cmd, "clear")) {
			try_op(bitmap, ocfs2_bitmap_clear, ptr, NULL);
		} else if (!strcmp(cmd, "test")) {
			if (!try_op(bitmap, ocfs2_bitmap_test, ptr,
				    &val)) {
				fprintf(stdout, "Bit %s is %s\n",
					ptr, val ? "set" : "clear");
			}
		} else if (!strcmp(cmd, "fns")) {
			if (!try_op64(bitmap,
				      ocfs2_bitmap_find_next_set,
				      ptr, &val64)) {
				fprintf(stdout, "Found %"PRIu64"\n",
					val64);
			}
		} else if (!strcmp(cmd, "fnc")) {
			if (!try_op64(bitmap,
				      ocfs2_bitmap_find_next_clear,
				      ptr, &val64)) {
				fprintf(stdout, "Found %"PRIu64"\n",
					val64);
			}
		} else if (!strcmp(cmd, "print")) {
			print_bitmap(bitmap);
		} else if (!strcmp(cmd, "dump")) {
			dump_regions(bitmap);
		} else if (!strcmp(cmd, "quit")) {
			break;
		} else {
			fprintf(stderr, "Invalid command: \"%s\"\n",
				cmd);
		}
	}
}

int main(int argc, char *argv[])
{
	errcode_t ret;
	int c;
	int alloc = 0;
	char *filename;
	ocfs2_filesys *fs;
	ocfs2_bitmap *bitmap;

	initialize_ocfs_error_table();

	while ((c = getopt(argc, argv, "a")) != EOF) {
		switch (c) {
			case 'a':
				alloc = 1;
				break;

			default:
				print_usage();
				return 1;
				break;
		}
	}

	if (optind >= argc) {
		fprintf(stderr, "Missing filename\n");
		print_usage();
		return 1;
	}
	filename = argv[optind];

	ret = ocfs2_open(filename, OCFS2_FLAG_RO, 0, 0, &fs);
	if (ret) {
		com_err(argv[0], ret,
			"while opening file \"%s\"", filename);
		return 1;
	}

	if (alloc)
		ret = ocfs2_block_bitmap_new(fs, "Testing", &bitmap);
	else
		ret = ocfs2_cluster_bitmap_new(fs, "Testing", &bitmap);
	if (ret) {
		com_err(argv[0], ret,
			"while creating bitmap");
		goto out_close;
	}

	run_test(bitmap);

	ocfs2_bitmap_free(bitmap);

out_close:
	ocfs2_close(fs);

	return ret;
}



#endif  /* DEBUG_EXE */