9.1. circular_heap — Circular heap

The circular heap is a dynamic memory allocator allocating buffers in a circular buffer. This puts a restriction on the user to free allocated buffers in the same order as they were allocated. This allocator is useful if you know the allocation order and need a low memory overhead on each allocated buffer and no memory fragmentation.

Below is an example of the internal state of a circular heap when buffers are allocated and freed.

  1. After initialization begin, alloc and free have the same value. All memory is available for allocation.

    begin
    alloc
     free                                                  end
      |-----------------------------------------------------|
    
  2. Allocating a buffer increments alloc.

    begin
     free                     alloc                        end
      |=========================|---------------------------|
    
  3. Allocating another buffer increments alloc once again.

    begin
     free                                      alloc       end
      |==========================================|----------|
    
  4. Freeing the first buffer increments free to the position of the first alloc.

    begin                      free            alloc       end
      |-------------------------|================|----------|
    
  5. Allocating a buffer that is bigger than the available space between alloc and end results in a buffer starting at begin. The memory between the old alloc and end will be unused.

    begin              alloc   free                        end
      |==================|------|================|oooooooooo|
    
  6. Freeing the second buffer increments free to the position of the second alloc.

    begin              alloc                    free       end
      |==================|-----------------------|oooooooooo|
    
  7. Freeing the third buffer sets free to alloc. All memory is available for allocation once again.

                       alloc
    begin               free                               end
      |------------------|----------------------------------|
    
  8. Done!


Source code: src/alloc/circular_heap.h, src/alloc/circular_heap.c

Test code: tst/alloc/circular_heap/main.c

Test coverage: src/alloc/circular_heap.c


Functions

int circular_heap_init(struct circular_heap_t *self_p, void *buf_p, size_t size)

Initialize given circular_heap.

Return
zero(0) or negative error code.
Parameters
  • self_p: Circular heap to initialize.
  • buf_p: Memory buffer.
  • size: Size of the memory buffer.

void *circular_heap_alloc(struct circular_heap_t *self_p, size_t size)

Allocate a buffer of given size from given circular heap.

Return
Pointer to allocated buffer, or NULL on failure.
Parameters
  • self_p: Circular heap to allocate from.
  • size: Number of bytes to allocate.

int circular_heap_free(struct circular_heap_t *self_p, void *buf_p)

Free the oldest allocated buffer.

Return
zero(0) or negative error code.
Parameters
  • self_p: Circular heap to free to.
  • buf_p: Buffer to free. Must be the oldest allocated buffer.

struct
#include <circular_heap.h>

Public Members

void *circular_heap_t::begin_p
void *circular_heap_t::end_p
void *circular_heap_t::alloc_p
void *circular_heap_t::free_p