diff options
| -rw-r--r-- | Makefrag.am | 1 | ||||
| -rw-r--r-- | kern/bitmap.c | 58 | ||||
| -rw-r--r-- | kern/bitmap.h | 59 |
3 files changed, 87 insertions, 31 deletions
diff --git a/Makefrag.am b/Makefrag.am index 86de4e69..d9e34c00 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -2,6 +2,7 @@ include arch/x86/Makefrag.am x15_SOURCES += \ kern/assert.h \ + kern/bitmap.c \ kern/bitmap.h \ kern/config.h \ kern/error.h \ diff --git a/kern/bitmap.c b/kern/bitmap.c new file mode 100644 index 00000000..f1388b1d --- /dev/null +++ b/kern/bitmap.c @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2013 Richard Braun. + * + * 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 3 of the License, or + * (at your option) any later version. + * + * 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, see <http://www.gnu.org/licenses/>. + */ + +#include <kern/bitmap.h> +#include <kern/limits.h> + +int +bitmap_find_next_bit(volatile unsigned long *bm, int nr_bits, int bit, + int complement) +{ + volatile unsigned long *start, *end; + unsigned long word; + + start = bm; + end = bm + BITMAP_LONGS(nr_bits); + + if (bit >= LONG_BIT) + bitmap_lookup(&bm, &bit); + + word = *bm; + + if (complement) + word = ~word; + + if (bit < LONG_BIT) + word &= ~(bitmap_mask(bit) - 1); + + for (;;) { + bit = __builtin_ffsl(word); + + if (bit != 0) + return ((bm - start) * LONG_BIT) + bit - 1; + + bm++; + + if (bm >= end) + return -1; + + word = *bm; + + if (complement) + word = ~word; + } +} diff --git a/kern/bitmap.h b/kern/bitmap.h index 36018bcc..b1c74843 100644 --- a/kern/bitmap.h +++ b/kern/bitmap.h @@ -57,6 +57,15 @@ bitmap_mask(int bit) } /* + * Return the index of the next set bit in the bitmap, starting (and + * including) the given bit index, or -1 if the bitmap is empty. If + * complement is true, bits are toggled before searching so that the + * result is the index of the next zero bit. + */ +int bitmap_find_next_bit(volatile unsigned long *bm, int nr_bits, int bit, + int complement); + +/* * Public interface. */ @@ -123,40 +132,10 @@ bitmap_test(volatile unsigned long *bm, int bit) return ((*bm & bitmap_mask(bit)) != 0); } -/* - * Return the index of the next set bit in the bitmap, starting (and - * including) the given bit index, or -1 if the bitmap is empty. - */ static inline int bitmap_find_next(volatile unsigned long *bm, int nr_bits, int bit) { - volatile unsigned long *start, *end; - unsigned long word; - - start = bm; - end = bm + BITMAP_LONGS(nr_bits); - - if (bit >= LONG_BIT) - bitmap_lookup(&bm, &bit); - - word = *bm; - - if (bit < LONG_BIT) - word &= ~(bitmap_mask(bit) - 1); - - for (;;) { - bit = __builtin_ffsl(word); - - if (bit != 0) - return ((bm - start) * LONG_BIT) + bit - 1; - - bm++; - - if (bm >= end) - return -1; - - word = *bm; - } + return bitmap_find_next_bit(bm, nr_bits, bit, 0); } static inline int @@ -165,10 +144,28 @@ bitmap_find_first(volatile unsigned long *bm, int nr_bits) return bitmap_find_next(bm, nr_bits, 0); } +static inline int +bitmap_find_next_zero(volatile unsigned long *bm, int nr_bits, int bit) +{ + return bitmap_find_next_bit(bm, nr_bits, bit, 1); +} + +static inline int +bitmap_find_first_zero(volatile unsigned long *bm, int nr_bits) +{ + return bitmap_find_next_zero(bm, nr_bits, 0); +} + #define bitmap_for_each(bm, nr_bits, bit) \ for ((bit) = 0; \ ((bit) < nr_bits) \ && (((bit) = bitmap_find_next(bm, nr_bits, bit)) != -1); \ (bit)++) +#define bitmap_for_each_zero(bm, nr_bits, bit) \ +for ((bit) = 0; \ + ((bit) < nr_bits) \ + && (((bit) = bitmap_find_next_zero(bm, nr_bits, bit)) != -1); \ + (bit)++) + #endif /* _KERN_BITMAP_H */ |