美文网首页
go实现页面缓存算法FIFO

go实现页面缓存算法FIFO

作者: 小怪兽狂殴奥特曼 | 来源:发表于2019-04-26 12:20 被阅读0次
package main
/*
算法:页面cache算法之FIFO
特点:最先进入最先淘汰
实现:链表+hashmap,hashmap用来加速查找
插入/查找/删除:O(1)
*/

import (
    "container/list"
    "fmt"
    "errors"
)

type Element struct {
    key string
    value int32
}

type cache_fifo struct {
    len int
    equeue list.List
    kmap map[string] *list.Element
}

func (fifo *cache_fifo)init(len int) {
    fifo.len = len
    //fifo.equeue = list.New()
    fifo.kmap = make(map[string] *list.Element)
}

func (fifo *cache_fifo)get(k string) (int32, error) {
    e := fifo.kmap[k]
    if(e==nil) {
        return 0,errors.New("not found")
    }
    return e.Value.(Element).value,nil
}

func (fifo *cache_fifo)del(k string) (error) {
    e := fifo.kmap[k]
    if(e!=nil) {
        fifo.equeue.Remove(e)
    }
    return nil
}

func (fifo *cache_fifo)add(ne Element) {
    if(fifo.equeue.Len() >= fifo.len) {
        ef := fifo.equeue.Front()
        e :=ef.Value.(Element)
        delete(fifo.kmap, e.key)
        fifo.equeue.Remove(ef)
    }
    nep := fifo.equeue.PushBack(ne)
    fifo.kmap[ne.key] = nep
}

func (fifo *cache_fifo)print() {
    for e := fifo.equeue.Front(); e != nil; e = e.Next() {
        fmt.Printf("%s/%d", e.Value.(Element).key, e.Value.(Element).value)
        fmt.Print("->")
    }
    fmt.Println()
}

// test
func main() {
    var fifo cache_fifo 
    fifo.init(4)
    fifo.add(Element{"d",4})
    fifo.add(Element{"a",1})
    fifo.add(Element{"b",2})
    fifo.add(Element{"c",3})
    fifo.print()
    fifo.add(Element{"e",5})
    fifo.print()
}

相关文章

网友评论

      本文标题:go实现页面缓存算法FIFO

      本文链接:https://www.haomeiwen.com/subject/hyefnqtx.html