/*

 * 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 "libdm/misc/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);

}

static int _test_word_rev(uint32_t test, int bit)

{

  uint32_t tb = test << (DM_BITS_PER_INT - 1 - bit);

  return (tb ? bit - clz(tb) : -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_prev(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 >= 0) {

    word = last_bit >> INT_SHIFT;

    test = bs[word + 1];

    bit = last_bit & (DM_BITS_PER_INT - 1);

    if ((bit = _test_word_rev(test, bit)) >= 0)

      return (word * DM_BITS_PER_INT) + bit;

    last_bit = (last_bit & ~(DM_BITS_PER_INT - 1)) - 1;

  }

  return -1;

}

int dm_bit_get_first(dm_bitset_t bs)

{

  return dm_bit_get_next(bs, -1);

}

int dm_bit_get_last(dm_bitset_t bs)

{

  return dm_bit_get_prev(bs, bs[0] + 1);

}

/*

 * Based on the Linux kernel __bitmap_parselist from lib/bitmap.c

 */

DM_EXPORT_NEW_SYMBOL(dm_bitset_t, dm_bitset_parse_list, 1_02_138)

  (const char *str, struct dm_pool *mem, size_t min_num_bits)

{

  unsigned a, b;

  int c, old_c, totaldigits, ndigits;

  size_t 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 whitespace,

      * 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 (min_num_bits && (nmaskbits < min_num_bits))

      nmaskbits = min_num_bits;

    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;

}

#if defined(GNU_SYMVER)

/*

 * Maintain backward compatibility with older versions that did not

 * accept a 'min_num_bits' argument to dm_bitset_parse_list().

 */

DM_EXPORT_SYMBOL(dm_bitset_parse_list, 1_02_129)

dm_bitset_t dm_bitset_parse_list_v1_02_129(const char *str, struct dm_pool *mem);

dm_bitset_t dm_bitset_parse_list_v1_02_129(const char *str, struct dm_pool *mem)

{

  return dm_bitset_parse_list(str, mem, 0);

}

#endif