/*
 * Copyright (c) 2014-2020 Douglas Gilbert.
 * All rights reserved.
 * Use of this source code is governed by a BSD-style
 * license that can be found in the BSD_LICENSE file.
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Version 1.02 [20201124]
 */

// C headers
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>
#include <errno.h>
#define __STDC_FORMAT_MACROS 1
#include <inttypes.h>

// C++ headers
#include <array>

#include "sg_scat_gath.h"
#include "sg_lib.h"
#include "sg_pr2serr.h"

using namespace std;

#define MAX_SGL_NUM_VAL (INT32_MAX - 1)  /* should reduce for testing */
// #define MAX_SGL_NUM_VAL 7  /* should reduce for testing */
#if MAX_SGL_NUM_VAL > INT32_MAX
#error "MAX_SGL_NUM_VAL cannot exceed 2^31 - 1"
#endif

bool
scat_gath_list::empty() const
{
    return sgl.empty();
}

bool
scat_gath_list::empty_or_00() const
{
    if (sgl.empty())
        return true;
    return ((sgl.size() == 1) && (sgl[0].lba == 0) && (sgl[0].num == 0));
}

int
scat_gath_list::num_elems() const
{
    return sgl.size();
}


/* Read numbers (up to 64 bits in size) from command line (comma (or
 * (single) space **) separated list). Assumed decimal unless prefixed
 * by '0x', '0X' or contains trailing 'h' or 'H' (which indicate hex).
 * Returns 0 if ok, or 1 if error. Assumed to be LBA (64 bit) and
 * number_of_block (32 bit) pairs. ** Space on command line needs to
 * be escaped, otherwise it is an operand/option separator. */
bool
scat_gath_list::load_from_cli(const char * cl_p, bool b_vb)
{
    bool split, full_pair;
    int in_len, k, j;
    const int max_nbs = MAX_SGL_NUM_VAL;
    int64_t ll, large_num;
    uint64_t prev_lba;
    char * cp;
    char * c2p;
    const char * lcp;
    class scat_gath_elem sge;

    if (NULL == cl_p) {
        pr2serr("%s: bad arguments\n", __func__);
        goto err_out;
    }
    lcp = cl_p;
    in_len = strlen(cl_p);
    if ('-' == cl_p[0]) {        /* read from stdin */
        pr2serr("%s: logic error: no stdin here\n", __func__);
        goto err_out;
    } else {        /* list of numbers (default decimal) on command line */
        k = strspn(cl_p, "0123456789aAbBcCdDeEfFhHxXiIkKmMgGtTpP, ");
        if (in_len != k) {
            if (b_vb)
                pr2serr("%s: error at pos %d\n", __func__, k + 1);
            goto err_out;
        }
        j = 0;
        full_pair = true;
        for (k = 0, split = false; ; ++k) {
            if (split) {
                /* splitting given elem with large number_of_blocks into
                 * multiple elems within array being built */
                ++j;
                sge.lba = prev_lba + (uint64_t)max_nbs;
                if (large_num > max_nbs) {
                    sge.num = (uint32_t)max_nbs;
                    prev_lba = sge.lba;
                    large_num -= max_nbs;
                    sgl.push_back(sge);
                } else {
                    sge.num = (uint32_t)large_num;
                    split = false;
                    if (b_vb)
                        pr2serr("%s: split large sg elem into %d element%s\n",
                                __func__, j, (j == 1 ? "" : "s"));
                    sgl.push_back(sge);
                    goto check_for_next;
                }
                continue;
            }
            full_pair = false;
            ll = sg_get_llnum(lcp);
            if (-1 != ll) {
                sge.lba = (uint64_t)ll;
                cp = (char *)strchr(lcp, ',');
                c2p = (char *)strchr(lcp, ' ');
                if (NULL == cp) {
                    cp = c2p;
                    if (NULL == cp)
                        break;
                }
                if (c2p && (c2p < cp))
                    cp = c2p;
                lcp = cp + 1;
            } else {
                if (b_vb)
                    pr2serr("%s: error at pos %d\n", __func__,
                            (int)(lcp - cl_p + 1));
                goto err_out;
            }
            ll = sg_get_llnum(lcp);
            if (ll >= 0) {
                full_pair = true;
                if (ll > max_nbs) {
                    sge.num = (uint32_t)max_nbs;
                    prev_lba = sge.lba;
                    large_num = ll - max_nbs;
                    split = true;
                    j = 1;
                    continue;
                }
                sge.num = (uint32_t)ll;
            } else {    /* bad or negative number as number_of_blocks */
                if (b_vb)
                    pr2serr("%s: bad number at pos %d\n", __func__,
                            (int)(lcp - cl_p + 1));
                goto err_out;
            }
            sgl.push_back(sge);
check_for_next:
            cp = (char *)strchr(lcp, ',');
            c2p = (char *)strchr(lcp, ' ');
            if (NULL == cp) {
                cp = c2p;
                if (NULL == cp)
                    break;
            }
            if (c2p && (c2p < cp))
                cp = c2p;
            lcp = cp + 1;
        }       /* end of for loop over items in operand */
        /* other than first pair, expect even number of items */
        if ((k > 0) && (! full_pair)) {
            if (b_vb)
                pr2serr("%s:  expected even number of items: "
                        "LBA0,NUM0,LBA1,NUM1...\n", __func__);
            goto err_out;
        }
    }
    return true;
err_out:
    if (0 == m_errno)
        m_errno = SG_LIB_SYNTAX_ERROR;
    return false;
}

