/*

 * Copyright (c) 2020 Red Hat, Inc.

 *

 * 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.

 * 

 * 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, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

 * 02110-1301, USA. 

 *

 * $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/numUtils.h#1 $

 *

 * THIS FILE IS A CANDIDATE FOR THE EVENTUAL UTILITY LIBRARY.

 */

#ifndef NUM_UTILS_H

#define NUM_UTILS_H

#include "common.h"

#include "numeric.h"

#include "types.h"

/**

 * Return true if and only if a number is a power of two.

 **/

static inline bool isPowerOfTwo(uint64_t n)

{

  return (n > 0) && ((n & (n - 1)) == 0);

}

/**

 * Efficiently calculate the base-2 logarithm of a number truncated to an

 * integer value.

 *

 * This also happens to be the bit index of the highest-order non-zero bit in

 * the binary representation of the number, which can easily be used to

 * calculate the bit shift corresponding to a bit mask or an array capacity,

 * or to calculate the binary floor or ceiling (next lowest or highest power

 * of two).

 *

 * @param n  The input value

 *

 * @return the integer log2 of the value, or -1 if the value is zero

 **/

static inline int logBaseTwo(uint64_t n)

{

  if (n == 0) {

    return -1;

  }

  // Many CPUs, including x86, directly support this calculation, so use the

  // GCC function for counting the number of leading high-order zero bits.

  return 63 - __builtin_clzll(n);

}

/**

 * Find the minimum of two physical block numbers.

 **/

__attribute__((warn_unused_result))

static inline PhysicalBlockNumber minBlock(PhysicalBlockNumber a,

                                           PhysicalBlockNumber b)

{

  return (a < b) ? a : b;

}

/**

 * Find the maximum of two physical block numbers.

 **/

__attribute__((warn_unused_result))

static inline PhysicalBlockNumber maxBlock(PhysicalBlockNumber a,

                                           PhysicalBlockNumber b)

{

  return (a > b) ? a : b;

}

/**

 * Find the minimum of two block counts.

 **/

__attribute__((warn_unused_result))

static inline BlockCount minBlockCount(BlockCount a, BlockCount b)

{

  return (a < b) ? a : b;

}

/**

 * Find the maximum of two block counts.

 **/

__attribute__((warn_unused_result))

static inline BlockCount maxBlockCount(BlockCount a, BlockCount b)

{

  return (a > b) ? a : b;

}

/**

 * Find the minimum of two sequence numbers.

 **/

__attribute__((warn_unused_result))

static inline SequenceNumber minSequenceNumber(SequenceNumber a,

                                               SequenceNumber b)

{

  return (a < b) ? a : b;

}

/**

 * Return the minimum of two page counts.

 **/

__attribute__((warn_unused_result))

static inline PageCount minPageCount(PageCount a, PageCount b)

{

  return (a < b) ? a : b;

}

/**

 * Return the maximum of two page counts.

 **/

__attribute__((warn_unused_result))

static inline PageCount maxPageCount(PageCount a, PageCount b)

{

  return (a > b) ? a : b;

}

/**

 * Round upward towards the nearest multiple of quantum.

 *

 * @param number        a number

 * @param quantum       the quantum

 *

 * @return the least multiple of quantum not less than number

 **/

__attribute__((warn_unused_result))

static inline size_t roundUpToMultipleSizeT(size_t number, size_t quantum)

{

  return number + quantum - 1 - ((number + quantum - 1) % quantum);

}

/**

 * Round upward towards the nearest multiple of quantum for uint64_t

 *

 * @param number        a number

 * @param quantum       the quantum

 *

 * @return the least multiple of quantum not less than number

 **/

__attribute__((warn_unused_result))

static inline uint64_t roundUpToMultipleUInt64T(uint64_t number,

                                                uint64_t quantum)

{

  return number + quantum - 1 - ((number + quantum - 1) % quantum);

}

/**

 * Check whether the given value is between the lower and upper bounds,

 * within a cyclic range of values from 0 to (modulus - 1). The value

 * and both bounds must be smaller than the modulus.

 *

 * @param lower    The lowest value to accept

 * @param value    The value to check

 * @param upper    The highest value to accept

 * @param modulus  The size of the cyclic space, no more than 2^15

 *

 * @return true if the value is in range

 **/

static inline bool inCyclicRange(uint16_t lower,

                                 uint16_t value,

                                 uint16_t upper,

                                 uint16_t modulus)

{

  if (value < lower) {

    value += modulus;

  }

  if (upper < lower) {

    upper += modulus;

  }

  return (value <= upper);

}

/**

 * Compute the number of buckets of a given size which are required to hold a

 * given number of objects.

 *

 * @param objectCount  The number of objects to hold

 * @param bucketSize   The size of a bucket

 *

 * @return The number of buckets required

 **/

static inline uint64_t computeBucketCount(uint64_t objectCount,

                                          uint64_t bucketSize)

{

  uint64_t quotient = objectCount / bucketSize;

  if ((objectCount % bucketSize) > 0) {

    ++quotient;

  }

  return quotient;

}

#endif // NUM_UTILS_H