Heap Management

[ru2aqare]

The problem with this

Code: Select all

              new_direction = compare_avl_node(   node - num_parameters_compare,
                                                    root->left - num_parameters_compare);

is that by adding or subtracting integers from pointers, you basically treat the pointer as an array, and calculate the address of another member in that array. In other words, you can't point to the next byte, doubleword, etc. this way, whereas assembly code can do it.

The problem is, the AVL tree code does not know of any container structures. I still think you should pass avl_node* pointers to the comparison function, and extract the address of the container structure there, like this:

Code: Select all

int avl_compare(avl_node* a, avl_node* b)
{
  mem_block* left = (mem_block*)((uint8*)a - &((mem_block*)NULL)->node);
  mem_block* rigth = ...;
  return (left->address < right->address) ? 1 : 0; // or whatever the actual comparison may be.
}

Since the comparison callback will be different for each type of container structure anyway, this does not pose a problem.

The pointer magic may seem difficult at first, but it can be tucked away into a macro. What this does is the following:
- takes the address of the avl_node structure (a)
- converts it into a byte pointer (uint8*)
- converts the value 0 into an pointer of type mem_block
- takes the address of the field 'node' in that structure. using the fact that the pointer points to virtual address zero, this returns the byte offset of the said field from the start of the structure.
- and subtracts the offset from the byte pointer, effectively moving the byte pointer to the start of the structure
- now the pointer is converted back to the correct type.


Or, if this seems complicated, you can cast the node pointers to uint8*, and subtract the offset manually. However,
another issue with a solution like

Code: Select all

unsigned int address = *(node - 2);

is that if you change the structure in any way - reorder fields, change structure member alignment, etc. - you have to replace all instances of subtracting two with for example subtracting four. The compiler on the other hand always generates the correct offset for you.

[ChristianF]

okay.
Now I got It. Sometimes I need a little bit longer to understand all.
And now it makes sense to write a new compare function everytime i want to use the list somewhere different.

Now I will have a look at how managing the Heap with the tree.
I think I will get this myself. If not I will come back and ask.

Until then...


Cheers Christian

*EDIT*
So a macro would look like this:

Code: Select all

#define GET_MEM_BLOCK_ADDRESS(node_address) \
    ((unsigned char *)node_address - &((heap_mem_block_t*)NULL)->node)

*EDIT 2*
There is only one little question. I perform a left rotation this way:

Code: Select all

avl_node_t *old_node = node;
node = node->left;
old_node->left = node->right;
node->right = old_node;

So I think I have to set the parent of old_node to node, so something like this:

Code: Select all

old_node->parent->right = node;

Is this right?

[ru2aqare]

So a macro would look like this:

Code: Select all

#define GET_MEM_BLOCK_ADDRESS(node_address) \
    ((unsigned char *)node_address - &((heap_mem_block_t*)NULL)->node)

I forgot to insert a cast, as you need to subtract an integer from the node address.

Code: Select all

#define GET_MEM_BLOCK_ADDRESS(node_address) \
    ((unsigned char *)node_address - (int)&((heap_mem_block_t*)NULL)->node)

There is only one little question. I perform a left rotation this way:

Code: Select all

avl_node_t *old_node = node;
node = node->left;
old_node->left = node->right;
node->right = old_node;

So I think I have to set the parent of old_node to node, so something like this:

Code: Select all

old_node->parent->right = node;

Is this right?

This seems a little off to me. I would do something like

Code: Select all

avl_node* parent = node->parent;
avl_node* right = node->right;

node->right = right->left;
parent = right;
parent->left = /* right->left =*/ node;

A left rotation is a rotation that pushes down the original node to the place of it's left child.

[ChristianF]

Hummm....
I found a document which describes the left rotation with this example:
A not balanced tree.

Code: Select all

\
 F
  \
   O
     \
      X

To Balance it with a left rotation you have to set F to O->right that the tree looks like this:

Code: Select all

   O
 \/ \
 F   X

Now we have to set the pointer from parent to F to O that the tree looks like this:

Code: Select all

   |
   O
  / \
 F   X

With this explanation I created a code looks like this:

Code: Select all

void rotate_avl_tree_left(avl_node_t *node)
{
    avl_node_t *parent = node->parent;

    node->left = parent;
    node->parent = parent->parent;
    parent->parent = node;
}

First I set the parent to nodes left. Then I copy the address to the parent from parent and save it in nodes parent. Finally I set parent->parent to node and the rotation is done.
Or am I misunderstanding something?

Cheers Christian

[ru2aqare]

Code: Select all

\
 F
  \
   O
     \
      X

Which of the three nodes does your 'node' and 'parent' variables point to?

With this explanation I created a code looks like this:

Code: Select all