bool
scat_gath_list::file2sgl_helper(FILE * fp, const char * fnp, bool def_hex,
                                bool flexible, bool b_vb)
{
    bool bit0;
    bool pre_addr1 = true;
    bool pre_hex_seen = false;
    int in_len, k, j, m, ind;
    const int max_nbs = MAX_SGL_NUM_VAL;
    int off = 0;
    int64_t ll;
    uint64_t ull, prev_lba;
    char * lcp;
    class scat_gath_elem sge;
    char line[1024];

    for (j = 0 ; ; ++j) {
        if (NULL == fgets(line, sizeof(line), fp))
            break;
        // could improve with carry_over logic if sizeof(line) too small
        in_len = strlen(line);
        if (in_len > 0) {
            if ('\n' == line[in_len - 1]) {
                --in_len;
                line[in_len] = '\0';
            } else {
                m_errno = SG_LIB_SYNTAX_ERROR;
                if (b_vb)
                    pr2serr("%s: %s: line too long, max %d bytes\n",
                            __func__, fnp, (int)(sizeof(line) - 1));
                goto err_out;
            }
        }
        if (in_len < 1)
            continue;
        lcp = line;
        m = strspn(lcp, " \t");
        if (m == in_len)
            continue;
        lcp += m;
        in_len -= m;
        if ('#' == *lcp)
            continue;
        if (pre_addr1 || pre_hex_seen) {
            /* Accept lines with leading 'HEX' and ignore as long as there
             * is one _before_ any LBA,NUM lines in the file. This allows
             * HEX marked sgls to be concaternated together. */
            if (('H' == toupper(lcp[0])) && ('E' == toupper(lcp[1])) &&
                ('X' == toupper(lcp[2]))) {
                pre_hex_seen = true;
                if (def_hex)
                    continue; /* bypass 'HEX' marker line if expecting hex */
                else {
                    if (flexible) {
                        def_hex = true; /* okay, switch to hex parse */
                        continue;
                    } else {
                        pr2serr("%s: %s: 'hex' string detected on line %d, "
                                "expecting decimal\n", __func__, fnp, j + 1);
                        m_errno = EINVAL;
                        goto err_out;
                    }
                }
            }
        }
        k = strspn(lcp, "0123456789aAbBcCdDeEfFhHxXbBdDiIkKmMgGtTpP, \t");
        if ((k < in_len) && ('#' != lcp[k])) {
            m_errno = EINVAL;
            if (b_vb)
                pr2serr("%s: %s: syntax error at line %d, pos %d\n",
                        __func__, fnp, j + 1, m + k + 1);
            goto err_out;
        }
        for (k = 0; k < 256; ++k) {
            /* limit parseable items on one line to 256 */
            if (def_hex) {      /* don't accept negatives or multipliers */
                if (1 == sscanf(lcp, "%" SCNx64, &ull))
                    ll = (int64_t)ull;
                else
                    ll = -1;    /* use (2**64 - 1) as error flag */
            } else
                ll = sg_get_llnum(lcp);
            if (-1 != ll) {
                ind = ((off + k) >> 1);
                bit0 = !! (0x1 & (off + k));
                if (ind >= SG_SGL_MAX_ELEMENTS) {
                    m_errno = EINVAL;
                    if (b_vb)
                        pr2serr("%s: %s: array length exceeded\n", __func__,
                                fnp);
                    goto err_out;
                }
                if (bit0) {     /* bit0 set when decoding a NUM */
                    if (ll < 0) {
                        m_errno = EINVAL;
                        if (b_vb)
                            pr2serr("%s: %s: bad number in line %d, at pos "
                                    "%d\n", __func__, fnp, j + 1,
                                    (int)(lcp - line + 1));
                        goto err_out;
                    }
                    if (ll > max_nbs) {
                        int h = 1;

                        /* split up this elem into multiple, smaller elems */
                        do {
                            sge.num = (uint32_t)max_nbs;
                            prev_lba = sge.lba;
                            sgl.push_back(sge);
                            sge.lba = prev_lba + (uint64_t)max_nbs;
                            ++h;
                            off += 2;
                            ll -= max_nbs;
                        } while (ll > max_nbs);
                        if (b_vb)
                            pr2serr("%s: split large sg elem into %d "
                                    "elements\n", __func__, h);
                    }
                    sge.num = (uint32_t)ll;
                    sgl.push_back(sge);
                } else {        /* bit0 clear when decoding a LBA */
                    if (pre_addr1)
                        pre_addr1 = false;
                    sge.lba = (uint64_t)ll;
                }
            } else {    /* failed to decode number on line */
                if ('#' == *lcp) { /* numbers before #, rest of line comment */
                    --k;
                    break;      /* goes to next line */
                }
                m_errno = EINVAL;
                if (b_vb)
                    pr2serr("%s: %s: error in line %d, at pos %d\n",
                            __func__, fnp, j + 1, (int)(lcp - line + 1));
                goto err_out;
            }
            lcp = strpbrk(lcp, " ,\t#");
            if ((NULL == lcp) || ('#' == *lcp))
                break;
            lcp += strspn(lcp, " ,\t");
            if ('\0' == *lcp)
                break;
        }       /* <<< end of for(k < 256) loop */
        off += (k + 1);
    }   /* <<< end of for loop, one iteration per line */
    /* allow one items, but not higher odd number of items */
    if ((off > 1) && (0x1 & off)) {
        m_errno = EINVAL;
        if (b_vb)
            pr2serr("%s: %s: expect even number of items: "
                    "LBA0,NUM0,LBA1,NUM1...\n", __func__, fnp);
        goto err_out;
    }
    clearerr(fp);    /* even EOF on first pass needs this before rescan */
    return true;
err_out:
    clearerr(fp);
    return false;
}

