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

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the Qt Mobility Components.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, 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 qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

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

#include "qvaluespace_p.h"

#include "qmallocpool_p.h"

#include "qvaluespacepublisher.h"

#include "qsystemreadwritelock_p.h"

#include "qpacketprotocol_p.h"

#include <QSet>

#include <QCoreApplication>

#include <QLocalSocket>

#include <QLocalServer>

#include <QDir>

#include <QVariant>

#include <QMutex>

#include <QSharedMemory>

#include <QTime>

#include <QThread>

QTM_BEGIN_NAMESPACE

#define VERSION_TABLE_ENTRIES 8191

#define ROOT_VERSION_ENTRY 0

#define MAX_PATH_SIZE 16384

#define MAX_DATA_SIZE 16384

#define INVALID_HANDLE 0xFFFF

#define ALIGN4b(n) ((n) + (((n) % 4)?(4 - ((n) % 4)):0))

// #define QVALUESPACE_UPDATE_STATS

static inline QDataStream& operator<<(QDataStream& stream, unsigned long v)

{

    if (sizeof(unsigned long) == sizeof(uint)) {

        stream << (uint)v;

        return stream;

    } else {

        stream << (quint64)v;

        return stream;

    }

}

static inline QDataStream& operator>>(QDataStream& stream, unsigned long& v)

{

    if (sizeof(unsigned long) == sizeof(uint)) {

        uint v32;

        stream >> v32;

        v = (unsigned long)v32;

    } else {

        quint64 v64;

        stream >> v64;

        v = (unsigned long)v64;

    }

    return stream;

}

static int vsmemcmp(const char * s1, int l1, const char * s2, int l2)

{

    if (l1 < l2)

        return -1;

    if (l1 > l2)

        return 1;

    return ::memcmp(s1, s2, l1);

}

///////////////////////////////////////////////////////////////////////////////

// declare VersionTable

///////////////////////////////////////////////////////////////////////////////

struct VersionTable {

    struct Entry {

        Entry(unsigned int v, unsigned int n) : version(v), nodePtr(n) {}

        unsigned int version;

        union {

            unsigned int nodePtr;

            unsigned int nxtFreeBlk; // 0 means no next free block

                                     // (as root is always 0)

        };

    };

    unsigned int nxtFreeBlk;

    unsigned int nextCreationId;

    Entry entries[VERSION_TABLE_ENTRIES];

};

// declare NodeOwner

/*

   Owner of data in a node.

   Overhead: 8

 */

struct NodeOwner {

    unsigned long data1;

    unsigned long data2;

};

// declare NodeDatum

/*

   Encapsulates the data and data owner associated with a Node.

   Overhead: 12 + data size

 */

struct NodeDatum {

    NodeOwner owner;

    enum Type { Boolean = QVariant::Bool,

                Int = QVariant::Int,

                UInt = QVariant::UInt,

                LongLong = QVariant::LongLong,

                ULongLong = QVariant::ULongLong,

                Double = QVariant::Double,

                Char = QVariant::Char,

                String = QVariant::String,

                ByteArray = QVariant::ByteArray,

                SerializedType /* Catch all for everything else */ };

    //Type type;

    unsigned short type;

    unsigned short len;

    char data[0];

};

// declare NodeWatch

/*

   Node write watcher.

   Overhead: 8

*/

struct NodeWatch {

    unsigned long data1;

    unsigned long data2;

};

///////////////////////////////////////////////////////////////////////////////

// declare Node

///////////////////////////////////////////////////////////////////////////////

/*

   In memory representation of a node.

   In memory, nodes are structured in one of the following three ways.

   Virtual (No Data) Node:

       <Node (dataCount == 0)><const char [] name>

   Single data node:

       <Node (dataCount == 1)><char [] name><NodeDatum><char [] data>

   Multiple data node:

       <Node (dataCount >= 2)><char [] name><unsigned int dataListPtr>

   With single watch:

       <Node (watchCount == 1)><char [] name><Rest of node...><NodeWatch>

   With multiple watch:

       <Node (watchCount >= 2)><char [] name><Rest of node...><unsigned int nodeWatchPtr>

   Overhead: 16 bytes + name size

 */

struct Node {

    unsigned short parent;    /* Id for my parent */

    unsigned int creationId;  /* Unique id set when I was constructed */

    unsigned short subNodes;  /* Sub node count */

    unsigned int subNodePtr;  /* Ptr to malloc'd array of sub node ptrs */

    unsigned short watchCount;

    unsigned short dataCount; /* Amount of data associated with this node */

    unsigned short nameLen;   /* Length of name in bytes */

    unsigned short dummy;     /* dummy for 4 byte alignment */

    char name[0];             /* My name - NO trailing null */

    bool valid() {

        return 0 != watchCount || 0 != dataCount || 0 != subNodes;

    }

    unsigned int dataBlockSize()

    {

        if(0 == dataCount) {

            return 0;

        } else if(1 == dataCount) {

            NodeDatum * datum = (NodeDatum *)dataBegin();

            return sizeof(NodeDatum) + datum->len;

        } else if(2 >= dataCount) {

            return sizeof(unsigned int);

        }

    }

