diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache')
4 files changed, 961 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache.go new file mode 100644 index 000000000..9b6a74977 --- /dev/null +++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache.go @@ -0,0 +1,125 @@ +// Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com> +// All rights reserved. +// +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Package cache provides interface and implementation of a cache algorithms. +package cache + +import ( + "sync/atomic" +) + +// SetFunc used by Namespace.Get method to create a cache object. SetFunc +// may return ok false, in that case the cache object will not be created. +type SetFunc func() (ok bool, value interface{}, charge int, fin SetFin) + +// SetFin will be called when corresponding cache object are released. +type SetFin func() + +// DelFin will be called when corresponding cache object are released. +// DelFin will be called after SetFin. The exist is true if the corresponding +// cache object is actually exist in the cache tree. +type DelFin func(exist bool) + +// PurgeFin will be called when corresponding cache object are released. +// PurgeFin will be called after SetFin. If PurgeFin present DelFin will +// not be executed but passed to the PurgeFin, it is up to the caller +// to call it or not. +type PurgeFin func(ns, key uint64, delfin DelFin) + +// Cache is a cache tree. +type Cache interface { + // SetCapacity sets cache capacity. + SetCapacity(capacity int) + + // GetNamespace gets or creates a cache namespace for the given id. + GetNamespace(id uint64) Namespace + + // Purge purges all cache namespaces, read Namespace.Purge method documentation. + Purge(fin PurgeFin) + + // Zap zaps all cache namespaces, read Namespace.Zap method documentation. + Zap(closed bool) +} + +// Namespace is a cache namespace. +type Namespace interface { + // Get gets cache object for the given key. The given SetFunc (if not nil) will + // be called if the given key does not exist. + // If the given key does not exist, SetFunc is nil or SetFunc return ok false, Get + // will return ok false. + Get(key uint64, setf SetFunc) (obj Object, ok bool) + + // Get deletes cache object for the given key. If exist the cache object will + // be deleted later when all of its handles have been released (i.e. no one use + // it anymore) and the given DelFin (if not nil) will finally be executed. If + // such cache object does not exist the given DelFin will be executed anyway. + // + // Delete returns true if such cache object exist. + Delete(key uint64, fin DelFin) bool + + // Purge deletes all cache objects, read Delete method documentation. + Purge(fin PurgeFin) + + // Zap detaches the namespace from the cache tree and delete all its cache + // objects. The cache objects deletion and finalizers execution are happen + // immediately, even if its existing handles haven't yet been released. + // A zapped namespace can't never be filled again. + // If closed is false then the Get function will always call the given SetFunc + // if it is not nil, but resultant of the SetFunc will not be cached. + Zap(closed bool) +} + +// Object is a cache object. +type Object interface { + // Release releases the cache object. Other methods should not be called + // after the cache object has been released. + Release() + + // Value returns value of the cache object. + Value() interface{} +} + +// Namespace state. +type nsState int + +const ( + nsEffective nsState = iota + nsZapped + nsClosed +) + +// Node state. +type nodeState int + +const ( + nodeEffective nodeState = iota + nodeEvicted + nodeRemoved +) + +// Fake object. +type fakeObject struct { + value interface{} + fin func() + once uint32 +} + +func (o *fakeObject) Value() interface{} { + if atomic.LoadUint32(&o.once) == 0 { + return o.value + } + return nil +} + +func (o *fakeObject) Release() { + if !atomic.CompareAndSwapUint32(&o.once, 0, 1) { + return + } + if o.fin != nil { + o.fin() + o.fin = nil + } +} diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go new file mode 100644 index 000000000..07a9939b2 --- /dev/null +++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/cache_test.go @@ -0,0 +1,236 @@ +// Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com> +// All rights reserved. +// +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +package cache + +import ( + "math/rand" + "testing" +) + +func set(ns Namespace, key uint64, value interface{}, charge int, fin func()) Object { + obj, _ := ns.Get(key, func() (bool, interface{}, int, SetFin) { + return true, value, charge, fin + }) + return obj +} + +func TestCache_HitMiss(t *testing.T) { + cases := []struct { + key uint64 + value string + }{ + {1, "vvvvvvvvv"}, + {100, "v1"}, + {0, "v2"}, + {12346, "v3"}, + {777, "v4"}, + {999, "v5"}, + {7654, "v6"}, + {2, "v7"}, + {3, "v8"}, + {9, "v9"}, + } + + setfin := 0 + c := NewLRUCache(1000) + ns := c.GetNamespace(0) + for i, x := range cases { + set(ns, x.key, x.value, len(x.value), func() { + setfin++ + }).Release() + for j, y := range cases { + r, ok := ns.Get(y.key, nil) + if j <= i { + // should hit + if !ok { + t.Errorf("case '%d' iteration '%d' is miss", i, j) + } else if r.Value().(string) != y.value { + t.Errorf("case '%d' iteration '%d' has invalid value got '%s', want '%s'", i, j, r.Value().(string), y.value) + } + } else { + // should miss + if ok { + t.Errorf("case '%d' iteration '%d' is hit , value '%s'", i, j, r.Value().(string)) + } + } + if ok { + r.Release() + } + } + } + + for i, x := range cases { + finalizerOk := false + ns.Delete(x.key, func(exist bool) { + finalizerOk = true + }) + + if !finalizerOk { + t.Errorf("case %d delete finalizer not executed", i) + } + + for j, y := range cases { + r, ok := ns.Get(y.key, nil) + if j > i { + // should hit + if !ok { + t.Errorf("case '%d' iteration '%d' is miss", i, j) + } else if r.Value().(string) != y.value { + t.Errorf("case '%d' iteration '%d' has invalid value got '%s', want '%s'", i, j, r.Value().(string), y.value) + } + } else { + // should miss + if ok { + t.Errorf("case '%d' iteration '%d' is hit, value '%s'", i, j, r.Value().(string)) + } + } + if ok { + r.Release() + } + } + } + + if setfin != len(cases) { + t.Errorf("some set finalizer may not be executed, want=%d got=%d", len(cases), setfin) + } +} + +func TestLRUCache_Eviction(t *testing.T) { + c := NewLRUCache(12) + ns := c.GetNamespace(0) + o1 := set(ns, 1, 1, 1, nil) + set(ns, 2, 2, 1, nil).Release() + set(ns, 3, 3, 1, nil).Release() + set(ns, 4, 4, 1, nil).Release() + set(ns, 5, 5, 1, nil).Release() + if r, ok := ns.Get(2, nil); ok { // 1,3,4,5,2 + r.Release() + } + set(ns, 9, 9, 10, nil).Release() // 5,2,9 + + for _, x := range []uint64{9, 2, 5, 1} { + r, ok := ns.Get(x, nil) + if !ok { + t.Errorf("miss for key '%d'", x) + } else { + if r.Value().(int) != int(x) { + t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int)) + } + r.Release() + } + } + o1.Release() + for _, x := range []uint64{1, 2, 5} { + r, ok := ns.Get(x, nil) + if !ok { + t.Errorf("miss for key '%d'", x) + } else { + if r.Value().(int) != int(x) { + t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int)) + } + r.Release() + } + } + for _, x := range []uint64{3, 4, 9} { + r, ok := ns.Get(x, nil) + if ok { + t.Errorf("hit for key '%d'", x) + if r.Value().(int) != int(x) { + t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int)) + } + r.Release() + } + } +} + +func TestLRUCache_SetGet(t *testing.T) { + c := NewLRUCache(13) + ns := c.GetNamespace(0) + for i := 0; i < 200; i++ { + n := uint64(rand.Intn(99999) % 20) + set(ns, n, n, 1, nil).Release() + if p, ok := ns.Get(n, nil); ok { + if p.Value() == nil { + t.Errorf("key '%d' contains nil value", n) + } else { + got := p.Value().(uint64) + if got != n { + t.Errorf("invalid value for key '%d' want '%d', got '%d'", n, n, got) + } + } + p.Release() + } else { + t.Errorf("key '%d' doesn't exist", n) + } + } +} + +func TestLRUCache_Purge(t *testing.T) { + c := NewLRUCache(3) + ns1 := c.GetNamespace(0) + o1 := set(ns1, 1, 1, 1, nil) + o2 := set(ns1, 2, 2, 1, nil) + ns1.Purge(nil) + set(ns1, 3, 3, 1, nil).Release() + for _, x := range []uint64{1, 2, 3} { + r, ok := ns1.Get(x, nil) + if !ok { + t.Errorf("miss for key '%d'", x) + } else { + if r.Value().(int) != int(x) { + t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int)) + } + r.Release() + } + } + o1.Release() + o2.Release() + for _, x := range []uint64{1, 2} { + r, ok := ns1.Get(x, nil) + if ok { + t.Errorf("hit for key '%d'", x) + if r.Value().(int) != int(x) { + t.Errorf("invalid value for key '%d' want '%d', got '%d'", x, x, r.Value().(int)) + } + r.Release() + } + } +} + +func BenchmarkLRUCache_SetRelease(b *testing.B) { + capacity := b.N / 100 + if capacity <= 0 { + capacity = 10 + } + c := NewLRUCache(capacity) + ns := c.GetNamespace(0) + b.ResetTimer() + for i := uint64(0); i < uint64(b.N); i++ { + set(ns, i, nil, 1, nil).Release() + } +} + +func BenchmarkLRUCache_SetReleaseTwice(b *testing.B) { + capacity := b.N / 100 + if capacity <= 0 { + capacity = 10 + } + c := NewLRUCache(capacity) + ns := c.GetNamespace(0) + b.ResetTimer() + + na := b.N / 2 + nb := b.N - na + + for i := uint64(0); i < uint64(na); i++ { + set(ns, i, nil, 1, nil).Release() + } + + for i := uint64(0); i < uint64(nb); i++ { + set(ns, i, nil, 1, nil).Release() + } +} diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/empty_cache.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/empty_cache.go new file mode 100644 index 000000000..1fbf81459 --- /dev/null +++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/empty_cache.go @@ -0,0 +1,246 @@ +// Copyright (c) 2013, Suryandaru Triandana <syndtr@gmail.com> +// All rights reserved. +// +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +package cache + +import ( + "sync" + "sync/atomic" +) + +type emptyCache struct { + sync.Mutex + table map[uint64]*emptyNS +} + +// NewEmptyCache creates a new initialized empty cache. +func NewEmptyCache() Cache { + return &emptyCache{ + table: make(map[uint64]*emptyNS), + } +} + +func (c *emptyCache) GetNamespace(id uint64) Namespace { + c.Lock() + defer c.Unlock() + + if ns, ok := c.table[id]; ok { + return ns + } + + ns := &emptyNS{ + cache: c, + id: id, + table: make(map[uint64]*emptyNode), + } + c.table[id] = ns + return ns +} + +func (c *emptyCache) Purge(fin PurgeFin) { + c.Lock() + for _, ns := range c.table { + ns.purgeNB(fin) + } + c.Unlock() +} + +func (c *emptyCache) Zap(closed bool) { + c.Lock() + for _, ns := range c.table { + ns.zapNB(closed) + } + c.table = make(map[uint64]*emptyNS) + c.Unlock() +} + +func (*emptyCache) SetCapacity(capacity int) {} + +type emptyNS struct { + cache *emptyCache + id uint64 + table map[uint64]*emptyNode + state nsState +} + +func (ns *emptyNS) Get(key uint64, setf SetFunc) (o Object, ok bool) { + ns.cache.Lock() + + switch ns.state { + case nsZapped: + ns.cache.Unlock() + if setf == nil { + return + } + + var value interface{} + var fin func() + ok, value, _, fin = setf() + if ok { + o = &fakeObject{ + value: value, + fin: fin, + } + } + return + case nsClosed: + ns.cache.Unlock() + return + } + + n, ok := ns.table[key] + if ok { + n.ref++ + } else { + if setf == nil { + ns.cache.Unlock() + return + } + + var value interface{} + var fin func() + ok, value, _, fin = setf() + if !ok { + ns.cache.Unlock() + return + } + + n = &emptyNode{ + ns: ns, + key: key, + value: value, + setfin: fin, + ref: 1, + } + ns.table[key] = n + } + + ns.cache.Unlock() + o = &emptyObject{node: n} + return +} + +func (ns *emptyNS) Delete(key uint64, fin DelFin) bool { + ns.cache.Lock() + + if ns.state != nsEffective { + ns.cache.Unlock() + if fin != nil { + fin(false) + } + return false + } + + n, ok := ns.table[key] + if !ok { + ns.cache.Unlock() + if fin != nil { + fin(false) + } + return false + } + n.delfin = fin + ns.cache.Unlock() + return true +} + +func (ns *emptyNS) purgeNB(fin PurgeFin) { + if ns.state != nsEffective { + return + } + for _, n := range ns.table { + n.purgefin = fin + } +} + +func (ns *emptyNS) Purge(fin PurgeFin) { + ns.cache.Lock() + ns.purgeNB(fin) + ns.cache.Unlock() +} + +func (ns *emptyNS) zapNB(closed bool) { + if ns.state != nsEffective { + return + } + for _, n := range ns.table { + n.execFin() + } + if closed { + ns.state = nsClosed + } else { + ns.state = nsZapped + } + ns.table = nil +} + +func (ns *emptyNS) Zap(closed bool) { + ns.cache.Lock() + ns.zapNB(closed) + delete(ns.cache.table, ns.id) + ns.cache.Unlock() +} + +type emptyNode struct { + ns *emptyNS + key uint64 + value interface{} + ref int + setfin SetFin + delfin DelFin + purgefin PurgeFin +} + +func (n *emptyNode) execFin() { + if n.setfin != nil { + n.setfin() + n.setfin = nil + } + if n.purgefin != nil { + n.purgefin(n.ns.id, n.key, n.delfin) + n.delfin = nil + n.purgefin = nil + } else if n.delfin != nil { + n.delfin(true) + n.delfin = nil + } +} + +func (n *emptyNode) evict() { + n.ns.cache.Lock() + n.ref-- + if n.ref == 0 { + if n.ns.state == nsEffective { + // Remove elem. + delete(n.ns.table, n.key) + // Execute finalizer. + n.execFin() + } + } else if n.ref < 0 { + panic("leveldb/cache: emptyNode: negative node reference") + } + n.ns.cache.Unlock() +} + +type emptyObject struct { + node *emptyNode + once uint32 +} + +func (o *emptyObject) Value() interface{} { + if atomic.LoadUint32(&o.once) == 0 { + return o.node.value + } + return nil +} + +func (o *emptyObject) Release() { + if !atomic.CompareAndSwapUint32(&o.once, 0, 1) { + return + } + o.node.evict() + o.node = nil +} diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/lru_cache.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/lru_cache.go new file mode 100644 index 000000000..3c98e076b --- /dev/null +++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/cache/lru_cache.go @@ -0,0 +1,354 @@ +// Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com> +// All rights reserved. +// +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +package cache + +import ( + "sync" + "sync/atomic" +) + +// lruCache represent a LRU cache state. +type lruCache struct { + sync.Mutex + + recent lruNode + table map[uint64]*lruNs + capacity int + size int +} + +// NewLRUCache creates a new initialized LRU cache with the given capacity. +func NewLRUCache(capacity int) Cache { + c := &lruCache{ + table: make(map[uint64]*lruNs), + capacity: capacity, + } + c.recent.rNext = &c.recent + c.recent.rPrev = &c.recent + return c +} + +// SetCapacity set cache capacity. +func (c *lruCache) SetCapacity(capacity int) { + c.Lock() + c.capacity = capacity + c.evict() + c.Unlock() +} + +// GetNamespace return namespace object for given id. +func (c *lruCache) GetNamespace(id uint64) Namespace { + c.Lock() + defer c.Unlock() + + if p, ok := c.table[id]; ok { + return p + } + + p := &lruNs{ + lru: c, + id: id, + table: make(map[uint64]*lruNode), + } + c.table[id] = p + return p +} + +// Purge purge entire cache. +func (c *lruCache) Purge(fin PurgeFin) { + c.Lock() + for _, ns := range c.table { + ns.purgeNB(fin) + } + c.Unlock() +} + +func (c *lruCache) Zap(closed bool) { + c.Lock() + for _, ns := range c.table { + ns.zapNB(closed) + } + c.table = make(map[uint64]*lruNs) + c.Unlock() +} + +func (c *lruCache) evict() { + top := &c.recent + for n := c.recent.rPrev; c.size > c.capacity && n != top; { + n.state = nodeEvicted + n.rRemove() + n.evictNB() + c.size -= n.charge + n = c.recent.rPrev + } +} + +type lruNs struct { + lru *lruCache + id uint64 + table map[uint64]*lruNode + state nsState +} + +func (ns *lruNs) Get(key uint64, setf SetFunc) (o Object, ok bool) { + lru := ns.lru + lru.Lock() + + switch ns.state { + case nsZapped: + lru.Unlock() + if setf == nil { + return + } + + var value interface{} + var fin func() + ok, value, _, fin = setf() + if ok { + o = &fakeObject{ + value: value, + fin: fin, + } + } + return + case nsClosed: + lru.Unlock() + return + } + + n, ok := ns.table[key] + if ok { + switch n.state { + case nodeEvicted: + // Insert to recent list. + n.state = nodeEffective + n.ref++ + lru.size += n.charge + lru.evict() + fallthrough + case nodeEffective: + // Bump to front + n.rRemove() + n.rInsert(&lru.recent) + } + n.ref++ + } else { + if setf == nil { + lru.Unlock() + return + } + + var value interface{} + var charge int + var fin func() + ok, value, charge, fin = setf() + if !ok { + lru.Unlock() + return + } + + n = &lruNode{ + ns: ns, + key: key, + value: value, + charge: charge, + setfin: fin, + ref: 2, + } + ns.table[key] = n + n.rInsert(&lru.recent) + + lru.size += charge + lru.evict() + } + + lru.Unlock() + o = &lruObject{node: n} + return +} + +func (ns *lruNs) Delete(key uint64, fin DelFin) bool { + lru := ns.lru + lru.Lock() + + if ns.state != nsEffective { + lru.Unlock() + if fin != nil { + fin(false) + } + return false + } + + n, ok := ns.table[key] + if !ok { + lru.Unlock() + if fin != nil { + fin(false) + } + return false + } + + n.delfin = fin + switch n.state { + case nodeRemoved: + lru.Unlock() + return false + case nodeEffective: + lru.size -= n.charge + n.rRemove() + n.evictNB() + } + n.state = nodeRemoved + + lru.Unlock() + return true +} + +func (ns *lruNs) purgeNB(fin PurgeFin) { + lru := ns.lru + if ns.state != nsEffective { + return + } + + for _, n := range ns.table { + n.purgefin = fin + if n.state == nodeEffective { + lru.size -= n.charge + n.rRemove() + n.evictNB() + } + n.state = nodeRemoved + } +} + +func (ns *lruNs) Purge(fin PurgeFin) { + ns.lru.Lock() + ns.purgeNB(fin) + ns.lru.Unlock() +} + +func (ns *lruNs) zapNB(closed bool) { + lru := ns.lru + if ns.state != nsEffective { + return + } + + if closed { + ns.state = nsClosed + } else { + ns.state = nsZapped + } + for _, n := range ns.table { + if n.state == nodeEffective { + lru.size -= n.charge + n.rRemove() + } + n.state = nodeRemoved + n.execFin() + } + ns.table = nil +} + +func (ns *lruNs) Zap(closed bool) { + ns.lru.Lock() + ns.zapNB(closed) + delete(ns.lru.table, ns.id) + ns.lru.Unlock() +} + +type lruNode struct { + ns *lruNs + + rNext, rPrev *lruNode + + key uint64 + value interface{} + charge int + ref int + state nodeState + setfin SetFin + delfin DelFin + purgefin PurgeFin +} + +func (n *lruNode) rInsert(at *lruNode) { + x := at.rNext + at.rNext = n + n.rPrev = at + n.rNext = x + x.rPrev = n +} + +func (n *lruNode) rRemove() bool { + // only remove if not already removed + if n.rPrev == nil { + return false + } + + n.rPrev.rNext = n.rNext + n.rNext.rPrev = n.rPrev + n.rPrev = nil + n.rNext = nil + + return true +} + +func (n *lruNode) execFin() { + if n.setfin != nil { + n.setfin() + n.setfin = nil + } + if n.purgefin != nil { + n.purgefin(n.ns.id, n.key, n.delfin) + n.delfin = nil + n.purgefin = nil + } else if n.delfin != nil { + n.delfin(true) + n.delfin = nil + } +} + +func (n *lruNode) evictNB() { + n.ref-- + if n.ref == 0 { + if n.ns.state == nsEffective { + // remove elem + delete(n.ns.table, n.key) + // execute finalizer + n.execFin() + } + } else if n.ref < 0 { + panic("leveldb/cache: lruCache: negative node reference") + } +} + +func (n *lruNode) evict() { + n.ns.lru.Lock() + n.evictNB() + n.ns.lru.Unlock() +} + +type lruObject struct { + node *lruNode + once uint32 +} + +func (o *lruObject) Value() interface{} { + if atomic.LoadUint32(&o.once) == 0 { + return o.node.value + } + return nil +} + +func (o *lruObject) Release() { + if !atomic.CompareAndSwapUint32(&o.once, 0, 1) { + return + } + + o.node.evict() + o.node = nil +} |