进程处理题目

提示：文章

前言

前期疑问：
本文目标：

三、解题

第一版

第一版的代码就没有战体我上来，第一版代码正常写的时候，到query查询阶段发现了不对劲。考虑了一下，需要在程序中维护一个hash表，才能从1000个数组中快速找到deviceId对应的数据

第二版代码如下：

#include <stdbool.h>
#include <stdio.h>
#include <malloc.h>
#include "securec.h"

#define PROCESS_GROUP_COUNT    3

typedef struct {
    int deviceId;
    int memSize;
    int procId;
} DeviceInfo;

typedef struct {
    bool status;
    int index;
} HashTable;

typedef struct {
    DeviceInfo deviceInfo[1000];
    int deviceMenSize;
    HashTable hashTable[1000];
    int hashCount;
} ProcessInfo;

typedef struct{
    ProcessInfo* processInfo;
    int processCount;
} DeviceGroup;

typedef struct {
    DeviceGroup deviceGroup[3];
} DeviceMgtSystem;

// 注意：该函数为类构造函数，返回的对象指针将作为其他待实现函数的入参；框架代码在调用该函数后，会输出 null（而非指针）
static DeviceMgtSystem *DeviceMgtSystemCreate(int procNum, int maxMemSize)
{
    DeviceMgtSystem* deviceMgtSystem = (DeviceMgtSystem*)malloc(sizeof(DeviceMgtSystem));
    for(int i = 0; i < PROCESS_GROUP_COUNT; i++) {
        deviceMgtSystem->deviceGroup[i].processInfo = (ProcessInfo*)malloc(sizeof(ProcessInfo) * procNum);
        for(int j = 0; j < procNum; j++)
        {
            memset_s(deviceMgtSystem->deviceGroup[i].processInfo[j].deviceInfo, sizeof(deviceMgtSystem->deviceGroup[i].processInfo[j].deviceInfo) , 0, sizeof(deviceMgtSystem->deviceGroup[i].processInfo[j].deviceInfo));
            memset_s(deviceMgtSystem->deviceGroup[i].processInfo[j].hashTable, sizeof(deviceMgtSystem->deviceGroup[i].processInfo[j].hashTable) , 0, sizeof(deviceMgtSystem->deviceGroup[i].processInfo[j].hashTable));
            deviceMgtSystem->deviceGroup[i].processInfo[j].hashCount = 0;
        }
    }

    for(int i = 0; i < PROCESS_GROUP_COUNT; i++)
    {
        deviceMgtSystem->deviceGroup[i].processCount = procNum;
        for(int j = 0; j < deviceMgtSystem->deviceGroup[i].processCount; j++)
        {
            for(int k = 0;  k < 1000; k++)
            {
                deviceMgtSystem->deviceGroup[i].processInfo[j].deviceMenSize = maxMemSize;
            }
        }
    }

    return deviceMgtSystem;
}

static int GetProcessIdByIdelMem(DeviceMgtSystem *sys, int deviceId, int deviceType)
{
    int memSize = 0;
    int index = 0;
    for(int i = 0; i < sys->deviceGroup[deviceType - 1].processCount; i++)
    {
        int deviceLastIndex = 0;
        if(sys->deviceGroup[deviceType - 1].processInfo[i].hashCount == 0)
        {
            deviceLastIndex = 0;
        }
        else if(sys->deviceGroup[deviceType - 1].processInfo[i].hashTable[sys->deviceGroup[deviceType - 1].processInfo[i].hashCount - 1].status == true)
        {
            deviceLastIndex = sys->deviceGroup[deviceType - 1].processInfo[i].hashTable[sys->deviceGroup[deviceType - 1].processInfo[i].hashCount - 1].index;
        }
        if(sys->deviceGroup[deviceType - 1].processInfo[i].deviceMenSize > memSize)
        {
            memSize = sys->deviceGroup[deviceType - 1].processInfo[i].deviceMenSize;
            index = i;
        }
    }

    return index;
}

