/*
 * Copyright 2003-2007, Ingo Weinhold, ingo_weinhold@gmx.de.
 * Distributed under the terms of the MIT License.
 */

#include "DiskDeviceJobGenerator.h"

#include <new>

#include <stdlib.h>
#include <string.h>

#include <DiskDevice.h>
#include <MutablePartition.h>

#include <ddm_userland_interface_defs.h>

#include "DiskDeviceJob.h"
#include "DiskDeviceJobQueue.h"
#include "PartitionDelegate.h"
#include "PartitionReference.h"

#include "CreateChildJob.h"
#include "DeleteChildJob.h"
#include "DefragmentJob.h"
#include "InitializeJob.h"
#include "MoveJob.h"
#include "RepairJob.h"
#include "ResizeJob.h"
#include "SetStringJob.h"
#include "UninitializeJob.h"


#undef TRACE
#define TRACE(x...)
//#define TRACE(x...)   printf(x)


using std::nothrow;


// compare_string
/*!     \brief \c NULL aware strcmp().

        \c NULL is considered the least of all strings. \c NULL equals \c NULL.

        \param str1 First string.
        \param str2 Second string.
        \return A value less than 0, if \a str1 is less than \a str2,
                        0, if they are equal, or a value greater than 0, if
                        \a str1 is greater \a str2.
*/
static inline int
compare_string(const char* str1, const char* str2)
{
        if (str1 == NULL) {
                if (str2 == NULL)
                        return 0;
                return 1;
        } else if (str2 == NULL)
                return -1;

        return strcmp(str1, str2);
}


// MoveInfo
struct DiskDeviceJobGenerator::MoveInfo {
        BPartition*     partition;
        off_t           position;
        off_t           target_position;
        off_t           size;
};


// PartitionRefInfo
struct DiskDeviceJobGenerator::PartitionRefInfo {
        PartitionRefInfo()
                : partition(NULL),
                  reference(NULL)
        {
        }

        ~PartitionRefInfo()
        {
                if (reference)
                        reference->ReleaseReference();
        }

        BPartition*                     partition;
        PartitionReference*     reference;
};


// constructor
DiskDeviceJobGenerator::DiskDeviceJobGenerator(BDiskDevice* device,
                DiskDeviceJobQueue* jobQueue)
        : fDevice(device),
          fJobQueue(jobQueue),
          fMoveInfos(NULL),
          fPartitionRefs(NULL),
          fContentsToMove(NULL),
          fContentsToMoveCount(0)
{
        // Make sure the arrays are big enough (worst case: all old partitions have
        // been deleted and new ones been created).
        fPartitionCount = fDevice->CountDescendants()
                + fDevice->_CountDescendants();

        fMoveInfos = new(nothrow) MoveInfo[fPartitionCount];
        fPartitionRefs = new(nothrow) PartitionRefInfo[fPartitionCount];
        fContentsToMove = new(nothrow) PartitionReference*[fPartitionCount];
}


// destructor
DiskDeviceJobGenerator::~DiskDeviceJobGenerator()
{
        delete[] fMoveInfos;
        delete[] fPartitionRefs;
        delete[] fContentsToMove;
}


// GenerateJobs
status_t
DiskDeviceJobGenerator::GenerateJobs()
{
        // check parameters
        if (!fDevice || !fJobQueue)
                return B_BAD_VALUE;

        if (!fMoveInfos || !fPartitionRefs || !fContentsToMove)
                return B_NO_MEMORY;

        // 1) Generate jobs for all physical partitions that don't have an
        // associated shadow partition, i.e. those that shall be deleted.
        // 2) Generate uninitialize jobs for all partition whose initialization
        // changes, also those that shall be initialized with a disk system.
        // This simplifies moving and resizing.
        status_t error = _GenerateCleanupJobs(fDevice);
        if (error != B_OK) {
                TRACE("DiskDeviceJobGenerator::GenerateJobs(): _GenerateCleanupJobs() "
                        "failed\n");
                return error;
        }

        // Generate jobs that move and resize the remaining physical partitions
        // to their final position/size.
        error = _GeneratePlacementJobs(fDevice);
        if (error != B_OK) {
                TRACE("DiskDeviceJobGenerator::GenerateJobs(): "
                        "_GeneratePlacementJobs() failed\n");
                return error;
        }

        // Generate the remaining jobs in one run: initialization, creation of
        // partitions, and changing of name, content name, type, parameters, and
        // content parameters.
        error = _GenerateRemainingJobs(NULL, fDevice);
        if (error != B_OK) {
                TRACE("DiskDeviceJobGenerator::GenerateJobs(): "
                        "_GenerateRemainingJobs() failed\n");
                return error;
        }

        TRACE("DiskDeviceJobGenerator::GenerateJobs(): succeeded\n");

        return B_OK;
}


