diff options
| -rw-r--r-- | Makefile.objs | 1 | ||||
| -rw-r--r-- | bitmap.c | 256 | ||||
| -rw-r--r-- | bitmap.h | 222 | ||||
| -rw-r--r-- | bitops.c | 142 | ||||
| -rw-r--r-- | bitops.h | 272 | ||||
| -rw-r--r-- | osdep.h | 4 |
6 files changed, 897 insertions, 0 deletions
diff --git a/Makefile.objs b/Makefile.objs index 2ac995ba5d..9e98a66e74 100644 --- a/Makefile.objs +++ b/Makefile.objs @@ -100,6 +100,7 @@ common-obj-y += msmouse.o ps2.o common-obj-y += qdev.o qdev-properties.o common-obj-y += block-migration.o common-obj-y += pflib.o +common-obj-y += bitmap.o bitops.o common-obj-$(CONFIG_BRLAPI) += baum.o common-obj-$(CONFIG_POSIX) += migration-exec.o migration-unix.o migration-fd.o diff --git a/bitmap.c b/bitmap.c new file mode 100644 index 0000000000..a62c8ba681 --- /dev/null +++ b/bitmap.c @@ -0,0 +1,256 @@ +/* + * Bitmap Module + * + * Stolen from linux/src/lib/bitmap.c + * + * Copyright (C) 2010 Corentin Chary + * + * This source code is licensed under the GNU General Public License, + * Version 2. + */ + +#include "bitops.h" +#include "bitmap.h" + +/* + * bitmaps provide an array of bits, implemented using an an + * array of unsigned longs. The number of valid bits in a + * given bitmap does _not_ need to be an exact multiple of + * BITS_PER_LONG. + * + * The possible unused bits in the last, partially used word + * of a bitmap are 'don't care'. The implementation makes + * no particular effort to keep them zero. It ensures that + * their value will not affect the results of any operation. + * The bitmap operations that return Boolean (bitmap_empty, + * for example) or scalar (bitmap_weight, for example) results + * carefully filter out these unused bits from impacting their + * results. + * + * These operations actually hold to a slightly stronger rule: + * if you don't input any bitmaps to these ops that have some + * unused bits set, then they won't output any set unused bits + * in output bitmaps. + * + * The byte ordering of bitmaps is more natural on little + * endian architectures. + */ + +int slow_bitmap_empty(const unsigned long *bitmap, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (bitmap[k]) { + return 0; + } + } + if (bits % BITS_PER_LONG) { + if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { + return 0; + } + } + + return 1; +} + +int slow_bitmap_full(const unsigned long *bitmap, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (~bitmap[k]) { + return 0; + } + } + + if (bits % BITS_PER_LONG) { + if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { + return 0; + } + } + + return 1; +} + +int slow_bitmap_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (bitmap1[k] != bitmap2[k]) { + return 0; + } + } + + if (bits % BITS_PER_LONG) { + if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { + return 0; + } + } + + return 1; +} + +void slow_bitmap_complement(unsigned long *dst, const unsigned long *src, + int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + dst[k] = ~src[k]; + } + + if (bits % BITS_PER_LONG) { + dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); + } +} + +int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + unsigned long result = 0; + + for (k = 0; k < nr; k++) { + result |= (dst[k] = bitmap1[k] & bitmap2[k]); + } + return result != 0; +} + +void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + + for (k = 0; k < nr; k++) { + dst[k] = bitmap1[k] | bitmap2[k]; + } +} + +void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + + for (k = 0; k < nr; k++) { + dst[k] = bitmap1[k] ^ bitmap2[k]; + } +} + +int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k; + int nr = BITS_TO_LONGS(bits); + unsigned long result = 0; + + for (k = 0; k < nr; k++) { + result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); + } + return result != 0; +} + +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) + +void bitmap_set(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_set >= 0) { + *p |= mask_to_set; + nr -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + if (nr) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + *p |= mask_to_set; + } +} + +void bitmap_clear(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_clear >= 0) { + *p &= ~mask_to_clear; + nr -= bits_to_clear; + bits_to_clear = BITS_PER_LONG; + mask_to_clear = ~0UL; + p++; + } + if (nr) { + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); + *p &= ~mask_to_clear; + } +} + +#define ALIGN_MASK(x,mask) (((x)+(mask))&~(mask)) + +/** + * bitmap_find_next_zero_area - find a contiguous aligned zero area + * @map: The address to base the search on + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + * @nr: The number of zeroed bits we're looking for + * @align_mask: Alignment mask for zero area + * + * The @align_mask should be one less than a power of 2; the effect is that + * the bit offset of all zero areas this function finds is multiples of that + * power of 2. A @align_mask of 0 means no alignment is required. + */ +unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask) +{ + unsigned long index, end, i; +again: + index = find_next_zero_bit(map, size, start); + + /* Align allocation */ + index = ALIGN_MASK(index, align_mask); + + end = index + nr; + if (end > size) { + return end; + } + i = find_next_bit(map, end, index); + if (i < end) { + start = i + 1; + goto again; + } + return index; +} + +int slow_bitmap_intersects(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits) +{ + int k, lim = bits/BITS_PER_LONG; + + for (k = 0; k < lim; ++k) { + if (bitmap1[k] & bitmap2[k]) { + return 1; + } + } + + if (bits % BITS_PER_LONG) { + if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { + return 1; + } + } + return 0; +} diff --git a/bitmap.h b/bitmap.h new file mode 100644 index 0000000000..efd5d3a1ed --- /dev/null +++ b/bitmap.h @@ -0,0 +1,222 @@ +/* + * Bitmap Module + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h + * + * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. + * See the COPYING.LIB file in the top-level directory. + */ + +#ifndef BITMAP_H +#define BITMAP_H + +#include "qemu-common.h" +#include "bitops.h" + +/* + * The available bitmap operations and their rough meaning in the + * case that the bitmap is a single unsigned long are thus: + * + * Note that nbits should be always a compile time evaluable constant. + * Otherwise many inlines will generate horrible code. + * + * bitmap_zero(dst, nbits) *dst = 0UL + * bitmap_fill(dst, nbits) *dst = ~0UL + * bitmap_copy(dst, src, nbits) *dst = *src + * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 + * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 + * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 + * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) + * bitmap_complement(dst, src, nbits) *dst = ~(*src) + * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? + * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? + * bitmap_empty(src, nbits) Are all bits zero in *src? + * bitmap_full(src, nbits) Are all bits set in *src? + * bitmap_set(dst, pos, nbits) Set specified bit area + * bitmap_clear(dst, pos, nbits) Clear specified bit area + * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area + */ + +/* + * Also the following operations apply to bitmaps. + * + * set_bit(bit, addr) *addr |= bit + * clear_bit(bit, addr) *addr &= ~bit + * change_bit(bit, addr) *addr ^= bit + * test_bit(bit, addr) Is bit set in *addr? + * test_and_set_bit(bit, addr) Set bit and return old value + * test_and_clear_bit(bit, addr) Clear bit and return old value + * test_and_change_bit(bit, addr) Change bit and return old value + * find_first_zero_bit(addr, nbits) Position first zero bit in *addr + * find_first_bit(addr, nbits) Position first set bit in *addr + * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit + * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit + */ + +#define BITMAP_LAST_WORD_MASK(nbits) \ + ( \ + ((nbits) % BITS_PER_LONG) ? \ + (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ + ) + +#define DECLARE_BITMAP(name,bits) \ + unsigned long name[BITS_TO_LONGS(bits)] + +#define small_nbits(nbits) \ + ((nbits) <= BITS_PER_LONG) + +int slow_bitmap_empty(const unsigned long *bitmap, int bits); +int slow_bitmap_full(const unsigned long *bitmap, int bits); +int slow_bitmap_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +void slow_bitmap_complement(unsigned long *dst, const unsigned long *src, + int bits); +void slow_bitmap_shift_right(unsigned long *dst, + const unsigned long *src, int shift, int bits); +void slow_bitmap_shift_left(unsigned long *dst, + const unsigned long *src, int shift, int bits); +int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); +int slow_bitmap_intersects(const unsigned long *bitmap1, + const unsigned long *bitmap2, int bits); + +static inline unsigned long *bitmap_new(int nbits) +{ + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + return qemu_mallocz(len); +} + +static inline void bitmap_zero(unsigned long *dst, int nbits) +{ + if (small_nbits(nbits)) { + *dst = 0UL; + } else { + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + memset(dst, 0, len); + } +} + +static inline void bitmap_fill(unsigned long *dst, int nbits) +{ + size_t nlongs = BITS_TO_LONGS(nbits); + if (!small_nbits(nbits)) { + int len = (nlongs - 1) * sizeof(unsigned long); + memset(dst, 0xff, len); + } + dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); +} + +static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, + int nbits) +{ + if (small_nbits(nbits)) { + *dst = *src; + } else { + int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + memcpy(dst, src, len); + } +} + +static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return (*dst = *src1 & *src2) != 0; + } + return slow_bitmap_and(dst, src1, src2, nbits); +} + +static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + *dst = *src1 | *src2; + } else { + slow_bitmap_or(dst, src1, src2, nbits); + } +} + +static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + *dst = *src1 ^ *src2; + } else { + slow_bitmap_xor(dst, src1, src2, nbits); + } +} + +static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return (*dst = *src1 & ~(*src2)) != 0; + } + return slow_bitmap_andnot(dst, src1, src2, nbits); +} + +static inline void bitmap_complement(unsigned long *dst, const unsigned long *src, + int nbits) +{ + if (small_nbits(nbits)) { + *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits); + } else { + slow_bitmap_complement(dst, src, nbits); + } +} + +static inline int bitmap_equal(const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); + } else { + return slow_bitmap_equal(src1, src2, nbits); + } +} + +static inline int bitmap_empty(const unsigned long *src, int nbits) +{ + if (small_nbits(nbits)) { + return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); + } else { + return slow_bitmap_empty(src, nbits); + } +} + +static inline int bitmap_full(const unsigned long *src, int nbits) +{ + if (small_nbits(nbits)) { + return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); + } else { + return slow_bitmap_full(src, nbits); + } +} + +static inline int bitmap_intersects(const unsigned long *src1, + const unsigned long *src2, int nbits) +{ + if (small_nbits(nbits)) { + return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; + } else { + return slow_bitmap_intersects(src1, src2, nbits); + } +} + +void bitmap_set(unsigned long *map, int i, int len); +void bitmap_clear(unsigned long *map, int start, int nr); +unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask); + +#endif /* BITMAP_H */ diff --git a/bitops.c b/bitops.c new file mode 100644 index 0000000000..d9de71f7e8 --- /dev/null +++ b/bitops.c @@ -0,0 +1,142 @@ +/* + * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * Copyright (C) 2008 IBM Corporation + * Written by Rusty Russell <rusty@rustcorp.com.au> + * (Inspired by David Howell's find_next_bit implementation) + * + * 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; either version + * 2 of the License, or (at your option) any later version. + */ + +#include "bitops.h" + +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) + +/* + * Find the next set bit in a memory region. + */ +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 + bitops_ffsl(tmp); +} + +/* + * This implementation of find_{first,next}_zero_bit was stolen from + * Linus' asm-alpha/bitops.h. + */ +unsigned long find_next_zero_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 >> (BITS_PER_LONG - 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 << size; + if (tmp == ~0UL) { /* Are any bits zero? */ + return result + size; /* Nope. */ + } +found_middle: + return result + ffz(tmp); +} + +unsigned long find_last_bit(const unsigned long *addr, unsigned long size) +{ + unsigned long words; + unsigned long tmp; + + /* Start at final word. */ + words = size / BITS_PER_LONG; + + /* Partial final word? */ + if (size & (BITS_PER_LONG-1)) { + tmp = (addr[words] & (~0UL >> (BITS_PER_LONG + - (size & (BITS_PER_LONG-1))))); + if (tmp) { + goto found; + } + } + + while (words) { + tmp = addr[--words]; + if (tmp) { + found: + return words * BITS_PER_LONG + bitops_flsl(tmp); + } + } + + /* Not found */ + return size; +} diff --git a/bitops.h b/bitops.h new file mode 100644 index 0000000000..ae7bcb1b1c --- /dev/null +++ b/bitops.h @@ -0,0 +1,272 @@ +/* + * Bitops Module + * + * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> + * + * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h + * + * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. + * See the COPYING.LIB file in the top-level directory. + */ + +#ifndef BITOPS_H +#define BITOPS_H + +#include "qemu-common.h" + +#define BITS_PER_BYTE CHAR_BIT +#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) + +#define BIT(nr) (1UL << (nr)) +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) + +/** + * bitops_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 bitops_ffsl(unsigned long word) +{ + int num = 0; + +#if LONG_MAX > 0x7FFFFFFF + if ((word & 0xffffffff) == 0) { + num += 32; + word >>= 32; + } +#endif + 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; +} + +/** + * bitops_fls - find last (most-significant) set bit in a long word + * @word: the word to search + * + * Undefined if no set bit exists, so code should check against 0 first. + */ +static __always_inline unsigned long bitops_flsl(unsigned long word) +{ + int num = BITS_PER_LONG - 1; + +#if LONG_MAX > 0x7FFFFFFF + if (!(word & (~0ul << 32))) { + num -= 32; + word <<= 32; + } +#endif + if (!(word & (~0ul << (BITS_PER_LONG-16)))) { + num -= 16; + word <<= 16; + } + if (!(word & (~0ul << (BITS_PER_LONG-8)))) { + num -= 8; + word <<= 8; + } + if (!(word & (~0ul << (BITS_PER_LONG-4)))) { + num -= 4; + word <<= 4; + } + if (!(word & (~0ul << (BITS_PER_LONG-2)))) { + num -= 2; + + word <<= 2; + } + if (!(word & (~0ul << (BITS_PER_LONG-1)))) + num -= 1; + return num; +} + +/** + * ffz - find first zero in word. + * @word: The word to search + * + * Undefined if no zero exists, so code should check against ~0UL first. + */ +static inline unsigned long ffz(unsigned long word) +{ + return bitops_ffsl(~word); +} + +/** + * set_bit - Set a bit in memory + * @nr: the bit to set + * @addr: the address to start counting from + */ +static inline void set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p |= mask; +} + +/** + * clear_bit - Clears a bit in memory + * @nr: Bit to clear + * @addr: Address to start counting from + */ +static inline void clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p &= ~mask; +} + +/** + * change_bit - Toggle a bit in memory + * @nr: Bit to change + * @addr: Address to start counting from + */ +static inline void change_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + + *p ^= mask; +} + +/** + * test_and_set_bit - Set a bit and return its old value + * @nr: Bit to set + * @addr: Address to count from + */ +static inline int test_and_set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + unsigned long old = *p; + + *p = old | mask; + return (old & mask) != 0; +} + +/** + * test_and_clear_bit - Clear a bit and return its old value + * @nr: Bit to clear + * @addr: Address to count from + */ +static inline int test_and_clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + unsigned long old = *p; + + *p = old & ~mask; + return (old & mask) != 0; +} + +/** + * test_and_change_bit - Change a bit and return its old value + * @nr: Bit to change + * @addr: Address to count from + */ +static inline int test_and_change_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); + unsigned long old; + + *p = old ^ mask; + return (old & mask) != 0; +} + +/** + * test_bit - Determine whether a bit is set + * @nr: bit number to test + * @addr: Address to start counting from + */ +static inline int test_bit(int nr, const volatile unsigned long *addr) +{ + return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); +} + +/** + * find_last_bit - find the last set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first set bit, or size. + */ +unsigned long find_last_bit(const unsigned long *addr, + unsigned long size); + +/** + * 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 bitmap size in bits + */ +unsigned long find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset); + +/** + * find_next_zero_bit - find the next cleared bit in a memory region + * @addr: The address to base the search on + * @offset: The bitnumber to start searching at + * @size: The bitmap size in bits + */ + +unsigned long find_next_zero_bit(const unsigned long *addr, + unsigned long size, + unsigned long offset); + +/** + * find_first_bit - find the first set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first set bit. + */ +static inline unsigned long find_first_bit(const unsigned long *addr, + unsigned long size) +{ + return find_next_bit(addr, size, 0); +} + +/** + * find_first_zero_bit - find the first cleared bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first cleared bit. + */ +static inline unsigned long find_first_zero_bit(const unsigned long *addr, + unsigned long size) +{ + return find_next_zero_bit(addr, size, 0); +} + +static inline unsigned long hweight_long(unsigned long w) +{ + unsigned long count; + + for (count = 0; w; w >>= 1) { + count += w & 1; + } + return count; +} + +#endif @@ -57,6 +57,10 @@ #define MAX(a, b) (((a) > (b)) ? (a) : (b)) #endif +#ifndef DIV_ROUND_UP +#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) +#endif + #ifndef ARRAY_SIZE #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) #endif |