#include <cstdio>
#include <sys/uio.h>
#include <utility>
#include <cassert>
#include <deque>

template<typename T>
struct ArrayWrapper
{
    ArrayWrapper(const T *_ptr, size_t _cnt) : ptr(_ptr), cnt(_cnt) {}
    size_t size() const { return cnt; }
    const T &operator[](size_t i) const { return ptr[i]; }
    size_t cnt;
    const T *ptr;
};

// returns index of iovec containing start of match, and index of start of match
// returns -1,-1 if nothing found
template<typename T>
std::pair<int,int> search_iov(const T &iov,
        const void *needle,size_t size)
{
    std::pair<int,int> start;
    const char *progress = (const char *)needle;
    for(int i=0; i<iov.size(); i++)
    {
        size_t start_j = 0;
RESTART:
        auto &v = iov[i];
        for(size_t j=start_j; j<v.iov_len; j++)
        {
            if(((const char *)v.iov_base)[j] == *progress)
            {
                if(progress==(const char *)needle)
                    start=std::make_pair(i,(int)j);
                progress++;
                if(progress==((const char *)needle)+size)
                    return start;
            }
            else if(progress != (const char *)needle)
            {
                // start was set, visit every character that matched and one that didn't
                // looking for first *needle
                for(int k=start.first; k<=i; k++)
                {
                    auto &v = iov[k];
                    for(size_t l=((k==start.first)?start.second:0);
                            l<=((k==i)?j:(v.iov_len-1));
                            l++)
                    {
                        if( ((const char *)v.iov_base)[l] == *(const char *)needle)
                        {
                            i = k;
                            start_j = l;
                            
                            // now we have to advance [i,start_j]
                            start_j ++;
                            if(start_j==iov[i].iov_len)
                            {
                                i++;
                                start_j=0;
                            }
                            
                            progress = (const char *)needle;
                            goto RESTART;
                        }
                    }
                }
                progress = (const char *)needle;
            }
        }
    }
    return std::make_pair(-1,-1);
}

int main()
{
    {
        iovec iovecs[3];
        iovecs[0].iov_base=(char *)"Hell";
        iovecs[0].iov_len=4;
        iovecs[1].iov_base=(char *)"o, wo";
        iovecs[1].iov_len=5;
        iovecs[2].iov_base=(char *)"rld";
        iovecs[2].iov_len=3;
    
        auto p = search_iov(ArrayWrapper(iovecs,3),(char *)"lo, wor",7);
        fprintf(stderr,"%d %d\n", p.first, p.second);
        assert(p == std::make_pair(0,3));
    }
    
    {
        iovec iovecs[3];
        iovecs[0].iov_base=(char *)"xxll";
        iovecs[0].iov_len=4;
        iovecs[1].iov_base=(char *)"x, wx";
        iovecs[1].iov_len=5;
        iovecs[2].iov_base=(char *)"xxx";
        iovecs[2].iov_len=3;
    
        auto p = search_iov(ArrayWrapper(iovecs,3),(char *)"xxxx",4);
        fprintf(stderr,"%d %d\n", p.first, p.second);
        assert(p == std::make_pair(1,4));
        
        p = search_iov(ArrayWrapper(iovecs,3),(char *)"xll",3);
        fprintf(stderr,"%d %d\n", p.first, p.second);
        assert(p == std::make_pair(0,1));
    }
    
    {
        std::deque<iovec> iovecs;
        iovecs.emplace_back(iovec{.iov_base=(void *)"12345",.iov_len=5});
        auto p = search_iov(iovecs,(char *)"234",3);
        fprintf(stderr,"%d %d\n", p.first, p.second);
        assert(p == std::make_pair(0,1));
    }
    
    return 0;
}