| /* |
| * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved. |
| * Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved. |
| * |
| * This file is part of the device-mapper userspace tools. |
| * |
| * This copyrighted material is made available to anyone wishing to use, |
| * modify, copy, or redistribute it subject to the terms and conditions |
| * of the GNU Lesser General Public License v.2.1. |
| * |
| * You should have received a copy of the GNU Lesser General Public License |
| * along with this program; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
| */ |
| |
| #include "dmlib.h" |
| |
| #include <ctype.h> |
| |
| /* FIXME: calculate this. */ |
| #define INT_SHIFT 5 |
| |
| dm_bitset_t dm_bitset_create(struct dm_pool *mem, unsigned num_bits) |
| { |
| unsigned n = (num_bits / DM_BITS_PER_INT) + 2; |
| size_t size = sizeof(int) * n; |
| dm_bitset_t bs; |
| |
| if (mem) |
| bs = dm_pool_zalloc(mem, size); |
| else |
| bs = dm_zalloc(size); |
| |
| if (!bs) |
| return NULL; |
| |
| *bs = num_bits; |
| |
| return bs; |
| } |
| |
| void dm_bitset_destroy(dm_bitset_t bs) |
| { |
| dm_free(bs); |
| } |
| |
| int dm_bitset_equal(dm_bitset_t in1, dm_bitset_t in2) |
| { |
| int i; |
| |
| for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--) |
| if (in1[i] != in2[i]) |
| return 0; |
| |
| return 1; |
| } |
| |
| void dm_bit_and(dm_bitset_t out, dm_bitset_t in1, dm_bitset_t in2) |
| { |
| int i; |
| |
| for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--) |
| out[i] = in1[i] & in2[i]; |
| } |
| void dm_bit_union(dm_bitset_t out, dm_bitset_t in1, dm_bitset_t in2) |
| { |
| int i; |
| for (i = (in1[0] / DM_BITS_PER_INT) + 1; i; i--) |
| out[i] = in1[i] | in2[i]; |
| } |
| |
| static int _test_word(uint32_t test, int bit) |
| { |
| uint32_t tb = test >> bit; |
| |
| return (tb ? ffs(tb) + bit - 1 : -1); |
| } |
| |
| int dm_bit_get_next(dm_bitset_t bs, int last_bit) |
| { |
| int bit, word; |
| uint32_t test; |
| |
| last_bit++; /* otherwise we'll return the same bit again */ |
| |
| /* |
| * bs[0] holds number of bits |
| */ |
| while (last_bit < (int) bs[0]) { |
| word = last_bit >> INT_SHIFT; |
| test = bs[word + 1]; |
| bit = last_bit & (DM_BITS_PER_INT - 1); |
| |
| if ((bit = _test_word(test, bit)) >= 0) |
| return (word * DM_BITS_PER_INT) + bit; |
| |
| last_bit = last_bit - (last_bit & (DM_BITS_PER_INT - 1)) + |
| DM_BITS_PER_INT; |
| } |
| |
| return -1; |
| } |
| |
| int dm_bit_get_first(dm_bitset_t bs) |
| { |
| return dm_bit_get_next(bs, -1); |
| } |
| |
| /* |
| * Based on the Linux kernel __bitmap_parselist from lib/bitmap.c |
| */ |
| dm_bitset_t dm_bitset_parse_list(const char *str, struct dm_pool *mem) |
| { |
| unsigned a, b; |
| int c, old_c, totaldigits, ndigits, nmaskbits; |
| int at_start, in_range; |
| dm_bitset_t mask = NULL; |
| const char *start = str; |
| size_t len; |
| |
| scan: |
| len = strlen(str); |
| totaldigits = c = 0; |
| nmaskbits = 0; |
| do { |
| at_start = 1; |
| in_range = 0; |
| a = b = 0; |
| ndigits = totaldigits; |
| |
| /* Get the next value or range of values */ |
| while (len) { |
| old_c = c; |
| c = *str++; |
| len--; |
| if (isspace(c)) |
| continue; |
| |
| /* A '\0' or a ',' signal the end of a value or range */ |
| if (c == '\0' || c == ',') |
| break; |
| /* |
| * whitespaces between digits are not allowed, |
| * but it's ok if whitespaces are on head or tail. |
| * when old_c is whilespace, |
| * if totaldigits == ndigits, whitespace is on head. |
| * if whitespace is on tail, it should not run here. |
| * as c was ',' or '\0', |
| * the last code line has broken the current loop. |
| */ |
| if ((totaldigits != ndigits) && isspace(old_c)) |
| goto_bad; |
| |
| if (c == '-') { |
| if (at_start || in_range) |
| goto_bad; |
| b = 0; |
| in_range = 1; |
| at_start = 1; |
| continue; |
| } |
| |
| if (!isdigit(c)) |
| goto_bad; |
| |
| b = b * 10 + (c - '0'); |
| if (!in_range) |
| a = b; |
| at_start = 0; |
| totaldigits++; |
| } |
| if (ndigits == totaldigits) |
| continue; |
| /* if no digit is after '-', it's wrong */ |
| if (at_start && in_range) |
| goto_bad; |
| if (!(a <= b)) |
| goto_bad; |
| if (b >= nmaskbits) |
| nmaskbits = b + 1; |
| while ((a <= b) && mask) { |
| dm_bit_set(mask, a); |
| a++; |
| } |
| } while (len && c == ','); |
| |
| if (!mask) { |
| if (!(mask = dm_bitset_create(mem, nmaskbits))) |
| goto_bad; |
| str = start; |
| goto scan; |
| } |
| |
| return mask; |
| bad: |
| if (mask) { |
| if (mem) |
| dm_pool_free(mem, mask); |
| else |
| dm_bitset_destroy(mask); |
| } |
| return NULL; |
| } |