/****************************************************************************
**
** Copyright (C) 2008-2010 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation (developer.feedback@nokia.com)
**
** This file is part of the HbCore module of the UI Extensions for Mobile.
**
** GNU Lesser General Public License Usage
** This file may be used under the terms of the GNU Lesser General Public
** License version 2.1 as published by the Free Software Foundation and
** appearing in the file LICENSE.LGPL included in the packaging of this file.
** Please review the following information to ensure the GNU Lesser General
** Public License version 2.1 requirements will be met:
** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** In addition, as a special exception, Nokia gives you certain additional
** rights.  These rights are described in the Nokia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** If you have questions regarding the use of this file, please contact
** Nokia at developer.feedback@nokia.com.
**
****************************************************************************/

#include "hbsharedmemoryallocators_p.h"

#include <QSharedMemory>
#include <QDebug>

#define TO_PTR(x) ((char*)(toPointer(x)))
#define TO_NODE_POINTER(x) ((TreeNode*)(toPointer(x)))
#define TO_BLOCK_POINTER(x) ((MemoryBlock*)(toPointer(x)))
#define TO_NODE_OFFSET(x) ((int)((char*)(x)-(char*)(chunk->data())))
#define TO_OFFSET(x) ((int)((char*)(x)-(char*)(chunk->data())))

// this identifier is used to check, if the splay tree is already
// initialized in given shared chunk
const unsigned int INITIALIZED_ALLOCATOR_IDENTIFIER = 0x53504C59; //'SPLY'

/**
 * HbSplayTreeAllocator::initialize
 *
 * Initializes splay tree and internal variables.
 * This can't fail if sharedChunk is valid.
 */
void HbSplayTreeAllocator::initialize(QSharedMemory *sharedChunk,
                                      const unsigned int offset,
                                      HbSharedMemoryAllocator *mainAllocator)
{
    Q_UNUSED(mainAllocator);
    chunk = sharedChunk;
    this->offset = offset;

    header = (HeapHeader*)(chunk->data()) + offset;
    if (header->identifier == INITIALIZED_ALLOCATOR_IDENTIFIER) {
        return; // already initialized
    }

    memset(header, 0, sizeof(HeapHeader));
    header->freeBytes = chunk->size()-offset-sizeof(HeapHeader)-sizeof(MemoryBlock);

    // insert first memory block in chunk
    MemoryBlock *block = (MemoryBlock*)&header[1];

    block->pointerNode.key = TO_OFFSET(block);
    block->lengthNode.key = (unsigned int)header->freeBytes;

    insertLengthNode(&header->lengthNode, &block->lengthNode);
    insertNode(&header->pointerNode, &block->pointerNode);

    header->identifier = INITIALIZED_ALLOCATOR_IDENTIFIER;
}

// Constructor
//
HbSplayTreeAllocator::HbSplayTreeAllocator()
    : chunk(0),
      offset(0)
{
}

// Destructor
//
HbSplayTreeAllocator::~HbSplayTreeAllocator()
{
}

/**
* HbSplayTreeAllocator::toPointer
*
* Helper function for converting offset to pointer
*/
void *HbSplayTreeAllocator::toPointer(unsigned int offset) const
{
    if (offset >= sizeof(HeapHeader)) {
        unsigned char *base = (unsigned char*)(chunk->data());
        return (&base[offset]);
    }
    return 0;
}

/**
 * HbSplayTreeAllocator::alloc
 * 
 * Allocate size bytes from shared memory.
 * Returns offset of allocated memory in shared chunk
 * or -1 if allocation failed.
 */
