1
\$\begingroup\$

I am a novice when it comes to C++ (as well as C++/CLI). I am trying to write a minimal 64-bit implementation of a List in C++ (using unsigned __int64 as the index data type), to store unsigned char values (bytes), as well as a C++/CLI wrapper for it that I will use to later to talk to it in C# land.

I may have succeeded (preliminary tests look good), so I am submitting the code for your review. Any helpful comments about changes I could make the code better would be appreciated, as well as comments about where the code might break down (this will be my first unmanaged / managed code wrapper).

Some background: I wrote this code because I needed a larger byte list in C#. I am working on a 64-bit memory scanner, and want to eventually suspend a program, then copy it in its entirety into a giant byte list for later digestion.

//UnmanagedBigByteList.h
#pragma once
#include <iostream>

class UnmanagedBigByteList
{
private:
    std::uint64_t _capacity = 4;
    std::uint64_t _count = 0;
    std::uint8_t* _items;

    void grow()
    {
        std::uint64_t newcapacity = _capacity * 2;
        std::uint8_t* newitems = new std::uint8_t[newcapacity];
        for (std::uint64_t i = 0; i < _capacity; i++)
        {
            newitems[i] = _items[i];
            //std::cout << "Adding " << i << " Element to grown list." << std::endl;
        }
        delete[] _items;
        _items = newitems;
        _capacity = newcapacity;
    }

public:
    UnmanagedBigByteList()
    {
        _items = new std::uint8_t[_capacity];
    }


    ~UnmanagedBigByteList()
    {
        delete[] _items;
    }

    void Add(std::uint8_t byte)
    {
        if (_capacity == _count)
        {
            grow();
        }
        _items[_count] = byte;
        _count++;

    }

    void Clear() 
    {
        delete[] _items;
        _capacity = 4;
        _count = 0;
        _items = new std::uint8_t[_capacity];
    
    }

    bool Contains(std::uint8_t byte)
    {
        for (std::uint64_t i = 0; i < _count; i++)
        {
            if (byte == _items[i]) 
            {
                return true;
            }
        }
        return false;
       
    }

    bool IndexOf(std::uint8_t byte, std::uint64_t* index)
    {
        for (std::uint64_t i = 0; i < _count; i++)
        {
            if (byte == _items[i])
            {
                *(index) = i;
                return true;
            }
        }
        return false;
    
    
    }

    std::uint64_t Count()
    {
        return _count;
    }

    std::uint64_t Capacity()
    {
        return _capacity;
    }

    std::uint8_t& operator[](std::uint64_t index)
    {
        return _items[index];
    }
};

//ManagedBigByteList.h
#pragma once
#include "UnmanagedBigByteList.h"

using namespace System;

namespace BigGenerics {
    public ref class ManagedBigByteList
    {
    private:
        UnmanagedBigByteList* _ubbl;
    public:
        ManagedBigByteList()
        {
            _ubbl = new UnmanagedBigByteList();
        }
        ~ManagedBigByteList()
        {
            delete _ubbl;
        }

        void Add(std::uint8_t byte)
        {
            _ubbl->Add(byte);
        }

        void Clear() 
        {
            _ubbl->Clear(); 
        }

        bool Contains(std::uint8_t byte)
        {
            return _ubbl->Contains(byte);       
        }

        bool IndexOf(std::uint8_t byte, std::uint64_t* index)
        {
            return _ubbl->IndexOf(byte, index);
        }

        property std::uint64_t Count
        {
            std::uint64_t get()
            {
                return _ubbl->Count();
            }
        }

        property std::uint64_t Capacity
        {
            std::uint64_t get()
            {
                return _ubbl->Capacity();
            }
        }

        property std::uint8_t& default[std::uint64_t]
        {
            std::uint8_t& get(std::uint64_t index)
            {
                return (*(_ubbl))[index];
            }
            void set(std::uint64_t index, std::uint8_t& value)
            {
                (*(_ubbl))[index] = value;
            }
        }

    };
}


//BigGenericsTest.cpp
#include "pch.h"
#include "ManagedBigByteList.h"

using namespace System;
using namespace BigGenerics;


