[riot-notifications] [RIOT-OS/RIOT] [WIP] Generic memory block allocator (#7651)

Tobias Heider notifications at github.com
Fri Sep 29 17:08:32 CEST 2017


> Since the memarray is a coherent array of blocks, would it be possible to use a bit map of the free blocks, instead of a linked list? I believe this would make free O(1) and malloc O(N) with lower memory overhead than the linked list implementation.

I've thought about using a bitmap index, i think it is even possible to malloc in O(1) using bitmagic. However I think the allocator list is the least complex solution and does not have notably more overhead than the bitmap in small pools and scales better.

> That way the actual struct would be down to 4 bytes, and both allocating/deallocating can be done in O(1), also re-using existing code.

I've thought about what you said and I actually don't see any real advantage of using a clist. The non-clist approach works just as well as the one you described. The only reason `memarray_free` is O(N) is the check whether the pointer is actually a element of the list (which I think is actually not necessary as no other free implementation does this).  Other than that, size and number of elements are only needed in the `memarray_init` function, regardless whether a clist or a normal list is initialized, so the memarray_t could be reduced to one 4 byte "head of the list" pointer in both cases.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/RIOT-OS/RIOT/pull/7651#issuecomment-333152761
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.riot-os.org/pipermail/notifications/attachments/20170929/bc522376/attachment.html>


More information about the notifications mailing list