int HbSplayTreeAllocator::alloc(int size)
{
    if (size <= 0) {
        throw std::bad_alloc();
    }

    size = ALIGN(size);

    if (size > (int)(header->freeBytes-sizeof(MemoryBlock))) {
        throw std::bad_alloc();
    }

    // splay the 'length' tree to obtain the best match
    TreeNode *node = TO_NODE_POINTER(splay(&header->lengthNode, (unsigned int)size));
    bool splayed = true;

    if (node && (node->key < (unsigned int)size)) {
        splayed = false;
        node = TO_NODE_POINTER(node->rightNode);
        if (node) {
            while (node->leftNode) {
                node = TO_NODE_POINTER(node->leftNode);
            }
        }
    }

    // no big enough nodes found, return error
    if (!node) {
        throw std::bad_alloc();
    }

    // 'length' node is the first attribute of the MemoryBlock, therefore every
    // 'length' node is also a MemoryBlock.
    MemoryBlock *block = (MemoryBlock*)node;
    int totalSize = size + sizeof(MemoryBlock);
    int remainingSize = (int)node->key - totalSize;
    unsigned char *ptr = (unsigned char*)&block[1];

    // Remove current block from the trees
    deleteLengthNode(&header->lengthNode, node, splayed);
    deleteNode(&header->pointerNode, &block->pointerNode, false);

    // If the block is larger than the requested size, split the block and 
    // insert the second block into the trees
    MemoryBlock *secondBlock = (MemoryBlock*)&ptr[size];
    if ((remainingSize >= (int)(ALIGN_SIZE)) && ((unsigned char*)secondBlock < ((unsigned char*)(chunk->data())+chunk->size()-sizeof(MemoryBlock)))) {

        block->lengthNode.key = (unsigned int)size;
        secondBlock->lengthNode.key = (unsigned int)remainingSize;
        secondBlock->pointerNode.key = TO_NODE_OFFSET(secondBlock);

        // Insert the second block into the trees
        insertLengthNode(&header->lengthNode, &secondBlock->lengthNode);
        insertNode(&header->pointerNode, &secondBlock->pointerNode);
    } else {
        totalSize = (int)node->key;
    }

    // Adjust the allocation size
    header->freeBytes -= totalSize;
    header->allocatedBytes += totalSize;

    // Clear attributes and return the pointer
    block->lengthNode.leftNode = 0;
    block->lengthNode.rightNode = 0;
    block->pointerNode.leftNode = 0;
    block->pointerNode.rightNode = 0;
    block->next = 0;
    block->prev = 0;
    block->allocatorIdentifier = MAIN_ALLOCATOR_IDENTIFIER;

	return TO_OFFSET(ptr);
}

/**
 * HbSplayTreeAllocator::allocatedSize
 *
 * Used for reallocation.
 * Returns actual allocated size for given offset.
 */
int HbSplayTreeAllocator::allocatedSize(int offset)
{
    int size = 0;
    if (offset > 0) {
		char *srcPtr = TO_PTR(offset);
		MemoryBlock *block = (MemoryBlock*)(srcPtr - sizeof(MemoryBlock));	
		size = block->lengthNode.key;
    }
    return size;
}

/**
 * HbSplayTreeAllocator::free
 *
 * Releases memory by pushing MemoryBlock's nodes back into the trees.
 * Also does adjacent free blocks merging.
 */
