I recently tried to use the free-list allocator in the standard library, but encountered some problems during use.Then I inspected this part of the code and found some other problems.

The pronlems are below:

1. When allocations are frequent and the size fluctuates greatly, it is easy to degenerate into only a proxy of the parent allocator and cannot make good use of free memory blocks.

2. When the memory size to be allocated is not in the [min, max] range, it instead requests the parent allocator to allocate, but this is unreasonable. This unreasonable request should be rejected and null should be returned.

3. The allocateZeroed method does not necessarily depend on the parent allocator's allocateZeroed.

4. It is not reasonable to directly forward the expand and reallocate methods of parent allocator.In fact, expand does not depend on the expand of parent allocator, and this also isolates the possibility of alignedExpand and alignedReallocate.

5. It cannot perfectly cope with situations where it does not exclusively onws the parent allocator.For example, when the free-list allocator does not exclusively onws the parent allocator, method owns may regard blocks allocated by other allocators that rely on the same parent allocator as being allocated by itself. Allocator's deallocate and deallocateAll have the same problem.

My ideas for improvement are as follows:

1. Add a field called volum for Node, indicating the memory size allocated by this block excluding Node, and the memory occupied by Node will not be overwritten. That is to say, when the block where Node is located is allocated, the memory occupied by Node itself will not be overwritten.

2. The free-list allocator maintains two linked lists internally, one representing the free memory block linked list, and the other representing the allocated memory block linked list. The free memory block linked list is sorted and inserted according to the size of the corresponding volum from small to large.

3. When an allocation request occurs, it will first try to search in the free memory block linked list. Because this linked list is sorted, it can allocate the memory block with the most suitable size relatively quickly. If a suitable memory block is found, it will be allocated and put the Node corresponding to this memory block at the beginning of the allocated-list, otherwise forward the request to the parent, construct a Node, and put this Node at the beginning of the allocated-list. If the adaptive mode is turned on, there will be some additional optimization operations during this period.

4. When choosing to deallocate a memory block, it will first check whether the block is being managed on the allocated-list (this is also the implementation logic of owns). If it is true, the block will be removed and inserted into the free-list. This operation It does not really return the memory block to the parent. The same is true for deallocateAll. This method inserts all memory blocks managed by allocated-list into free-list for future allocation requests.

5. When this allocator is destroyed, the memory blocks managed by the two linked lists will be returned to the parent. Of course, you can also manually reduce the length of the free-list.

6. Then based on the above ideas, I provide alignedAllocate, alignedExpand and alignedRellocate, resolveInternalPointer.

This is just a general idea. For details, you can check out the code I improved on https://github.com/malyjacob/free-list. There are comments and explanations in it. Of course, I only improved the non-thread safe parts. If possible, the thread safe version can also adopt this improvement idea.