Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.546.mcz ==================== Summary ==================== Name: Collections-ul.546 Author: ul Time: 10 December 2013, 7:14:34.339 pm UUID: 6fa6992c-8f61-47fa-aedd-173df2cb89f0 Ancestors: Collections-fbs.545 Scalable LRUCache. Migration code is in the postscript. =============== Diff against Collections-fbs.545 =============== Item was changed: Object subclass: #LRUCache + instanceVariableNames: 'map head calls hits size factory values' - instanceVariableNames: 'size factory calls hits values' classVariableNames: '' poolDictionaries: '' category: 'Collections-Cache'! + !LRUCache commentStamp: 'ul 11/23/2013 22:20' prior: 0! + I'm a cache of values, given a key I return a Value from the cache or from the factory. + + I use map (a Dictionary) to find the corresponding value to the given key. I store the values in nodes, which are arrays of size 4. Together with head the nodes form a circular doubly-linked list with a head element. + The first element of a list node is the next list node, the second element is the previous list node. The third element (if exists) is the key, the fourth (if exists) is the value for the given key. + The nodes in the list are ordered by access time. The first node is the most recently accessed, the last one is the least recently accessed.! - !LRUCache commentStamp: '<historical>' prior: 0! - I'm a cache of values, given a key I return a Value from the cache or from the factory! Item was changed: ----- Method: LRUCache>>at: (in category 'accessing') ----- at: aKey "answer the object for aKey, if not present in the cache creates it" + | element keyHash | + self isMigrated ifTrue: [ + calls := calls + 1. + ^map + at: aKey + ifPresent: [ :node | + hits := hits + 1. + self + unlink: node; + moveToFirst: node. + node at: 4 ] + ifAbsent: [ + | node | + map size = size + ifTrue: [ + node := head at: 2. + self unlink: node ] + ifFalse: [ + node := Array new: 4 ]. + self moveToFirst: node. + map at: aKey put: node. + node + at: 3 put: aKey; + at: 4 put: (factory value: aKey) ] ]. calls := calls + 1. keyHash := aKey hash. 1 to: size do: [:index | element := values at: index. (keyHash = (element at: 2) and: [aKey = (element at: 1)]) ifTrue: ["Found!!" hits := hits + 1. values replaceFrom: 2 to: index with: (values first: index - 1). values at: 1 put: element. ^ element at: 3]]. "Not found!!" element := {aKey. keyHash. factory value: aKey}. values replaceFrom: 2 to: size with: values allButLast. values at: 1 put: element. ^ element at: 3! Item was changed: ----- Method: LRUCache>>initializeSize:factory: (in category 'initialization') ----- + initializeSize: anInteger factory: aBlock - initializeSize: aNumber factory: aBlock "initialize the receiver's size and factory" + + anInteger strictlyPositive ifFalse: [ self error: 'Size must be at least 1' ]. + size := anInteger. + head := Array new: 2. + head + at: 1 put: head; + at: 2 put: head. + map := PluggableDictionary integerDictionary. - size := aNumber. - values := Array new: aNumber withAll: {nil. nil. nil}. factory := aBlock. calls := 0. hits := 0! Item was added: + ----- Method: LRUCache>>isMigrated (in category 'migration') ----- + isMigrated + + ^map notNil! Item was added: + ----- Method: LRUCache>>migrate (in category 'migration') ----- + migrate + + self isMigrated ifTrue: [ ^self ]. + head := Array new: 2. + head + at: 1 put: head; + at: 2 put: head. + map := PluggableDictionary integerDictionary. + values reverseDo: [ :each | + | node | + node := { nil. nil. each first. each third }. + map at: each first put: node. + self moveToFirst: node ]. + values := nil + ! Item was added: + ----- Method: LRUCache>>moveToFirst: (in category 'private') ----- + moveToFirst: node + "Move node after head in the doubly-linked list. If the node is linked, it must be unlinked first." + + | next | + next := head at: 1. + node + at: 1 put: next; + at: 2 put: head. + next at: 2 put: node. + head at: 1 put: node! Item was added: + ----- Method: LRUCache>>unlink: (in category 'private') ----- + unlink: node + "Unlink the node from the doubly-linked list represented by head." + + | next previous | + next := node at: 1. + previous := node at: 2. + next at: 2 put: previous. + previous at: 1 put: next! Item was changed: + (PackageInfo named: 'Collections') postscript: 'LRUCache allInstancesDo: #migrate'! - (PackageInfo named: 'Collections') postscript: 'WeakRegistry allInstancesDo: [ :each | each installFinalizer ]'! |
Free forum by Nabble | Edit this page |