void rotate_avl_tree_left(avl_node_t *node)
{
    avl_node_t *parent = node->parent;

    node->left = parent;
    node->parent = parent->parent;
    parent->parent = node;
}

I dont think this code is correct. First, parent->left and parent->right are not modified, thus they point to the original nodes, which are no longer in correct order. Second, node->left is not saved anywhere, this leaks a node.

[ChristianF]

Okay.
"O" is node and "F" is parent.

I dont think this code is correct. First, parent->left and parent->right are not modified, thus they point to the original nodes, which are no longer in correct order. Second, node->left is not saved anywhere, this leaks a node.

Okay.
The First is right, I have to set left or right of parent to NULL with something like this:

Code: Select all

    if(parent->left == node)
        parent->left = NULL;
    else
        parent->right = NULL;

But the second is not right. In node->left is NULL. If in node->left is something different to NULL, then node->right is null and i perform a right rotation.

Here is a little example: The tree is empty (after creating it).

Code: Select all

|
NULL

Then I add an element F. So the tree looks like this:

Code: Select all

|
F
|__________
|          |
NULL       NULL

Now I add the element O which changes the tree to this:

Code: Select all

|
F
|__________
|          |
NULL       O
           |__________
           |          |
           NULL       NULL

When I add now the node X the tree have to be rebalanced because on the right side are more nodes than left:

Code: Select all

|
F
|__________
|          |
NULL       O
           |__________
           |          |
           NULL       X
                      |__________
                      |          |
                      NULL       NULL

So I perform a Left Rotation. After that the tree looks like this and is rebalanced:

Code: Select all

|
O
|__________
|          |
F          X

So i think the code is right and with an example like this above, I wrote the following code:

Code: Select all

void rotate_avl_tree_left(avl_node_t *node)
{
    /* Some Security Checks */
    if(node == NULL)
        panic("AVL Error: node contains no valid address (node = NULL)!");
    if(node->parent == NULL)
        panic("AVL Error: can't rotaten root node!");

    /* Save the parent node :) */
    avl_node_t *parent = node->parent;
    /* Set the parent of node to the left side */
    node->left = parent;
    /* Reset the left or right poitnter from parent */
    if(parent->left == node)
        parent->left = NULL;
    else
        parent->right = NULL;
    /* If it is the root node the parent pointer of parent may be NULL :) */
    node->parent = parent->parent;
    /* Set the pointer parent of parent to node */
    parent->parent = node;
    /* Set the parents left or right pointer to node if node->parent is not Null */
    if(node->parent != NULL)
    {
        if(node->parent->left == parent)
            node->parent->left = node;
        else
            node->parent->right = node;
    }
}

So I don't understand why my code should be wrong.


Cheers Christian

[JamesM]

Hi,

I grepped the internet for a long time before I finally found a document about AVL trees that gave me the information I wanted. I noted it down in my comments for later use, so here it is:

Code: Select all

  // This way of choosing which rotation to do took me AGES to find...
  // See http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

My rotation code:

Code: Select all

void Tree<void*,void*>::rebalanceNode(Node *n)
{
  // This way of choosing which rotation to do took me AGES to find...
  // See http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html
  int balance = balanceFactor(n);
  if (balance < -1) // If it's left imbalanced, we need a right rotation.
  {
    if (balanceFactor(n->leftChild) > 0) // If its left child is right heavy...
    {
      // We need a RL rotation - left rotate n's left child, then right rotate N.
      rotateLeft(n->leftChild);
      rotateRight(n);
    }
    else
    {
      // RR rotation will do.
      rotateRight(n);
    }
  }
  else if (balance > 1)
  {
    if (balanceFactor(n->rightChild) < 0) // If its right child is left heavy...
    {
      // We need a LR rotation; Right rotate N's right child, then left rotate N.
      rotateRight(n->rightChild);
      rotateLeft(n);
    }
    else
    {
      // LL rotation.
      rotateLeft(n);
    }
  }
}

Code: Select all

void Tree<void*,void*>::rotateLeft(Node *n)
{
  // See Cormen,Lieserson,Rivest&Stein  pp-> 278 for pseudocode.
  Node *y = n->rightChild;            // Set Y.

  n->rightChild = y->leftChild;       // Turn Y's left subtree into N's right subtree.
  if (y->leftChild != 0)
    y->leftChild->parent = n;

  y->parent = n->parent;              // Link Y's parent to N's parent.
  if (n->parent == 0)
    root = y;
  else if (n == n->parent->leftChild)
    n->parent->leftChild = y;
  else
    n->parent->rightChild = y;
  y->leftChild = n;
  n->parent = y;
}