/* Read numbers from filename (or stdin), line by line (comma (or (single)
 * space) separated list); places starting_LBA,number_of_block pairs in an
 * array of scat_gath_elem elements pointed to by the returned value. If
 * this fails NULL is returned and an error number is written to errp (if it
 * is non-NULL). Assumed decimal (and may have suffix multipliers) when
 * def_hex==false; if a number is prefixed by '0x', '0X' or contains trailing
 * 'h' or 'H' that denotes a hex number. When def_hex==true all numbers are
 * assumed to be hex (ignored '0x' prefixes and 'h' suffixes) and multipliers
 * are not permitted. Heap allocates an array just big enough to hold all
 * elements if the file is countable. Pipes and stdin are not considered
 * countable. In the non-countable case an array of MAX_FIXED_SGL_ELEMS
 * elements is pre-allocated; if it is exceeded sg_convert_errno(EDOM) is
 * placed in *errp (if it is non-NULL). One of the first actions is to write
 * 0 to *errp (if it is non-NULL) so the caller does not need to zero it
 * before calling. */
bool
scat_gath_list::load_from_file(const char * file_name, bool def_hex,
                               bool flexible, bool b_vb)
{
    bool have_stdin;
    bool have_err = false;
    FILE * fp;
    const char * fnp;

    have_stdin = ((1 == strlen(file_name)) && ('-' == file_name[0]));
    if (have_stdin) {
        fp = stdin;
        fnp = "<stdin>";
    } else {
        fnp = file_name;
        fp = fopen(fnp, "r");
        if (NULL == fp) {
            m_errno = errno;
            if (b_vb)
                pr2serr("%s: opening %s: %s\n", __func__, fnp,
                        safe_strerror(m_errno));
            return false;
        }
    }
    if (! file2sgl_helper(fp, fnp, def_hex, flexible, b_vb))
        have_err = true;
    if (! have_stdin)
        fclose(fp);
    return have_err ? false : true;
}

