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

**

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

/**

 * HbSplayTreeAllocator::initialize

 *

 * Initializes splay tree and internal variables.

 * This can't fail if sharedChunk is valid.

 */

void HbSplayTreeAllocator::initialize(HbSharedMemoryWrapper *sharedChunk,

                                      const quintptr offset,

                                      HbSharedMemoryAllocator *mainAllocator)

{

    Q_UNUSED(mainAllocator);

    chunk = sharedChunk;

    this->offset = offset;

    header = address<HeapHeader>(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 = reinterpret_cast<MemoryBlock*>(&header[1]);

    block->pointerNode.key = TO_OFFSET(block);

    block->lengthNode.key = static_cast<quintptr>(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(quintptr offset) const

{

    if (offset >= sizeof(HeapHeader)) {

        unsigned char *base = static_cast<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.

 */

qptrdiff 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, static_cast<quintptr>(size)));

    bool splayed = true;

    if (node && (node->key < static_cast<quintptr>(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 = reinterpret_cast<MemoryBlock*>(node);

    int totalSize = size + sizeof(MemoryBlock);

    int remainingSize = int(node->key) - totalSize;

    unsigned char *ptr = reinterpret_cast<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 = reinterpret_cast<MemoryBlock*>(&ptr[size]);

    if (remainingSize >= ALIGN_SIZE

        && reinterpret_cast<unsigned char*>(secondBlock)

           < address<unsigned char>(chunk->size() - sizeof(MemoryBlock))) {

        block->lengthNode.key = static_cast<quintptr>(size);

        secondBlock->lengthNode.key = static_cast<quintptr>(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(qptrdiff offset)

{

    int size = 0;

    if (offset > 0) {

        char *srcPtr = TO_PTR(offset);

        MemoryBlock *block = reinterpret_cast<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(qptrdiff offset)

{

    if (offset <= 0) {

        return;

    }

    MemoryBlock *block = TO_BLOCK_POINTER(offset - sizeof(MemoryBlock));

    MemoryBlock *nextBlock = reinterpret_cast<MemoryBlock*>(reinterpret_cast<char*>(&block[1]) + block->lengthNode.key);

    // Adjust the free bytes

    header->freeBytes += block->lengthNode.key;

    header->allocatedBytes -= block->lengthNode.key;

    TreeNode *node = 0;

    quintptr predecessor = 0;

    if (reinterpret_cast<char*>(nextBlock) > reinterpret_cast<char*>(chunk->data())

        && reinterpret_cast<char*>(nextBlock) < address<char>(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 = reinterpret_cast<MemoryBlock*>(

                                reinterpret_cast<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 += sizeof(MemoryBlock);

                header->allocatedBytes -= 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.

 */

quintptr HbSplayTreeAllocator::splay(quintptr *root, quintptr 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(quintptr *root, TreeNode *node, bool splayed)

{

    quintptr 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(quintptr *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(quintptr *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(quintptr *root, TreeNode *node, bool splayed)

{

    MemoryBlock *block = reinterpret_cast<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);

            quintptr 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 = static_cast<quintptr>(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(quintptr *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 = reinterpret_cast<MemoryBlock*>(node);

    if (!t || (t->lengthNode.key != node->key)) {

        // Insert into the tree

        p->prev = 0;

        p->next = 0;

        insertNode(root, node, reinterpret_cast<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);

        }

    }

}

/**

 * HbSplayTreeAllocator::size

 *

 * Gets the total size as bytes used.

 */

int HbSplayTreeAllocator::size()

{

    // splay the 'pointer' tree to obtain last pointer

    quintptr last_offset = static_cast<quintptr>(chunk->size());

    TreeNode *node = TO_NODE_POINTER(splay(&header->pointerNode, last_offset));

    if (node) {

        TreeNode *right = TO_NODE_POINTER(node->rightNode);

        if (right) {

            node = right;

        }

        MemoryBlock *block = reinterpret_cast<MemoryBlock*>(reinterpret_cast<char*>(node)

                             - sizeof(TreeNode));

        return TO_OFFSET(block) + sizeof(MemoryBlock) - 1; // not aligned, but actual last byte allocated.;

    }

    return -1;

}

int HbSplayTreeAllocator::freeBytes()

{

    return header->freeBytes;

}