void Tree<void*,void*>::rotateRight(Node *n)
{
  Node *y = n->leftChild;
  
  n->leftChild = y->rightChild;
  if (y->rightChild != 0)
    y->rightChild->parent = n;
  
  y->parent = n->parent;
  if (n->parent == 0)
    root = y;
  else if (n == n->parent->leftChild)
    n->parent->leftChild = y;
  else
    n->parent->rightChild = y;
  
  y->rightChild = n;
  n->parent = y;
}

Hope this helps!

James

[ChristianF]

It helped a lot.
It is now clear how I have to rotate a node
With the link I rewrote my functions to this:

Code: Select all

void rotate_avl_tree_left(avl_tree_t *tree, avl_node_t *node)
{
    /* Some Security Checks */
    if(node == NULL)
        panic("AVL Error: node contains no valid address (node = NULL)!");
    if(node->parent == NULL)
        panic("AVL Error: can't rotaten root node!");

    avl_node_t *right = node->right;
    /* Set the right subtree od node to the left subtree of right */
    node->right = right->left;
    /* Change the parent pointer of the left subtree from node */
    if(node->left != NULL)
        right->left->parent = node;
    /* change the parent pointer of right to the parent of node */
    right->parent = node->parent;
    /* save right in nodes parents left or right pointer  */
    if(node->parent == NULL)
        tree->root_node = right;
    else if(node == node->parent->left)
        node->parent->left = right;
    else
        node->parent->right = right;
    /* save node as left subtree of right */
    right->left = node;
    /* set right as  parent of node */
    node->parent = right;
}

Code: Select all

void rotate_avl_tree_right(avl_tree_t *tree, avl_node_t *node)
{
    /* Some Security Checks */
    if(node == NULL)
        panic("AVL Error: node contains no valid address (node = NULL)!");
    if(node->parent == NULL)
        panic("AVL Error: can't rotaten root node!");

    avl_node_t *left = node->left;

    /* Set node->left to the right subtree of left */
    node->left = left->right;
    /* Change the parent of the right subtree of left */
    if(node->right != NULL)
        left->right->parent = node;
    /* change the parent pointer of left to the parent of node */
    left->parent = node->parent;
    /* save left in nodes parents left or right pointer */
    if(node->parent == NULL)
        tree->root_node = left;
    else if(node == node->parent->left)
        node->parent->left = left;
    else
        node->parent->right = left;
    /* save node as right subtree of left */
    left->right = node;
    /* set left as parent of node */
    node->parent = left;
}

I couldn't test it now, but it will be tested when I come home.
May be I remove the security Checks, because it will be checked by the function for rebalancing the tree...

Thanks for all the help.
Cheers Christian

*EDIT*
There is another thing.
My function to insert a new node hangs the node at the correct free pointer (left or right) like this:

Code: Select all

// ....
root->right = node;
node->parent = root;
// ....

After inserting I call the function to rebalance the whole tree. So i don't need a variable that contains a balance value right?
Or should I rebalance only the nodes?

[ChristianF]

Mmmhhh....
I have another little question:
You call a function named balanceFactor. Does this function returns the balance factor of the tree or of the node?
Could it be the same if i write the following?

Code: Select all

int balance = node->balance;

Cheers Christian

*EDIT*
I have written a function to insert a new node. At the moment it looks like this:

Code: Select all

/*
 * direction = 0: put element on the left side
 * direction = 1: put element on the right side
 */
void internal_insert_avl_tree_node( avl_tree_t *tree,
                                    avl_node_t *root,
                                    avl_node_t *node,
                                    unsigned int direction)
{
    /* Some Security Checks */
    if(root == NULL)
        panic("AVL Error: root contains NULL!\nNULL is not a valid address!");
    if(node == NULL)
        panic("AVL Error: node contains NULL!\nNULL is not a valid address!");

    switch(direction)
    {
        /* add node on the left side */
        case (-1):
        {
            if(root->left == NULL)
            {
                root->left = node;
                node->parent = root;
            }
            else
                internal_insert_avl_tree_node(tree, root->left, node, (*tree->func)(root, node));
        } break;
        /* add node on the right side */
        case (+1):
        {
            if(root->right == NULL)
            {
                root->right = node;
                node->parent = root;
            }
            else
                internal_insert_avl_tree_node(tree, root->right, node, (*tree->func)(root, node));
        } break;
        /* Should never come to this point when the compare function is right */
        default:
            panic("AVL Error: direction must contain 1 or -1!");
    }
}

void insert_avl_tree_node(  avl_tree_t *tree,
                            avl_node_t *node)
{
    /* Some Security Checks */
    if(tree == NULL)
        panic("AVL Error: tree contains NULL!\nNULL is not a valid address!");
    if(tree->root_node == NULL)
        panic("AVL Error: tree->root_node contains NULL!\nNULL is not a valid address!");
    if(node == NULL)
        panic("AVL Error: node contains NULL!\nNULL is not a valid address!");

    /* Search tree for element */
    if(!find_avl_tree_node(tree, node))
        return; /* We found the element so return */
    /* Insert the new node with the internal function */
    internal_insert_avl_tree_node(tree, tree->root_node, node, (*tree->func)(tree->root, node));
    /* Rebalance the changed tree */
    rebalance_avl_tree(tree);
}

