Arduino Dynamic Array

No, only pointers to DYNAMIC allocations need to be moved.

Either manually have a list of a few variables or have an array of pointers… and only those can be defragged, etc.

At some point you have to decide how abstract you need things. I imagined the important part is allocating a FEW objects of various sizes and juggling/resizing them. The pointers themselves don’t really need to be dynamic.

unsigned char *dynamic_ptr[10];

Etc… And you could use some macros to get prettier code vs dynamic_ptr[5] everywhere.

I still have very little idea what you’re thinking.

  • How does the defragger know which heap objects it can and can’t relocate?
  • How does the defragger know where the pointers referencing the heap objects are located?
  • How does the system handle pointers to pointers?

When I was thinking of having pointers to pointers,
I was thinking of the typical implementation of a shared pointer:

Shared Pointer Implementation
template< typename T >
class SharedPointerSentry
{
private:
	using Counter = unsigned int;

private:
	T * pointer;
	Counter useCount;

public:
	SharedPointerSentry(T * pointer, int useCount)
		: pointer(pointer), useCount(useCount)
	{
	}
	
	T * getPointer(void) const
	{
		return this->pointer;
	}
	
	bool isAlive(void) const
	{
		return (this->useCount > 0);
	}
	
	void addReference(void)
	{
		++this->useCount;
	}
	
	void removeReference(void)
	{
		// Error condition
		if(useCount == 0)
			return;
		
		--this->useCount;
		if(useCount == 0)
		{
			delete pointer;
			pointer = nullptr;
		}
	}
};

template< typename T >
class SharedPointer
{
private:
	using Senty = SharedPointerSentry<T>;
	
private:
	Sentry * sentry;
	
public:
	SharedPointer(void) = default;

	SharedPointer(T * pointer)
		: sentry((pointer != nullptr) ? new Sentry(pointer, 1) : nullptr)
	{
	}
	
	SharedPointer(const SharedPointer & other)
		: sentry(other.sentry)
	{
		if(sentry != nullptr)
			sentry->addReference();
	}
	
	~SharedPointer(void)
	{
		if(sentry != nullptr)
		{
			this->sentry->removeReference();
			if(this->sentry->isAlive())
				delete this->sentry;
			this->sentry = nullptr;
		}
	}
	
	T * operator ->(void)
	{
		return (this->sentry != nullptr) ? this->sentry->getPointer() : nullptr;
	}
	
	const T * operator ->(void) const
	{
		return (this->sentry != nullptr) ? this->sentry->getPointer() : nullptr;
	}
	
	T & operator *(void)
	{
		if(this->sentry != nullptr)
			return *(this->sentry->getPointer());
		else
		{
			// Error case
			T * t = nullptr;
			return *t;
		}
	}
	
	const T & operator *(void) const
	{
		if(this->sentry != nullptr)
			return *(this->sentry->getPointer());
		else
		{
			// Error case
			T * t = nullptr;
			return *t;
		}
	}
};
  1. IMHO there wouldn’t be much point (on a small chip) if you didn’t allow EVERY heap object to be moved.
  2. I suggested an array of pointers that could be moved: unsigned char *dynamic_ptr[10];. Though perhaps it’d be void type and you’d recast them as needed.
  3. It wouldn’t. And it wouldn’t need to. In any pointer chain only the FINAL pointer should point to dynamically allocated memory. Anything else is kind of crazy IMHO.

You could have a class like shared pointer keep build on top of an array of dynamic pointers and abstract it further if you wanted. So you could create up to x SharedPointers and it would “just work”.

Oh, in C++ you can override ->, HA, that’s amazing. Didn’t know that.

For those like me that still have to think every time I use a pointer or reference, this would just add another level of confusion that would make my brain explode.

Every time you move a block you have to change the value of any pointer that was pointing to that block,
so if everything’s movable it becomes incredibly difficult to keep track of everything.

The only way I can think to do it requires forcing pointers to have precisely one owner, like a std::unique_ptr, but that would make actually using the pointers difficult.

That’s only half an answer.

Then you wouldn’t be able to implement trees or linked lists of any kind without some serious workarounds.

Where would one put the nodes of a linked list if not on the heap?

Nothing ‘just works’ without careful design and planning.

All the existing smart pointer types are quite complex internally.

  • std::unique_ptr overrides its copy assignment operator and copy constructor to perform a move instead.
  • std::shared_ptr maintains a heap-allocated object that holds the actual pointer and performs reference counting (in a manner similar to the code I posted, but more sophisticated).
  • std::weak_ptr, I don’t actually know it’s implemented, but I know it must be relatively complex because it’s capable of being temporarily ‘locked’ to ensure it’s strong for a given period of use and such mechanisms are rarely straightforward.

The C++ rabbit hole runs deep.
I recommend reading an implementation of the standard library some time,
there’s some really mind blowing stuff going on behind the scenes.

Pointers are more of an issue than references, which is why it bothers me that so many tutorials chose to exaplain pointers first.
References are the more natural choice.

To add to the confusion, the compiler will attempt to chain the -> operator until it returns a pointer, so if (for example) it returned a reference, the compiler would then call the -> operator of the object referred to.

struct ObjectA
{
  ObjectA * operator ->(void) const
  {
    return this;
  }

  void someFunction(void) {}
}

struct ObjectB
{
  ObjectA a;
  ObjectA & operator->(void) const
  {
  }
}

void test(void)
{
  ObjectB b;
  // Calls b.a.someFunction()
  b->someFunction();
}

Useful for implementing smart pointers, but it wouldn’t be wise to use it for much else, which is why not many people know about it.
I find people tend to see cool features like this and think “how can I abuse this?”.

Or to put it another way

Your scientists were so preoccupied with whether or not they could, they didn’t stop to think if they should.

Not if you only have a small amount of pointers… like say you have a screen buffer (or a few) and several sprites/masks to go with… that’s just one example of a use case where it’d be easy to keep all the pointers together in one place YET still benefit from the dynamic nature of allocating/deallocating the RAM.

Now if what you want is a linked list with 100 dynamically allocated elements - then yeah, that’s a bit tougher… but also it might not be THAT tough… if that’s ALL you need… walking a linked list and reallocating one element at a time to “defrag” it would likely be a pretty simply algorithm.

And yes, references are super helpful things - though I feel like they are just pointers by a different name.

Obviously all of this depends on someones use case and what they are wanting to do. There are situations where it might be trivial to keep track of things and situations where it might be next to impossible. I’m just saying it’s a spectrum and that there are definitely use cases as the “easy” end.

One could also imagine a runtime that made this simpler… like telling the runtime that all pointers themselves should be allocated in this given address space… so ANYWHERE in code you copied or created a pointer it would always be in that address space… then when you went to update pointers you’d just search for any matching pointer and update it also - no matter how many there were. Or even just move whole blocks of RAM and then iterate over all the pointers just applying the same “offset” to them if they are in the reallocation “zone”.

On a small AVR chip defrag by just shifting all of RAM down in order to close the gaps wouldn’t be that terrible of a dirty solution.

I am wondering if the OP is keeping up or even interested anymore? :slight_smile:

2 Likes