diff options
author | Benjamin Herrenschmidt <benh@kernel.crashing.org> | 2016-12-22 14:16:09 +1100 |
---|---|---|
committer | Stewart Smith <stewart@linux.vnet.ibm.com> | 2017-01-04 17:28:59 +1100 |
commit | e4f1764f8041e2f0ee58235add6740f980872753 (patch) | |
tree | e73f084fa72424d6cb04ad0948eaa76494d25e0d /core/bitmap.c | |
parent | 366c3936a9e9b458cf30c386208ec7ecf084c3f3 (diff) | |
download | skiboot-e4f1764f8041e2f0ee58235add6740f980872753.zip skiboot-e4f1764f8041e2f0ee58235add6740f980872753.tar.gz skiboot-e4f1764f8041e2f0ee58235add6740f980872753.tar.bz2 |
bitmap: Add basic bitmap ops
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org>
[stewart@linux.vnet.ibm.com: add (C) header]
Signed-off-by: Stewart Smith <stewart@linux.vnet.ibm.com>
Diffstat (limited to 'core/bitmap.c')
-rw-r--r-- | core/bitmap.c | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/core/bitmap.c b/core/bitmap.c new file mode 100644 index 0000000..be0700f --- /dev/null +++ b/core/bitmap.c @@ -0,0 +1,56 @@ +/* Copyright 2016 IBM Corp. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + * implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include "bitmap.h" + +static int __bitmap_find_bit(bitmap_t map, unsigned int start, unsigned int count, + bool value) +{ + unsigned int el, first_bit; + unsigned int end = start + count; + bitmap_elem_t e, ev; + int b; + + ev = value ? -1ul : 0; + el = BITMAP_ELEM(start); + first_bit = BITMAP_BIT(start); + + while (start < end) { + e = map[el] ^ ev; + e |= ((1ul << first_bit) - 1); + if (~e) + break; + start = (start + BITMAP_ELSZ) & ~(BITMAP_ELSZ - 1); + first_bit = 0; + el++; + } + for (b = first_bit; b < BITMAP_ELSZ && start < end; b++,start++) { + if ((e & (1ull << b)) == 0) + return start; + } + + return -1; +} + +int bitmap_find_zero_bit(bitmap_t map, unsigned int start, unsigned int count) +{ + return __bitmap_find_bit(map, start, count, false); +} + +int bitmap_find_one_bit(bitmap_t map, unsigned int start, unsigned int count) +{ + return __bitmap_find_bit(map, start, count, true); +} + |