[squeak-dev] The Trunk: Collections-ul.547.mcz

commits at source.squeak.org commits at source.squeak.org
Tue Dec 10 20:45:26 UTC 2013


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

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

Name: Collections-ul.547
Author: ul
Time: 10 December 2013, 7:15:33.532 pm
UUID: b9d6e526-de0c-47ae-ae30-97c8bb601e4c
Ancestors: Collections-ul.546

Finish migration. Remove migration code.

=============== Diff against Collections-ul.546 ===============

Item was changed:
  Object subclass: #LRUCache
+ 	instanceVariableNames: 'map head calls hits size factory'
- 	instanceVariableNames: 'map head calls hits size factory 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.!

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.
+ 	^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) ]!
- 	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>>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.
+ 	next == node ifTrue: [ ^self ].
  	node
  		at: 1 put: next;
  		at: 2 put: head.
  	next at: 2 put: node.
  	head at: 1 put: node!



More information about the Squeak-dev mailing list