/****************************************************************************

**

** 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;

    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;

}