const char *
scat_gath_list::linearity_as_str() const
{
    switch (linearity) {
    case SGL_LINEAR:
        return "linear";
    case SGL_MONOTONIC:
        return "monotonic";
    case SGL_MONO_OVERLAP:
        return "monotonic, overlapping";
    case SGL_NON_MONOTONIC:
        return "non-monotonic";
    default:
        return "unknown";
    }
}

void
scat_gath_list::set_weaker_linearity(enum sgl_linearity_e lin)
{
    int i_lin = (int)lin;

    if (i_lin > (int)linearity)
        linearity = lin;
}

/* id_str may be NULL (if so replace by "unknown"), present to enhance verbose
 * output. */
void
scat_gath_list::dbg_print(bool skip_meta, const char * id_str, bool to_stdout,
                          bool show_sgl) const
{
    int num = sgl.size();
    const char * caller = id_str ? id_str : "unknown";
    FILE * fp = to_stdout ? stdout : stderr;

    if (! skip_meta) {
        fprintf(fp, "%s: elems=%d, sgl %spresent, linearity=%s\n",
                caller, num, (sgl.empty() ? "not " : ""),
                linearity_as_str());
        fprintf(fp, "  sum=%" PRId64 ", sum_hard=%s lowest=0x%" PRIx64
                ", high_lba_p1=", sum, (sum_hard ? "true" : "false"),
                lowest_lba);
        fprintf(fp, "0x%" PRIx64 "\n", high_lba_p1);
    }
    fprintf(fp, "  >> %s scatter gather list (%d element%s):\n", caller, num,
            (num == 1 ? "" : "s"));
    if (show_sgl) {
        int k;

        for (k = 0; k < num; ++k) {
            const class scat_gath_elem & sge = sgl[k];

            fprintf(fp, "    lba: 0x%" PRIx64 ", number: 0x%" PRIx32,
                    sge.lba, sge.num);
            if (sge.lba > 0)
                fprintf(fp, " [next lba: 0x%" PRIx64 "]", sge.lba + sge.num);
            fprintf(fp, "\n");
        }
    }
}

/* Assumes sgl array (vector) is setup. The other fields in this object are
 * set by analyzing sgl in a single pass. The fields that are set are:
 * fragmented, lowest_lba, high_lba_p1, monotonic, overlapping, sum and
 * sum_hard. Degenerate elements (i.e. those with 0 blocks) are ignored apart
 * from when one is last which makes sum_hard false and its LBA becomes
 * high_lba_p1 if it is the highest in the list. An empty sgl is equivalent
 * to a 1 element list with [0, 0], so sum_hard==false, monit==true,
 * fragmented==false and overlapping==false . id_str may be NULL, present
 * to enhance verbose output. */
void
scat_gath_list::sum_scan(const char * id_str, bool show_sgl, bool b_vb)
{
    bool degen = false;
    bool first = true;
    bool regular = true;        /* no overlapping segments detected */
    int k;
    int elems = sgl.size();
    uint32_t prev_num, t_num;
    uint64_t prev_lba, t_lba, low, high, end;

    sum = 0;
    for (k = 0, low = 0, high = 0; k < elems; ++k) {
        const class scat_gath_elem & sge = sgl[k];

        degen = false;
        t_num = sge.num;
        if (0 == t_num) {
            degen = true;
            if (! first)
                continue;       /* ignore degen element that not first */
        }
        if (first) {
            low = sge.lba;
            sum = t_num;
            high = sge.lba + sge.num;
            first = false;
        } else {
            t_lba = sge.lba;
            if ((prev_lba + prev_num) != t_lba)
                set_weaker_linearity(SGL_MONOTONIC);
            sum += t_num;
            end = t_lba + t_num;
            if (end > high)
                high = end;     /* high is one plus highest LBA */
            if (prev_lba < t_lba)
                ;
            else if (prev_lba == t_lba) {
                if (prev_num > 0) {
                    set_weaker_linearity(SGL_MONO_OVERLAP);
                    break;
                }
            } else {
                low = t_lba;
                set_weaker_linearity(SGL_NON_MONOTONIC);
                break;
            }
            if (regular) {
                if ((prev_lba + prev_num) > t_lba)
                    regular = false;
            }
        }
        prev_lba = sge.lba;
        prev_num = sge.num;
    }           /* end of for loop while still elements and monot true */

    if (k < elems) {    /* only here if above breaks are taken */
        prev_lba = t_lba;
        ++k;
        for ( ; k < elems; ++k) {
            const class scat_gath_elem & sge = sgl[k];

            degen = false;
            t_lba = sge.lba;
            t_num = sge.num;
            if (0 == t_num) {
                degen = true;
                continue;
            }
            sum += t_num;
            end = t_lba + t_num;
            if (end > high)
                high = end;
            if (prev_lba > t_lba) {
                if (t_lba < low)
                    low = t_lba;
            }
            prev_lba = t_lba;
        }
    } else
        if (! regular)
            set_weaker_linearity(SGL_MONO_OVERLAP);

    lowest_lba = low;
    if (degen && (elems > 0)) { /* last element always impacts high_lba_p1 */
        t_lba = sgl[elems - 1].lba;
        high_lba_p1 = (t_lba > high) ? t_lba : high;
    } else
        high_lba_p1 = high;
    sum_hard = (elems > 0) ? ! degen : false;
    if (b_vb)
        dbg_print(false, id_str, false, show_sgl);
}