void HbSplayTreeAllocator::free(int offset)
{
    if (offset <= 0) {
        return;
    }

    MemoryBlock *block = TO_BLOCK_POINTER(offset - sizeof(MemoryBlock));
    MemoryBlock *nextBlock = (MemoryBlock*)((unsigned char*)&block[1] + block->lengthNode.key);

    // Adjust the free bytes
    header->freeBytes += block->lengthNode.key;
    header->allocatedBytes -= block->lengthNode.key;

    TreeNode *node = 0;
    unsigned int predecessor = 0;
    if ((char*)nextBlock > (char*)chunk->data() && (char*)nextBlock < ((char*)chunk->data()+chunk->size())) {
        node = TO_NODE_POINTER(splay(&header->pointerNode, nextBlock->pointerNode.key));
    }

    if (node) {
		// Find previous block
        if (node->key < nextBlock->pointerNode.key) {
            predecessor = TO_NODE_OFFSET(node);
        } else if ((predecessor = node->leftNode) > 0) {
            while (TO_NODE_POINTER(predecessor)->rightNode) {
                predecessor = TO_NODE_POINTER(predecessor)->rightNode;
            }
        }

        // See if the block can be merged with the sucessor
        if (node->key == nextBlock->pointerNode.key) {
            // Remove the successor from both trees
            deleteLengthNode(&header->lengthNode, &nextBlock->lengthNode, false);
            deleteNode(&header->pointerNode, &nextBlock->pointerNode, true); 

            // Adjust the size
            block->lengthNode.key += (nextBlock->lengthNode.key + sizeof(MemoryBlock));
            header->freeBytes += sizeof(MemoryBlock);
            header->allocatedBytes -= sizeof(MemoryBlock);
        }

        // See if the block can be merged with the predecessor
        if (predecessor) {
            MemoryBlock *b = TO_BLOCK_POINTER(TO_NODE_POINTER(predecessor)->key);
            MemoryBlock *t = (MemoryBlock*)((unsigned char*)&b[1] + b->lengthNode.key);

            // Merge with the predecessor
            if (t->pointerNode.key == block->pointerNode.key) {
                // Remove the predecessor from the 'length' tree
                deleteLengthNode(&header->lengthNode, &b->lengthNode, false);

                // Adjust the size
                b->lengthNode.key += (block->lengthNode.key + sizeof(MemoryBlock));
                header->freeBytes += (int)sizeof(MemoryBlock);
                header->allocatedBytes -= (int)sizeof(MemoryBlock);

                // Re-insert the node in 'length' tree
                insertLengthNode(&header->lengthNode, &b->lengthNode);
                
                block = 0; // We don't have to insert the node
            }
        }
    }

    // Insert the node
    if (block) {
        insertLengthNode(&header->lengthNode, &block->lengthNode);
        insertNode(&header->pointerNode, &block->pointerNode);
    }
}

/**
 * HbSplayTreeAllocator::splay
 * 
 * Adjust the tree so that the best matching node goes to the top.
 */
unsigned int HbSplayTreeAllocator::splay(unsigned int *root, unsigned int key)
{
    TreeNode *t = TO_NODE_POINTER(*root);
    if (!t) {
        return 0;
    }

    TreeNode n;
    n.key = 0;
    n.leftNode = 0;
    n.rightNode = 0;
    TreeNode *left = &n;
    TreeNode *right = left;
    TreeNode *temp = 0;

    for (;;) {
        if (key < t->key) {
            if (t->leftNode == 0) {
                break;
            }

            // Rotate right
            if (key < TO_NODE_POINTER(t->leftNode)->key) {
                temp = TO_NODE_POINTER(t->leftNode);
                t->leftNode = temp->rightNode;
                temp->rightNode = TO_NODE_OFFSET(t);
                t = temp;

                if (t->leftNode == 0) {
                    break;
                }
            }

            // Link right
            right->leftNode = TO_NODE_OFFSET(t);
            right = t;
            t = TO_NODE_POINTER(t->leftNode);
        } else if (key > t->key) {
            if (t->rightNode == 0) {
                break;
            }

            // Rotate left
            if (key > TO_NODE_POINTER(t->rightNode)->key) {
                temp = TO_NODE_POINTER(t->rightNode);
                t->rightNode = temp->leftNode;
                temp->leftNode = TO_NODE_OFFSET(t);
                t = temp;

                if (t->rightNode == 0) {
                    break;
                }
            }
                              
            // Link left
            left->rightNode = TO_NODE_OFFSET(t);
            left = t;
            t = TO_NODE_POINTER(t->rightNode);
        } else {
            break;
        }
    }

    // Re-create the node
    left->rightNode = t->leftNode;
    right->leftNode = t->rightNode;
    t->leftNode = n.rightNode;
    t->rightNode = n.leftNode;

    return (*root = TO_NODE_OFFSET(t));
}

/**
 * HbSplayTreeAllocator::deleteNode
 * 
 * Delete a node from the tree. If 'splayed' is true, then the tree
 * is assumed to be splayed with the correct key.
 */
