stafconverter.cpp

Software Testing Automation Framework (STAF)的开发代码

/*****************************************************************************/
/* Software Testing Automation Framework (STAF)                              */
/* (C) Copyright IBM Corp. 2001                                              */
/*                                                                           */
/* This software is licensed under the Common Public License (CPL) V1.0.     */
/*****************************************************************************/

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

#include "STAF.h"
#include "STAF_fstream.h"
#include "STAF_iostream.h"
#include "STAFUtil.h"
#include "STAFConverter.h"

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

Node::Node()
{
    for (unsigned i = 0; i < 256; i++)
        index[i] = 0;
}

Node::Node(Node *nextNode)
{
    for (unsigned i = 0; i < 256; i++)
        node[i] = nextNode;
}

Node::Node(Leaf *nextLeaf)
{
    for (unsigned i = 0; i < 256; i++)
        leaf[i] = nextLeaf;
}

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

CompactTree::CompactTree()
{ 
    // if this constructor is used, then we set its mode to unknown since 
    // no memory has been allocated. using this constructor does not gua-
    // rantee that the user will ever deserialize the tree,  so we should 
    // not let the destructor delete memory that has not been allocated.

    fMode      = kUnknown;
    fNodeSize  = sizeof(Node);
    fLeafSize  = 0; // set by deserialize
}

CompactTree::CompactTree(unsigned int sizeOfKey, unsigned int sizeOfVal,
                         const unsigned char *defValPtr)
{
    // if this constructor is used, then we set its mode as  serialize. the
    // destructor will walk down the levels and  delete each node/leaf when
    // the tree is in serialize mode.  note that even if somebody used this
    // constructor but never writes into the tree or serializes the tree it
    // will still be ok since we allocate 1 node/leaf for each level as the
    // default. 

    fMode      = kSerialize;
    fSizeOfKey = sizeOfKey;
    fSizeOfVal = sizeOfVal;
    fNodeSize  = sizeof(Node);
    fLeafSize  = 256 * fSizeOfVal;

    int i = 0;

    for (i = 0; i < fSizeOfKey; i++)
        fLevelIndex[i] = 0;

    // allocate 1 leaf of 256 Chars (not chars) and initialize
    // with default value or zeroes if no default specified

    Leaf *leafPtr = new Leaf[fLeafSize];

    if (defValPtr != 0)
    {
        Leaf *nextValPtr = leafPtr;
        for (i = 0; i < 256; i++, nextValPtr += fSizeOfVal)
            memcpy(nextValPtr, defValPtr, fSizeOfVal);
    }
    else memset(leafPtr, 0, fLeafSize);

    // create the default nodes for each level and initialize

    for (i = 0; i < fSizeOfKey - 1; i++)
        fLevelVector[i].push_back((void *)new Node());

    fLevelVector[i].push_back((void *)leafPtr);
}

CompactTree::~CompactTree()
{
    switch (fMode)
    {
        case kSerialize:
        break;

        case kDeserialize:
        delete[] pNodeBuffer;
        return;
 
        default:
        return;
    }

    // this is reached only when the tree was in serialized mode.
    // in serialized mode, we have allocated individual nodes/leaves
    // for each level (at least 1 per level for the default) so we
    // must now delete them.

    int i = 0, j = 0;

    // walk down each level and delete each node/leaf

    for (i = 0; i < fSizeOfKey - 1; i++)
    {
        for (j = 0; j < fLevelIndex[i]; j++)
        {
            Node *nextNodePtr = (Node *)fLevelVector[i][j];
            delete nextNodePtr;
        }
    }

    for (j = 0; j < fLevelIndex[i]; j++)
    {
        Leaf *nextLeafPtr = (Leaf *)fLevelVector[i][j];
        delete nextLeafPtr;
    }
}

int CompactTree::serialize(fstream &outStream)
{
    // write the sizes of both the key and the values to
    // the binary file

    outStream.write((char *)&fSizeOfKey, sizeof(fSizeOfKey));
    outStream.write((char *)&fSizeOfVal, sizeof(fSizeOfVal));

    int i = 0;

    // write the count of nodes/leaves per level

    for (i = 0; i < fSizeOfKey; i++)
    {
        unsigned int count = fLevelVector[i].size();
        outStream.write((char *)&count, sizeof(count));
    }

    int j = 0;

    // write each node traversing the tree in width-first order

    for (i = 0; i < fSizeOfKey - 1; i++)
    {
        for (j = 0; j < fLevelVector[i].size(); j++)
        {      
            Node *nextPtr = (Node *)fLevelVector[i][j];
            outStream.write((char *)nextPtr, fNodeSize);
        }
    }

    // write each leaf as well (i = fSizeOfKey - 1)

    for (j = 0; j < fLevelVector[i].size(); j++)
    {
        Leaf *leafPtr = (Leaf *)fLevelVector[i][j];
        outStream.write((char *)leafPtr, fLeafSize);
    }

    return 0;
}

