Repository: tailix/libkernaux (language: python)

Issue:
Rename memory allocator to free list



Discussion / hints:

Fix patch:
diff --git a/.gitignore b/.gitignore
index 8f453765..668b2ef2 100644
--- a/.gitignore
+++ b/.gitignore
@@ -129,7 +129,7 @@
 /tests/test_cmdline_gen
 /tests/test_cmdline_gen.c
 /tests/test_elf
-/tests/test_alloc
+/tests/test_free_list
 /tests/test_mbr
 /tests/test_memmap
 /tests/test_multiboot2_common_packing
diff --git a/ChangeLog b/ChangeLog
index ceab3fbb..6851f7d1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,10 +1,13 @@
+2022-06-22  Alex Kotov  <kotovalexarian@gmail.com>
+
+	* include/kernaux/free_list.h: Finished
+
 2022-06-21  Alex Kotov  <kotovalexarian@gmail.com>
 
 	* include/kernaux/generic/malloc.h: Added
 
 2022-06-20  Alex Kotov  <kotovalexarian@gmail.com>
 
-	* include/kernaux/alloc.h: Finished
 	* include/kernaux/generic/mutex.h: Mutex moved here
 	* include/kernaux/macro.h: Definitions "KERNAUX_ACCESS_*" made stable
 	* include/kernaux/macro.h: Macro "KERNAUX_PROTECTED_FIELD" added
@@ -15,8 +18,8 @@
 
 2022-06-17  Alex Kotov  <kotovalexarian@gmail.com>
 
-	* configure.ac: Added package "alloc"
-	* include/kernaux/alloc.h: Added
+	* configure.ac: Added package "free-list"
+	* include/kernaux/free_list.h: Added
 
 2022-06-16  Alex Kotov  <kotovalexarian@gmail.com>
 
diff --git a/Makefile.am b/Makefile.am
index 9a3ed72d..b1e38983 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -51,15 +51,15 @@ endif
 if WITH_FRAMEBUFFER
 libkernaux_la_SOURCES += src/framebuffer.c
 endif
+if WITH_FREE_LIST
+libkernaux_la_SOURCES += src/free_list.c
+endif
 if WITH_IO
 libkernaux_la_SOURCES += src/io.c
 endif
 if WITH_LIBC
 libkernaux_la_LIBADD += libc/libc.la
 endif
-if WITH_ALLOC
-libkernaux_la_SOURCES += src/alloc.c
-endif
 if WITH_MBR
 libkernaux_la_SOURCES += src/mbr.c
 endif
diff --git a/README.md b/README.md
index d70f1ddc..38e66974 100644
--- a/README.md
+++ b/README.md
@@ -58,7 +58,7 @@ zero). Work-in-progress APIs can change at any time.
   * [Framebuffer](/include/kernaux/framebuffer.h) (*planned*)
   * USB (*planned*)
 * Algorithms
-  * [Memory allocator](/include/kernaux/alloc.h) (*non-breaking since* **?.?.?**)
+  * [Free list memory allocator](/include/kernaux/free_list.h) (*non-breaking since* **?.?.?**)
   * [Simple command line parser](/include/kernaux/cmdline.h) (*non-breaking since* **0.2.0**)
     * [Example](/examples/cmdline.c)
   * [Page Frame Allocator](/include/kernaux/pfa.h) (*work in progress*)
@@ -154,8 +154,8 @@ stable options.
 All packages are included by default. To exclude all packages except those
 explicitly included, use `--without-all`.
 
-* `--with[out]-alloc` - memory allocator
 * `--with[out]-cmdline` - command line parser
+* `--with[out]-free-list` - free list memory allocator
 * `--with[out]-io` - input/output
 * `--with[out]-memmap` - memory map
 * `--with[out]-ntoa` - itoa/ftoa