static int DeviceMgtSystemCreateDevice(DeviceMgtSystem *sys, int deviceId, int deviceType, int memSize)
{
    int processIndex = GetProcessIdByIdelMem(sys, deviceId, deviceType);
    if(sys->deviceGroup[deviceType - 1].processInfo[processIndex].deviceMenSize >= memSize)
    {
        sys->deviceGroup[deviceType - 1].processInfo[processIndex].deviceMenSize -= memSize;
        sys->deviceGroup[deviceType - 1].processInfo[processIndex].deviceInfo[deviceId].memSize = memSize;
        sys->deviceGroup[deviceType - 1].processInfo[processIndex].deviceInfo[deviceId].deviceId = deviceId;
        sys->deviceGroup[deviceType - 1].processInfo[processIndex].deviceInfo[deviceId].procId = processIndex;

        sys->deviceGroup[deviceType - 1].processInfo[processIndex].hashTable[sys->deviceGroup[deviceType - 1].processInfo[processIndex].hashCount].status = true;
        sys->deviceGroup[deviceType - 1].processInfo[processIndex].hashTable[sys->deviceGroup[deviceType - 1].processInfo[processIndex].hashCount].index = deviceId;

        sys->deviceGroup[deviceType - 1].processInfo[processIndex].hashCount += 1;
        return processIndex;
    }
    return -1;
}

static bool DeviceMgtSystemDeleteDevice(DeviceMgtSystem *sys, int deviceId)
{
    for(int i = 0; i < PROCESS_GROUP_COUNT; i++)
    {
        for(int j = 0; j < sys->deviceGroup[i].processCount; j++)
        {
            for(int k = 0; k < sys->deviceGroup[i].processInfo[j].hashCount; k++)
            {
                if(sys->deviceGroup[i].processInfo[j].hashTable[k].status == true)
                {
                    if(sys->deviceGroup[i].processInfo[j].hashTable[k].index == deviceId)
                    {
                        sys->deviceGroup[i].processInfo[j].hashTable[k].status = false;
                        sys->deviceGroup[i].processInfo[j].deviceMenSize += sys->deviceGroup[i].processInfo[j].deviceInfo[sys->deviceGroup[i].processInfo[j].hashTable[k].index].memSize;
                        sys->deviceGroup[i].processInfo[j].hashCount--;
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

// int diff = ((DeviceInfo*) a)->memSize - ((DeviceInfo*) b)->memSize;
// 从小到大排序
static int compare(const void* a, const void* b)
{
    int diff = ((DeviceInfo*) b)->memSize - ((DeviceInfo*) a)->memSize;
    if(diff == 0)
    {
        diff = ((DeviceInfo*) a)->procId - ((DeviceInfo*) b)->procId;
    }
    return diff;
}

// 注意：返回的数组必须在函数内调用malloc进行内存分配，由框架代码调用free进行内存释放。
// 同时，所返回的数组长度必须保存在 *returnSize 中。
static DeviceInfo *DeviceMgtSystemQueryDevice(DeviceMgtSystem *sys, int deviceType, size_t *returnSize)
{
    int deviceCount = 0;
    DeviceInfo* deviceInfo = (DeviceInfo*)malloc(sizeof(DeviceInfo) * 1000);
    for(int j = 0; j < sys->deviceGroup[deviceType - 1].processCount; j++)
    {
        int counter = 0;
        for(int k = 0; k < sys->deviceGroup[deviceType - 1].processInfo[j].hashCount; k++)
        {

            if(sys->deviceGroup[deviceType - 1].processInfo[j].hashTable[k].status == true)
            {
                counter++;
                int hashIndex = sys->deviceGroup[deviceType - 1].processInfo[j].hashTable[k].index;
                deviceInfo[deviceCount] = sys->deviceGroup[deviceType - 1].processInfo[j].deviceInfo[hashIndex];
                deviceCount++;
            }
            if(sys->deviceGroup[deviceType - 1].processInfo[j].hashCount == counter)
            {
                break;
            }
        }
    }


//    for(int i = 0; i < 3; i++)
//    {
//        printf("procId:%d deviceId:%d memSize:%d\n", deviceInfo[i].procId, deviceInfo[i].deviceId, deviceInfo[i].memSize);
//    }
    qsort(deviceInfo, deviceCount, sizeof(DeviceInfo), compare);
    *returnSize = deviceCount;

    return deviceInfo;
}

static void DeviceMgtSystemFree(DeviceMgtSystem *sys)
{

}

上述代码执行下面的用例会异常

null
0
1
1
[]
[[18, 50, 0], [3, 30, 1], [12, 20, 1]]
0
0
-1
true
0
[[15, 40, 0]]
[[26, 70, 0], [3, 30, 1], [12, 20, 1]]			// 这边不符合预期

总结

未完待续