Leetcode 146 LRUCache-526互联

/*
 *
 * Copyright (C) 2023-08-18 13:51 zxinlog <zxinlog@126.com>
 *
 */

#include <func.h>
#define N 1000

// 普通Node
typedef struct Node {
    int key;
    int value;
    struct Node *prev;
    struct Node *next;
} Node;

// 定义 HashNode
typedef struct HashNode {
    int key;
    Node *node;
    struct HashNode *next;
} HashNode;

// 定义HashTable
typedef struct HashTable {
    HashNode *arr[N];
    int capacity;
} HashTable;

// 定义LRUCache
typedef struct {
    Node *head;
    Node *tail;
    int capacity;
    int size;
    HashTable *hash_table;
} LRUCache;

// function begin: --------------------------------------------
Node *initNode();
HashTable *initHashTable();
Node *findHashTable(HashTable *hash_table, int key);
LRUCache *lRUCacheCreate(int capacity);
Node *findHashTable(HashTable *hash_table, int key);
void removeHashTable(HashTable *hash_table, int key);
void insertHashTable(HashTable *hash_table, int key, Node *node);
int lRUCacheGet(LRUCache *obj, int key);
Node *removeHead(LRUCache *obj);
void addTail(LRUCache *obj, Node *node);
void lRUCachePut(LRUCache *obj, int key, int value);
void lRUCacheFree(LRUCache *obj);
// function end: --------------------------------------------

Node *initNode() {
    Node *node = (Node *) malloc(sizeof(Node));
    node->prev = NULL;
    node->next = NULL;
    return node;
}

HashTable *initHashTable() {
    HashTable *hash_table = (HashTable *) malloc(sizeof(HashTable));
    hash_table->capacity = N;
    for (int i = 0; i < N; i++) {
        hash_table->arr[i] = NULL;
    }
    return hash_table;
}

LRUCache *lRUCacheCreate(int capacity) {
    LRUCache *cache = (LRUCache *) malloc(sizeof(LRUCache));
    cache->head = initNode();
    cache->tail = initNode();
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;
    cache->capacity = capacity;
    cache->size = 0;
    cache->hash_table = initHashTable();
    return cache;
}

// HashTable 查找
Node *findHashTable(HashTable *hash_table, int key) {
    int index = key < 0 ? (key % hash_table->capacity) + (hash_table->capacity - 1) : (key % hash_table->capacity);
    HashNode *pnode = hash_table->arr[index];
    while (pnode != NULL) {
        if (pnode->key == key) {
            return pnode->node;
        }
        pnode = pnode->next;
    }
    return NULL;
}

void removeHashTable(HashTable *hash_table, int key) {
    int index = key < 0 ? (key % hash_table->capacity) + (hash_table->capacity - 1) : (key % hash_table->capacity);
    HashNode *p1 = NULL;
    HashNode *p2 = hash_table->arr[index];
    // NULL
    if (p2 == NULL) {
        return;
    }
    // p2 is the hash_node what will delete.
    else if (p2->key == key) {
        hash_table->arr[index] = p2->next;
        free(p2);
        return;
    }
    // p2 is not the hash_node to delete.
    //  双指针
    while (p2 != NULL && p2->key != key) {
        p1 = p2;
        p2 = p2->next;
    }
    if (p1 != NULL && p2 != NULL) {
        p1->next = p2->next;
        free(p2);
        return;
    }
}

void insertHashTable(HashTable *hash_table, int key, Node *node) {
    HashNode *hash_node = (HashNode *) malloc(sizeof(HashNode));
    hash_node->node = node;
    hash_node->key = key;
    int index = key < 0 ? (key % hash_table->capacity) + (hash_table->capacity - 1) : (key % hash_table->capacity);
    hash_node->next = hash_table->arr[index];
    hash_table->arr[index] = hash_node;
}
int lRUCacheGet(LRUCache *obj, int key) {
    Node *pnode = findHashTable(obj->hash_table, key);
    if (pnode == NULL) {
        return -1;
    } else {
        if (obj->head->next != obj->tail) {
            pnode->prev->next = pnode->next;
            pnode->next->prev = pnode->prev;
            addTail(obj, pnode);
        }
        return pnode->value;
    }
}

Node *removeHead(LRUCache *obj) {
    Node *node = obj->head->next;
    obj->head->next = node->next;
    node->next->prev = obj->head;
    return node;
}

void addTail(LRUCache *obj, Node *node) {
    node->next = obj->tail;
    node->prev = obj->tail->prev;
    obj->tail->prev->next = node;
    obj->tail->prev = node;
}

void lRUCachePut(LRUCache *obj, int key, int value) {
    Node *pnode = findHashTable(obj->hash_table, key);

    // 没有且容量没满
    if (pnode == NULL && obj->size < obj->capacity) {
        Node *node = (Node *) malloc(sizeof(Node));
        node->key = key;
        node->value = value;
        node->prev = NULL;
        node->next = NULL;
        addTail(obj, node);
        insertHashTable(obj->hash_table, node->key, node);
        ++obj->size;
    }
    // 没有且容量满了
    else if (pnode == NULL && obj->size == obj->capacity) {
        // printf("obj->size == obj->capacity\n");
        Node *node = removeHead(obj);
        removeHashTable(obj->hash_table, node->key);
        node->key = key;
        node->value = value;
        addTail(obj, node);
        insertHashTable(obj->hash_table, node->key, node);
    }
    // 有
    else if (pnode != NULL) {
        pnode->value = value;
        if (pnode == obj->head->prev) {
            return;
        } else {
            pnode->prev->next = pnode->next;
            pnode->next->prev = pnode->prev;
            addTail(obj, pnode);
        }
    }
}

void lRUCacheFree(LRUCache *obj) {
    Node *p1;
    Node *p2 = obj->head->next;
    while (p2 != obj->tail) {
        p1 = p2;
        removeHashTable(obj->hash_table, p2->key);
        p2 = p2->next;
        free(p1);
    }
    free(obj->head);
    free(obj->tail);
    free(obj->hash_table);
    free(obj);
}

void showCache(LRUCache *cache) {
    Node *p = cache->head->next;
    while (p != cache->tail) {
        printf("(%d,%d)  ", p->key, p->value);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LRUCache *cache = lRUCacheCreate(3);
    lRUCachePut(cache, 1, 2);
    lRUCachePut(cache, 2, 4);
    showCache(cache);
    lRUCacheFree(cache);
}