fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAX_LEN 100
  6. #define CACHE_CAPACITY 3
  7. #define HASH_SIZE 1024
  8.  
  9. // Node cho doubly linked list và hash table
  10. typedef struct Node {
  11.     int key;
  12.     char value[MAX_LEN];
  13.     int freq;
  14.     struct Node *prev, *next;
  15.     struct Node *hnext; // next trong hash chain
  16. } Node;
  17.  
  18. // Hash map đơn giản
  19. Node* hashmap[HASH_SIZE];
  20.  
  21. // Hàm băm đơn giản
  22. int hash(int key) {
  23.     return key % HASH_SIZE;
  24. }
  25.  
  26. Node* hash_get(int key) {
  27.     int idx = hash(key);
  28.     Node* cur = hashmap[idx];
  29.     while (cur) {
  30.         if (cur->key == key) return cur;
  31.         cur = cur->hnext;
  32.     }
  33.     return NULL;
  34. }
  35.  
  36. void hash_put(Node* node) {
  37.     int idx = hash(node->key);
  38.     node->hnext = hashmap[idx];
  39.     hashmap[idx] = node;
  40. }
  41.  
  42. void hash_remove(int key) {
  43.     int idx = hash(key);
  44.     Node *cur = hashmap[idx], *prev = NULL;
  45.     while (cur) {
  46.         if (cur->key == key) {
  47.             if (prev) prev->hnext = cur->hnext;
  48.             else hashmap[idx] = cur->hnext;
  49.             return;
  50.         }
  51.         prev = cur;
  52.         cur = cur->hnext;
  53.     }
  54. }
  55.  
  56. // ==== LRU ====
  57. Node *lru_head = NULL, *lru_tail = NULL;
  58. int lru_size = 0;
  59.  
  60. void lru_move_to_front(Node* node) {
  61.     if (node == lru_head) return;
  62.     if (node->prev) node->prev->next = node->next;
  63.     if (node->next) node->next->prev = node->prev;
  64.     if (node == lru_tail) lru_tail = node->prev;
  65.     node->prev = NULL;
  66.     node->next = lru_head;
  67.     if (lru_head) lru_head->prev = node;
  68.     lru_head = node;
  69.     if (!lru_tail) lru_tail = lru_head;
  70. }
  71.  
  72. void lru_remove_tail() {
  73.     if (!lru_tail) return;
  74.     Node* temp = lru_tail;
  75.     if (lru_tail->prev) lru_tail->prev->next = NULL;
  76.     lru_tail = lru_tail->prev;
  77.     if (!lru_tail) lru_head = NULL;
  78.     hash_remove(temp->key);
  79.     free(temp);
  80.     lru_size--;
  81. }
  82.  
  83. void lru_put(int key, const char* value) {
  84.     Node* node = hash_get(key);
  85.     if (node) {
  86.         strncpy(node->value, value, MAX_LEN);
  87.         lru_move_to_front(node);
  88.         return;
  89.     }
  90.     if (lru_size == CACHE_CAPACITY) lru_remove_tail();
  91.     Node* new_node = (Node*)malloc(sizeof(Node));
  92.     new_node->key = key;
  93.     strncpy(new_node->value, value, MAX_LEN);
  94.     new_node->prev = new_node->next = new_node->hnext = NULL;
  95.     new_node->freq = 1;
  96.     new_node->next = lru_head;
  97.     if (lru_head) lru_head->prev = new_node;
  98.     lru_head = new_node;
  99.     if (!lru_tail) lru_tail = lru_head;
  100.     hash_put(new_node);
  101.     lru_size++;
  102. }
  103.  
  104. char* lru_get(int key) {
  105.     Node* node = hash_get(key);
  106.     if (!node) return NULL;
  107.     node->freq++;
  108.     lru_move_to_front(node);
  109.     return node->value;
  110. }
  111.  
  112. void print_lru_cache() {
  113.     Node* cur = lru_head;
  114.     printf("LRU Cache: ");
  115.     while (cur) {
  116.         printf("(%d:%s) ", cur->key, cur->value);
  117.         cur = cur->next;
  118.     }
  119.     printf("\n");
  120. }
  121.  
  122. // ==== MRU ====
  123. Node *mru_head = NULL, *mru_tail = NULL;
  124. int mru_size = 0;
  125.  
  126. void mru_remove_head() {
  127.     if (!mru_head) return;
  128.     Node* temp = mru_head;
  129.     if (mru_head->next) mru_head->next->prev = NULL;
  130.     mru_head = mru_head->next;
  131.     if (!mru_head) mru_tail = NULL;
  132.     hash_remove(temp->key);
  133.     free(temp);
  134.     mru_size--;
  135. }
  136.  
  137. void mru_put(int key, const char* value) {
  138.     Node* node = hash_get(key);
  139.     if (node) {
  140.         strncpy(node->value, value, MAX_LEN);
  141.         return;
  142.     }
  143.     if (mru_size == CACHE_CAPACITY) mru_remove_head();
  144.     Node* new_node = (Node*)malloc(sizeof(Node));
  145.     new_node->key = key;
  146.     strncpy(new_node->value, value, MAX_LEN);
  147.     new_node->prev = mru_tail;
  148.     new_node->next = NULL;
  149.     new_node->hnext = NULL;
  150.     new_node->freq = 1;
  151.     if (mru_tail) mru_tail->next = new_node;
  152.     mru_tail = new_node;
  153.     if (!mru_head) mru_head = new_node;
  154.     hash_put(new_node);
  155.     mru_size++;
  156. }
  157.  
  158. void print_mru_cache() {
  159.     Node* cur = mru_head;
  160.     printf("MRU Cache: ");
  161.     while (cur) {
  162.         printf("(%d:%s) ", cur->key, cur->value);
  163.         cur = cur->next;
  164.     }
  165.     printf("\n");
  166. }
  167.  
  168. // ==== MFU ====
  169. Node* mfu_list = NULL;
  170. int mfu_size = 0;
  171.  
  172. void mfu_remove_most_frequent() {
  173.     Node *prev = NULL, *cur = mfu_list, *target = NULL, *target_prev = NULL;
  174.     int max_freq = -1;
  175.     while (cur) {
  176.         if (cur->freq > max_freq) {
  177.             max_freq = cur->freq;
  178.             target = cur;
  179.             target_prev = prev;
  180.         }
  181.         prev = cur;
  182.         cur = cur->next;
  183.     }
  184.     if (!target) return;
  185.     if (target_prev) target_prev->next = target->next;
  186.     else mfu_list = target->next;
  187.     hash_remove(target->key);
  188.     free(target);
  189.     mfu_size--;
  190. }
  191.  
  192. void mfu_put(int key, const char* value) {
  193.     Node* node = hash_get(key);
  194.     if (node) {
  195.         strncpy(node->value, value, MAX_LEN);
  196.         node->freq++;
  197.         return;
  198.     }
  199.     if (mfu_size == CACHE_CAPACITY) mfu_remove_most_frequent();
  200.     Node* new_node = (Node*)malloc(sizeof(Node));
  201.     new_node->key = key;
  202.     strncpy(new_node->value, value, MAX_LEN);
  203.     new_node->prev = new_node->next = NULL;
  204.     new_node->hnext = NULL;
  205.     new_node->freq = 1;
  206.     new_node->next = mfu_list;
  207.     mfu_list = new_node;
  208.     hash_put(new_node);
  209.     mfu_size++;
  210. }
  211.  
  212. void print_mfu_cache() {
  213.     Node* cur = mfu_list;
  214.     printf("MFU Cache: ");
  215.     while (cur) {
  216.         printf("(%d:%s|f%d) ", cur->key, cur->value, cur->freq);
  217.         cur = cur->next;
  218.     }
  219.     printf("\n");
  220. }
  221.  
  222. int main() {
  223.     printf("=== LRU Cache Test ===\n");
  224.     lru_put(1, "A"); lru_put(2, "B"); lru_put(3, "C");
  225.     print_lru_cache();
  226.     lru_get(2); print_lru_cache();
  227.     lru_put(4, "D"); print_lru_cache();
  228.  
  229.     memset(hashmap, 0, sizeof(hashmap));
  230.     printf("\n=== MRU Cache Test ===\n");
  231.     mru_put(1, "A"); mru_put(2, "B"); mru_put(3, "C");
  232.     print_mru_cache();
  233.     mru_put(4, "D"); print_mru_cache();
  234.  
  235.     memset(hashmap, 0, sizeof(hashmap));
  236.     printf("\n=== MFU Cache Test ===\n");
  237.     mfu_put(1, "A"); mfu_put(2, "B"); mfu_put(3, "C");
  238.     print_mfu_cache();
  239.     mfu_put(2, "B"); mfu_put(4, "D");
  240.     print_mfu_cache();
  241.  
  242.     return 0;
  243. }
  244.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== LRU Cache Test ===
LRU Cache: (3:C) (2:B) (1:A) 
LRU Cache: (2:B) (3:C) (1:A) 
LRU Cache: (4:D) (2:B) (3:C) 

=== MRU Cache Test ===
MRU Cache: (1:A) (2:B) (3:C) 
MRU Cache: (2:B) (3:C) (4:D) 

=== MFU Cache Test ===
MFU Cache: (3:C|f1) (2:B|f1) (1:A|f1) 
MFU Cache: (4:D|f1) (3:C|f1) (1:A|f1)
https://ideone.com/SLmSnt
language:
C (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!