simple_lru.c

#include <stdio.h>
#include <stdlib.h>

struct page {
    int value;
    page *next;
};

int miss = 0;
int hit = 0;

void print_node(page *node){
    page *p = node;
    if(!p->next){
        return;
    }
    p = p->next;
    while(p) {
        printf("%d\t", p->value);
        p = p->next;
    }
    printf("\n");
}

int search_page(page *node, const int value){
    page *p = node;
    page *pre = node;
    if(!p->next){
        return 0;
    }
    p = p->next;
    while(p) {
        if(p->value == value) {
            /* replace */
            if(p->next!=NULL) {
                pre->next = p->next;
            } else {
                pre->next=NULL;
            }
            if(node->next!=p){
                p->next = node->next;
                node->next = p;
            }
            return 1;
        }
        pre = p;
        p = p->next;
    }
    return 0;
}

int put(page *node, const int value){
    int r = search_page(node, value);
    if(r==1){
        hit+=1;
        printf("hit value %d\n", value);
        return 1;
    }
    miss+=1;
    printf("miss value %d\n", value);
    page *p = (page*)malloc(sizeof(page));
    p->value = value;
    p->next = NULL;
    if(node->next==NULL){
        node->next = p;
    } else {
        p->next = node->next;
        node->next = p;
    }
    return 1;
}

page *init(const int value){
    /* init the first node */
    page *p = (page*)malloc(sizeof(page));
    p->value = value;
    p->next = NULL;
    return p;
}

int main(){
    page *node = init(-1);
    int total=22;
    int a[22] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2,
                 3, 7, 6, 3, 2, 1, 2, 3, 6, 6, 4};
    for(int i=0;i<total;i++){
        put(node, a[i]);
        print_node(node);
    }
    printf("total miss %d\n", miss);
    printf("total hit %d\n", hit);
    return 0;
}