/*
* 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 <code>true</code> 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