Changes between Version 5 and Version 6 of FAQ/AlgorithmicComplexity


Ignore:
Timestamp:
Feb 3, 2006, 8:01:05 AM (14 years ago)
Author:
JoelSherrill
Comment:

/* Heap */ Add Pavel's suggestion of TLSF

Legend:

Unmodified
Added
Removed
Modified
  • FAQ/AlgorithmicComplexity

    v5 v6  
    8383
    8484The list of free blocks is managed as an unsorted listed.  Allocating a memory block requires a linear search of all free blocks until one large enough to satisfy the request is located.
     85== Pavel Pisa's Suggestion ==
     86
     87Posted as http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html
     88
     89TLSF dynamic storage allocator
     90
     91http://rtportal.upv.es/rtmalloc/allocators/tlsf/index.shtml
     92
     93This is nice approach, O(1) allocate, O(1) delete. Needs to do
     94find first bit set to compute log of size and then two find first
     95bit set instructions and atomic double linked list delete for allocate.
     96
     97Only log computation and some set bit and list insert
     98for free. Fragmentation is kept on reasonable level
     99
     100As for license, I know the people and I expect no problems.
     101Even rewrite of the code onto RTEMS primitives from scratch
     102is possible. Idea is so clean, simple but unique that there
     103is no problem to reimplement it.
    85104= Classic API =
    86105