So what is the best way to calculate the balance factor. Should I pass this as a pointer which will be changed every time?
There is another problem too. What would happen if the elements are equal? I call the compare function which compares 2 adresses at the moment. If i change this into for example the size of memory blocks it could crash, because I use the heap to store informations like the TSS table which has every time the same size. Or am I wrong?

[JamesM]

balanceFactor is a simple function that recursively calculates the balance factor of one node. However, once a node has had its balance factor calculated, the value is cached in a value in the node, so as long as you work bottom-up balanceFactor will run in constant time. So it's not a dirty log(n) timesink.

[ru2aqare]

So what is the best way to calculate the balance factor. Should I pass this as a pointer which will be changed every time?

No, as JamesM pointed out, it is recommended to cache this value.

There is another problem too. What would happen if the elements are equal? I call the compare function which compares 2 adresses at the moment. If i change this into for example the size of memory blocks it could crash, because I use the heap to store informations like the TSS table which has every time the same size. Or am I wrong?

If the elements are equal, my code refuses to modify the element in the tree, and returns a non-null value to let the caller know that it tried to insert a duplicate. Or you could just silently ignore a match, and overwrite the element with the new one. Since the comparison function indicates that they are equal, this does not change the tree at all.

The point is, only the caller and the comparison function (which is ultimately specified by the caller) know exactly the structure of memory block of an element - the AVL code does not even need to, because it only touches the inner structure (avl_node or what) that enables the memory block to be inserted into the tree. The comparison function requires two arguments - the addresses of the elements to compare. Adding additional arguments that specify the size seems superfluous - after all, the size can be determined by writing:

Code: Select all

int CompareCallback(pAvlNode nodeA, pAvlNode nodeB)
{
    pTss tssA = (pTss)nodeA; // or similar
    int size = sizeof(*tssA);
   ...
}

[ChristianF]

Okay then the value will be cached.

So I have to recalculate the balance factor after every rotation and the original balance factor of an just inserted node is 0.
But I have to recalculate the value of each node above the new node after inserting a new node. And in the worst case I have to rebalance the whole tree.

Looks like I just understood it...

Cheers Christian

[ChristianF]

The function to insert a new node works.
When the new node is inserted the node of the parent and the parent node of node->parent changes like this:

Code: Select all

node->parent += 1;
//or
node->parent -=1;
//-----------------------------------
// and
node->parent->parent += 1;
//or 
node->parent->parent -=1;

that is not a problem any longer. The problem now is to calculate the new balance value after rotation.
Actually with the link of JamesM I got somethins like this:

Code: Select all

// right rotation
node->balance += (1 - MIN(left->balance, 0));
left->balance += (1 + MAX(node->balance,0));
// left rotation
node->balance -= (1 + MAX(right->balance,0));
right->balance -= (1 - MIN(node->balance));

But then I got sometimes balance values like 2 or 3, so it isn't the right calculation.
What is wrong in this calculation?

[ChristianF]

So okay.
The tree is working. I tested it within a little Program I wrote for windows.
But now is there something difficult. My Structure for a memory block looks like this:

Code: Select all

typedef struct heap_mem_block
{
	unsigned int address;
	size_t size;

	avl_node_t *node;
} heap_mem_block_t;

And the Heap Manager Strucure looks like this:

Code: Select all

typedef struct heap_manager
{
	unsigned int heap_start_address;
	unsigned int heap_end_address;
	unsigned int heap_max_size;

	int supervisor;
	int readonly;

	avl_tree_t *tree;
} heap_manager_t;

So ok, If I want to allocate some memory, I need to calculate the address. For this I have to lookup the last address (biggest node). And then add the node behing this address, but this isn't very good. When I free some memory from the mid of the tree, it won't be used until all nodes after are freed.
So what is the best way to manage the heap? I thought over it, but I got no better solution. Two trees with free and used Memory is kind of stupid.

Hope you could give me some ideas...
Cheers Christian

[ru2aqare]

So what is the best way to manage the heap? I thought over it, but I got no better solution. Two trees with free and used Memory is kind of stupid.

Hope you could give me some ideas...
Cheers Christian

Actually I did just that. An AVL tree contains the free blocks, and another tree contains the allocated blocks. This allows me fast allocation, and I can check whether a memory block to be released is actually allocated (or not allocated, which means there is a bug in the caller). Furthermore all blocks - be it allocated or unused - are chained in a linked list, which allows dumping of the heap in case something goes horribly wrong.