// _AddJob
status_t
DiskDeviceJobGenerator::_AddJob(DiskDeviceJob* job)
{
        if (!job)
                return B_NO_MEMORY;

        status_t error = fJobQueue->AddJob(job);
        if (error != B_OK)
                delete job;

        return error;
}


// _GenerateCleanupJobs
status_t
DiskDeviceJobGenerator::_GenerateCleanupJobs(BPartition* partition)
{
// TODO: Depending on how this shall be handled, we might want to unmount
// all descendants of a partition to be uninitialized or removed.
        if (BMutablePartition* shadow = _GetMutablePartition(partition)) {
                if ((shadow->ChangeFlags() & B_PARTITION_CHANGED_INITIALIZATION)
                        && partition->fPartitionData->content_type) {
                        // partition changes initialization
                        status_t error = _GenerateUninitializeJob(partition);
                        if (error != B_OK)
                                return error;
                } else {
                        // recurse
                        for (int32 i = 0; BPartition* child = partition->_ChildAt(i); i++) {
                                status_t error = _GenerateCleanupJobs(child);
                                if (error != B_OK)
                                        return error;
                        }
                }
        } else if (BPartition* parent = partition->Parent()) {
                // create job and add it to the queue
                status_t error = _GenerateDeleteChildJob(parent, partition);
                if (error != B_OK)
                        return error;
        }
        return B_OK;
}


// _GeneratePlacementJobs
status_t
DiskDeviceJobGenerator::_GeneratePlacementJobs(BPartition* partition)
{
        if (BMutablePartition* shadow = _GetMutablePartition(partition)) {
                // Don't resize/move partitions that have an unrecognized contents.
                // They must have been uninitialized before.
                if (shadow->Status() == B_PARTITION_UNRECOGNIZED
                        && (shadow->Size() != partition->Size()
                                || shadow->Offset() != partition->Offset())) {
                        return B_ERROR;
                }

                if (shadow->Size() > partition->Size()) {
                        // size grows: resize first
                        status_t error = _GenerateResizeJob(partition);
                        if (error != B_OK)
                                return error;
                }

                // place the children
                status_t error = _GenerateChildPlacementJobs(partition);
                if (error != B_OK)
                        return error;

                if (shadow->Size() < partition->Size()) {
                        // size shrinks: resize now
                        status_t error = _GenerateResizeJob(partition);
                        if (error != B_OK)
                                return error;
                }
        }

        return B_OK;
}