/* Usually will append (or add to start if empty) sge unless 'extra_blks'
 * exceeds MAX_SGL_NUM_VAL. In that case multiple sge_s are added with
 * sge.num = MAX_SGL_NUM_VAL or less (for final sge) until extra_blks is
 * exhausted. Returns new size of scatter gather list. */
int
scat_gath_list::append_1or(int64_t extra_blks, int64_t start_lba)
{
    int o_num = sgl.size();
    const int max_nbs = MAX_SGL_NUM_VAL;
    int64_t cnt = 0;
    class scat_gath_elem sge;

    if ((extra_blks <= 0) && (start_lba < 0))
        return o_num;       /* nothing to do */
    if ((o_num > 0) && (! sum_hard)) {
        sge = sgl[o_num - 1];   /* assume sge.num==0 */
        if (sge.lba == (uint64_t)start_lba) {
            if (extra_blks <= max_nbs)
                sge.num = extra_blks;
            else
                sge.num = max_nbs;
            sgl[o_num - 1] = sge;
            cnt = sge.num;
            sum += cnt;
            sum_hard = true;
            if (cnt <= extra_blks) {
                high_lba_p1 = sge.lba + cnt;
                return o_num;
            }
        }
    } else if (0 == o_num) {
        lowest_lba = start_lba;
        if (0 == extra_blks) {
            sge.lba = start_lba;
            sge.num = 0;
            sgl.push_back(sge);
            high_lba_p1 = sge.lba;
            return sgl.size();
        }
    }
    for ( ; cnt < extra_blks; cnt += max_nbs) {
        sge.lba = start_lba + cnt;
        if ((extra_blks - cnt) <= max_nbs)
            sge.num = extra_blks - cnt;
        else
            sge.num = max_nbs;
        sgl.push_back(sge);
        sum += sge.num;
    }           /* always loops at least once */
    sum_hard = true;
    high_lba_p1 = sge.lba + sge.num;
    return sgl.size();
}

int
scat_gath_list::append_1or(int64_t extra_blks)
{
    int o_num = sgl.size();

    if (o_num < 1)
        return append_1or(extra_blks, 0);

    class scat_gath_elem sge = sgl[o_num - 1];

    return append_1or(extra_blks, sge.lba + sge.num);
}

bool
sgls_eq_off(const scat_gath_list & left, int l_e_ind, int l_blk_off,
            const scat_gath_list & right, int r_e_ind, int r_blk_off,
            bool allow_partial)
{
    int lelems = left.sgl.size();
    int relems = right.sgl.size();

    while ((l_e_ind < lelems) && (r_e_ind < relems)) {
        if ((left.sgl[l_e_ind].lba + l_blk_off) !=
            (right.sgl[r_e_ind].lba + r_blk_off))
            return false;

        int lrem = left.sgl[l_e_ind].num - l_blk_off;
        int rrem = right.sgl[r_e_ind].num - r_blk_off;

        if (lrem == rrem) {
            ++l_e_ind;
            l_blk_off = 0;
            ++r_e_ind;
            r_blk_off = 0;
        } else if (lrem < rrem) {
            ++l_e_ind;
            l_blk_off = 0;
            r_blk_off += lrem;
        } else {
            ++r_e_ind;
            r_blk_off = 0;
            l_blk_off += rrem;
        }
    }
    if ((l_e_ind >= lelems) && (r_e_ind >= relems))
        return true;
    return allow_partial;
}

