设计LRU缓存结构

题解 | [C语言]设计LRU缓存结构

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param operatorsRowLen int operators数组行数
 * @param operatorsColLen int* operators数组列数
 * @param k int整型 the k
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#define BUF_LEN 100000
static int lrubuf[BUF_LEN];
static int lrubufindex = 0;
static int returnbuf[BUF_LEN];
static int returnindex = 0;
static int keyindex = 0;
#define  min(x,y)   ((x)<=(y)?(x):(y))
void setval(int *buf, int key )
{
    int i = 0;
    int tempkey = 0;
    int keyval = min(key,keyindex);
    for(;i<keyval;i++)
    {
        if(*(buf+1) == lrubuf[2*i])
            break;
    }
    if(i != keyval)
    {
        memmove(&lrubuf[2*i],&lrubuf[2*(i+1)],(keyval - i - 1) * 8);
        lrubuf[2*keyval - 2] = *(buf +1);
        lrubuf[2*keyval -1] = *(buf + 2);
    }
    
    if(keyindex < key)
    {
        
    }
    else
    {
        memmove(lrubuf,&lrubuf[2],(key - 1) * 8);
        lrubufindex -= 2;
    }
    lrubuf[lrubufindex++] = *(buf + 1);
    lrubuf[lrubufindex++] = *(buf + 2);
    i++;
}
void getval(int *buf, int key)
{
    int i = 0;
    int res = -1;
    int temp[2];
    int keyval = min(key,keyindex);
    for(i = 0;i < keyval ; i ++)
    {
        if(lrubuf[2*i] == *(buf+1))
        {
            temp[0] = lrubuf[2*i];
            temp[1] = res = lrubuf[2*i + 1];
            
            memmove(&lrubuf[2*i],&lrubuf[2*(i+1)],(keyval - i - 1) * 8);
            lrubuf[2*keyval - 2] = temp[0];
            lrubuf[2*keyval -1] = temp[1];
            
            break;
        }
        else
            res = -1;
    }
    returnbuf[returnindex] = res;
    returnindex ++;
}

int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    // write code here
    for(int i = 0;i < operatorsRowLen; i ++)
    {
        if(** (operators + i) == 1)
        {
            setval(*(operators + i), k );
            keyindex ++;
        }
        else if(** (operators + i) == 2)
        {
            getval(*(operators + i), k);
        }
    }
    *returnSize = returnindex;
    return returnbuf;
}

//1.创建链表首尾节点，首尾节点不参与数据的存储，存储数据需要在首尾节点之间创建新的链表节点；
//2.降维数据的原始数据，读取每个数组的第一个元素opt，根据opt值选择Set or Get函数；
//3.Set函数处理以下两个问题：
//检测是否存在KEY，如果存在，移动节点至第一个有效链表节点；
//如果不存在KEY，判断缓存器的有效个数是否达到最大值K，如果达到最大值K，需要删除最后一个节点；然后再创建新的节点，插入第一个有效节点处；
//4.Get函数，检测是否存在KEY，如果存在，返回对应的value，移动至第一个有效节点处，否则返回-1；

	

struct Lru_node
{
    int key;
    int value;
    struct Lru_node* prev;
    struct Lru_node* next;
};

static int Len_K = 0;
static int ListnodeLen = 0;
static struct Lru_node* Head = NULL;
static struct Lru_node* Tail = NULL;

void Initial_Node(void)//初始化，创建首尾节点，该首尾节点不参与存储缓存器数据
{
    Head = (struct Lru_node*)malloc(sizeof(struct Lru_node));
    Head->key = 0;
    Head->value = 0;
    Head->prev = NULL;
    Head->next = NULL;

    Tail = (struct Lru_node*)malloc(sizeof(struct Lru_node));
    Tail->key = 0;
    Tail->value = 0;
    Tail->prev = NULL;
    Tail->next = NULL;

    Head->next = Tail;
    Tail->prev = Head;
}