int CompactTree::deserialize(fstream &inStream)
{
    // read the sizes of both the key and the values from
    // the binary file

    inStream.read((char *)&fSizeOfKey, sizeof(fSizeOfKey));
    inStream.read((char *)&fSizeOfVal, sizeof(fSizeOfVal));

    fLeafSize = 256 * fSizeOfVal; 

    int i = 0;

    // read the count of nodes/leaves per level

    for (i = 0; i < fSizeOfKey; i++)
    {
        inStream.read((char *)&fLevelIndex[i], sizeof(unsigned int));
    }

    unsigned int totalNodes = 0;
    unsigned int totalLeaves = 0;

    // count up the total number of inner nodes and leaves

    for (i = 0; i < fSizeOfKey - 1; i++)
        totalNodes += fLevelIndex[i]; 

    totalLeaves = fLevelIndex[i];

    try
    {
        // since we allocate memory here then we set the mode
        // as deserialize in order to let the destructor know
        // what it needs to clean up
         
        fMode = kDeserialize;

        // allocate one common buffer (for cache efficiency)
        // to store both inner nodes and leaves

        char *pBuffer = new char[fNodeSize * totalNodes +
                                 fLeafSize * totalLeaves];

        // Note: pNodeBuffer + totalNodes increment in Node-
        // size bytes, so there is no need to scale by 256

        pNodeBuffer = (Node *)(pBuffer);
        pLeafBuffer = (Leaf *)(pNodeBuffer + totalNodes);

        // special case for key size = 1, there must be only
        // 1 leaf and no nodes so just read it in and return

        if (fSizeOfKey == 1)
        {
            inStream.read((char *)pLeafBuffer, fLeafSize);
            return 0;
        }

        // read the entire nodes. while deserializing, convert
        // all node contained indeces into actual pointers to
        // their respective next-level nodes

        inStream.read((char *)pNodeBuffer, fNodeSize * totalNodes);

        Node *nextNodePtr = pNodeBuffer;

        int j = 0, k = 0;
        
        // for each level ...
        for (i = 0; i < fSizeOfKey - 2; i++)
        {
            // for each node in the level ...
            for (j = 0; j < fLevelIndex[i]; j++, nextNodePtr++)
            {
                // for each entry in the node ...
                for (k = 0; k < 256; k++)
                {
                    // point to its corresponding next level node
                    nextNodePtr->node[k] = nextNodePtr + 
                                           nextNodePtr->index[k] +
                                           fLevelIndex[i] - j;
                }
            }
        }

        // read the entire leaves. while deserializing, convert
        // all node contained indeces into actual pointers to
        // their respective data leaves
        
        inStream.read((char *)pLeafBuffer, fLeafSize * totalLeaves);

        // for each node in the previous-to-last level ...
        for (j = 0; j < fLevelIndex[i]; j++, nextNodePtr++)
        {
            // for each entry in the node ...
            for (k = 0; k < 256; k++)
            {
                // point to its corresponding leaf
                nextNodePtr->leaf[k] = pLeafBuffer + 
                                       nextNodePtr->index[k] * 
                                       256 * fSizeOfVal;
            }
        }
    }
    catch (...)
    {
        cerr << "Caught unknown exception in CompactTree::deserialize()"
             << endl;

        return 2;
    }

    return 0;
}

void CompactTree::put(const unsigned char *key, const unsigned char *val)
{
    Leaf *leafPtr;

    // XXX: do real exception handling

    if (key == 0 || val == 0)
    {
        cerr << "CompactTree::put(), key or val = NULL" << endl;
        return;
    }

    // special case for key size 1

    if (fSizeOfKey == 1)
    {
        leafPtr = (Leaf *)fLevelVector[0][0];
        memcpy((char *)&leafPtr[ key[0] * fSizeOfVal ], val, fSizeOfVal);
        return;
    }

    int i = 0;
    Node *prevPtr = 0;
    Node *nextPtr = (Node *)fLevelVector[0][0];
    bool needsNodeBranch = false;

    // check if a node branch is needed

    for (i = 0; i < fSizeOfKey - 2 && !needsNodeBranch; i++)
    {
        if (nextPtr->index[key[i]] == 0)
        {
            needsNodeBranch = true;
            break;
        }

        prevPtr = nextPtr;
        nextPtr = (Node *)fLevelVector[i + 1][nextPtr->index[key[i]]];
    }

    if (needsNodeBranch)
    {
        // i has the index of last non-default level
        // prevPtr points to last non-default level,
        // nextPtr points to first default level

        // create internal nodes

        for (; i < fSizeOfKey - 2; i++)
        {
            nextPtr->index[key[i]] = fLevelVector[i + 1].size();
            prevPtr = nextPtr;
            nextPtr = new Node();
            fLevelVector[i + 1].push_back((void *)nextPtr);
        }
    }

    // check if a leaf branch is needed, otherwise get the
    // leaf

    if (nextPtr->index[key[i]] == 0)
    {
        nextPtr->index[key[i]] = fLevelVector[i + 1].size();
        leafPtr = new Leaf[fLeafSize];
        memcpy(leafPtr, fLevelVector[fSizeOfKey - 1][0], fLeafSize);
        fLevelVector[fSizeOfKey - 1].push_back((void *)leafPtr);
    }
    else 
    {
        leafPtr = (Leaf *)fLevelVector[fSizeOfKey - 1][nextPtr->index[key[i]]];
    }

    // copy value into leaf and we are done!!!

    memcpy((char *)&leafPtr[ key[fSizeOfKey - 1] * fSizeOfVal ], 
           val, fSizeOfVal);
}

const unsigned char *CompactTree::get(const unsigned char *key)
{
    Leaf *leafPtr = pLeafBuffer;
    Node *nextPtr = pNodeBuffer;

    // XXX: do real exception handling

    if (key == 0) 
    {
        cerr << "CompactTree::get(), key = NULL" << endl;
        return 0;
    }

    switch (fSizeOfKey)
    {
        case 1:
        
        switch (fSizeOfVal)
        {
            case 1:
            return &leafPtr[key[0]];

            case 2:
            return &leafPtr[key[0] << 1];