The Trunk: Collections-ul.617.mcz

Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.617.mcz

==================== Summary ====================

Name: Collections-ul.617
Author: ul
Time: 12 April 2015, 2:59:01.46 am
UUID: 483f2798-971c-4066-8b82-4a2271420294
Ancestors: Collections-ul.616

LRUCache changes:
- added a #reset method, which removes all elements from the cache
- replaced the Arrays storing the list of elements with custom classes (LRUCacheHeadNode and LRUCacheNode).
- fix: the map variable gets correctly updated, when the cache is full

=============== Diff against Collections-ul.616 ===============

Item was changed:
  Object subclass: #LRUCache
  instanceVariableNames: 'map head calls hits size factory'
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Cache'!
 
+ !LRUCache commentStamp: 'ul 4/12/2015 02:55' prior: 0!
- !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 a Dictionary to find the corresponding value for the given key. I also store the key-value pairs in a circular doubly-linked list with a head element. The list is implemented by an LRUCacheHeadNode - stored in the head instance variable - and an LRUCacheNode for each key-value pair. The nodes in the list are ordered by access time. The first node (next of head) is the most recently accessed, the last one (previous of head) is the least recently accessed.
+ If the number of stored key-value pairs is equal to size, and a new pair needs to be stored, then I remove the least recently used pair before adding the new pair.!
- 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.!

Item was changed:
  ----- Method: LRUCache>>at: (in category 'accessing') -----
  at: aKey
  "answer the object for aKey, if not present in the cache creates it"
 
+ head class == LRUCacheHeadNode ifFalse: [ self reset ].
  calls := calls + 1.
  ^map
  at: aKey
  ifPresent: [ :node |
  hits := hits + 1.
+ head next == node ifFalse: [
+ node
+ unlink;
+ linkAfter: head ].
+ node value ]
- self
- unlink: node;
- moveToFirst: node.
- node at: 4 ]
  ifAbsent: [
  | node |
  map size = size
  ifTrue: [
+ node := head previous.
+ node unlink.
+ map removeKey: node key. ]
+ ifFalse: [ node := LRUCacheNode new ].
+ node linkAfter: head.
- node := head at: 2.
- self unlink: node ]
- ifFalse: [
- node := Array new: 4 ].
- self moveToFirst: node.
  map at: aKey put: node.
  node
+ key: aKey;
+ value: (factory value: aKey);
+ value ]!
- at: 3 put: aKey;
- at: 4 put: (factory value: aKey) ]!

Item was changed:
  ----- Method: LRUCache>>initializeSize:factory: (in category 'initialization') -----
  initializeSize: anInteger factory: aBlock
  "initialize the receiver's size and factory"
 
  anInteger strictlyPositive ifFalse: [ self error: 'Size must be at least 1' ].
  size := anInteger.
+ head := LRUCacheHeadNode new.
- head := Array new: 2.
- head
- at: 1 put: head;
- at: 2 put: head.
  map := PluggableDictionary integerDictionary.
  factory := aBlock.
  calls := 0.
  hits := 0!

Item was added:
+ ----- Method: LRUCache>>reset (in category 'initialization') -----
+ reset
+
+ self initializeSize: size factory: factory!

Item was added:
+ Object subclass: #LRUCacheHeadNode
+ instanceVariableNames: 'next previous'
+ classVariableNames: ''
+ poolDictionaries: ''
+ category: 'Collections-Cache'!

Item was added:
+ ----- Method: LRUCacheHeadNode>>initialize (in category 'initialize-release') -----
+ initialize
+
+ previous := next := self!

Item was added:
+ ----- Method: LRUCacheHeadNode>>next (in category 'accessing') -----
+ next
+
+ ^next!

Item was added:
+ ----- Method: LRUCacheHeadNode>>next: (in category 'accessing') -----
+ next: anObject
+
+ next := anObject!

Item was added:
+ ----- Method: LRUCacheHeadNode>>previous (in category 'accessing') -----
+ previous
+
+ ^previous!

Item was added:
+ ----- Method: LRUCacheHeadNode>>previous: (in category 'accessing') -----
+ previous: anObject
+
+ previous := anObject!

Item was added:
+ LRUCacheHeadNode subclass: #LRUCacheNode
+ instanceVariableNames: 'key value'
+ classVariableNames: ''
+ poolDictionaries: ''
+ category: 'Collections-Cache'!

Item was added:
+ ----- Method: LRUCacheNode>>key (in category 'accessing') -----
+ key
+
+ ^key!

Item was added:
+ ----- Method: LRUCacheNode>>key: (in category 'accessing') -----
+ key: anObject
+
+ key := anObject!

Item was added:
+ ----- Method: LRUCacheNode>>linkAfter: (in category 'list operations') -----
+ linkAfter: anLRUCacheHeadNode
+
+ next := anLRUCacheHeadNode next.
+ previous := anLRUCacheHeadNode.
+ next previous: self.
+ previous next: self!

Item was added:
+ ----- Method: LRUCacheNode>>printOn: (in category 'accessing') -----
+ printOn: stream
+
+ super printOn: stream.
+ stream
+ nextPut: $(;
+ print: key;
+ nextPutAll: ', ';
+ print: value;
+ nextPut: $)!

Item was added:
+ ----- Method: LRUCacheNode>>unlink (in category 'list operations') -----
+ unlink
+
+ next previous: previous.
+ previous next: next.
+ next := previous := nil!

Item was added:
+ ----- Method: LRUCacheNode>>value (in category 'accessing') -----
+ value
+
+ ^value!

Item was added:
+ ----- Method: LRUCacheNode>>value: (in category 'accessing') -----
+ value: anObject
+
+ value := anObject!