CODEWITHSUNDEEP
c++arraysiteratorrandom-access
Fred
Fred

Reputation: 457

Random access to array of raw buffers of different sizes?

I have an array of array: struct chunk { char * data; size_t size; }; chunk * chunks;. The data size in each chunk is dynamic and differ between chunks. Linear access to data is easy with a nested for loop:

for (chunk * chunk_it = chunks; chunk_it != chunks + count; ++chunk_it) {
    for (char * it = chunk_it->data; it != chunk_it->data + chunk_it->size; ++it) {
        /* use it here */
    }
}

I want to turn this into random access to chunks->data using operator[] as an interface, spanning multiple chunks.

It works by linearly searching for the right chunk, then just calculating the offset of the data I want.

template <class T>
void random_access(int n) {
    chunk * c;
    for (int i = 0; i < count; ++i) {
        c = chunks + i;
        size_t size = c->size;
        if (n - size < 0) {
            n -= size; // mutate n to fit into current chunk
        } else {
            break; // found
        }
    }

    T * data = reinterpret_cast<T *>(c->data + n);

    // use data here
}

Is there a more efficient way to do this? It would be crazy to do this every time I need a T from chunks. I plan on iterating over all chunk data linearly, but I want to use the data outside of the function, and thus need to return it at the inner loop (hence why I want to turn it inside out). I also thought of using a function pointer at the inner loop, but rather not as just doing chunk_iterator[n] is much nicer.

Upvotes: 0

Views: 63

Answers (1)

Galik
Galik

Reputation: 48655

I understand your data structure is more complicated but could you not do something like this?

I build a contiguous block of the chunk data and record the position and size of each one in the chunks array:

class chunk_manager
{
    struct chunk
    {
        std::size_t position;
        std::size_t size;

        chunk(std::size_t position, std::size_t size)
        : position(position), size(size) {}
    };

public:

    void add_chunk(std::string const& chunk)
    {
        m_chunks.emplace_back(m_data.size(), chunk.size());
        m_data.append(chunk);
    }

    char* random_access(std::size_t n) { return &m_data[n]; }

    std::size_t size_in_bytes() const { return m_data.size(); }

private:
    std::vector<chunk> m_chunks;
    std::string m_data;
};

int main()
{
    chunk_manager cm;

    cm.add_chunk("abc");
    cm.add_chunk("def");
    cm.add_chunk("ghi");

    for(auto n = 0ULL; n < cm.size_in_bytes(); ++n)
        std::cout << cm.random_access(n) << '\n';
}

Upvotes: 1

Related Questions