/* If bad arguments returns -1, otherwise returns the lowest LBA in *sglp .
 * If no elements considered returns 0. If ignore_degen is true than
 * ignores all elements with sge.num zero unless always_last is also
 * true in which case the last element is always considered. */
int64_t
scat_gath_list::get_lowest_lba(bool ignore_degen, bool always_last) const
{
    int k;
    const int num_elems = sgl.size();
    bool some = (num_elems > 0);
    int64_t res = INT64_MAX;

    for (k = 0; k < num_elems; ++k) {
        if ((0 == sgl[k].num) && ignore_degen)
            continue;
        if ((int64_t)sgl[k].lba < res)
            res = sgl[k].lba;
    }
    if (always_last && some) {
        if ((int64_t)sgl[k - 1].lba < res)
            res = sgl[k - 1].lba;
    }
    return (INT64_MAX == res) ? 0 : res;
}

/* Returns >= 0 if sgl can be simplified to a single LBA. So an empty sgl
 * will return 0; a one element sgl will return its LBA. A multiple element
 * sgl only returns the first element's LBA (that is not degenerate) if the
 * sgl is monotonic and not fragmented. In the extreme case takes last
 * element's LBA if all prior elements are degenerate. Else returns -1 .
 * Assumes sgl_sum_scan() has been called. */
int64_t
scat_gath_list::get_low_lba_from_linear() const
{
    const int num_elems = sgl.size();
    int k;

    if (num_elems <= 1)
        return (1 == num_elems) ? sgl[0].lba : 0;
    else {
        if (linearity == SGL_LINEAR) {
            for (k = 0; k < (num_elems - 1); ++k) {
                if (sgl[k].num > 0)
                    return sgl[k].lba;
            }
            /* take last element's LBA if all earlier are degenerate */
            return sgl[k].lba;
        } else
            return -1;
    }
}

bool
scat_gath_list::is_pipe_suitable() const
{
    return (lowest_lba == 0) && (linearity == SGL_LINEAR);
}

scat_gath_iter::scat_gath_iter(const scat_gath_list & parent)
    : sglist(parent), it_el_ind(0), it_blk_off(0), blk_idx(0)
{
    int elems = sglist.num_elems();

    if (elems > 0)
        extend_last = (0 == sglist.sgl[elems - 1].num);
}

bool
scat_gath_iter::set_by_blk_idx(int64_t _blk_idx)
{
    bool first;
    int k;
    const int elems = sglist.sgl.size();
    const int last_ind = elems - 1;
    int64_t bc = _blk_idx;

    if (bc < 0)
        return false;

    if (bc == blk_idx)
        return true;
    else if (bc > blk_idx) {
        k = it_el_ind;
        bc -= blk_idx;
    } else
        k = 0;
    for (first = true; k < elems; ++k, first = false) {
        uint32_t num = ((k == last_ind) && extend_last) ? MAX_SGL_NUM_VAL :
                                                          sglist.sgl[k].num;
        if (first) {
            if ((int64_t)(num - it_blk_off) < bc)
                bc -= (num - it_blk_off);
            else {
                it_blk_off = bc + it_blk_off;
                break;
            }
        } else {
            if ((int64_t)num < bc)
                bc -= num;
            else {
                it_blk_off = (uint32_t)bc;
                break;
            }
        }
    }
    it_el_ind = k;
    blk_idx = _blk_idx;

    if (k < elems)
        return true;
    else if ((k == elems) && (0 == it_blk_off))
        return true;    /* EOL */
    else
        return false;
}

/* Given a blk_count, the iterator (*iter_p) is moved toward the EOL.
 * Returns true unless blk_count takes iterator two or more past the last
 * element. So if blk_count takes the iterator to the EOL, this function
 * returns true. Takes into account iterator's extend_last flag. */
