Current project status

[MichaelFabrizio]

I'd like to explain in more detail where the project stands, and also how the project will grow moving forward.

I view this project as having three parts:

1. The KeyVector data structure
2. The allocator class Pool, which initializes memory up-front for applications
3. Expand testing and compatibility

My goal is to stabilize the API for KeyVector first. I will accomplish this by expanding the testing coverage to include every possible state change.

Worth noting, it is possible to wrap KeyVector into an standard library vector:

std::vector<KeyVector> vector;

This allows you to create dynamic memory on the fly using battle-tested standard libraries by wrapping the KeyVector object. For this reason I am placing less focus right now on the Allocator class Pool, because there are good standard library options.

I really do need to emphasize for this case:

std::vector<KeyVector> vector;

Assumes KeyVector itself is memory safe. All methods need formal verification, and that's why I'm expanding test coverage first.

[MichaelFabrizio]

[July 23rd, 2024] Update:

[Status: Complete] Randomized testing for the KeyVector - High success correlation [Methodology]

1. A set of numbers N was chosen ranging from [0, N) and then shuffled using a pseudorandom generator
2. The shuffled set, N, was passed to the Add(const Key key) function.
3. Another shuffled set N2 on the range [0, N2) was passed to the Remove function.

[Axiom] For a sufficiently large set of N randomized keys, all KeyVector branches are activated multiple times.

[Conclusion] Tests were conducted in stages, for numbers on the range [0, 50000), and all values were tracked correctly to their equivalent key. This implies a strong degree of statistical accuracy of this model for moving elements around.

However, more tests need to be conducted for destructible T() elements, to confirm all code paths properly destroy every element.

[MichaelFabrizio]

July 27th, 2024

Important Project Considerations

• Users of this library can bypass the Allocator class Pool, and directly use a KeyVector. The easiest approach is to wrap a KeyVector in a std::unique_ptr.

typedef KeyVector<Health, unsigned char, 256> some_keyvec_type;
std::make_unique<some_keyvec_type>(new some_keyvec_type());

Pointer stability: The KeyVector does not have pointer stability. Let me clarify why this is important on a performance level. We must take a philosophy of immediately handling all state changes. This means when we call the Add(Key) function, that key is guaranteed to be immediately placed in the data structure.

In order to accomplish this, internally there are swaps between different elements. This occurs immediately. It's a valid design choice, but it does break pointer stability. It would be the library implementers' job to design their own wrapper API for an end user if they wanted to provide some such pointer stability.

In practical terms, this means a user of the KeyVector object should always follow this sequence for getting objects:

some_key_vec.Add(30); // Internal state has changed.

// **Must** call Find(Key) to refresh any elements. Do not reuse references.
auto& ref_key_30 = some_key_vec.Find(30);

// Free to use newly retrieved key.
ref_key_30.Health_Value = 100;

// Now, suppose a user calls Add(Key2) again
some_key_vec.Add(50); // Internal state has changed.

// **Must** call Find(Key) to refresh any elements.
// ref_key_30.Health_Value = 100; // UNDEFINED BEHAVIOR. OLD REFERENCE.
ref_key_30 = some_key_vec.Find(30); // REFRESHED POINTER. GOOD TO USE.