/*
- * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved.
+ * Copyright (c) 2000-2005 Silicon Graphics, Inc.
+ * All Rights Reserved.
*
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of version 2 of the GNU General Public License as
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation.
*
- * This program is distributed in the hope that it would be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * This program is distributed in the hope that it would 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.
*
- * Further, this software is distributed without any warranty that it is
- * free of the rightful claim of any third person regarding infringement
- * or the like. Any license provided herein, whether implied or
- * otherwise, applies only to this software file. Patent licenses, if
- * any, provided herein do not apply to combinations of this program with
- * other software, or any other product whatsoever.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write the Free Software Foundation, Inc., 59
- * Temple Place - Suite 330, Boston MA 02111-1307, USA.
- *
- * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
- * Mountain View, CA 94043, or:
- *
- * http://www.sgi.com
- *
- * For further information regarding this notice, see:
- *
- * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
- */
-
-/*
- * XFS bit manipulation routines, used in non-realtime code.
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
-
#include "xfs.h"
#include "xfs_bit.h"
#include "xfs_log.h"
#include "xfs_trans.h"
#include "xfs_buf_item.h"
+/*
+ * XFS bit manipulation routines, used in non-realtime code.
+ */
#ifndef HAVE_ARCH_HIGHBIT
/*
* Index of high bit number in byte, -1 for none set, 0..7 otherwise.
*/
-const char xfs_highbit[256] = {
+STATIC const char xfs_highbit[256] = {
-1, 0, 1, 1, 2, 2, 2, 2, /* 00 .. 07 */
3, 3, 3, 3, 3, 3, 3, 3, /* 08 .. 0f */
4, 4, 4, 4, 4, 4, 4, 4, /* 10 .. 17 */
xfs_lowbit64(
__uint64_t v)
{
- int n;
- n = ffs((unsigned)v);
- if (n <= 0) {
- n = ffs(v >> 32);
- if (n >= 0)
- n+=32;
+ __uint32_t w = (__uint32_t)v;
+ int n = 0;
+
+ if (w) { /* lower bits */
+ n = ffs(w);
+ } else { /* upper bits */
+ w = (__uint32_t)(v >> 32);
+ if (w && (n = ffs(w)))
+ n += 32;
}
- return (n <= 0) ? n : n-1;
+ return n - 1;
}
/*
xfs_highbit64(
__uint64_t v)
{
- __uint32_t h = v >> 32;
+ __uint32_t h = (__uint32_t)(v >> 32);
+
if (h)
return xfs_highbit32(h) + 32;
- return xfs_highbit32((__u32)v);
+ return xfs_highbit32((__uint32_t)v);
}
int
xfs_contig_bits(uint *map, uint size, uint start_bit)
{
-#if BITS_PER_LONG == 32
- return find_next_zero_bit((unsigned long *)map,
- size * sizeof(uint) * 8, start_bit) - start_bit;
-#else
- /*
- * The first argument to find_next_zero_bit needs to be aligned,
- * but this is coming from the xfs_buf_log_format_t on-disk
- * struct, which can't be padded or otherwise modified w/o breaking
- * on-disk compatibility... so create a temporary, aligned
- * variable, copy over the bitmap, and send that to find_next_zero_bit
- * This only happens in recovery, so it's ugly but not too bad.
- */
- void * addr;
- int bit;
- size_t bitmap_size = size * sizeof(uint);
-
- addr = (void *)kmem_alloc(bitmap_size, KM_SLEEP);
- memcpy(addr, map, size * sizeof(uint));
-
- bit = find_next_zero_bit((unsigned long *)addr,
- size * sizeof(uint) * 8, start_bit) - start_bit;
+ uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
+ uint result = 0;
+ uint tmp;
- kmem_free(addr, bitmap_size);
+ size <<= BIT_TO_WORD_SHIFT;
- return bit;
-#endif
+ ASSERT(start_bit < size);
+ size -= start_bit & ~(NBWORD - 1);
+ start_bit &= (NBWORD - 1);
+ if (start_bit) {
+ tmp = *p++;
+ /* set to one first offset bits prior to start */
+ tmp |= (~0U >> (NBWORD-start_bit));
+ if (tmp != ~0U)
+ goto found;
+ result += NBWORD;
+ size -= NBWORD;
+ }
+ while (size) {
+ if ((tmp = *p++) != ~0U)
+ goto found;
+ result += NBWORD;
+ size -= NBWORD;
+ }
+ return result - start_bit;
+found:
+ return result + ffz(tmp) - start_bit;
}
/*
start_bit &= (NBWORD - 1);
if (start_bit) {
tmp = *p++;
- /* set to zero first offset bits */
+ /* set to zero first offset bits prior to start */
tmp &= (~0U << start_bit);
- if (size < NBWORD)
- goto found_first;
if (tmp != 0U)
- goto found_middle;
- size -= NBWORD;
+ goto found;
result += NBWORD;
+ size -= NBWORD;
}
- while (size >= NBWORD) {
+ while (size) {
if ((tmp = *p++) != 0U)
- goto found_middle;
+ goto found;
result += NBWORD;
size -= NBWORD;
}
- if (!size)
- return -1;
- tmp = *p;
-found_first:
-found_middle:
+ return -1;
+found:
return result + ffs(tmp) - 1;
}
git://git.onelab.eu / linux-2.6.git / blobdiff