    unsigned int watchBlockSize()

    {

        if(0 == watchCount)

            return 0;

        else if(1 == watchCount)

            return sizeof(NodeWatch);

        else if(2 >= watchCount)

            return sizeof(unsigned int);

        return 0;

    }

    unsigned int size()

    {

        unsigned int rv = sizeof(Node);

        rv += ALIGN4b(nameLen);

        if(watchCount == 1) {

            rv += sizeof(NodeWatch);

        } else if(watchCount >= 2) {

            rv += sizeof(unsigned int);

        }

        if(dataCount == 1) {

            NodeDatum * datum = (NodeDatum *)dataBegin();

            rv += sizeof(NodeDatum) + ALIGN4b(datum->len);

        } else if(dataCount >= 2) {

            rv += sizeof(unsigned int);

        }

        return rv;

    }

    void * dataBegin()

    {

        return (void *)(name + ALIGN4b(nameLen));

    }

    void * watchBegin()

    {

        if(0 == dataCount) {

            return dataBegin();

        } else if(1 == dataCount) {

            NodeDatum * datum = (NodeDatum *)dataBegin();

            return datum->data + ALIGN4b(datum->len);

        } else {

            return name + ALIGN4b(nameLen) + sizeof(unsigned int);

        }

    }

};

bool operator==(const NodeOwner &lhs, const NodeOwner &rhs)

{

    return 0 == ::memcmp(&lhs, &rhs, sizeof(NodeOwner));

}

bool operator!=(const NodeOwner &lhs, const NodeOwner &rhs)

{

    return 0 != ::memcmp(&lhs, &rhs, sizeof(NodeOwner));

}

bool operator==(const NodeWatch &lhs, const NodeWatch &rhs)

{

    return 0 == ::memcmp(&lhs, &rhs, sizeof(NodeWatch));

}

bool operator!=(const NodeWatch &lhs, const NodeWatch &rhs)

{

    return 0 != ::memcmp(&lhs, &rhs, sizeof(NodeWatch));

}

static const NodeWatch INVALID_WATCH = {0,0};

static const NodeOwner INVALID_OWNER = {0,0};

///////////////////////////////////////////////////////////////////////////////

// declare FixedMemoryTree

///////////////////////////////////////////////////////////////////////////////

class FixedMemoryTree : public QObject

{

    Q_OBJECT

public:

    FixedMemoryTree(void * mem, unsigned int size, bool initMem);

    // Returns the closest node to the specified path

    unsigned short findClosest(const char * path,

                               const char ** matched);

    unsigned short findClosest(unsigned int from,

                               const char * subPath,

                               const char ** matched);

    NodeDatum * data(unsigned short node);

    bool addWatch(const char * path, NodeWatch owner);

    bool remWatch(const char * path, NodeWatch owner);

    bool insert(const char * path,

                NodeDatum::Type type,

                const char * data,

                unsigned int dataLen,

                NodeOwner owner);

    unsigned short offsetOfSubNode(unsigned short node,

                                   unsigned short subNode);

    bool remove(const char * path, NodeOwner owner);

    inline Node * getNode(unsigned int);

    inline Node * subNode(unsigned int, unsigned short);

    inline unsigned int version(unsigned int);

    inline void * fromPtr(unsigned int ptr);

#ifdef QVALUESPACE_UPDATE_STATS

    inline QMallocPool *mallocPool() const { return pool; }

#endif

    typedef void (*NodeChangeFunction)(unsigned short node, void *ctxt);

    void setNodeChangeFunction(NodeChangeFunction, void *);

private:

    static unsigned int growListSize(unsigned int currentSize);

    static unsigned int shrunkListSize(unsigned int currentSize,

                                       unsigned int toSize);

    bool setWatch(unsigned short node, NodeWatch owner);

    bool remWatch(unsigned short node, NodeWatch owner);

    bool setData(unsigned short node, NodeOwner owner,

                 NodeDatum::Type type,  const char * data,

                 unsigned int dataLen);

    void removeFrom(unsigned short from, unsigned short subNodeNumber);

    unsigned short findRecur(unsigned short node, const char * path,

                             const char ** consumed);

    bool insertRecur(unsigned short node, const char * path,

                     NodeDatum::Type type, const char * data,

                     unsigned int dataLen, NodeOwner owner);

    bool addWatchRecur(unsigned short node, const char * path,

                       NodeWatch owner);

    bool remWatchRecur(unsigned short node, const char * path,

                       NodeWatch owner);

    bool removeRecur(unsigned short node, const char * path,

                     NodeOwner owner);

    unsigned short removeRecur(unsigned short, NodeOwner owner);

    unsigned int locateInNode(Node * node, const char * name,

                              unsigned int len, bool * match);

    inline unsigned int ptr(void * mem);

    inline VersionTable * versionTable();

    inline void bump(unsigned short node);

    unsigned short newNode(const char * name, unsigned int len,

                           NodeWatch owner);