void HbSplayTreeAllocator::deleteNode(unsigned int *root, TreeNode *node, bool splayed)
{
    unsigned int x = *root;

    if (splayed) {
        x = TO_NODE_OFFSET(node);
    } else {
        x = splay(&x, node->key);
    }

    if (TO_NODE_POINTER(x)->key == node->key) {
        if (node->leftNode == 0) {
            x = node->rightNode;
        } else {
            x = splay(&node->leftNode, node->key);
            TO_NODE_POINTER(x)->rightNode = node->rightNode;
        }
    }
    *root = x;
}

/**
 * HbSplayTreeAllocator::insertNode
 * 
 * Insert a new node into the tree.
 */
void HbSplayTreeAllocator::insertNode(unsigned int *root, TreeNode *node)
{
    insertNode(root, node, TO_NODE_POINTER(splay(root, node->key)));
}

/**
 * HbSplayTreeAllocator::insertNode
 * 
 * Insert a new node into the tree.
 */
void HbSplayTreeAllocator::insertNode(unsigned int *root, TreeNode *node, TreeNode *t)
{
    if (t == 0) {
        node->leftNode = 0;
        node->rightNode = 0;
    } else if (node->key < t->key) {
        node->leftNode = t->leftNode;
        node->rightNode = TO_NODE_OFFSET(t);
        t->leftNode = 0;
    } else {
        node->rightNode = t->rightNode;
        node->leftNode = TO_NODE_OFFSET(t);
        t->rightNode = 0;
    }

    *root = TO_NODE_OFFSET(node);
}

/**
 * HbSplayTreeAllocator::deleteLengthNode
 * 
 * For length nodes, we must additionally check linked list for correct node.
 */
void HbSplayTreeAllocator::deleteLengthNode(unsigned int *root, TreeNode *node, bool splayed)
{
    MemoryBlock *block = (MemoryBlock*)node;

    // If the node is not the first node in the linked list,
    // simply de-link node from the linked list.
    if (block->prev) {
        TO_BLOCK_POINTER(block->prev)->next = block->next;
        if (block->next) {
            TO_BLOCK_POINTER (block->next)->prev = block->prev;
        }
    } else {
        // If the node is the first node of the linked list, then
        // remove it from the tree and add the next node from the linked
        // list to the tree.
        if (block->next) {
            MemoryBlock *t = TO_BLOCK_POINTER(block->next);
            unsigned int x = *root;
            
            if (splayed) {
                x = TO_NODE_OFFSET(node);
            } else {
                x = splay(&x, node->key);
            }

            if (x && TO_NODE_POINTER(x)->key == node->key) {
                t->lengthNode.leftNode = TO_NODE_POINTER(x)->leftNode;
                t->lengthNode.rightNode = TO_NODE_POINTER(x)->rightNode;
                t->prev = 0;
                *root = (unsigned int)block->next;
            }
        } else {
            deleteNode(root, node, false);
        }
    }
}

/**
 * HbSplayTreeAllocator::insertLengthNode
 * 
 * Many length nodes can have the same key. Therefore, we have to build
 * linked list for the nodes with same key.
 */
void HbSplayTreeAllocator::insertLengthNode(unsigned int *root, TreeNode *node)
{
    // Length TreeNode is the first entry in the MemoryBlock. Therefore,
    // we can safely typecast TreeNode to a MemoryBlock.
    MemoryBlock *t = TO_BLOCK_POINTER(splay(root, node->key));
    MemoryBlock *p = (MemoryBlock*)node;

    if (!t || (t->lengthNode.key != node->key)) {
        // Insert into the tree
        p->prev = 0;
        p->next = 0;
        insertNode(root, node, (TreeNode*)t);
    } else {
        // Link to the existing tree node
        p->next = t->next;
        p->prev = TO_NODE_OFFSET(t);
        t->next = TO_NODE_OFFSET(p);
        
        if (p->next) {
            TO_BLOCK_POINTER(p->next)->prev = TO_NODE_OFFSET(p);
        }
    }
}

int HbSplayTreeAllocator::freeBytes()
{
    return header->freeBytes;
}

int HbSplayTreeAllocator::allocatedBytes()
{
    return header->allocatedBytes;
}
