Function util_getBlockMultipleSubRange

quest/src/core/utilities.cpp:961–994

}

std::pair<qindex, qindex> util_getBlockMultipleSubRange(
    qindex rangeLen, qindex blockLen, int idSubRange, int numSubRanges
) {
    // divides a range into whole blocks (and a single leftover sub-block) and
    // attempts to uniformly distribute the blocks across the specified number of
    // sub-ranges. When the blocks do not divide evenly between sub-ranges, the
    // leftover blocks are spread apart across sub-ranges. When the range does not 
    // divide evenly into blocks, the overflow is given to the final sub-range.

    qindex numFullBlocks = rangeLen / blockLen; // floors
    qindex subBlockLen = rangeLen % blockLen;

    qindex baseNumBlocksPerSubRange = numFullBlocks / numSubRanges;
    qindex numExtraBlocks = numFullBlocks % numSubRanges;

    // determine how many extra blocks this subrange should contain
    qindex prevExtra = (idSubRange * numExtraBlocks) / numSubRanges;
    qindex prevShift = (idSubRange * numExtraBlocks) % numSubRanges;
    bool hereExtra = (prevShift + numExtraBlocks) >= numSubRanges;

    // allocate blocks to this sub-range
    qindex startBlockInd = idSubRange * baseNumBlocksPerSubRange + prevExtra;
    qindex endBlockInd = startBlockInd + baseNumBlocksPerSubRange + hereExtra;

    // find this sub-range indices within [0, rangeLen)
    qindex startInd = startBlockInd * blockLen;
    qindex endInd = endBlockInd * blockLen; // exclusive

    // arbitrarily allocate the leftover sub-block to the final sub-range
    if (idSubRange == numSubRanges - 1)
        endInd += subBlockLen;

    return std::make_pair(startInd, endInd);
}