    unsigned short newNode(const char * name,

                           unsigned int len,

                           NodeOwner owner = INVALID_OWNER,

                           NodeDatum::Type type = (NodeDatum::Type)0,

                           const char * data = 0,

                           unsigned int dataLen = 0);

    inline Node * node(unsigned int);

    char * poolMem;

    QMallocPool * pool;

    bool changed;

    NodeChangeFunction changeFunc;

    void * changeFuncContext;

};

///////////////////////////////////////////////////////////////////////////////

// define FixedMemoryTree

///////////////////////////////////////////////////////////////////////////////

FixedMemoryTree::FixedMemoryTree(void * mem, unsigned int size,

                                 bool initMemory )

: poolMem((char *)mem), pool(0), changed(false), changeFunc(0)

{

    Q_ASSERT(size);

    Q_ASSERT(poolMem);

    if(initMemory) {

        /* Initialize layer version table - would be worth randomizing the

           nextFreeBlk chain to distribute entries across the 128-bit change

           notification. */

        ::memset(poolMem,0, sizeof(VersionTable));

        for(int ii = 0; ii < VERSION_TABLE_ENTRIES; ++ii)

            versionTable()->entries[ii].nxtFreeBlk =

                (ii + 1) % VERSION_TABLE_ENTRIES;

        /* Create malloc pool on the non-version table portion of the layer */

        pool =

            new QMallocPool(poolMem + sizeof(VersionTable),

                            size - sizeof(VersionTable),

                            QMallocPool::Owned, QLatin1String("FixedMemoryTree"));

        /* Create root node and fixup free block pointer */

        versionTable()->nxtFreeBlk =

            versionTable()->entries[ROOT_VERSION_ENTRY].nxtFreeBlk;

        Node * root = (Node *)pool->malloc(sizeof(Node));

        ::memset(root,0, sizeof(Node));

        root->creationId = versionTable()->nextCreationId++;

        root->parent = INVALID_HANDLE;

        Q_ASSERT((char *)root > poolMem);

        versionTable()->entries[ROOT_VERSION_ENTRY] =

            VersionTable::Entry(1, ptr(root));

    }

}

unsigned short FixedMemoryTree::findClosest(const char * path,

                                            const char ** matched)

{

    Q_ASSERT(path);

    Q_ASSERT(matched);

    Q_ASSERT(path[0] == '/');

    ++path; // Skip initial '/'

    if('\0' == *path)

        return ROOT_VERSION_ENTRY;

    else

        return findRecur(ROOT_VERSION_ENTRY, path, matched);

}

unsigned short FixedMemoryTree::findClosest(unsigned int from,

                                            const char * subPath,

                                            const char ** matched)

{

    Q_ASSERT(subPath);

    Q_ASSERT(matched);

    Q_ASSERT(subPath[0] == '/');

    ++subPath; // Skip initial '/'

    if('\0' == *subPath)

        return from;

    else

        return findRecur(from, subPath, matched);

}

/*!

  Returns the default datum for \a node, or NULL if one doesn't exist.

  */

NodeDatum * FixedMemoryTree::data(unsigned short node)

{

    Node * n = this->node(node);

    if(0 == n->dataCount) {

        return 0;

    } else if(1 == n->dataCount) {

        return (NodeDatum *)n->dataBegin();

    } else {

        unsigned int * valueList =

            (unsigned int *)fromPtr(*(unsigned int *)n->dataBegin());

        return (NodeDatum *)fromPtr(*valueList);

    }

}

/*!

  Inserts a watch for \a owner at the specified \a path

*/

bool FixedMemoryTree::addWatch(const char * path, NodeWatch owner)

{

    Q_ASSERT(path);

    Q_ASSERT(path[0] == '/');

    Q_ASSERT(INVALID_WATCH != owner);

    ++path; // Skip initial '/'

    if(*path == '\0')

        return setWatch(ROOT_VERSION_ENTRY, owner);

    else

        return addWatchRecur(ROOT_VERSION_ENTRY, path, owner);

}

/*!

  Removes an existing watch for \a owner from the specified \a path

*/

bool FixedMemoryTree::remWatch(const char * path, NodeWatch owner)

{

    Q_ASSERT(path);

    Q_ASSERT(path[0] == '/');

    Q_ASSERT(INVALID_WATCH != owner);

    ++path; // Skip initial '/'

    if(*path == '\0')

        return remWatch((unsigned short)ROOT_VERSION_ENTRY, owner);

    else

        return remWatchRecur(ROOT_VERSION_ENTRY, path, owner);

}

/*!

  Inserts \a data of length \a dataLen at \a path with the set \a owner.

  Returns true if the tree has visibly changed.

  */

bool FixedMemoryTree::insert(const char * path, NodeDatum::Type type,

                             const char * data, unsigned int dataLen,

                             NodeOwner owner)

{

    Q_ASSERT(path);

    Q_ASSERT(path[0] == '/');

    Q_ASSERT(data || !dataLen);

    Q_ASSERT(INVALID_OWNER != owner);

    if(dataLen > MAX_DATA_SIZE)

        return false;

    ++path; // Skip initial '/'