// _GenerateChildPlacementJobs
status_t
DiskDeviceJobGenerator::_GenerateChildPlacementJobs(BPartition* partition)
{
        BMutablePartition* shadow = _GetMutablePartition(partition);

        // nothing to do, if the partition contains no partitioning system or
        // shall be re-initialized
        if (!shadow->ContentType()
                || (shadow->ChangeFlags() & B_PARTITION_CHANGED_INITIALIZATION)) {
                return B_OK;
        }

        // first resize all children that shall shrink and place their descendants
        int32 childCount = 0;
        int32 moveForth = 0;
        int32 moveBack = 0;

        for (int32 i = 0; BPartition* child = partition->_ChildAt(i); i++) {
                if (BMutablePartition* childShadow = _GetMutablePartition(child)) {
                        // add a MoveInfo for the child
                        MoveInfo& info = fMoveInfos[childCount];
                        childCount++;
                        info.partition = child;
                        info.position = child->Offset();
                        info.target_position = childShadow->Offset();
                        info.size = child->Size();

                        if (info.position < info.target_position)
                                moveForth++;
                        else if (info.position > info.target_position)
                                moveBack++;

                        // resize the child, if it shall shrink
                        if (childShadow->Size() < child->Size()) {
                                status_t error = _GeneratePlacementJobs(child);
                                if (error != B_OK)
                                        return error;
                                info.size = childShadow->Size();
                        }
                }
        }

        // sort the move infos
        if (childCount > 0 && moveForth + moveBack > 0) {
                qsort(fMoveInfos, childCount, sizeof(MoveInfo),
                        _CompareMoveInfoPosition);
        }

        // move the children to their final positions
        while (moveForth + moveBack > 0) {
                int32 moved = 0;
                if (moveForth < moveBack) {
                        // move children back
                        for (int32 i = 0; i < childCount; i++) {
                                MoveInfo& info = fMoveInfos[i];
                                if (info.position > info.target_position) {
                                        if (i == 0
                                                || info.target_position >= fMoveInfos[i - 1].position
                                                        + fMoveInfos[i - 1].size) {
                                                // check OK -- the partition wouldn't be moved before
                                                // the end of the preceding one
                                                status_t error = _GenerateMoveJob(info.partition);
                                                if (error != B_OK)
                                                        return error;
                                                info.position = info.target_position;
                                                moved++;
                                                moveBack--;
                                        }
                                }
                        }
                } else {
                        // move children forth
                        for (int32 i = childCount - 1; i >= 0; i--) {
                                MoveInfo &info = fMoveInfos[i];
                                if (info.position > info.target_position) {
                                        if (i == childCount - 1
                                                || info.target_position + info.size
                                                        <= fMoveInfos[i - 1].position) {
                                                // check OK -- the partition wouldn't be moved before
                                                // the end of the preceding one
                                                status_t error = _GenerateMoveJob(info.partition);
                                                if (error != B_OK)
                                                        return error;
                                                info.position = info.target_position;
                                                moved++;
                                                moveForth--;
                                        }
                                }
                        }
                }

                // terminate, if no partition could be moved
                if (moved == 0)
                        return B_ERROR;
        }

        // now resize all children that shall grow/keep their size and place
        // their descendants
        for (int32 i = 0; BPartition* child = partition->_ChildAt(i); i++) {
                if (BMutablePartition* childShadow = _GetMutablePartition(child)) {
                        if (childShadow->Size() >= child->Size()) {
                                status_t error = _GeneratePlacementJobs(child);
                                if (error != B_OK)
                                        return error;
                        }
                }
        }

        return B_OK;
}


// _GenerateRemainingJobs
status_t
DiskDeviceJobGenerator::_GenerateRemainingJobs(BPartition* parent,
        BPartition* partition)
{
        user_partition_data* partitionData = partition->fPartitionData;

        uint32 changeFlags
                = partition->fDelegate->MutablePartition()->ChangeFlags();

        // create the partition, if not existing yet
        if (!partitionData) {
                if (!parent)
                        return B_BAD_VALUE;

                status_t error = _GenerateCreateChildJob(parent, partition);
                if (error != B_OK)
                        return error;
        } else {
                // partition already exists: set non-content properties

                // name
                if ((changeFlags & B_PARTITION_CHANGED_NAME)
                        || compare_string(partition->Name(), partitionData->name)) {
                        if (!parent)
                                return B_BAD_VALUE;

                        status_t error = _GenerateSetNameJob(parent, partition);
                        if (error != B_OK)
                                return error;
                }

                // type
                if ((changeFlags & B_PARTITION_CHANGED_TYPE)
                        || compare_string(partition->Type(), partitionData->type)) {
                        if (!parent)
                                return B_BAD_VALUE;

                        status_t error = _GenerateSetTypeJob(parent, partition);
                        if (error != B_OK)
                                return error;
                }

                // parameters
                if ((partition->Parameters() != NULL)
                        && ((changeFlags & B_PARTITION_CHANGED_PARAMETERS) != 0
                                || compare_string(partition->Parameters(),
                                        partitionData->parameters))) {
                        if (!parent)
                                return B_BAD_VALUE;

                        status_t error = _GenerateSetParametersJob(parent, partition);
                        if (error != B_OK)
                                return error;
                }
        }

        if (partition->ContentType()) {
                // initialize the partition, if required
                if (changeFlags & B_PARTITION_CHANGED_INITIALIZATION) {
                        status_t error = _GenerateInitializeJob(partition);
                        if (error != B_OK)
                                return error;
                } else {
                        // partition not (re-)initialized, set content properties

                        // content name
                        if ((changeFlags & B_PARTITION_CHANGED_NAME)
                                || compare_string(partition->RawContentName(),
                                        partitionData->content_name)) {
                                status_t error = _GenerateSetContentNameJob(partition);
                                if (error != B_OK)
                                        return error;
                        }

                        // content parameters
                        if ((partition->ContentParameters() != NULL)
                                && ((changeFlags & B_PARTITION_CHANGED_PARAMETERS) != 0
                                        || compare_string(partition->ContentParameters(),
                                                partitionData->content_parameters))) {
                                status_t error = _GenerateSetContentParametersJob(partition);
                                if (error != B_OK)
                                        return error;
                        }

                        // defragment
                        if (changeFlags & B_PARTITION_CHANGED_DEFRAGMENTATION) {
                                status_t error = _GenerateDefragmentJob(partition);
                                if (error != B_OK)
                                        return error;
                        }

                        // check / repair
                        bool repair = (changeFlags & B_PARTITION_CHANGED_REPAIR);
                        if ((changeFlags & B_PARTITION_CHANGED_CHECK)
                                || repair) {
                                status_t error = _GenerateRepairJob(partition, repair);
                                if (error != B_OK)
                                        return error;
                        }
                }
        }

        // recurse
        for (int32 i = 0; BPartition* child = partition->ChildAt(i); i++) {
                status_t error = _GenerateRemainingJobs(partition, child);
                if (error != B_OK)
                        return error;
        }

        return B_OK;
}


