Reimplement AVL trees
authorcoderain <coderain@sdf.org>
Wed, 7 Feb 2018 19:45:38 +0000 (20:45 +0100)
committercoderain <coderain@sdf.org>
Wed, 7 Feb 2018 19:45:38 +0000 (20:45 +0100)
kernel/include/avl_tree.h [deleted file]
kernel/include/cache.h
kernel/include/memory.h
kernel/src/avl_tree.c [deleted file]
kernel/src/cache.c
kernel/src/memory/memory.c
sdk/avltree.h [new file with mode: 0644]

diff --git a/kernel/include/avl_tree.h b/kernel/include/avl_tree.h
deleted file mode 100644 (file)
index ee5e5e7..0000000
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- * avl_tree.h
- *
- * Copyright (C) 2013 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as
- * published by the Free Software Foundation, either version 3 of the
- * License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef _AVL_TREE_H_
-#define _AVL_TREE_H_
-
-#include <common.h>
-
-typedef struct _avl_tree_t
-{
-    struct _avl_tree_t *parent, *left, *right, *next_equal;
-    qword_t key;
-} avl_tree_t;
-
-void avl_tree_insert(avl_tree_t **tree, avl_tree_t *node);
-avl_tree_t *avl_tree_lookup(avl_tree_t *tree, qword_t key);
-bool_t avl_tree_remove(avl_tree_t **tree, avl_tree_t *node);
-avl_tree_t *avl_tree_lower_bound(avl_tree_t *tree, qword_t key);
-avl_tree_t *avl_tree_upper_bound(avl_tree_t *tree, qword_t key);
-bool_t avl_tree_change_key(avl_tree_t **tree, avl_tree_t *node, qword_t new_key);
-avl_tree_t *avl_get_next_node(avl_tree_t *node);
-avl_tree_t *avl_get_previous_node(avl_tree_t *node);
-
-#endif
index e7abe15641d2f07b2736ee9995fd4d1cccfc9e20..f4492bccb2bcec8c4be2a9a8866abd73aac1cea4 100644 (file)
@@ -22,8 +22,8 @@
 
 #include <common.h>
 #include <sync.h>
-#include <avl_tree.h>
 #include <device.h>
+#include <sdk/avltree.h>
 
 #define CACHE_WRITE_THROUGH (1 << 0)
 
@@ -31,7 +31,8 @@ typedef dword_t (*read_write_buffer_proc_t)(void *context, void *buffer, qword_t
 
 typedef struct
 {
-    avl_tree_t tree;
+    avl_node_t node;
+    qword_t address;
     bool_t dirty;
     byte_t data[VARIABLE_SIZE];
 } cache_entry_t;
@@ -48,10 +49,15 @@ typedef struct
     dword_t flags;
     dword_t block_size;
     read_write_buffer_proc_t read_proc, write_proc;
-    avl_tree_t *root;
+    avl_tree_t entries;
 } cache_descriptor_t;
 
-dword_t cleanup_cache(cache_descriptor_t *cache);
+void init_cache(cache_descriptor_t *cache,
+                dword_t flags,
+                dword_t block_size,
+                read_write_buffer_proc_t read_proc,
+                read_write_buffer_proc_t write_proc);
+void cleanup_cache(cache_descriptor_t *cache);
 dword_t read_cache(cache_descriptor_t *cache, void *context, byte_t *buffer, qword_t offset, dword_t length, dword_t *bytes_read);
 dword_t write_cache(cache_descriptor_t *cache, void *context, const byte_t *buffer, qword_t offset, dword_t length, dword_t *bytes_written);
 dword_t flush_cache(cache_descriptor_t *cache, void *context);
index 622ce29c8a21907ab1afaab0d6fde7629cabadb9..0392118b31a57d44e5cb1aa8dbcef93af383e018 100644 (file)
@@ -23,9 +23,9 @@
 #include <common.h>
 #include <interrupt.h>
 #include <boot/multiboot.h>
-#include <avl_tree.h>
 #include <object.h>
 #include <filesystem.h>
+#include <sdk/avltree.h>
 #include <sdk/memory.h>
 
 #define PAGE_SIZE      4096
@@ -91,8 +91,8 @@ typedef struct
     void *page_directory;
     void *pool_address;
     uintptr_t pool_size;
-    avl_tree_t *by_addr_tree_root;
-    avl_tree_t *by_size_tree_root;
+    avl_tree_t by_addr_tree;
+    avl_tree_t by_size_tree;
     resource_t resource;
     list_entry_t evictable_blocks;
     list_entry_t *evict_blk_ptr;