bool
scat_gath_iter::add_blks(uint64_t blk_count)
{
    bool first;
    int k;
    const int elems = sglist.sgl.size();
    const int last_ind = elems - 1;
    uint64_t bc = blk_count;

    if (0 == bc)
        return true;
    for (first = true, k = it_el_ind; k < elems; ++k) {
        uint32_t num = ((k == last_ind) && extend_last) ? MAX_SGL_NUM_VAL :
                                                          sglist.sgl[k].num;
        if (first) {
            first = false;
            if ((uint64_t)(num - it_blk_off) <= bc)
                bc -= (num - it_blk_off);
            else {
                it_blk_off = bc + it_blk_off;
                break;
            }
        } else {
            if ((uint64_t)num <= bc)
                bc -= num;
            else {
                it_blk_off = (uint32_t)bc;
                break;
            }
        }
    }
    it_el_ind = k;
    blk_idx += blk_count;

    if (k < elems)
        return true;
    else if ((k == elems) && (0 == it_blk_off))
        return true;    /* EOL */
    else
        return false;
}

/* Move the iterator from its current position (which may be to EOL) towards
 * the start of the sgl (i.e. backwards) for blk_count blocks. Returns true
 * if iterator is valid after the move, else returns false. N.B. if false is
 * returned, then the iterator is invalid and may need to set it to a valid
 * value. */
bool
scat_gath_iter::sub_blks(uint64_t blk_count)
{
    bool first;
    int k = it_el_ind;
    uint64_t bc = 0;
    const uint64_t orig_blk_count = blk_count;

    if (0 == blk_count)
        return true;
    for (first = true; k >= 0; --k) {
        if (first) {
            if (blk_count > (uint64_t)it_blk_off)
                blk_count -= it_blk_off;
            else {
                it_blk_off -= blk_count;
                break;
            }
            first = false;
        } else {
            uint32_t off = sglist.sgl[k].num;

            bc = blk_count;
            if (bc > (uint64_t)off)
                blk_count -= off;
            else {
                bc = off - bc;
                break;
            }
        }
    }
    if (k < 0) {
        blk_idx = 0;
        it_blk_off = 0;
        return false;           /* bad situation */
    }
    if ((int64_t)orig_blk_count <= blk_idx)
        blk_idx -= orig_blk_count;
    else
        blk_idx = 0;
    it_el_ind = k;
    if (! first)
        it_blk_off = (uint32_t)bc;
    return true;
}

/* Returns LBA referred to by iterator if valid or returns SG_LBA_INVALID
 * (-1) if at end or invalid. */
int64_t
scat_gath_iter::current_lba() const
{
    const int elems = sglist.sgl.size();
    int64_t res = SG_LBA_INVALID; /* for at end or invalid (-1) */

    if (it_el_ind < elems) {
        class scat_gath_elem sge = sglist.sgl[it_el_ind];

        if ((uint32_t)it_blk_off < sge.num)
            return sge.lba + it_blk_off;
        else if (((uint32_t)it_blk_off == sge.num) &&
                 ((it_el_ind + 1) < elems)) {
            class scat_gath_iter iter(*this);

            ++iter.it_el_ind;
            iter.it_blk_off = 0;
            /* worst case recursion will stop at end of sgl */
            return iter.current_lba();
        }
    }
    return res;
}

int64_t
scat_gath_iter::current_lba_rem_num(int & rem_num) const
{
    const int elems = sglist.sgl.size();
    int64_t res = SG_LBA_INVALID; /* for at end or invalid (-1) */

    if (it_el_ind < elems) {
        class scat_gath_elem sge = sglist.sgl[it_el_ind];

        if ((uint32_t)it_blk_off < sge.num) {
            rem_num = sge.num - it_blk_off;
            return sge.lba + it_blk_off;
        } else if (((uint32_t)it_blk_off == sge.num) &&
                 ((it_el_ind + 1) < elems)) {
            class scat_gath_iter iter(*this);

            ++iter.it_el_ind;
            iter.it_blk_off = 0;
            /* worst case recursion will stop at end of sgl */
            return iter.current_lba_rem_num(rem_num);
        }
    }
    rem_num = -1;
    return res;
}

class scat_gath_elem
scat_gath_iter::current_elem() const
{
    const int elems = sglist.sgl.size();
    class scat_gath_elem sge;

    sge.make_bad();
    if (it_el_ind < elems)
        return sglist.sgl[it_el_ind];
    return sge;
}

/* Returns true of no sgl or sgl is at the end [elems, 0], otherwise it
 * returns false. */