// _GetMutablePartition
BMutablePartition*
DiskDeviceJobGenerator::_GetMutablePartition(BPartition* partition)
{
        if (!partition)
                return NULL;

        return partition->fDelegate
                ? partition->fDelegate->MutablePartition() : NULL;
}


// _GenerateInitializeJob
status_t
DiskDeviceJobGenerator::_GenerateInitializeJob(BPartition* partition)
{
        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        InitializeJob* job = new(nothrow) InitializeJob(reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->ContentType(),
                partition->RawContentName(), partition->ContentParameters());
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateUninitializeJob
status_t
DiskDeviceJobGenerator::_GenerateUninitializeJob(BPartition* partition)
{
        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        BPartition* parent = partition->Parent();
        PartitionReference* parentReference = NULL;
        if (parent != NULL) {
                error = _GetPartitionReference(parent, parentReference);
                if (error != B_OK)
                        return error;
        }

        return _AddJob(new(nothrow) UninitializeJob(reference, parentReference));
}


// _GenerateSetContentNameJob
status_t
DiskDeviceJobGenerator::_GenerateSetContentNameJob(BPartition* partition)
{
        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        SetStringJob* job = new(nothrow) SetStringJob(reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->RawContentName(),
                B_DISK_DEVICE_JOB_SET_CONTENT_NAME);
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateSetContentParametersJob
status_t
DiskDeviceJobGenerator::_GenerateSetContentParametersJob(BPartition* partition)
{
        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        SetStringJob* job = new(nothrow) SetStringJob(reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->ContentParameters(),
                B_DISK_DEVICE_JOB_SET_CONTENT_PARAMETERS);
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateDefragmentJob
status_t
DiskDeviceJobGenerator::_GenerateDefragmentJob(BPartition* partition)
{
        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        return _AddJob(new(nothrow) DefragmentJob(reference));
}


// _GenerateRepairJob
status_t
DiskDeviceJobGenerator::_GenerateRepairJob(BPartition* partition, bool repair)
{
        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        return _AddJob(new(nothrow) RepairJob(reference, repair));
}


// _GenerateCreateChildJob
status_t
DiskDeviceJobGenerator::_GenerateCreateChildJob(BPartition* parent,
        BPartition* partition)
{
        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        CreateChildJob* job = new(nothrow) CreateChildJob(parentReference,
                reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->Offset(), partition->Size(), partition->Type(),
                partition->Name(), partition->Parameters());
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateDeleteChildJob
status_t
DiskDeviceJobGenerator::_GenerateDeleteChildJob(BPartition* parent,
        BPartition* partition)
{
        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        return _AddJob(new(nothrow) DeleteChildJob(parentReference, reference));
}


// _GenerateResizeJob
status_t
DiskDeviceJobGenerator::_GenerateResizeJob(BPartition* partition)
{
        BPartition* parent = partition->Parent();
        if (!parent)
                return B_BAD_VALUE;

        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        return _AddJob(new(nothrow) ResizeJob(parentReference, reference,
                partition->Size(), partition->ContentSize()));
}


// _GenerateMoveJob
status_t
DiskDeviceJobGenerator::_GenerateMoveJob(BPartition* partition)
{
        BPartition* parent = partition->Parent();
        if (!parent)
                return B_BAD_VALUE;

        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        // collect all descendants whose contents need to be moved
        fContentsToMoveCount = 0;
        error = _CollectContentsToMove(partition);
        if (error != B_OK)
                return B_OK;

        // create and init the job
        MoveJob* job = new(nothrow) MoveJob(parentReference, reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->Offset(), fContentsToMove,
                fContentsToMoveCount);
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateSetNameJob
status_t
DiskDeviceJobGenerator::_GenerateSetNameJob(BPartition* parent,
        BPartition* partition)
{
        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        SetStringJob* job = new(nothrow) SetStringJob(parentReference, reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->Name(), B_DISK_DEVICE_JOB_SET_NAME);
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateSetTypeJob
status_t
DiskDeviceJobGenerator::_GenerateSetTypeJob(BPartition* parent,
        BPartition* partition)
{
        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        SetStringJob* job = new(nothrow) SetStringJob(parentReference, reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->Type(), B_DISK_DEVICE_JOB_SET_TYPE);
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _GenerateSetParametersJob
status_t
DiskDeviceJobGenerator::_GenerateSetParametersJob(BPartition* parent,
        BPartition* partition)
{
        PartitionReference* parentReference;
        status_t error = _GetPartitionReference(parent, parentReference);
        if (error != B_OK)
                return error;

        PartitionReference* reference;
        error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        SetStringJob* job = new(nothrow) SetStringJob(parentReference, reference);
        if (!job)
                return B_NO_MEMORY;

        error = job->Init(partition->Parameters(),
                B_DISK_DEVICE_JOB_SET_PARAMETERS);
        if (error != B_OK) {
                delete job;
                return error;
        }

        return _AddJob(job);
}


// _CollectContentsToMove
status_t
DiskDeviceJobGenerator::_CollectContentsToMove(BPartition* partition)
{
        BMutablePartition* shadow = _GetMutablePartition(partition);
        if (shadow->Status() == B_PARTITION_UNRECOGNIZED)
                return B_ERROR;

        // if the partition has contents, push its ID
        if (shadow->ContentType()
                && !(shadow->ChangeFlags() & B_PARTITION_CHANGED_INITIALIZATION)) {
                status_t error = _PushContentsToMove(partition);
                if (error != B_OK)
                        return error;
        }

        // recurse
        for (int32 i = 0; BPartition* child = partition->ChildAt(i); i++) {
                status_t error = _CollectContentsToMove(child);
                if (error != B_OK)
                        return error;
        }
        return B_OK;
}


// _PushContentsToMove
status_t
DiskDeviceJobGenerator::_PushContentsToMove(BPartition* partition)
{
        if (fContentsToMoveCount >= fPartitionCount)
                return B_ERROR;

        PartitionReference* reference;
        status_t error = _GetPartitionReference(partition, reference);
        if (error != B_OK)
                return error;

        fContentsToMove[fContentsToMoveCount++] = reference;

        return B_OK;
}


// _GetPartitionReference
status_t
DiskDeviceJobGenerator::_GetPartitionReference(BPartition* partition,
        PartitionReference*& reference)
{
        if (!partition)
                return B_BAD_VALUE;

        for (int32 i = 0; i < fPartitionCount; i++) {
                PartitionRefInfo& info = fPartitionRefs[i];

                if (info.partition == partition) {
                        reference = info.reference;
                        return B_OK;
                }

                if (info.partition == NULL) {
                        // create partition reference
                        info.reference = new(nothrow) PartitionReference();
                        if (!info.reference)
                                return B_NO_MEMORY;

                        // set partition ID and change counter
                        user_partition_data* partitionData = partition->fPartitionData;
                        if (partitionData) {
                                info.reference->SetPartitionID(partitionData->id);
                                info.reference->SetChangeCounter(partitionData->change_counter);
                        }

                        info.partition = partition;
                        reference = info.reference;
                        return B_OK;
                }
        }

        // Out of slots -- that can't happen.
        return B_ERROR;
}


// _CompareMoveInfoOffset
int
DiskDeviceJobGenerator::_CompareMoveInfoPosition(const void* _a, const void* _b)
{
        const MoveInfo* a = static_cast<const MoveInfo*>(_a);
        const MoveInfo* b = static_cast<const MoveInfo*>(_b);
        if (a->position < b->position)
                return -1;
        if (a->position > b->position)
                return 1;
        return 0;
}