diff --git a/configure.ac b/configure.ac
index 09070073..1095946b 100644
--- a/configure.ac
+++ b/configure.ac
@@ -57,11 +57,11 @@ AC_ARG_ENABLE([tests-python], AS_HELP_STRING([--enable-tests-python], [enable te
 
 dnl Packages (enabled by default)
 AC_ARG_WITH(  [all],          AS_HELP_STRING([--without-all],         [without all default packages]))
-AC_ARG_WITH(  [alloc],        AS_HELP_STRING([--without-alloc],       [without memory allocator]))
 AC_ARG_WITH(  [cmdline],      AS_HELP_STRING([--without-cmdline],     [without command line parser]))
 AC_ARG_WITH(  [console],      AS_HELP_STRING([--without-console],     [without serial console]))
 AC_ARG_WITH(  [elf],          AS_HELP_STRING([--without-elf],         [without ELF utils]))
 AC_ARG_WITH(  [framebuffer],  AS_HELP_STRING([--without-framebuffer], [without framebuffer]))
+AC_ARG_WITH(  [free-list],    AS_HELP_STRING([--without-free-list],   [without free list memory allocator]))
 AC_ARG_WITH(  [io],           AS_HELP_STRING([--without-io],          [without input/output]))
 AC_ARG_WITH(  [mbr],          AS_HELP_STRING([--without-mbr],         [without Master Boot Record]))
 AC_ARG_WITH(  [memmap],       AS_HELP_STRING([--without-memmap],      [without memory map]))
@@ -90,11 +90,11 @@ AS_IF([test "$enable_tests_all" = yes], do_enable_tests_all)
 
 AC_DEFUN([do_without_all],
 [
-if test -z "$with_alloc";       then with_alloc=no;       fi
 if test -z "$with_cmdline";     then with_cmdline=no;     fi
 if test -z "$with_console";     then with_console=no;     fi
 if test -z "$with_elf";         then with_elf=no;         fi
 if test -z "$with_framebuffer"; then with_framebuffer=no; fi
+if test -z "$with_free_list";   then with_free_list=no;   fi
 if test -z "$with_io";          then with_io=no;          fi
 if test -z "$with_mbr";         then with_mbr=no;         fi
 if test -z "$with_memmap";      then with_memmap=no;      fi
@@ -127,11 +127,11 @@ AS_IF([test "$enable_tests_python" = yes], [enable_tests_python=yes], [enable_te
 
 dnl Packages (enabled by default)
 AS_IF([test "$with_all"            = no ], [with_all=no],             [with_all=yes])
-AS_IF([test "$with_alloc"          = no ], [with_alloc=no],           [with_alloc=yes])
 AS_IF([test "$with_cmdline"        = no ], [with_cmdline=no],         [with_cmdline=yes])
 AS_IF([test "$with_console"        = no ], [with_console=no],         [with_console=yes])
 AS_IF([test "$with_elf"            = no ], [with_elf=no],             [with_elf=yes])
 AS_IF([test "$with_framebuffer"    = no ], [with_framebuffer=no],     [with_framebuffer=yes])
+AS_IF([test "$with_free_list"      = no ], [with_free_list=no],       [with_free_list=yes])
 AS_IF([test "$with_io"             = no ], [with_io=no],              [with_io=yes])
 AS_IF([test "$with_mbr"            = no ], [with_mbr=no],             [with_mbr=yes])
 AS_IF([test "$with_memmap"         = no ], [with_memmap=no],          [with_memmap=yes])
@@ -183,11 +183,11 @@ AM_CONDITIONAL([ENABLE_TESTS],        [test "$enable_tests"        = yes])
 AM_CONDITIONAL([ENABLE_TESTS_PYTHON], [test "$enable_tests_python" = yes])
 
 dnl Packages (enabled by default)
-AM_CONDITIONAL([WITH_ALLOC],          [test "$with_alloc"          = yes])
 AM_CONDITIONAL([WITH_CMDLINE],        [test "$with_cmdline"        = yes])
 AM_CONDITIONAL([WITH_CONSOLE],        [test "$with_console"        = yes])
 AM_CONDITIONAL([WITH_ELF],            [test "$with_elf"            = yes])
 AM_CONDITIONAL([WITH_FRAMEBUFFER],    [test "$with_framebuffer"    = yes])
+AM_CONDITIONAL([WITH_FREE_LIST],      [test "$with_free_list"      = yes])
 AM_CONDITIONAL([WITH_IO],             [test "$with_io"             = yes])
 AM_CONDITIONAL([WITH_MBR],            [test "$with_mbr"            = yes])
 AM_CONDITIONAL([WITH_MEMMAP],         [test "$with_memmap"         = yes])
@@ -224,11 +224,11 @@ AS_IF([test "$enable_tests"        = yes], [AC_DEFINE([ENABLE_TESTS],        [1]
 AS_IF([test "$enable_tests_python" = yes], [AC_DEFINE([ENABLE_TESTS_PYTHON], [1], [enabled tests that require Python 3 with YAML and Jinja2])])
 
 dnl Packages (enabled by default)
-AS_IF([test "$with_alloc"          = yes], [AC_DEFINE([WITH_ALLOC],          [1], [with memory allocator])])
 AS_IF([test "$with_cmdline"        = yes], [AC_DEFINE([WITH_CMDLINE],        [1], [with command line parser])])
 AS_IF([test "$with_console"        = yes], [AC_DEFINE([WITH_CONSOLE],        [1], [with serial console])])
 AS_IF([test "$with_elf"            = yes], [AC_DEFINE([WITH_ELF],            [1], [with ELF utils])])
 AS_IF([test "$with_framebuffer"    = yes], [AC_DEFINE([WITH_FRAMEBUFFER],    [1], [with framebuffer])])
+AS_IF([test "$with_free_list"      = yes], [AC_DEFINE([WITH_FREE_LIST],      [1], [with free list memory allocator])])
 AS_IF([test "$with_io"             = yes], [AC_DEFINE([WITH_IO],             [1], [with input/output])])
 AS_IF([test "$with_mbr"            = yes], [AC_DEFINE([WITH_MBR],            [1], [with Master Boot Record])])
 AS_IF([test "$with_memmap"         = yes], [AC_DEFINE([WITH_MEMMAP],         [1], [with memory map])])
@@ -252,11 +252,11 @@ AS_IF([test "$enable_debug"        = yes], [AC_DEFINE([KERNAUX_DEBUG],       [1]
 ##########################
 
 dnl Packages (enabled by default)
-AS_IF([test "$with_alloc"       = no], [AC_SUBST([comment_line_alloc],       [//])])
 AS_IF([test "$with_cmdline"     = no], [AC_SUBST([comment_line_cmdline],     [//])])
 AS_IF([test "$with_console"     = no], [AC_SUBST([comment_line_console],     [//])])
 AS_IF([test "$with_elf"         = no], [AC_SUBST([comment_line_elf],         [//])])
 AS_IF([test "$with_framebuffer" = no], [AC_SUBST([comment_line_framebuffer], [//])])
+AS_IF([test "$with_free_list"   = no], [AC_SUBST([comment_line_free_list],   [//])])
 AS_IF([test "$with_io"          = no], [AC_SUBST([comment_line_io],          [//])])
 AS_IF([test "$with_mbr"         = no], [AC_SUBST([comment_line_mbr],         [//])])
 AS_IF([test "$with_memmap"      = no], [AC_SUBST([comment_line_memmap],      [//])])
diff --git a/include/Makefile.am b/include/Makefile.am
index ffe30c3d..45e9ce02 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -19,9 +19,6 @@ if ASM_X86_64
 nobase_include_HEADERS += kernaux/asm/x86_64.h
 endif
 
-if WITH_ALLOC
-nobase_include_HEADERS += kernaux/alloc.h
-endif
 if WITH_CMDLINE
 nobase_include_HEADERS += kernaux/cmdline.h
 endif
@@ -34,6 +31,9 @@ endif
 if WITH_FRAMEBUFFER
 nobase_include_HEADERS += kernaux/framebuffer.h
 endif
+if WITH_FREE_LIST
+nobase_include_HEADERS += kernaux/free_list.h
+endif
 if WITH_IO
 nobase_include_HEADERS += kernaux/io.h
 endif
diff --git a/include/kernaux.h.in b/include/kernaux.h.in
index be4340d7..92c339ce 100644
--- a/include/kernaux.h.in
+++ b/include/kernaux.h.in
@@ -10,11 +10,11 @@
 #include <kernaux/generic/malloc.h>
 #include <kernaux/generic/mutex.h>
 
-@comment_line_alloc@#include <kernaux/alloc.h>
 @comment_line_cmdline@#include <kernaux/cmdline.h>
 @comment_line_console@#include <kernaux/console.h>
 @comment_line_elf@#include <kernaux/elf.h>
 @comment_line_framebuffer@#include <kernaux/framebuffer.h>
+@comment_line_free_list@#include <kernaux/free_list.h>
 @comment_line_io@#include <kernaux/io.h>
 @comment_line_mbr@#include <kernaux/mbr.h>
 @comment_line_memmap@#include <kernaux/memmap.h>
diff --git a/include/kernaux/alloc.h b/include/kernaux/alloc.h
deleted file mode 100644
index 604e3e6e..00000000
--- a/include/kernaux/alloc.h
+++ /dev/null
@@ -1,36 +0,0 @@
-#ifndef KERNAUX_INCLUDED_ALLOC
-#define KERNAUX_INCLUDED_ALLOC
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#include <kernaux/macro.h>
-#include <kernaux/generic/malloc.h>
-#include <kernaux/generic/mutex.h>
-
-#include <stddef.h>
-
-typedef struct KernAux_Alloc_Node {
-    struct KernAux_Alloc_Node *KERNAUX_PRIVATE_FIELD(next);
-    struct KernAux_Alloc_Node *KERNAUX_PRIVATE_FIELD(prev);
-    size_t KERNAUX_PRIVATE_FIELD(size);
-    char *KERNAUX_PRIVATE_FIELD(block);
-} *KernAux_Alloc_Node;
-
-typedef struct KernAux_Alloc {
-    struct KernAux_Malloc malloc;
-    KernAux_Mutex KERNAUX_PRIVATE_FIELD(mutex);
-    KernAux_Alloc_Node KERNAUX_PRIVATE_FIELD(head);
-} *KernAux_Alloc;
-
-struct KernAux_Alloc KernAux_Alloc_create(KernAux_Mutex mutex);
-void KernAux_Alloc_init(KernAux_Alloc alloc, KernAux_Mutex mutex);
-
-void KernAux_Alloc_add_zone(KernAux_Alloc alloc, void *ptr, size_t size);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif
diff --git a/include/kernaux/free_list.h b/include/kernaux/free_list.h
new file mode 100644
index 00000000..03a78291
--- /dev/null
+++ b/include/kernaux/free_list.h
@@ -0,0 +1,37 @@
+#ifndef KERNAUX_INCLUDED_FREE_LIST
+#define KERNAUX_INCLUDED_FREE_LIST
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <kernaux/macro.h>
+#include <kernaux/generic/malloc.h>
+#include <kernaux/generic/mutex.h>
+
+#include <stddef.h>
+
+typedef struct KernAux_FreeList_Node {
+    struct KernAux_FreeList_Node *KERNAUX_PRIVATE_FIELD(next);
+    struct KernAux_FreeList_Node *KERNAUX_PRIVATE_FIELD(prev);
+    size_t KERNAUX_PRIVATE_FIELD(size);
+    char *KERNAUX_PRIVATE_FIELD(block);
+} *KernAux_FreeList_Node;
+
+typedef struct KernAux_FreeList {
+    struct KernAux_Malloc malloc;
+    KernAux_Mutex KERNAUX_PRIVATE_FIELD(mutex);
+    KernAux_FreeList_Node KERNAUX_PRIVATE_FIELD(head);
+} *KernAux_FreeList;
+
+struct KernAux_FreeList KernAux_FreeList_create(KernAux_Mutex mutex);
+void KernAux_FreeList_init(KernAux_FreeList free_list, KernAux_Mutex mutex);
+
+void
+KernAux_FreeList_add_zone(KernAux_FreeList free_list, void *ptr, size_t size);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/src/alloc.c b/src/alloc.c
deleted file mode 100644
index 6ba1e76a..00000000
--- a/src/alloc.c
+++ /dev/null
@@ -1,283 +0,0 @@
-/**
- * The code was inspired by the Embedded Artistry's libmemory.
- *
- * Copyright (c) 2017-2022 Embedded Artistry LLC
- * Copyright (c) 2020-2022 Alex Kotov
- */
-
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include <kernaux/alloc.h>
-#include <kernaux/assert.h>
-#include <kernaux/generic/malloc.h>
-#include <kernaux/generic/mutex.h>
-
-#include <stddef.h>
-#include <stdint.h>
-#include <string.h>
-
-#define NODE_HEADER_SIZE (offsetof(struct KernAux_Alloc_Node, block))
-#define MIN_ZONE_SIZE (2 * NODE_HEADER_SIZE)
-#define MIN_SPLIT_SIZE (NODE_HEADER_SIZE + 16)
-
-#define CONTAINER_OF(ptr, type, member) ((type*)((uintptr_t)(ptr) - offsetof(type, member)))
-
-//#define ALIGN_MASK(align) ((align) - 1) // align should be a power of 2
-//#define ALIGN_UP(val, align) (((val) + ALIGN_MASK(align)) & ~ALIGN_MASK(align))
-
-//#define PTR_ALIGNMENT (sizeof(void*)) // TODO: align node to this value
-
-#define LOCK(alloc)                               \
-    do {                                          \
-        if ((alloc)->mutex) {                     \
-            KernAux_Mutex_lock((alloc)->mutex);   \
-        }                                         \
-    } while (0)
-
-#define UNLOCK(alloc)                             \
-    do {                                          \
-        if ((alloc)->mutex) {                     \
-            KernAux_Mutex_unlock((alloc)->mutex); \
-        }                                         \
-    } while (0)
-
-static void *KernAux_Alloc_calloc (void *malloc, size_t nmemb, size_t size);
-static void  KernAux_Alloc_free   (void *malloc, void *ptr);
-static void *KernAux_Alloc_malloc (void *malloc, size_t size);
-static void *KernAux_Alloc_realloc(void *malloc, void *ptr, size_t size);
-
-static void KernAux_Alloc_defrag(KernAux_Alloc alloc);
-static void KernAux_Alloc_insert(
-    KernAux_Alloc alloc,
-    KernAux_Alloc_Node node,
-    KernAux_Alloc_Node prev,
-    KernAux_Alloc_Node next
-);
-static void KernAux_Alloc_remove(KernAux_Alloc alloc, KernAux_Alloc_Node node);
-
-struct KernAux_Alloc KernAux_Alloc_create(const KernAux_Mutex mutex)
-{
-    struct KernAux_Alloc alloc;
-    alloc.malloc.calloc  = KernAux_Alloc_calloc;
-    alloc.malloc.free    = KernAux_Alloc_free;
-    alloc.malloc.malloc  = KernAux_Alloc_malloc;
-    alloc.malloc.realloc = KernAux_Alloc_realloc;
-    KernAux_Alloc_init(&alloc, mutex);
-    return alloc;
-}
-
-void KernAux_Alloc_init(const KernAux_Alloc alloc, const KernAux_Mutex mutex)
-{
-    KERNAUX_ASSERT(alloc);
-
-    alloc->mutex = mutex;
-    alloc->head = NULL;
-}
-
-void KernAux_Alloc_add_zone(
-    const KernAux_Alloc alloc,
-    void *const ptr,
-    const size_t size
-) {
-    KERNAUX_ASSERT(alloc);
-    KERNAUX_ASSERT(ptr);
-    KERNAUX_ASSERT(size >= MIN_ZONE_SIZE);
-
-    LOCK(alloc);
-
-    KernAux_Alloc_Node new_node = ptr;
-    new_node->size = size;
-
-    KernAux_Alloc_Node prev_node = NULL;
-    KernAux_Alloc_Node next_node;
-    KernAux_Alloc_Node last_node = NULL;
-
-    for (
-        KernAux_Alloc_Node item_node = alloc->head;
-        item_node;
-        item_node = item_node->next
-    ) {
-        last_node = item_node;
-
-        if (item_node > new_node) {
-            next_node = item_node;
-            if (item_node->prev) prev_node = item_node->prev;
-            goto block_found;
-        }
-    }
-
-    prev_node = last_node;
-    next_node = NULL;
-
-block_found:
-    KernAux_Alloc_insert(alloc, new_node, prev_node, next_node);
-    KernAux_Alloc_defrag(alloc);
-
-    UNLOCK(alloc);
-}
-
-void *KernAux_Alloc_calloc(
-    void *const malloc,
-    const size_t nmemb,
-    const size_t size
-) {
-    KERNAUX_ASSERT(malloc);
-
-    const size_t total_size = nmemb * size;
-    KERNAUX_ASSERT(total_size >= nmemb);
-    KERNAUX_ASSERT(total_size >= size);
-    KERNAUX_ASSERT(total_size / nmemb == size);
-
-    void *const ptr = KernAux_Alloc_malloc(malloc, total_size);
-    if (ptr) memset(ptr, 0, total_size);
-    return ptr;
-}
-
-void KernAux_Alloc_free(void *const malloc, void *const ptr)
-{
-    const KernAux_Alloc alloc = malloc;
-
-    KERNAUX_ASSERT(alloc);
-    if (!ptr) return;
-
-    LOCK(alloc);
-
-    KernAux_Alloc_Node node =
-        CONTAINER_OF(ptr, struct KernAux_Alloc_Node, block);
-
-    KernAux_Alloc_Node last_node = NULL;
-
-    for (
-        KernAux_Alloc_Node item_node = alloc->head;
-        item_node;
-        item_node = item_node->next
-    ) {
-        last_node = item_node;
-
-        if (item_node > node) {
-            KernAux_Alloc_insert(alloc, node, item_node->prev, item_node);
-            goto block_added;
-        }
-    }
-
-    KernAux_Alloc_insert(alloc, node, last_node, NULL);
-
-block_added:
-    KernAux_Alloc_defrag(alloc);
-
-    UNLOCK(alloc);
-}
-
-void *KernAux_Alloc_malloc(void *const malloc, const size_t size)
-{
-    const KernAux_Alloc alloc = malloc;
-
-    KERNAUX_ASSERT(alloc);
-    if (size == 0) return NULL;
-
-    LOCK(alloc);
-
-    KernAux_Alloc_Node node = NULL;
-
-    for (
-        KernAux_Alloc_Node item_node = alloc->head;
-        item_node;
-        item_node = item_node->next
-    ) {
-        if (item_node->size - NODE_HEADER_SIZE >= size) {
-            node = item_node;
-            break;
-        }
-    }
-
-    if (node) {
-        // Can we split the block?
-        if (node->size - size >= MIN_SPLIT_SIZE) {
-            KernAux_Alloc_Node new_node =
-                (KernAux_Alloc_Node)(((uintptr_t)&node->block) + size);
-            node->size = NODE_HEADER_SIZE + size;
-            new_node->size = node->size - size - NODE_HEADER_SIZE;
-            KernAux_Alloc_insert(alloc, new_node, node, node->next);
-        }
-
-        KernAux_Alloc_remove(alloc, node);
-    }
-
-    UNLOCK(alloc);
-
-    if (node) {
-        return &node->block;
-    } else {
-        return NULL;
-    }
-}
-
-void *KernAux_Alloc_realloc(
-    void *const malloc,
-    void *const ptr,
-    const size_t size
-) {
-    const KernAux_Alloc alloc = malloc;
-    KERNAUX_ASSERT(alloc);
-
-    KERNAUX_ASSERT(0); // TODO
-    (void)alloc;
-    (void)ptr;
-    (void)size;
-
-    return NULL;
-}
-
-void KernAux_Alloc_defrag(const KernAux_Alloc alloc)
-{
-    KERNAUX_ASSERT(alloc);
-
-    for (
-        KernAux_Alloc_Node item_node = alloc->head;
-        item_node;
-        item_node = item_node->next
-    ) {
-        const KernAux_Alloc_Node node = item_node->prev;
-        if (!node) continue;
-        if (((uintptr_t)node) + node->size != (uintptr_t)item_node) continue;
-
-        node->size += item_node->size;
-        KernAux_Alloc_remove(alloc, item_node);
-    }
-}
-
-void KernAux_Alloc_insert(
-    const KernAux_Alloc alloc,
-    const KernAux_Alloc_Node node,
-    const KernAux_Alloc_Node prev,
-    const KernAux_Alloc_Node next
-) {
-    KERNAUX_ASSERT(alloc);
-    KERNAUX_ASSERT(node);
-    KERNAUX_ASSERT(node != prev);
-    KERNAUX_ASSERT(node != next);
-    KERNAUX_ASSERT(!prev || prev->next == next);
-    KERNAUX_ASSERT(!next || next->prev == prev);
-
-    if (!prev) alloc->head = node;
-    node->next = next;
-    node->prev = prev;
-    if (node->next) node->next->prev = node;
-    if (node->prev) node->prev->next = node;
-}
-
-void KernAux_Alloc_remove(
-    const KernAux_Alloc alloc,
-    const KernAux_Alloc_Node node
-) {
-    KERNAUX_ASSERT(alloc);
-    KERNAUX_ASSERT(node);
-    KERNAUX_ASSERT(!node->next || node->next->prev == node);
-    KERNAUX_ASSERT(!node->prev || node->prev->next == node);
-
-    if (alloc->head == node) alloc->head = node->next;
-    if (node->next) node->next->prev = node->prev;
-    if (node->prev) node->prev->next = node->next;
-}
diff --git a/src/free_list.c b/src/free_list.c
new file mode 100644
index 00000000..88a9ee01
--- /dev/null
+++ b/src/free_list.c
@@ -0,0 +1,293 @@
+/**
+ * The code was inspired by the Embedded Artistry's libmemory.
+ *
+ * Copyright (c) 2017-2022 Embedded Artistry LLC
+ * Copyright (c) 2020-2022 Alex Kotov
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <kernaux/assert.h>
+#include <kernaux/free_list.h>
+#include <kernaux/generic/malloc.h>
+#include <kernaux/generic/mutex.h>
+
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#define NODE_HEADER_SIZE (offsetof(struct KernAux_FreeList_Node, block))
+#define MIN_ZONE_SIZE (2 * NODE_HEADER_SIZE)
+#define MIN_SPLIT_SIZE (NODE_HEADER_SIZE + 16)
+
+#define CONTAINER_OF(ptr, type, member) ((type*)((uintptr_t)(ptr) - offsetof(type, member)))
+
+//#define ALIGN_MASK(align) ((align) - 1) // align should be a power of 2
+//#define ALIGN_UP(val, align) (((val) + ALIGN_MASK(align)) & ~ALIGN_MASK(align))
+
+//#define PTR_ALIGNMENT (sizeof(void*)) // TODO: align node to this value
+
+#define LOCK(free_list)                               \
+    do {                                              \
+        if ((free_list)->mutex) {                     \
+            KernAux_Mutex_lock((free_list)->mutex);   \
+        }                                             \
+    } while (0)
+
+#define UNLOCK(free_list)                             \
+    do {                                              \
+        if ((free_list)->mutex) {                     \
+            KernAux_Mutex_unlock((free_list)->mutex); \
+        }                                             \
+    } while (0)
+
+static void *KernAux_FreeList_calloc (void *malloc, size_t nmemb, size_t size);
+static void  KernAux_FreeList_free   (void *malloc, void *ptr);
+static void *KernAux_FreeList_malloc (void *malloc, size_t size);
+static void *KernAux_FreeList_realloc(void *malloc, void *ptr, size_t size);
+
+static void KernAux_FreeList_defrag(KernAux_FreeList free_list);
+static void KernAux_FreeList_insert(
+    KernAux_FreeList free_list,
+    KernAux_FreeList_Node node,
+    KernAux_FreeList_Node prev,
+    KernAux_FreeList_Node next
+);
+static void KernAux_FreeList_remove(
+    KernAux_FreeList free_list,
+    KernAux_FreeList_Node node
+);
+
+struct KernAux_FreeList KernAux_FreeList_create(const KernAux_Mutex mutex)
+{
+    struct KernAux_FreeList free_list;
+    KernAux_FreeList_init(&free_list, mutex);
+    return free_list;
+}
+
+void KernAux_FreeList_init(
+    const KernAux_FreeList free_list,
+    const KernAux_Mutex mutex
+) {
+    KERNAUX_ASSERT(free_list);
+
+    free_list->malloc.calloc  = KernAux_FreeList_calloc;
+    free_list->malloc.free    = KernAux_FreeList_free;
+    free_list->malloc.malloc  = KernAux_FreeList_malloc;
+    free_list->malloc.realloc = KernAux_FreeList_realloc;
+    free_list->mutex = mutex;
+    free_list->head = NULL;
+}
+
+void KernAux_FreeList_add_zone(
+    const KernAux_FreeList free_list,
+    void *const ptr,
+    const size_t size
+) {
+    KERNAUX_ASSERT(free_list);
+    KERNAUX_ASSERT(ptr);
+    KERNAUX_ASSERT(size >= MIN_ZONE_SIZE);
+
+    LOCK(free_list);
+
+    KernAux_FreeList_Node new_node = ptr;
+    new_node->size = size;
+
+    KernAux_FreeList_Node prev_node = NULL;
+    KernAux_FreeList_Node next_node;
+    KernAux_FreeList_Node last_node = NULL;
+
+    for (
+        KernAux_FreeList_Node item_node = free_list->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        last_node = item_node;
+
+        if (item_node > new_node) {
+            next_node = item_node;
+            if (item_node->prev) prev_node = item_node->prev;
+            goto block_found;
+        }
+    }
+
+    prev_node = last_node;
+    next_node = NULL;
+
+block_found:
+    KernAux_FreeList_insert(free_list, new_node, prev_node, next_node);
+    KernAux_FreeList_defrag(free_list);
+
+    UNLOCK(free_list);
+}
+
+void *KernAux_FreeList_calloc(
+    void *const malloc,
+    const size_t nmemb,
+    const size_t size
+) {
+    KERNAUX_ASSERT(malloc);
+
+    const size_t total_size = nmemb * size;
+    KERNAUX_ASSERT(total_size >= nmemb);
+    KERNAUX_ASSERT(total_size >= size);
+    KERNAUX_ASSERT(total_size / nmemb == size);
+
+    void *const ptr = KernAux_FreeList_malloc(malloc, total_size);
+    if (ptr) memset(ptr, 0, total_size);
+    return ptr;
+}
+
+void KernAux_FreeList_free(void *const malloc, void *const ptr)
+{
+    const KernAux_FreeList free_list = malloc;
+
+    KERNAUX_ASSERT(free_list);
+    if (!ptr) return;
+
+    LOCK(free_list);
+
+    KernAux_FreeList_Node node =
+        CONTAINER_OF(ptr, struct KernAux_FreeList_Node, block);
+
+    KernAux_FreeList_Node last_node = NULL;
+
+    for (
+        KernAux_FreeList_Node item_node = free_list->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        last_node = item_node;
+
+        if (item_node > node) {
+            KernAux_FreeList_insert(
+                free_list,
+                node,
+                item_node->prev,
+                item_node
+            );
+            goto block_added;
+        }
+    }
+
+    KernAux_FreeList_insert(free_list, node, last_node, NULL);
+
+block_added:
+    KernAux_FreeList_defrag(free_list);
+
+    UNLOCK(free_list);
+}
+
+void *KernAux_FreeList_malloc(void *const malloc, const size_t size)
+{
+    const KernAux_FreeList free_list = malloc;
+
+    KERNAUX_ASSERT(free_list);
+    if (size == 0) return NULL;
+
+    LOCK(free_list);
+
+    KernAux_FreeList_Node node = NULL;
+
+    for (
+        KernAux_FreeList_Node item_node = free_list->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        if (item_node->size - NODE_HEADER_SIZE >= size) {
+            node = item_node;
+            break;
+        }
+    }
+
+    if (node) {
+        // Can we split the block?
+        if (node->size - size >= MIN_SPLIT_SIZE) {
+            KernAux_FreeList_Node new_node =
+                (KernAux_FreeList_Node)(((uintptr_t)&node->block) + size);
+            node->size = NODE_HEADER_SIZE + size;
+            new_node->size = node->size - size - NODE_HEADER_SIZE;
+            KernAux_FreeList_insert(free_list, new_node, node, node->next);
+        }
+
+        KernAux_FreeList_remove(free_list, node);
+    }
+
+    UNLOCK(free_list);
+
+    if (node) {
+        return &node->block;
+    } else {
+        return NULL;
+    }
+}
+
+void *KernAux_FreeList_realloc(
+    void *const malloc,
+    void *const ptr,
+    const size_t size
+) {
+    const KernAux_FreeList free_list = malloc;
+    KERNAUX_ASSERT(free_list);
+
+    KERNAUX_ASSERT(0); // TODO
+    (void)free_list;
+    (void)ptr;
+    (void)size;
+
+    return NULL;
+}
+
+void KernAux_FreeList_defrag(const KernAux_FreeList free_list)
+{
+    KERNAUX_ASSERT(free_list);
+
+    for (
+        KernAux_FreeList_Node item_node = free_list->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        const KernAux_FreeList_Node node = item_node->prev;
+        if (!node) continue;
+        if (((uintptr_t)node) + node->size != (uintptr_t)item_node) continue;
+
+        node->size += item_node->size;
+        KernAux_FreeList_remove(free_list, item_node);
+    }
+}
+
+void KernAux_FreeList_insert(
+    const KernAux_FreeList free_list,
+    const KernAux_FreeList_Node node,
+    const KernAux_FreeList_Node prev,
+    const KernAux_FreeList_Node next
+) {
+    KERNAUX_ASSERT(free_list);
+    KERNAUX_ASSERT(node);
+    KERNAUX_ASSERT(node != prev);
+    KERNAUX_ASSERT(node != next);
+    KERNAUX_ASSERT(!prev || prev->next == next);
+    KERNAUX_ASSERT(!next || next->prev == prev);
+
+    if (!prev) free_list->head = node;
+    node->next = next;
+    node->prev = prev;
+    if (node->next) node->next->prev = node;
+    if (node->prev) node->prev->next = node;
+}
+
+void KernAux_FreeList_remove(
+    const KernAux_FreeList free_list,
+    const KernAux_FreeList_Node node
+) {
+    KERNAUX_ASSERT(free_list);
+    KERNAUX_ASSERT(node);
+    KERNAUX_ASSERT(!node->next || node->next->prev == node);
+    KERNAUX_ASSERT(!node->prev || node->prev->next == node);
+
+    if (free_list->head == node) free_list->head = node->next;
+    if (node->next) node->next->prev = node->prev;
+    if (node->prev) node->prev->next = node->next;
+}


Test patch:
diff --git a/tests/Makefile.am b/tests/Makefile.am
index b678d571..d5d476e8 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -56,18 +56,6 @@ multiboot2_info_print2_SOURCES = \
 	multiboot2_info_example2.h
 endif
 
-##############
-# test_alloc #
-##############
-
-if WITH_ALLOC
-TESTS += test_alloc
-test_alloc_LDADD = $(top_builddir)/libkernaux.la
-test_alloc_SOURCES = \
-	main.c \
-	test_alloc.c
-endif
-
 ################
 # test_cmdline #
 ################
@@ -114,6 +102,18 @@ test_elf_SOURCES = \
 	test_elf.c
 endif
 
+##################
+# test_free_list #
+##################
+
+if WITH_FREE_LIST
+TESTS += test_free_list
+test_free_list_LDADD = $(top_builddir)/libkernaux.la
+test_free_list_SOURCES = \
+	main.c \
+	test_free_list.c
+endif
+
 ############
 # test_mbr #
 ############
diff --git a/tests/test_alloc.c b/tests/test_alloc.c
deleted file mode 100644
index 9fc51d7f..00000000
--- a/tests/test_alloc.c
+++ /dev/null
@@ -1,106 +0,0 @@
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#define KERNAUX_ACCESS_PRIVATE
-
-#include <kernaux/alloc.h>
-
-#include <assert.h>
-#include <stddef.h>
-#include <string.h>
-
-static void test_default();
-static void test_calloc();
-static void test_calloc_nomem();
-static void test_cross_zone_defrag();
-
-void test_main()
-{
-    test_default();
-    test_calloc();
-    test_calloc_nomem();
-    test_cross_zone_defrag();
-}
-
-void test_default()
-{
-    char memory_block[1000];
-    struct KernAux_Alloc alloc = KernAux_Alloc_create(NULL);
-    KernAux_Alloc_add_zone(&alloc, memory_block, sizeof(memory_block));
-
-    char *const ptr1 = KernAux_Malloc_malloc(&alloc.malloc, 100);
-    assert(ptr1);
-    assert(ptr1 > memory_block);
-    assert(ptr1 < &memory_block[1000]);
-
-    char *const ptr2 = KernAux_Malloc_calloc(&alloc.malloc, 100, 1);
-    assert(ptr2);
-    assert(ptr2 > ptr1);
-    assert(ptr2 < &memory_block[1000]);
-
-    char *const ptr3 = KernAux_Malloc_calloc(&alloc.malloc, 1, 100);
-    assert(ptr3);
-    assert(ptr3 > ptr2);
-    assert(ptr3 < &memory_block[1000]);
-
-    char *const ptr4 = KernAux_Malloc_malloc(&alloc.malloc, 100);
-    assert(ptr4);
-    assert(ptr4 > ptr3);
-    assert(ptr4 < &memory_block[1000]);
-
-    KernAux_Malloc_free(&alloc.malloc, ptr2);
-    KernAux_Malloc_free(&alloc.malloc, ptr3);
-
-    char *const ptr5 = KernAux_Malloc_malloc(&alloc.malloc, 100);
-    assert(ptr5 == ptr2);
-
-    char *const ptr6 = KernAux_Malloc_calloc(&alloc.malloc, 10, 10);
-    assert(ptr6 == ptr3);
-
-    KernAux_Malloc_free(&alloc.malloc, ptr2);
-    KernAux_Malloc_free(&alloc.malloc, ptr3);
-
-    char *const ptr7 = KernAux_Malloc_malloc(&alloc.malloc, 200);
-    assert(ptr7 == ptr2);
-}
-
-void test_calloc()
-{
-    char zone[1000];
-    struct KernAux_Alloc alloc = KernAux_Alloc_create(NULL);
-    KernAux_Alloc_add_zone(&alloc, zone, 1000);
-    char *const ptr = KernAux_Malloc_calloc(&alloc.malloc, 1, 900);
-    for (size_t index = 0; index < 900; ++index) {
-        assert(ptr[index] == 0);
-    }
-    KernAux_Malloc_free(&alloc.malloc, ptr);
-}
-
-void test_calloc_nomem()
-{
-    char zone[1000];
-    struct KernAux_Alloc alloc = KernAux_Alloc_create(NULL);
-    KernAux_Alloc_add_zone(&alloc, zone, sizeof(zone));
-    void *const ptr = KernAux_Malloc_calloc(&alloc.malloc, 1, sizeof(zone));
-    assert(ptr == NULL);
-}
-
-void test_cross_zone_defrag()
-{
-    char zone[1000];
-    struct KernAux_Alloc alloc = KernAux_Alloc_create(NULL);
-    KernAux_Alloc_add_zone(&alloc, &zone[0],   500);
-    KernAux_Alloc_add_zone(&alloc, &zone[500], 500);
-
-    size_t nodes_count = 0;
-    for (
-        KernAux_Alloc_Node item_node = alloc.head;
-        item_node;
-        item_node = item_node->next
-    ) {
-        ++nodes_count;
-    }
-
-    assert(nodes_count == 1);
-}
diff --git a/tests/test_free_list.c b/tests/test_free_list.c
new file mode 100644
index 00000000..9c632d5a
--- /dev/null
+++ b/tests/test_free_list.c
@@ -0,0 +1,106 @@
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#define KERNAUX_ACCESS_PRIVATE
+
+#include <kernaux/free_list.h>
+
+#include <assert.h>
+#include <stddef.h>
+#include <string.h>
+
+static void test_default();
+static void test_calloc();
+static void test_calloc_nomem();
+static void test_cross_zone_defrag();
+
+void test_main()
+{
+    test_default();
+    test_calloc();
+    test_calloc_nomem();
+    test_cross_zone_defrag();
+}
+
+void test_default()
+{
+    char memory_block[1000];
+    struct KernAux_FreeList free_list = KernAux_FreeList_create(NULL);
+    KernAux_FreeList_add_zone(&free_list, memory_block, sizeof(memory_block));
+
+    char *const ptr1 = KernAux_Malloc_malloc(&free_list.malloc, 100);
+    assert(ptr1);
+    assert(ptr1 > memory_block);
+    assert(ptr1 < &memory_block[1000]);
+
+    char *const ptr2 = KernAux_Malloc_calloc(&free_list.malloc, 100, 1);
+    assert(ptr2);
+    assert(ptr2 > ptr1);
+    assert(ptr2 < &memory_block[1000]);
+
+    char *const ptr3 = KernAux_Malloc_calloc(&free_list.malloc, 1, 100);
+    assert(ptr3);
+    assert(ptr3 > ptr2);
+    assert(ptr3 < &memory_block[1000]);
+
+    char *const ptr4 = KernAux_Malloc_malloc(&free_list.malloc, 100);
+    assert(ptr4);
+    assert(ptr4 > ptr3);
+    assert(ptr4 < &memory_block[1000]);
+
+    KernAux_Malloc_free(&free_list.malloc, ptr2);
+    KernAux_Malloc_free(&free_list.malloc, ptr3);
+
+    char *const ptr5 = KernAux_Malloc_malloc(&free_list.malloc, 100);
+    assert(ptr5 == ptr2);
+
+    char *const ptr6 = KernAux_Malloc_calloc(&free_list.malloc, 10, 10);
+    assert(ptr6 == ptr3);
+
+    KernAux_Malloc_free(&free_list.malloc, ptr2);
+    KernAux_Malloc_free(&free_list.malloc, ptr3);
+
+    char *const ptr7 = KernAux_Malloc_malloc(&free_list.malloc, 200);
+    assert(ptr7 == ptr2);
+}
+
+void test_calloc()
+{
+    char zone[1000];
+    struct KernAux_FreeList free_list = KernAux_FreeList_create(NULL);
+    KernAux_FreeList_add_zone(&free_list, zone, 1000);
+    char *const ptr = KernAux_Malloc_calloc(&free_list.malloc, 1, 900);
+    for (size_t index = 0; index < 900; ++index) {
+        assert(ptr[index] == 0);
+    }
+    KernAux_Malloc_free(&free_list.malloc, ptr);
+}
+
+void test_calloc_nomem()
+{
+    char zone[1000];
+    struct KernAux_FreeList free_list = KernAux_FreeList_create(NULL);
+    KernAux_FreeList_add_zone(&free_list, zone, sizeof(zone));
+    void *const ptr = KernAux_Malloc_calloc(&free_list.malloc, 1, sizeof(zone));
+    assert(ptr == NULL);
+}
+
+void test_cross_zone_defrag()
+{
+    char zone[1000];
+    struct KernAux_FreeList free_list = KernAux_FreeList_create(NULL);
+    KernAux_FreeList_add_zone(&free_list, &zone[0],   500);
+    KernAux_FreeList_add_zone(&free_list, &zone[500], 500);
+
+    size_t nodes_count = 0;
+    for (
+        KernAux_FreeList_Node item_node = free_list.head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        ++nodes_count;
+    }
+
+    assert(nodes_count == 1);
+}