bool
scat_gath_iter::at_end() const
{
    const int elems = sglist.sgl.size();

    return ((0 == elems) || ((it_el_ind == elems) && (0 == it_blk_off)));
}

/* Returns true if associated iterator is monotonic (increasing) and not
 * fragmented. Empty sgl and single element degenerate considered linear.
 * Assumes sgl_sum_scan() has been called on sgl. */
bool
scat_gath_iter::is_sgl_linear() const
{
    return sglist.linearity == SGL_LINEAR;
}

/* Should return 1 or more unless max_n<=0 or at_end() */
int
scat_gath_iter::linear_for_n_blks(int max_n) const
{
    int k, rem;
    const int elems = sglist.sgl.size();
    uint64_t prev_lba;
    class scat_gath_elem sge;

    if (at_end() || (max_n <= 0))
        return 0;
    sge = sglist.sgl[it_el_ind];
    rem = (int)sge.num - it_blk_off;
    if (rem <= 0) {
        sge = sglist.sgl[it_el_ind + 1];
        rem = (int)sge.num;
    }
    if (max_n <= rem)
        return max_n;
    prev_lba = sge.lba + sge.num;
    for (k = it_el_ind + 1; k < elems; ++k) {
        sge = sglist.sgl[k];
        if (sge.lba != prev_lba)
            return rem;
        rem += sge.num;
        if (max_n <= rem)
            return max_n;
        prev_lba = sge.lba + sge.num;
    }
    return rem;
}

/* id_str may be NULL (if so replace by "unknown"), present to enhance verbose
 * output. */
void
scat_gath_iter::dbg_print(const char * id_str, bool to_stdout,
                          int verbose) const
{
    const char * caller = id_str ? id_str : "unknown";
    FILE * fp = to_stdout ? stdout : stderr;

    fprintf(fp, "%s: it_el_ind=%d, it_blk_off=%d, blk_idx=%" PRId64 "\n",
            caller, it_el_ind, it_blk_off, blk_idx);
    fprintf(fp, "  extend_last=%d\n", extend_last);
    if (verbose)
        sglist.dbg_print(false, " iterator's", to_stdout, verbose > 1);
}

/* Calculates difference between iterators, logically: res <-- lhs - rhs
 * Checks that lhsp and rhsp have same underlying sgl, if not returns
 * INT_MIN. Assumes iterators close enough for result to lie in range
 * from (-INT_MAX) to INT_MAX (inclusive). */
int
diff_between_iters(const class scat_gath_iter & left,
                   const class scat_gath_iter & right)
{
    int res, k, r_e_ind, l_e_ind;

    if (&left.sglist != &right.sglist) {
        pr2serr("%s: bad args\n", __func__);
        return INT_MIN;
    }
    r_e_ind = right.it_el_ind;
    l_e_ind = left.it_el_ind;
    if (l_e_ind < r_e_ind) { /* so difference will be negative */
        res = diff_between_iters(right, left);        /* cheat */
        if (INT_MIN == res)
            return res;
        return -res;
    } else if (l_e_ind == r_e_ind)
        return (int)left.it_blk_off - (int)right.it_blk_off;
    /* (l_e_ind > r_e_ind) so (lhs > rhs) */
    res = (int)right.sglist.sgl[r_e_ind].num - right.it_blk_off;
    for (k = 1; (r_e_ind + k) < l_e_ind; ++k) {
        // pr2serr("%s: k=%d, res=%d, num=%d\n", __func__, k, res,
        //         (int)right.sglist.sgl[r_e_ind + k].num);
        res += (int)right.sglist.sgl[r_e_ind + k].num;
    }
    res += left.it_blk_off;
    // pr2serr("%s: at exit res=%d\n", __func__, res);
    return res;
}

/* Compares from the current iterator positions of left and left until
 * the shorter list is exhausted. Returns false on the first inequality.
 * If no inequality and both remaining lists are same length then returns
 * true. If no inequality but remaining lists differ in length then returns
 * allow_partial. */
bool
sgls_eq_from_iters(const class scat_gath_iter & left,
                   const class scat_gath_iter & right,
                   bool allow_partial)
{
    return sgls_eq_off(left.sglist, left.it_el_ind, left.it_blk_off,
                       right.sglist, right.it_el_ind, right.it_blk_off,
                       allow_partial);
}