int main(array<System::String ^> ^args)
{
    ManagedBigByteList^ newList = gcnew ManagedBigByteList();

    for (std::uint64_t i = 0; i < 60; i++)
    {
        std::uint8_t newItem = i;
        
        newList->Add(newItem);
    }

    //unsigned char newItem2 = 200;
    //newList[59] = newItem2;

    //unsigned char* newItem3 = new unsigned char(150);
    //newList[58] = *newItem3;
    //newList[59] = unsigned char(2000);
    System::Console::WriteLine("Checking if IndexOf() works.");
    std::uint64_t* index;
    if (newList->IndexOf(std::uint8_t(30), index))
    {
        System::Console::WriteLine("IndexOf works!");
        System::Console::WriteLine("Value of 30 found at: " + *index);
    }
    
    for (std::uint64_t i = 0; i < newList->Count; i++)
    {

        System::Console::WriteLine(i + " Element is: " + newList[i].ToString());
        //unsigned char newItem = i;
        //newList->Add(newItem);
    }
    
    //System::Console::WriteLine("First Element is: " + newList[0].ToString());

    return 0;
}
\$\endgroup\$
3
  • \$\begingroup\$ Apparently there is. :-). I've updated the code. I've been using this (docs.microsoft.com/en-us/cpp/dotnet/…) as a guide to the data types (C++ vs. .Net), which is why I was using the double-underscore type. Is there a better guide, or is it just something you become familiar with as you learn the language? \$\endgroup\$ Nov 5 at 10:52
  • \$\begingroup\$ No idea, I'm afraid - I only use standard C++, and very averse to using compilers' internal types. That's why I asked. \$\endgroup\$ Nov 5 at 10:54
  • 1
    \$\begingroup\$ Why not just use a std::vector<std::uint8_t> to store the bytes? \$\endgroup\$
    – G. Sliepen
    Nov 5 at 16:15
1
\$\begingroup\$

I'm not sure why you don't simply use a List<byte> in C# or std::vector<std::uint8_t> in C++ as already mentioned by G.Sliepen.

I'm going to ignore that for now and continue with the review.

Use the correct types.

You should use std::size_t instead of std::uint64_t for the array size and index variables. Using std::uint64_t in 32-bit mode will not allow your list to be any bigger than using a 32-bit type.

Shrinking the list

Consider adding a ShrinkToSize function. Your current implementation only allows for the list to grow.

Checking if new was successful

You cannot simply assume that there is enough memory available.

Optimizing Grow

In void grow() you copy the existing element one by one. Modern compilers may be smart enough to automatically translate this into a call to memcpy or memmove but I would rather have used std::copy.

For these types of lists with basic types, good old C's memory allocation functions have an ace up its sleeve over C++'s new and delete. You could have used malloc instead of new and free instead of delete and then realloc to grow or shrink the list.

Using templates

You can use templates to make your list reusable for different types:

template <class T>
class UnmanagedBigByteList
{
private:
    std::uint64_t _capacity = 4;
    std::uint64_t _count = 0;
    T* _items;
    // ...
}

template <class T>
public ref class ManagedBigByteList
{
private:
    UnmanagedBigByteList<T>* _ubbl;
public:
    ManagedBigByteList()
    {
        _ubbl = new UnmanagedBigByteList<T>();
    }
    // ...
}

int main(array<System::String^>^ args)
{
    ManagedBigByteList<std::uint8_t>^ newList = gcnew ManagedBigByteList<std::uint8_t>();
    for (std::uint64_t i = 0; i < 60; i++)
    {
        std::uint8_t newItem = i;
        newList->Add(newItem);
    }
    // ..
}

Final thoughts

I suspect that you may be trying to implement a 64-bit List in a 32-bit address space. This is not impossible but would be much more complicated than simply using 64-bit size and index variables.

To do this you will need to split the list into blocks/pages that can either be in RAM or in a file. How to manage this optimally would make a great new question :-)

\$\endgroup\$
4
  • \$\begingroup\$ Thank you so much for your review. What I've been trying to do is implement a 64-bit memory scanner in C# (in which I copy the entirety of a live, but suspended program, into a giant byte list for analysis), but ran into the problem that the largest number of elements someone can allocate (for a list) in .Net is a uint32's max value. To get around this, I am writing part of it in unmanaged C++, with a managed C++ wrapper. The machine I am developing this on is a Threadripper, with 256 GB of RAM, so there is plenty of memory for scanning and debugging 64-bit programs. \$\endgroup\$ Nov 10 at 21:44
  • \$\begingroup\$ Does std::vector support an unsigned int64's max value worth of elements? I tried writing this initially with templates in mind, but incompatibilities between generics and templates had me giving up in frustration. Everything else is spot on. I thank you for your time, and patience. I wish I could reward you more. \$\endgroup\$ Nov 10 at 21:45
  • \$\begingroup\$ @user3799003, std::vector does not have this same stupid limitation as List so you are good to go! \$\endgroup\$
    – jdt
    Nov 10 at 22:05
  • \$\begingroup\$ @user3799003, one more thing that you should consider is that there is a cost involved every time you move between the managed and unmanaged space. It may be better to batch your calls to BigByteList instead of adding one element at a time. Here it would be best to experiment and see what is the most efficient =) \$\endgroup\$
    – jdt
    Nov 10 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.