@@ -118,9 +118,11 @@ typedef struct
 
 struct memory_block
 {
-    avl_tree_t by_addr_tree;
-    avl_tree_t by_size_tree;
+    avl_node_t by_addr_node;
+    avl_node_t by_size_node;
     list_entry_t evict_link;
+    uintptr_t address;
+    size_t size;
     dword_t flags;
     memory_address_space_t *address_space;
     memory_section_t *section;
diff --git a/kernel/src/avl_tree.c b/kernel/src/avl_tree.c
deleted file mode 100644 (file)
index a4c2142..0000000
+++ /dev/null
@@ -1,271 +0,0 @@
-/*
- * avl_tree.c
- *
- * Copyright (C) 2016 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as
- * published by the Free Software Foundation, either version 3 of the
- * License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include <avl_tree.h>
-#include <exception.h>
-
-static int avl_tree_height(avl_tree_t *tree)
-{
-    if (tree == NULL) return 0;
-    return 1 + MAX(avl_tree_height(tree->left), avl_tree_height(tree->right));
-}
-
-static int avl_tree_balance_factor(avl_tree_t *tree)
-{
-    int left_height = avl_tree_height(tree->left);
-    int right_height = avl_tree_height(tree->right);
-
-    return left_height - right_height;
-}
-
-static void avl_tree_rotation(avl_tree_t **tree, bool_t clockwise)
-{
-    avl_tree_t *root = *tree;
-    if (root == NULL) return;
-
-    if (clockwise)
-    {
-        avl_tree_t *pivot = root->left;
-        root->left = pivot->right;
-        if (root->left) root->left->parent = root;
-        pivot->right = root;
-        pivot->parent = root->parent;
-        root->parent = pivot;
-        *tree = pivot;
-    }
-    else
-    {
-        avl_tree_t *pivot = root->right;
-        root->right = pivot->left;
-        if (root->right) root->right->parent = root;
-        pivot->left = root;
-        pivot->parent = root->parent;
-        root->parent = pivot;
-        *tree = pivot;
-    }
-}
-
-static void avl_tree_balance(avl_tree_t **tree)
-{
-    avl_tree_t *root = *tree;
-    if (root == NULL) return;
-
-    int balance_factor = avl_tree_balance_factor(root);
-    if (balance_factor < -1)
-    {
-        if (avl_tree_balance_factor(root->right) > 0) avl_tree_rotation(&root->right, TRUE);
-        avl_tree_rotation(tree, FALSE);
-    }
-    else if (balance_factor > 1)
-    {
-        if (avl_tree_balance_factor(root->left) < 0) avl_tree_rotation(&root->left, FALSE);
-        avl_tree_rotation(tree, TRUE);
-    }
-}
-
-static void avl_tree_insert_internal(avl_tree_t **tree, avl_tree_t *node, avl_tree_t *parent)
-{
-    avl_tree_t *root = *tree;
-
-    if (root == NULL)
-    {
-        node->parent = parent;
-        node->left = node->right = node->next_equal = NULL;
-        *tree = node;
-        return;
-    }
-
-    if (node->key < root->key) avl_tree_insert_internal(&root->left, node, root);
-    else avl_tree_insert_internal(&root->right, node, root);
-
-    avl_tree_balance(tree);
-}
-
-void avl_tree_insert(avl_tree_t **tree, avl_tree_t *node)
-{
-    avl_tree_t *existing = avl_tree_lookup(*tree, node->key);
-
-    if (existing != NULL)
-    {
-        node->next_equal = existing->next_equal;
-        existing->next_equal = node;
-    }
-    else
-    {
-        avl_tree_insert_internal(tree, node, NULL);
-    }
-}
-
-bool_t avl_tree_remove(avl_tree_t **tree, avl_tree_t *node)
-{
-    bool_t result;
-    avl_tree_t *root = *tree;
-    if (root == NULL) return FALSE;
-
-    if (root->key == node->key)
-    {
-        if (root->next_equal != NULL)
-        {
-            if (root == node)
-            {
-                root->next_equal->parent = root->parent;
-                root->next_equal->left = root->left;
-                root->next_equal->right = root->right;
-
-                if (root->parent)
-                {
-                    if (root == root->parent->left) root->parent->left = root->next_equal;
-                    else if (root == root->parent->right) root->parent->right = root->next_equal;
-                }
-
-                if (root->left) root->left->parent = root->next_equal;
-                if (root->right) root->right->parent = root->next_equal;
-
-                *tree = root->next_equal;
-            }
-            else
-            {
-                avl_tree_t *ptr = root;
-                while (ptr->next_equal != node) ptr = ptr->next_equal;
-                ptr->next_equal = ptr->next_equal->next_equal;
-            }
-        }
-        else if (root->left == NULL && root->right == NULL)
-        {
-            *tree = NULL;
-        }
-        else if (root->left != NULL && root->right == NULL)
-        {
-            root->left->parent = root->parent;
-            *tree = root->left;
-        }
-        else if (root->right != NULL && root->left == NULL)
-        {
-            root->right->parent = root->parent;
-            *tree = root->right;
-        }
-        else
-        {
-            avl_tree_t *replacement = root->left;
-            while (replacement->right != NULL) replacement = replacement->right;
-
-            avl_tree_t *next_replacement = NULL;
-
-            if (replacement->next_equal)
-            {
-                next_replacement = replacement->next_equal;
-                next_replacement->parent = replacement->parent;
-                next_replacement->left = replacement->left;
-                next_replacement->right = replacement->right;
-            }
-            else if (replacement->left)
-            {
-                next_replacement = replacement->left;
-            }
-
-            if (replacement->parent->right == replacement) replacement->parent->right = next_replacement;
-            else replacement->parent->left = next_replacement;
-
-            replacement->parent = root->parent;
-            replacement->left = root->left;
-            replacement->right = root->right;
-
-            if (root->left) root->left->parent = replacement;
-            if (root->right) root->right->parent = replacement;
-
-            *tree = replacement;
-        }
-
-        return TRUE;
-    }
-    else if (node->key < root->key) result = avl_tree_remove(&root->left, node);
-    else result = avl_tree_remove(&root->right, node);
-
-    avl_tree_balance(tree);
-    return result;
-}
-
-avl_tree_t *avl_tree_lookup(avl_tree_t *tree, qword_t key)
-{
-    if (tree == NULL) return NULL;
-
-    if (tree->key == key) return tree;
-    else if (key < tree->key) return avl_tree_lookup(tree->left, key);
-    else return avl_tree_lookup(tree->right, key);
-}
-
-avl_tree_t *avl_tree_lower_bound(avl_tree_t *tree, qword_t key)
-{
-    while (tree != NULL && tree->key > key) tree = tree->left;
-    if (tree == NULL) return NULL;
-
-    while (tree->right != NULL && tree->right->key <= key) tree = tree->right;
-    return tree;
-}
-
-avl_tree_t *avl_tree_upper_bound(avl_tree_t *tree, qword_t key)
-{
-    while (tree != NULL && tree->key < key) tree = tree->right;
-    if (tree == NULL) return NULL;
-
-    while (tree->left != NULL && tree->left->key >= key) tree = tree->left;
-    return tree;
-}
-
-bool_t avl_tree_change_key(avl_tree_t **tree, avl_tree_t *node, qword_t new_key)
-{
-    if (!avl_tree_remove(tree, node)) return FALSE;
-
-    node->key = new_key;
-    avl_tree_insert(tree, node);
-
-    return TRUE;
-}
-
-avl_tree_t *avl_get_next_node(avl_tree_t *node)
-{
-    if (node->right)
-    {
-        node = node->right;
-        while (node->left) node = node->left;
-    }
-    else
-    {
-        while (node->parent && node->parent->right == node) node = node->parent;
-        node = node->parent;
-    }
-
-    return node;
-}
-
-avl_tree_t *avl_get_previous_node(avl_tree_t *node)
-{
-    if (node->left)
-    {
-        node = node->left;
-        while (node->right) node = node->right;
-    }
-    else
-    {
-        while (node->parent && node->parent->left == node) node = node->parent;
-        node = node->parent;
-    }
-
-    return node;
-}
index fdbed04a7811ec2468f23b4ef8f5673242f70d11..4102e42f24adc92686603f4a3d9b40c2f655b125 100644 (file)
 #include <cache.h>
 #include <heap.h>
 
-static void flush_cache_internal(cache_descriptor_t *cache, avl_tree_t *node, void *context)
+static void flush_cache_internal(cache_descriptor_t *cache, avl_node_t *node, void *context)
 {
     if (node == NULL) return;
 
-    cache_entry_t *entry = CONTAINER_OF(node, cache_entry_t, tree);
+    cache_entry_t *entry = CONTAINER_OF(node, cache_entry_t, node);
     if (entry->dirty)
     {
         dword_t written;
-        dword_t ret = cache->write_proc(context, entry->data, entry->tree.key * cache->block_size, cache->block_size, &written);
+        dword_t ret = cache->write_proc(context, entry->data, entry->address * cache->block_size, cache->block_size, &written);
         if ((ret == ERR_SUCCESS) || (written == cache->block_size)) entry->dirty = FALSE;
     }
 
@@ -37,23 +37,47 @@ static void flush_cache_internal(cache_descriptor_t *cache, avl_tree_t *node, vo
     flush_cache_internal(cache, node->right, context);
 }
 
-static void cleanup_cache_internal(avl_tree_t *node)
+static void cleanup_cache_internal(avl_node_t *node)
 {
     if (node == NULL) return;
 
     cleanup_cache_internal(node->left);
     cleanup_cache_internal(node->right);
 
-    cache_entry_t *entry = CONTAINER_OF(node, cache_entry_t, tree);
+    cache_entry_t *entry = CONTAINER_OF(node, cache_entry_t, node);
     heap_free(&evictable_heap, entry);
 }
 
-dword_t cleanup_cache(cache_descriptor_t *cache)
+static int compare_address(const void *key1, const void *key2)
 {
-    cleanup_cache_internal(cache->root);
-    cache->root = NULL;
+    const qword_t first = *(const qword_t*)key1;
+    const qword_t second = *(const qword_t*)key2;
 
-    return ERR_SUCCESS;
+    if (first < second) return -1;
+    else if (first == second) return 0;
+    else return 1;
+}
+
+void init_cache(cache_descriptor_t *cache,
+                dword_t flags,
+                dword_t block_size,
+                read_write_buffer_proc_t read_proc,
+                read_write_buffer_proc_t write_proc)
+{
+    cache->enabled = TRUE;
+    cache->resource = 0;
+    cache->flags = flags;
+    cache->block_size = block_size;
+    cache->read_proc = read_proc;
+    cache->write_proc = write_proc;
+
+    AVL_TREE_INIT(&cache->entries, cache_entry_t, node, address, compare_address);
+}
+
+void cleanup_cache(cache_descriptor_t *cache)
+{
+    cleanup_cache_internal(cache->entries.root);
+    cache->entries.root = NULL;
 }
 
 dword_t read_cache(cache_descriptor_t *cache, void *context, byte_t *buffer, qword_t offset, dword_t length, dword_t *bytes_read)
@@ -70,14 +94,14 @@ dword_t read_cache(cache_descriptor_t *cache, void *context, byte_t *buffer, qwo
     for (i = first_block; i <= last_block; i++)
     {
         dword_t start_offset = 0, bytes_to_copy = cache->block_size;
-        avl_tree_t *element = avl_tree_lookup(cache->root, i);
+        avl_node_t *element = avl_tree_lookup(&cache->entries, &i);
 
         if (element == NULL && !exclusive)
         {
             release_resource(&cache->resource);
             acquire_resource_exclusive(&cache->resource);
             exclusive = TRUE;
-            element = avl_tree_lookup(cache->root, i);
+            element = avl_tree_lookup(&cache->entries, &i);
         }
 
         if (element == NULL)
@@ -85,7 +109,7 @@ dword_t read_cache(cache_descriptor_t *cache, void *context, byte_t *buffer, qwo
             cache_entry_t *new_entry = (cache_entry_t*)heap_alloc(&evictable_heap, sizeof(cache_entry_t) + cache->block_size);
             if (new_entry != NULL)
             {
-                new_entry->tree.key = i;
+                new_entry->address = i;
                 new_entry->dirty = FALSE;
             }
 
@@ -96,11 +120,11 @@ dword_t read_cache(cache_descriptor_t *cache, void *context, byte_t *buffer, qwo
                 break;
             }
 
-            avl_tree_insert(&cache->root, &new_entry->tree);
-            element = &new_entry->tree;
+            avl_tree_insert(&cache->entries, &new_entry->node);
+            element = &new_entry->node;
         }
 
-        cache_entry_t *entry = CONTAINER_OF(element, cache_entry_t, tree);
+        cache_entry_t *entry = CONTAINER_OF(element, cache_entry_t, node);
 
         if (first_block == last_block)
         {
@@ -138,7 +162,7 @@ dword_t write_cache(cache_descriptor_t *cache, void *context, const byte_t *buff
     for (i = first_block; i <= last_block; i++)
     {
         dword_t start_offset = 0, bytes_to_copy = cache->block_size;
-        avl_tree_t *element = avl_tree_lookup(cache->root, i);
+        avl_node_t *element = avl_tree_lookup(&cache->entries, &i);
 
         if (element == NULL)
         {
@@ -149,7 +173,7 @@ dword_t write_cache(cache_descriptor_t *cache, void *context, const byte_t *buff
                 break;
             }
 
-            new_entry->tree.key = i;
+            new_entry->address = i;
             new_entry->dirty = FALSE;
 
             ret = cache->read_proc(context, new_entry->data, i * (qword_t)cache->block_size, cache->block_size, NULL);
@@ -159,11 +183,11 @@ dword_t write_cache(cache_descriptor_t *cache, void *context, const byte_t *buff
                 break;
             }
 
-            avl_tree_insert(&cache->root, &new_entry->tree);
-            element = &new_entry->tree;
+            avl_tree_insert(&cache->entries, &new_entry->node);
+            element = &new_entry->node;
         }
 
-        cache_entry_t *entry = CONTAINER_OF(element, cache_entry_t, tree);
+        cache_entry_t *entry = CONTAINER_OF(element, cache_entry_t, node);
 
         if (first_block == last_block)
         {
@@ -201,6 +225,6 @@ dword_t write_cache(cache_descriptor_t *cache, void *context, const byte_t *buff
 
 dword_t flush_cache(cache_descriptor_t *cache, void *context)
 {
-    flush_cache_internal(cache, cache->root, context);
+    flush_cache_internal(cache, cache->entries.root, context);
     return ERR_SUCCESS;
 }
index 03458e3e1e367beb235d5a8788ac584428fedbad..15a3fc9ff68bc6ced54410430452a14ef27ae02a 100644 (file)
@@ -320,7 +320,7 @@ static void *evict_page_from_address_space(memory_address_space_t *space)
 
     while (chances)
     {
-        address = (dword_t)block->by_addr_tree.key + space->evict_page_num * PAGE_SIZE;
+        address = (dword_t)block->address + space->evict_page_num * PAGE_SIZE;
         pd_index = ADDR_TO_PDE(address);
         pt_index = ADDR_TO_PTE(address);
         if (!(cached_directory[pd_index] & PAGE_PRESENT)) goto next;
@@ -348,7 +348,7 @@ static void *evict_page_from_address_space(memory_address_space_t *space)
 next:
         space->evict_page_num++;
 
-        if (space->evict_page_num == (dword_t)block->by_size_tree.key)
+        if (space->evict_page_num == (dword_t)block->size)
         {
             space->evict_page_num = 0;
             space->evict_blk_ptr = space->evict_blk_ptr->next;
@@ -522,31 +522,31 @@ static void mem_tree_free(memory_block_t *block)
 static memory_block_t *find_block_by_addr_internal(memory_block_t *block, void *address)
 {
     qword_t key = (qword_t)(dword_t)address;
-    qword_t start_addr = block->by_addr_tree.key;
-    qword_t end_addr = start_addr + block->by_size_tree.key * PAGE_SIZE;
+    qword_t start_addr = block->address;
+    qword_t end_addr = start_addr + block->size * PAGE_SIZE;
 
     if (key >= start_addr && key < end_addr) return block;
 
     if (key < start_addr)
     {
-        if (!block->by_addr_tree.left) return NULL;
+        if (!block->by_addr_node.left) return NULL;
 
-        memory_block_t *left_block = CONTAINER_OF(block->by_addr_tree.left, memory_block_t, by_addr_tree);
+        memory_block_t *left_block = CONTAINER_OF(block->by_addr_node.left, memory_block_t, by_addr_node);
         return find_block_by_addr_internal(left_block, address);
     }
     else
     {
-        if (!block->by_addr_tree.right) return NULL;
+        if (!block->by_addr_node.right) return NULL;
 
-        memory_block_t *right_block = CONTAINER_OF(block->by_addr_tree.right, memory_block_t, by_addr_tree);
+        memory_block_t *right_block = CONTAINER_OF(block->by_addr_node.right, memory_block_t, by_addr_node);
         return find_block_by_addr_internal(right_block, address);
     }
 }
 
 static memory_block_t *find_block_by_addr(memory_address_space_t *space, void *address)
 {
-    if (!space->by_addr_tree_root) return NULL;
-    memory_block_t *root = CONTAINER_OF(space->by_addr_tree_root, memory_block_t, by_addr_tree);
+    if (!space->by_addr_tree.root) return NULL;
+    memory_block_t *root = CONTAINER_OF(space->by_addr_tree.root, memory_block_t, by_addr_node);
     return find_block_by_addr_internal(root, address);
 }
 
@@ -555,24 +555,24 @@ static bool_t clone_blocks_recursive(memory_address_space_t *space, memory_block
     memory_block_t *clone = mem_tree_alloc();
     if (clone == NULL) return FALSE;
 
-    clone->by_addr_tree.key = block->by_addr_tree.key;
-    clone->by_size_tree.key = block->by_size_tree.key;
+    clone->address = block->address;
+    clone->size = block->size;
     block->flags |= MEMORY_BLOCK_COPY_ON_WRITE;
     clone->flags = block->flags;
     clone->address_space = space;
     clone->section = block->section;
 
-    avl_tree_insert(&space->by_addr_tree_root, &clone->by_addr_tree);
-    avl_tree_insert(&space->by_size_tree_root, &clone->by_size_tree);
+    avl_tree_insert(&space->by_addr_tree, &clone->by_addr_node);
+    avl_tree_insert(&space->by_size_tree, &clone->by_size_node);
 
-    memory_block_t *left_block = CONTAINER_OF(block->by_addr_tree.left, memory_block_t, by_addr_tree);
-    memory_block_t *right_block = CONTAINER_OF(block->by_addr_tree.right, memory_block_t, by_addr_tree);
+    memory_block_t *left_block = CONTAINER_OF(block->by_addr_node.left, memory_block_t, by_addr_node);
+    memory_block_t *right_block = CONTAINER_OF(block->by_addr_node.right, memory_block_t, by_addr_node);
 
-    if ((block->by_addr_tree.left && !clone_blocks_recursive(space, left_block))
-        || (block->by_addr_tree.right && !clone_blocks_recursive(space, right_block)))
+    if ((block->by_addr_node.left && !clone_blocks_recursive(space, left_block))
+        || (block->by_addr_node.right && !clone_blocks_recursive(space, right_block)))
     {
-        avl_tree_remove(&space->by_addr_tree_root, &clone->by_addr_tree);
-        avl_tree_remove(&space->by_size_tree_root, &clone->by_size_tree);
+        avl_tree_remove(&space->by_addr_tree, &clone->by_addr_node);
+        avl_tree_remove(&space->by_size_tree, &clone->by_size_node);
         mem_tree_free(clone);
         return FALSE;
     }
@@ -583,8 +583,8 @@ static bool_t clone_blocks_recursive(memory_address_space_t *space, memory_block
 static inline void release_memory_block(memory_block_t *block)
 {
     dword_t page;
-    dword_t start_address = (dword_t)block->by_addr_tree.key;
-    dword_t end_address = start_address + (dword_t)block->by_size_tree.key * PAGE_SIZE;
+    dword_t start_address = (dword_t)block->address;
+    dword_t end_address = start_address + (dword_t)block->size * PAGE_SIZE;
 
     critical_t critical;
     enter_critical(&critical);
@@ -649,15 +649,15 @@ static void free_blocks_recursive(memory_block_t *block)
 {
     release_memory_block(block);
 
-    if (block->by_addr_tree.left)
+    if (block->by_addr_node.left)
     {
-        memory_block_t *left_block = CONTAINER_OF(block->by_addr_tree.left, memory_block_t, by_addr_tree);
+        memory_block_t *left_block = CONTAINER_OF(block->by_addr_node.left, memory_block_t, by_addr_node);
         free_blocks_recursive(left_block);
     }
 
-    if (block->by_addr_tree.right)
+    if (block->by_addr_node.right)
     {
-        memory_block_t *right_block = CONTAINER_OF(block->by_addr_tree.right, memory_block_t, by_addr_tree);
+        memory_block_t *right_block = CONTAINER_OF(block->by_addr_node.right, memory_block_t, by_addr_node);
         free_blocks_recursive(right_block);
     }
 
@@ -666,27 +666,27 @@ static void free_blocks_recursive(memory_block_t *block)
 
 static memory_block_t *find_free_block_internal(memory_block_t *root, void *address, dword_t size)
 {
-    avl_tree_t *ptr;
+    avl_node_t *ptr;
 
-    if (root->by_size_tree.left && (dword_t)root->by_size_tree.key > size)
+    if (root->by_size_node.left && (dword_t)root->size > size)
     {
-        memory_block_t *left = CONTAINER_OF(root->by_size_tree.left, memory_block_t, by_size_tree);
+        memory_block_t *left = CONTAINER_OF(root->by_size_node.left, memory_block_t, by_size_node);
         memory_block_t *block = find_free_block_internal(left, address, size);
         if (block) return block;
     }
 
-    if ((dword_t)root->by_size_tree.key >= size)
+    if ((dword_t)root->size >= size)
     {
-        for (ptr = &root->by_size_tree; ptr != NULL; ptr = ptr->next_equal)
+        for (ptr = &root->by_size_node; ptr != NULL; ptr = ptr->next_equal)
         {
-            memory_block_t *block = CONTAINER_OF(ptr, memory_block_t, by_size_tree);
+            memory_block_t *block = CONTAINER_OF(ptr, memory_block_t, by_size_node);
 
             if (!(block->flags & MEMORY_BLOCK_FREE)) continue;
 
             if (address != NULL)
             {
-                dword_t block_start = (dword_t)block->by_addr_tree.key;
-                dword_t block_end = block_start + ((dword_t)block->by_size_tree.key * PAGE_SIZE) - 1;
+                dword_t block_start = (dword_t)block->address;
+                dword_t block_end = block_start + ((dword_t)block->size * PAGE_SIZE) - 1;
 
                 dword_t needed_start = (dword_t)address;
                 dword_t needed_end = needed_start + (size * PAGE_SIZE) - 1;
@@ -698,14 +698,14 @@ static memory_block_t *find_free_block_internal(memory_block_t *root, void *addr
         }
     }
 
-    if (!root->by_size_tree.right) return NULL;
-    memory_block_t *right = CONTAINER_OF(root->by_size_tree.right, memory_block_t, by_size_tree);
+    if (!root->by_size_node.right) return NULL;
+    memory_block_t *right = CONTAINER_OF(root->by_size_node.right, memory_block_t, by_size_node);
     return find_free_block_internal(right, address, size);
 }
 
 static memory_block_t *find_free_block(memory_address_space_t *address_space, void *address, dword_t size)
 {
-    memory_block_t *root_block = CONTAINER_OF(address_space->by_size_tree_root, memory_block_t, by_size_tree);
+    memory_block_t *root_block = CONTAINER_OF(address_space->by_size_tree.root, memory_block_t, by_size_node);
     return find_free_block_internal(root_block, address, size);
 }
 
@@ -768,19 +768,17 @@ static inline memory_block_t *combine_blocks_forward(memory_block_t *mem_block)
 {
     while (TRUE)
     {
-        avl_tree_t *next = avl_get_next_node(&mem_block->by_addr_tree);
+        avl_node_t *next = avl_get_next_node(&mem_block->by_addr_node);
         if (!next) break;
 
-        memory_block_t *next_block = CONTAINER_OF(next, memory_block_t, by_addr_tree);
+        memory_block_t *next_block = CONTAINER_OF(next, memory_block_t, by_addr_node);
         if (!(next_block->flags & MEMORY_BLOCK_FREE)) break;
 
-        avl_tree_change_key(&mem_block->address_space->by_size_tree_root,
-                            &mem_block->by_size_tree,
-                            (dword_t)mem_block->by_size_tree.key
-                            + (dword_t)next_block->by_size_tree.key);
+        size_t new_size = mem_block->size + next_block->size;
+        avl_tree_change_key(&mem_block->address_space->by_size_tree, &mem_block->by_size_node, &new_size);
 
-        avl_tree_remove(&mem_block->address_space->by_addr_tree_root, &next_block->by_addr_tree);
-        avl_tree_remove(&mem_block->address_space->by_size_tree_root, &next_block->by_size_tree);
+        avl_tree_remove(&mem_block->address_space->by_addr_tree, &next_block->by_addr_node);
+        avl_tree_remove(&mem_block->address_space->by_size_tree, &next_block->by_size_node);
         mem_tree_free(next_block);
     }
 
@@ -791,19 +789,17 @@ static inline memory_block_t *combine_blocks_backward(memory_block_t *mem_block)
 {
     while (TRUE)
     {
-        avl_tree_t *previous = avl_get_previous_node(&mem_block->by_addr_tree);
+        avl_node_t *previous = avl_get_previous_node(&mem_block->by_addr_node);
         if (!previous) break;
 
-        memory_block_t *prev_block = CONTAINER_OF(previous, memory_block_t, by_addr_tree);
+        memory_block_t *prev_block = CONTAINER_OF(previous, memory_block_t, by_addr_node);
         if (!(prev_block->flags & MEMORY_BLOCK_FREE)) break;
 
-        avl_tree_change_key(&mem_block->address_space->by_size_tree_root,
-                            &prev_block->by_size_tree,
-                            (dword_t)prev_block->by_size_tree.key
-                            + (dword_t)mem_block->by_size_tree.key);
+        size_t new_size = prev_block->size + mem_block->size;
+        avl_tree_change_key(&mem_block->address_space->by_size_tree, &prev_block->by_size_node, &new_size);
 
-        avl_tree_remove(&mem_block->address_space->by_addr_tree_root, &mem_block->by_addr_tree);
-        avl_tree_remove(&mem_block->address_space->by_size_tree_root, &mem_block->by_size_tree);
+        avl_tree_remove(&mem_block->address_space->by_addr_tree, &mem_block->by_addr_node);
+        avl_tree_remove(&mem_block->address_space->by_size_tree, &mem_block->by_size_node);
         mem_tree_free(mem_block);
 
         mem_block = prev_block;
@@ -901,7 +897,7 @@ dword_t map_memory_in_address_space(memory_address_space_t *address_space,
     }
 
     dword_t flags = PAGE_GLOBAL;
-    dword_t real_address = (address != NULL) ? (dword_t)address : (dword_t)block->by_addr_tree.key;
+    dword_t real_address = (address != NULL) ? (dword_t)address : (dword_t)block->address;
 
     block_flags &= ~MEMORY_BLOCK_EVICTABLE;
     if (block_flags & MEMORY_BLOCK_ACCESSIBLE) flags |= PAGE_PRESENT;
@@ -915,45 +911,44 @@ dword_t map_memory_in_address_space(memory_address_space_t *address_space,
         return ret;
     }
 
-    if ((dword_t)block->by_addr_tree.key < (dword_t)address)
+    if ((dword_t)block->address < (dword_t)address)
     {
         memory_block_t *new_block = mem_tree_alloc();
         new_block->flags = MEMORY_BLOCK_FREE;
-        new_block->by_addr_tree.key = block->by_addr_tree.key;
-        new_block->by_size_tree.key = (qword_t)(((dword_t)address - block->by_addr_tree.key) / PAGE_SIZE);
+        new_block->address = block->address;
+        new_block->size = (size_t)(((dword_t)address - block->address) / PAGE_SIZE);
         new_block->address_space = address_space;
         new_block->section = NULL;
 
-        avl_tree_change_key(&address_space->by_size_tree_root,
-                            &block->by_size_tree,
-                            (dword_t)block->by_size_tree.key - (dword_t)new_block->by_size_tree.key);
-        avl_tree_change_key(&address_space->by_addr_tree_root, &block->by_addr_tree, (dword_t)address);
+        size_t new_size = block->size - new_block->size;
+        avl_tree_change_key(&address_space->by_size_tree, &block->by_size_node, &new_size);
+        avl_tree_change_key(&address_space->by_addr_tree, &block->by_addr_node, &address);
 
-        avl_tree_insert(&address_space->by_addr_tree_root, &new_block->by_addr_tree);
-        avl_tree_insert(&address_space->by_size_tree_root, &new_block->by_size_tree);
+        avl_tree_insert(&address_space->by_addr_tree, &new_block->by_addr_node);
+        avl_tree_insert(&address_space->by_size_tree, &new_block->by_size_node);
 
         combine_blocks_backward(new_block);
     }
 
-    if ((dword_t)block->by_size_tree.key > size)
+    if ((dword_t)block->size > size)
     {
         memory_block_t *new_block = mem_tree_alloc();
         new_block->flags = MEMORY_BLOCK_FREE;
-        new_block->by_addr_tree.key = (qword_t)(block->by_addr_tree.key + (size * PAGE_SIZE));
-        new_block->by_size_tree.key = (qword_t)((dword_t)block->by_size_tree.key - size);
+        new_block->address = (qword_t)(block->address + (size * PAGE_SIZE));
+        new_block->size = (qword_t)((dword_t)block->size - size);
         new_block->address_space = address_space;
         new_block->section = NULL;
 
-        avl_tree_change_key(&address_space->by_size_tree_root, &block->by_size_tree, size);
+        avl_tree_change_key(&address_space->by_size_tree, &block->by_size_node, &size);
 
-        avl_tree_insert(&address_space->by_addr_tree_root, &new_block->by_addr_tree);
-        avl_tree_insert(&address_space->by_size_tree_root, &new_block->by_size_tree);
+        avl_tree_insert(&address_space->by_addr_tree, &new_block->by_addr_node);
+        avl_tree_insert(&address_space->by_size_tree, &new_block->by_size_node);
 
         combine_blocks_forward(new_block);
     }
 
     block->flags = block_flags;
-    *virtual = (void*)((dword_t)block->by_addr_tree.key);
+    *virtual = (void*)((dword_t)block->address);
 
     release_resource(&address_space->resource);
     return ERR_SUCCESS;
@@ -978,7 +973,7 @@ dword_t pin_memory(const void *virtual, void **pinned, uintptr_t size, bool_t lo
         return ERR_NOMEMORY;
     }
 
-    dword_t real_address = (address != NULL) ? (dword_t)address : (dword_t)block->by_addr_tree.key;
+    dword_t real_address = (address != NULL) ? (dword_t)address : (dword_t)block->address;
     dword_t new_flags = PAGE_PRESENT | PAGE_GLOBAL;
     if (!lock_contents) new_flags |= PAGE_WRITABLE;
 
@@ -1000,46 +995,45 @@ dword_t pin_memory(const void *virtual, void **pinned, uintptr_t size, bool_t lo
         reference_page(phys_page);
     }
 
-    if ((dword_t)block->by_addr_tree.key < (dword_t)address)
+    if ((dword_t)block->address < (dword_t)address)
     {
         memory_block_t *new_block = mem_tree_alloc();
         new_block->flags = MEMORY_BLOCK_FREE;
-        new_block->by_addr_tree.key = block->by_addr_tree.key;
-        new_block->by_size_tree.key = (qword_t)(((dword_t)address - block->by_addr_tree.key) / PAGE_SIZE);
+        new_block->address = block->address;
+        new_block->size = (size_t)(((dword_t)address - block->address) / PAGE_SIZE);
         new_block->address_space = &mapping_space;
         new_block->section = NULL;
 
-        avl_tree_change_key(&mapping_space.by_size_tree_root,
-                            &block->by_size_tree,
-                            (dword_t)block->by_size_tree.key - (dword_t)new_block->by_size_tree.key);
-        avl_tree_change_key(&mapping_space.by_addr_tree_root, &block->by_addr_tree, (dword_t)address);
+        size_t new_size = block->size - new_block->size;
+        avl_tree_change_key(&mapping_space.by_size_tree, &block->by_size_node, &new_size);
+        avl_tree_change_key(&mapping_space.by_addr_tree, &block->by_addr_node, &address);
 
-        avl_tree_insert(&mapping_space.by_addr_tree_root, &new_block->by_addr_tree);
-        avl_tree_insert(&mapping_space.by_size_tree_root, &new_block->by_size_tree);
+        avl_tree_insert(&mapping_space.by_addr_tree, &new_block->by_addr_node);
+        avl_tree_insert(&mapping_space.by_size_tree, &new_block->by_size_node);
 
         combine_blocks_backward(new_block);
     }
 
-    if ((dword_t)block->by_size_tree.key > size)
+    if ((dword_t)block->size > size)
     {
         memory_block_t *new_block = mem_tree_alloc();
         new_block->flags = MEMORY_BLOCK_FREE;
-        new_block->by_addr_tree.key = (qword_t)(block->by_addr_tree.key + (size * PAGE_SIZE));
-        new_block->by_size_tree.key = (qword_t)((dword_t)block->by_size_tree.key - size);
+        new_block->address = (qword_t)(block->address + (size * PAGE_SIZE));
+        new_block->size = (qword_t)((dword_t)block->size - size);
         new_block->address_space = &mapping_space;
         new_block->section = NULL;
 
-        avl_tree_change_key(&mapping_space.by_size_tree_root, &block->by_size_tree, size);
+        avl_tree_change_key(&mapping_space.by_size_tree, &block->by_size_node, &size);
 
-        avl_tree_insert(&mapping_space.by_addr_tree_root, &new_block->by_addr_tree);
-        avl_tree_insert(&mapping_space.by_size_tree_root, &new_block->by_size_tree);
+        avl_tree_insert(&mapping_space.by_addr_tree, &new_block->by_addr_node);
+        avl_tree_insert(&mapping_space.by_size_tree, &new_block->by_size_node);
 
         combine_blocks_forward(new_block);
     }
 
     block->flags = MEMORY_BLOCK_ACCESSIBLE;
     if (!lock_contents) block->flags |= MEMORY_BLOCK_WRITABLE;
-    *pinned = (void*)((dword_t)block->by_addr_tree.key) + PAGE_OFFSET((uintptr_t)virtual);
+    *pinned = (void*)((dword_t)block->address) + PAGE_OFFSET((uintptr_t)virtual);
 
     release_resource(&address_space->resource);
     release_resource(&mapping_space.resource);
@@ -1050,21 +1044,21 @@ dword_t unmap_memory_in_address_space(memory_address_space_t *address_space, voi
 {
     acquire_resource_exclusive(&mapping_space.resource);
 
-    avl_tree_t *node = avl_tree_lookup(mapping_space.by_addr_tree_root, (dword_t)virtual);
+    avl_node_t *node = avl_tree_lookup(&mapping_space.by_addr_tree, &virtual);
     if (node == NULL)
     {
         release_resource(&mapping_space.resource);
         return ERR_INVALID;
     }
 
-    memory_block_t *mem_block = CONTAINER_OF(node, memory_block_t, by_addr_tree);
+    memory_block_t *mem_block = CONTAINER_OF(node, memory_block_t, by_addr_node);
     if (mem_block->flags & MEMORY_BLOCK_FREE)
     {
         release_resource(&mapping_space.resource);
         return ERR_INVALID;
     }
 
-    unmap_memory_internal((void*)((dword_t)mem_block->by_addr_tree.key), (dword_t)mem_block->by_size_tree.key);
+    unmap_memory_internal((void*)((dword_t)mem_block->address), (dword_t)mem_block->size);
 
     mem_block->flags = MEMORY_BLOCK_FREE;
     mem_block = combine_blocks_backward(mem_block);
@@ -1118,45 +1112,44 @@ dword_t alloc_memory_in_address_space(memory_address_space_t *address_space,
         }
     }
 
-    if ((dword_t)block->by_addr_tree.key < (dword_t)base_address)
+    if ((dword_t)block->address < (dword_t)base_address)
     {
         memory_block_t *new_block = mem_tree_alloc();
         new_block->flags = MEMORY_BLOCK_FREE;
-        new_block->by_addr_tree.key = block->by_addr_tree.key;
-        new_block->by_size_tree.key = (qword_t)(((dword_t)base_address - block->by_addr_tree.key) / PAGE_SIZE);
+        new_block->address = block->address;
+        new_block->size = (size_t)(((dword_t)base_address - block->address) / PAGE_SIZE);
         new_block->address_space = address_space;
         new_block->section = NULL;
 
-        avl_tree_change_key(&address_space->by_size_tree_root,
-                            &block->by_size_tree,
-                            (dword_t)block->by_size_tree.key - (dword_t)new_block->by_size_tree.key);
-        avl_tree_change_key(&address_space->by_addr_tree_root, &block->by_addr_tree, (dword_t)base_address);
+        size_t new_size = block->size - new_block->size;
+        avl_tree_change_key(&address_space->by_size_tree, &block->by_size_node, &new_size);
+        avl_tree_change_key(&address_space->by_addr_tree, &block->by_addr_node, &base_address);
 
-        avl_tree_insert(&address_space->by_addr_tree_root, &new_block->by_addr_tree);
-        avl_tree_insert(&address_space->by_size_tree_root, &new_block->by_size_tree);
+        avl_tree_insert(&address_space->by_addr_tree, &new_block->by_addr_node);
+        avl_tree_insert(&address_space->by_size_tree, &new_block->by_size_node);
 
         combine_blocks_backward(new_block);
     }
 
-    if ((dword_t)block->by_size_tree.key > size)
+    if ((dword_t)block->size > size)
     {
         memory_block_t *new_block = mem_tree_alloc();
         new_block->flags = MEMORY_BLOCK_FREE;
-        new_block->by_addr_tree.key = (qword_t)(block->by_addr_tree.key + (size * PAGE_SIZE));
-        new_block->by_size_tree.key = (qword_t)((dword_t)block->by_size_tree.key - size);
+        new_block->address = (qword_t)(block->address + (size * PAGE_SIZE));
+        new_block->size = (qword_t)((dword_t)block->size - size);
         new_block->address_space = address_space;
         new_block->section = NULL;
 
-        avl_tree_change_key(&address_space->by_size_tree_root, &block->by_size_tree, size);
+        avl_tree_change_key(&address_space->by_size_tree, &block->by_size_node, &size);
 
-        avl_tree_insert(&address_space->by_addr_tree_root, &new_block->by_addr_tree);
-        avl_tree_insert(&address_space->by_size_tree_root, &new_block->by_size_tree);
+        avl_tree_insert(&address_space->by_addr_tree, &new_block->by_addr_node);
+        avl_tree_insert(&address_space->by_size_tree, &new_block->by_size_node);
 
         combine_blocks_forward(new_block);
     }
 
     block->flags = block_flags;
-    *address = (void*)((dword_t)block->by_addr_tree.key);
+    *address = (void*)((dword_t)block->address);
     if (block_flags & MEMORY_BLOCK_EVICTABLE) list_append(&address_space->evictable_blocks, &block->evict_link);
 
     release_resource(&address_space->resource);
@@ -1167,14 +1160,14 @@ dword_t free_memory_in_address_space(memory_address_space_t *address_space, void
 {
     acquire_resource_exclusive(&address_space->resource);
 
-    avl_tree_t *node = avl_tree_lookup(address_space->by_addr_tree_root, (dword_t)address);
+    avl_node_t *node = avl_tree_lookup(&address_space->by_addr_tree, &address);
     if (node == NULL)
     {
         release_resource(&address_space->resource);
         return ERR_INVALID;
     }
 
-    memory_block_t *mem_block = CONTAINER_OF(node, memory_block_t, by_addr_tree);
+    memory_block_t *mem_block = CONTAINER_OF(node, memory_block_t, by_addr_node);
     if (mem_block->flags & MEMORY_BLOCK_FREE)
     {
         release_resource(&address_space->resource);
@@ -1471,8 +1464,8 @@ sysret_t syscall_set_memory_flags(handle_t process, void *address, dword_t flags
     }
 
     dword_t page;
-    dword_t start_address = (dword_t)block->by_addr_tree.key;
-    dword_t end_address = start_address + (dword_t)block->by_size_tree.key * PAGE_SIZE;
+    dword_t start_address = (dword_t)block->address;
+    dword_t end_address = start_address + (dword_t)block->size * PAGE_SIZE;
     dword_t page_flags = 0;
 
     if (flags & MEMORY_BLOCK_ACCESSIBLE) page_flags |= PAGE_PRESENT;
@@ -1536,8 +1529,8 @@ sysret_t syscall_query_memory(handle_t process, void *address, memory_block_info
 
     EH_TRY
     {
-        info->address = block->by_addr_tree.key;
-        info->size = block->by_size_tree.key;
+        info->address = block->address;
+        info->size = block->size;
         info->flags = block->flags;
     }
     EH_CATCH
@@ -2147,13 +2140,34 @@ cleanup:
     return ret;
 }
 
+static int compare_address(const void *key1, const void *key2)
+{
+    const uintptr_t first = *(const uintptr_t*)key1;
+    const uintptr_t second = *(const uintptr_t*)key2;
+
+    if (first < second) return -1;
+    else if (first == second) return 0;
+    else return 1;
+}
+
+static int compare_size(const void *key1, const void *key2)
+{
+    const size_t first = *(const size_t*)key1;
+    const size_t second = *(const size_t*)key2;
+
+    if (first < second) return -1;
+    else if (first == second) return 0;
+    else return 1;
+}
+
 dword_t create_address_space(void *base_address, dword_t page_count, memory_address_space_t *mem_space)
 {
     dword_t ret = ERR_NOMEMORY;
 
     mem_space->pool_address = base_address;
     mem_space->pool_size = page_count;
-    mem_space->by_addr_tree_root = mem_space->by_size_tree_root = NULL;
+    AVL_TREE_INIT(&mem_space->by_addr_tree, memory_block_t, by_addr_node, address, compare_address);
+    AVL_TREE_INIT(&mem_space->by_size_tree, memory_block_t, by_size_node, size, compare_size);
     mem_space->resource = 0;
     list_init(&mem_space->evictable_blocks);
     mem_space->evict_blk_ptr = NULL;
@@ -2177,14 +2191,14 @@ dword_t create_address_space(void *base_address, dword_t page_count, memory_addr
     memory_block_t *initial = mem_tree_alloc();
     if (initial != NULL)
     {
-        initial->by_addr_tree.key = (qword_t)((dword_t)base_address);
-        initial->by_size_tree.key = (qword_t)page_count;
+        initial->address = (uintptr_t)base_address;
+        initial->size = page_count;
         initial->flags = MEMORY_BLOCK_FREE;
         initial->address_space = mem_space;
         initial->section = NULL;
 
-        avl_tree_insert(&mem_space->by_addr_tree_root, &initial->by_addr_tree);
-        avl_tree_insert(&mem_space->by_size_tree_root, &initial->by_size_tree);
+        avl_tree_insert(&mem_space->by_addr_tree, &initial->by_addr_node);
+        avl_tree_insert(&mem_space->by_size_tree, &initial->by_size_node);
         ret = ERR_SUCCESS;
     }
 
@@ -2205,7 +2219,8 @@ dword_t clone_address_space(memory_address_space_t *original, memory_address_spa
 
     clone->pool_address = original->pool_address;
     clone->pool_size = original->pool_size;
-    clone->by_addr_tree_root = clone->by_size_tree_root = NULL;
+    AVL_TREE_INIT(&clone->by_addr_tree, memory_block_t, by_addr_node, address, NULL);
+    AVL_TREE_INIT(&clone->by_size_tree, memory_block_t, by_size_node, size, NULL);
     clone->resource = 0;
     list_init(&clone->evictable_blocks);
     clone->evict_blk_ptr = NULL;
@@ -2215,9 +2230,9 @@ dword_t clone_address_space(memory_address_space_t *original, memory_address_spa
     clone->stats.evicted = original->stats.evicted;
     clone->stats.shared = original->stats.committed;
 
-    if (original->by_addr_tree_root != NULL)
+    if (original->by_addr_tree.root != NULL)
     {
-        memory_block_t *root_block = CONTAINER_OF(original->by_addr_tree_root, memory_block_t, by_addr_tree);
+        memory_block_t *root_block = CONTAINER_OF(original->by_addr_tree.root, memory_block_t, by_addr_node);
         if (!clone_blocks_recursive(clone, root_block))
         {
             ret = ERR_NOMEMORY;
@@ -2266,12 +2281,11 @@ void delete_address_space(memory_address_space_t *mem_space)
     ASSERT(get_page_directory() != mem_space->page_directory);
     acquire_resource_exclusive(&mem_space->resource);
 
-    if (mem_space->by_addr_tree_root)
+    if (mem_space->by_addr_tree.root)
     {
-        memory_block_t *root = CONTAINER_OF(mem_space->by_addr_tree_root, memory_block_t, by_addr_tree);
+        memory_block_t *root = CONTAINER_OF(mem_space->by_addr_tree.root, memory_block_t, by_addr_node);
         free_blocks_recursive(root);
-        mem_space->by_addr_tree_root = NULL;
-        mem_space->by_size_tree_root = NULL;
+        mem_space->by_addr_tree.root = mem_space->by_size_tree.root = NULL;
     }
 
     free_physical_page(mem_space->page_directory);
@@ -2425,7 +2439,7 @@ bool_t memory_fault_handler(void *address, registers_t *regs)
         {
             list_entry_t *ptr;
             shared_page_t *page = NULL;
-            qword_t offset = block->section_offset + (qword_t)aligned_address - (qword_t)block->by_addr_tree.key;
+            qword_t offset = block->section_offset + (qword_t)aligned_address - (qword_t)block->address;
 
             page_flags = PAGE_PRESENT;
             if (block->flags & MEMORY_BLOCK_WRITABLE) page_flags |= PAGE_WRITABLE;
diff --git a/sdk/avltree.h b/sdk/avltree.h
new file mode 100644 (file)
index 0000000..1c56f5e
--- /dev/null
@@ -0,0 +1,431 @@
+/*
+ * avltree.h
+ *
+ * Copyright (C) 2018 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef __MONOLITHIUM_AVLTREE_H__
+#define __MONOLITHIUM_AVLTREE_H__
+
+#include "defs.h"
+
+#define AVL_TREE_INIT(t, s, n, k, c) avl_tree_init((t), (ptrdiff_t)&((s*)NULL)->k - (ptrdiff_t)&((s*)NULL)->n, sizeof(((s*)NULL)->k), c)
+
+typedef int (*avl_compare_proc_t)(const void *key1, const void *key2);
+
+typedef struct avl_node
+{
+    struct avl_node *parent;
+    struct avl_node *left;
+    struct avl_node *right;
+    struct avl_node *next_equal;
+    struct avl_node *prev_equal;
+    int balance;
+} avl_node_t;
+
+typedef struct avl_tree
+{
+    avl_node_t *root;
+    ptrdiff_t key_offset;
+    size_t key_size;
+    avl_compare_proc_t compare;
+} avl_tree_t;
+
+static inline void avl_tree_init(avl_tree_t *tree, ptrdiff_t key_offset, size_t key_size, avl_compare_proc_t compare)
+{
+    tree->root = NULL;
+    tree->key_offset = key_offset;
+    tree->key_size = key_size;
+    tree->compare = compare;
+}
+
+static inline void *avl_get_keyptr(const avl_tree_t *tree, const avl_node_t *node)
+{
+    return (void*)((ptrdiff_t)node + tree->key_offset);
+}
+
+static inline avl_node_t *avl_tree_lookup(const avl_tree_t *tree, const void *key)
+{
+    avl_node_t *node = tree->root;
+
+    while (node)
+    {
+        const void *node_key = avl_get_keyptr(tree, node);
+        int comparison = tree->compare(key, node_key);
+
+        if (comparison == 0) return node;
+        else if (comparison < 0) node = node->left;
+        else node = node->right;
+    }
+
+    return NULL;
+}
+
+static inline avl_node_t *avl_tree_lower_bound(const avl_tree_t *tree, const void *key)
+{
+    avl_node_t *node = tree->root;
+
+    while (node && tree->compare(avl_get_keyptr(tree, node), key) > 0) node = node->left;
+    if (!node) return NULL;
+
+    while (node->right && tree->compare(avl_get_keyptr(tree, node->right), key) <= 0) node = node->right;
+    return node;
+}
+
+static inline avl_node_t *avl_tree_upper_bound(const avl_tree_t *tree, const void *key)
+{
+    avl_node_t *node = tree->root;
+
+    while (node && tree->compare(avl_get_keyptr(tree, node), key) < 0) node = node->right;
+    if (!node) return NULL;
+
+    while (node->left && tree->compare(avl_get_keyptr(tree, node->left), key) >= 0) node = node->left;
+    return node;
+}
+
+static inline avl_node_t *avl_get_next_node(const avl_node_t *node)
+{
+    while (node->prev_equal) node = node->prev_equal;
+
+    if (node->right)
+    {
+        node = node->right;
+        while (node->left) node = node->left;
+    }
+    else
+    {
+        while (node->parent && node->parent->right == node) node = node->parent;
+        node = node->parent;
+    }
+
+    return (avl_node_t*)node;
+}
+
+static inline avl_node_t *avl_get_previous_node(const avl_node_t *node)
+{
+    while (node->prev_equal) node = node->prev_equal;
+
+    if (node->left)
+    {
+        node = node->left;
+        while (node->right) node = node->right;
+    }
+    else
+    {
+        while (node->parent && node->parent->left == node) node = node->parent;
+        node = node->parent;
+    }
+
+    return (avl_node_t*)node;
+}
+
+static inline avl_node_t *avl_rotate_left(avl_tree_t *tree, avl_node_t *root)
+{
+    avl_node_t *pivot = root->right;
+    root->right = pivot->left;
+    if (root->right) root->right->parent = root;
+
+    pivot->parent = root->parent;
+    pivot->left = root;
+    root->parent = pivot;
+
+    if (pivot->parent)
+    {
+        if (pivot->parent->left == root) pivot->parent->left = pivot;
+        else if (pivot->parent->right == root) pivot->parent->right = pivot;
+    }
+    else
+    {
+        tree->root = pivot;
+    }
+
+    root->balance -= pivot->balance > 0 ? pivot->balance + 1 : 1;
+    pivot->balance += root->balance < 0 ? root->balance - 1 : -1;
+    return pivot;
+}
+
+static inline avl_node_t *avl_rotate_right(avl_tree_t *tree, avl_node_t *root)
+{
+    avl_node_t *pivot = root->left;
+    root->left = pivot->right;
+    if (root->left) root->left->parent = root;
+
+    pivot->parent = root->parent;
+    pivot->right = root;
+    root->parent = pivot;
+
+    if (pivot->parent)
+    {
+        if (pivot->parent->left == root) pivot->parent->left = pivot;
+        else if (pivot->parent->right == root) pivot->parent->right = pivot;
+    }
+    else
+    {
+        tree->root = pivot;
+    }
+
+    root->balance -= pivot->balance < 0 ? pivot->balance - 1 : -1;
+    pivot->balance += root->balance > 0 ? root->balance + 1 : 1;
+    return pivot;
+}
+
+static void avl_tree_insert(avl_tree_t *tree, avl_node_t *node)
+{
+    node->left = node->right = node->parent = node->next_equal = node->prev_equal = NULL;
+    node->balance = 0;
+
+    if (!tree->root)
+    {
+        tree->root = node;
+        return;
+    }
+
+    avl_node_t *current = tree->root;
+    const void *node_key = avl_get_keyptr(tree, node);
+
+    while (TRUE)
+    {
+        const void *key = avl_get_keyptr(tree, current);
+        int comparison = tree->compare(node_key, key);
+
+        if (comparison == 0)
+        {
+            while (current->next_equal) current = current->next_equal;
+            current->next_equal = node;
+            node->prev_equal = current;
+            return;
+        }
+        else if (comparison < 0)
+        {
+            if (!current->left)
+            {
+                node->parent = current;
+                current->left = node;
+                break;
+            }
+            else
+            {
+                current = current->left;
+            }
+        }
+        else
+        {
+            if (!current->right)
+            {
+                node->parent = current;
+                current->right = node;
+                break;
+            }
+            else
+            {
+                current = current->right;
+            }
+        }
+    }
+
+    while (current)
+    {
+        if (node == current->left) current->balance--;
+        else current->balance++;
+
+        if (current->balance == 0) break;
+
+        if (current->balance < -1)
+        {
+            if (node->balance > 0) avl_rotate_left(tree, current->left);
+            current = avl_rotate_right(tree, current);
+            break;
+        }
+        else if (current->balance > 1)
+        {
+            if (node->balance < 0) avl_rotate_right(tree, current->right);
+            current = avl_rotate_left(tree, current);
+            break;
+        }
+
+        node = current;
+        current = current->parent;
+    }
+}
+
+static void avl_tree_remove(avl_tree_t *tree, avl_node_t *node)
+{
+    if (node->prev_equal)
+    {
+        node->prev_equal->next_equal = node->next_equal;
+        if (node->next_equal) node->next_equal->prev_equal = node->prev_equal;
+        node->next_equal = node->prev_equal = NULL;
+        return;
+    }
+    else if (node->next_equal)
+    {
+        node->next_equal->parent = node->parent;
+        node->next_equal->left = node->left;
+        node->next_equal->right = node->right;
+        node->next_equal->prev_equal = NULL;
+
+        if (node->parent)
+        {
+            if (node->parent->left == node) node->parent->left = node->next_equal;
+            else node->parent->right = node->next_equal;
+        }
+        else
+        {
+            tree->root = node->next_equal;
+        }
+
+        if (node->left) node->left->parent = node->next_equal;
+        if (node->right) node->right->parent = node->next_equal;
+
+        node->parent = node->left = node->right = node->next_equal = NULL;
+        node->balance = 0;
+        return;
+    }
+
+    if (node->left && node->right)
+    {
+        avl_node_t *replacement = node->right;
+
+        if (replacement->left)
+        {
+            while (replacement->left) replacement = replacement->left;
+
+            avl_node_t *temp_parent = replacement->parent;
+            avl_node_t *temp_right = replacement->right;
+            int temp_balance = replacement->balance;
+
+            replacement->parent = node->parent;
+            replacement->left = node->left;
+            replacement->right = node->right;
+            replacement->balance = node->balance;
+
+            if (replacement->parent)
+            {
+                if (replacement->parent->left == node) replacement->parent->left = replacement;
+                else replacement->parent->right = replacement;
+            }
+            else
+            {
+                tree->root = replacement;
+            }
+
+            if (replacement->left) replacement->left->parent = replacement;
+            if (replacement->right) replacement->right->parent = replacement;
+
+            node->parent = temp_parent;
+            node->left = NULL;
+            node->right = temp_right;
+            node->balance = temp_balance;
+
+            if (node->parent->left == replacement) node->parent->left = node;
+            else node->parent->right = node;
+
+            if (node->right) node->right->parent = node;
+        }
+        else
+        {
+            avl_node_t *temp_right = replacement->right;
+            int temp_balance = replacement->balance;
+
+            replacement->parent = node->parent;
+            replacement->left = node->left;
+            replacement->right = node;
+            replacement->balance = node->balance;
+
+            if (replacement->parent)
+            {
+                if (replacement->parent->left == node) replacement->parent->left = replacement;
+                else replacement->parent->right = replacement;
+            }
+            else
+            {
+                tree->root = replacement;
+            }
+
+            if (replacement->left) replacement->left->parent = replacement;
+
+            node->parent = replacement;
+            node->left = NULL;
+            node->right = temp_right;
+            node->balance = temp_balance;
+
+            if (node->right) node->right->parent = node;
+        }
+    }
+
+    avl_node_t *current = node->parent;
+    bool_t left_child;
+
+    if (current)
+    {
+        left_child = current->left == node;
+
+        if (left_child)
+        {
+            current->left = node->left ? node->left : node->right;
+            if (current->left) current->left->parent = current;
+        }
+        else
+        {
+            current->right = node->left ? node->left : node->right;
+            if (current->right) current->right->parent = current;
+        }
+    }
+    else
+    {
+        tree->root = node->left ? node->left : node->right;
+        if (tree->root) tree->root->parent = NULL;
+    }
+
+    node->parent = node->left = node->right = NULL;
+    node->balance = 0;
+
+    while (current)
+    {
+        if (left_child) current->balance++;
+        else current->balance--;
+
+        if (current->balance == 1 || current->balance == -1) break;
+
+        if (current->balance < -1)
+        {
+            int balance = current->left->balance;
+            if (balance > 0) avl_rotate_left(tree, current->left);
+            current = avl_rotate_right(tree, current);
+            if (balance == 0) break;
+        }
+        else if (current->balance > 1)
+        {
+            int balance = current->right->balance;
+            if (balance < 0) avl_rotate_right(tree, current->right);
+            current = avl_rotate_left(tree, current);
+            if (balance == 0) break;
+        }
+
+        node = current;
+        current = current->parent;
+        if (current) left_child = current->left == node;
+    }
+}
+
+static inline void avl_tree_change_key(avl_tree_t *tree, avl_node_t *node, const void *new_key)
+{
+    avl_tree_remove(tree, node);
+    __builtin_memcpy(avl_get_keyptr(tree, node), new_key, tree->key_size);
+    avl_tree_insert(tree, node);
+}
+
+#endif