void Delete_End()//删除最后一个节点
{
    struct Lru_node*Delete_Temp = NULL;
    Delete_Temp = Tail->prev;
    Tail->prev->prev->next = Tail;
    Tail->prev = Tail->prev->prev;

    free(Delete_Temp);

    ListnodeLen--;
}

void Insert_Head(int key, int value)//创建新的节点，并将该节点添加至缓存器的第一个有效节点位置
{
    struct Lru_node*NewNode = NULL;

    if(ListnodeLen == Len_K) //检查缓存器的当前节点数量是否达到设定的最大值K
    {
        Delete_End();//如果节点数达到最大值K，则需要删除最后一个节点
    }

    NewNode = (struct Lru_node*)malloc(sizeof(struct Lru_node));//创建新的节点
    NewNode->key = key;
    NewNode->value = value;

    NewNode->prev = Head;
    NewNode->next = Head->next;
    Head->next->prev = NewNode;
    Head->next = NewNode;
    //Head = NewNode;

    ListnodeLen++;
}

void Move_Head(struct Lru_node*Move_node)//移动当前节点至缓存器第一个有效节点
{
    Move_node->prev->next = Move_node->next;
    Move_node->next->prev = Move_node->prev;

    Move_node->prev = Head;
    Move_node->next = Head->next;
    Head->next->prev = Move_node;
    Head->next = Move_node;
    //Head = Move_node;
}

void Set(int key, int value) //Set函数，如果KEY存在，刷新该节点至缓存器的第一个单元，否则增加新的节点至第一个有效存储单元位置
{
    struct Lru_node* Set_temp = NULL;
    Set_temp = Head->next;  //缓存器第一个存储单元
    while(Set_temp->next != NULL)//查询缓存器元素KEY
    {
        if(Set_temp->key == key)
        {
            Move_Head(Set_temp);//KEY存在，刷新该节点至缓存器的第一个单元
            break;
        }
        Set_temp = Set_temp->next;
    }
    if(Set_temp->next == NULL)
    {
        Insert_Head(key,value);//KEY不存在，创建新的节点至缓存器的第一个单元
    }

}

int Get(int key)  //Get函数实现，判断缓存器是否存在KEY，如果有返回value，否则返回-1
{
    struct Lru_node* Get_temp = NULL;
    Get_temp = Head->next; //缓存器第一个存储单元
    int returnVlaue =0;
    while(Get_temp->next != NULL)  //查询缓存器元素KEY
    {
        if (Get_temp->key == key)
        {
            Move_Head(Get_temp);  //查找到Key后，刷新至缓存器第一个有效存储单元
            returnVlaue = Get_temp->value; //返回对应的value值
            break;
        }
        Get_temp = Get_temp->next;
    }

    if(Get_temp->next == NULL)
    {
        returnVlaue = -1; //未查找到Key后，返回-1
    }

    return returnVlaue;
}

int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    // write code here
    int*ope_arry = NULL;  //读取数组数据
    int*return_arry = NULL; //当OPT=2时，返回数据春初数组
    *returnSize = 0;   //返回数据数组元素个数
    Len_K = k;   //全局变量，春初当前缓存器中的有效数据个数

    Initial_Node();  //初始化函数，生成链表的头节点以及尾节点

    for(int i=0;i < operatorsRowLen; i++) //降维读物输入数组
    {
        ope_arry = operators[i];
        if(ope_arry[0]==1)  //判断OPT = 1 
        {
            Set(ope_arry[1],ope_arry[2]);    //执行Set函数
        }
        else if(ope_arry[0]==2)  //判断OPT = 2
        {
            *returnSize = *returnSize +1;  //返回数据数组元素个数增加1
            return_arry = (int *)realloc(return_arry, (*returnSize) * sizeof(int));//刷新数组内存空间
            return_arry[*returnSize-1] = Get(ope_arry[1]);//执行Get函数，并将返回值存入返回值数组
        }
    }
    return return_arry;
}