!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: keysoftvaluedict.gs,v 1.10 2008-01-09 22:50:12 stever Exp $
!
! Superclass Hierarchy:
!   KeySoftValueDictionary, KeyValueDictionary, AbstractDictionary, Collection, Object.
!
!=========================================================================

expectvalue %String
run
| res cls oldCls clsName |
clsName := #KeySoftValueDictionary .
oldCls := Globals at:clsName otherwise: nil .
oldCls == nil ifTrue:[
  res := KeyValueDictionary _newKernelSubclass: clsName"KeySoftValueDictionary"
    instVarNames: #( )
    classVars: #()
    classInstVars: #()
    poolDictionaries: #[]
    inDictionary: Globals
    constraints: #[ ]
    instancesInvariant: false
    isModifiable: true
    reservedOop: 941 .
  cls := Globals at: clsName .
  cls makeInstancesNonPersistent .
  cls _disallowGciCreateStore . 
  cls immediateInvariant .
] ifFalse: [
  res := clsName asString + 'already exists'.
  oldCls instancesNonPersistent ifFalse:[ nil error:'should be NP' ].
].
^ res
%

removeallmethods KeySoftValueDictionary
removeallclassmethods 

category: 'For Documentation Installation only'
classmethod
installDocumentation

| doc txt |
doc := GsClassDocumentation newForClass: self.

txt := (GsDocText new) details:
'KeySoftValueDictionary is a subclass of KeyValueDictionary.
 Instances of KeySoftValueDictionary are non-persistent and may not be
 committed ot the repository.

 All values in KeySoftValueDictionary are instances of SoftReference .

 Various instance methods in KeySoftValueDictionary will automatically
 remove from a KeySoftValueDictionary any SoftReferences whose value
 instVar has been cleared by the in-memory garbage collector.' .
doc documentClassWith: txt.

self description: doc.
%

category: 'Private'
method
collisionBucketClass

"Returns the class of object to create when keys collide."

^ SoftCollisionBucket
%

category: 'Private
method
_referenceAt: tableIdx 

" for the key stored in the hash table at tableIdx ,
  return the softRef if softRef.value non-nil, otherwise 
  remove the soft reference and associated key .
"
| aSoftRef val |
aSoftRef := self _at: tableIdx + 1 .
aSoftRef ~~ nil ifTrue:[ 
  val := aSoftRef _value .
  val == nil ifTrue:[ 
    self _basicAt: tableIdx     put: nil . "remove key"
    self _basicAt: tableIdx + 1 put: nil . "remove SoftRef"
    numElements := numElements - 1 .
    ^ nil .
  ].
  ^ aSoftRef
].
^ nil
%

category: 'Accessing'
method
referenceAt: aKey otherwise: aValue

" Return the SoftReference corresponding to aKey ,
  or return aValue if aKey not found."

| hash hashKey collisionBkt ref |

nil == aKey ifTrue:[ ^ aValue ].
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey ifTrue: [ 
  collisionBkt := self valueAt: hash.
  nil == collisionBkt ifFalse: [ 
  ref := collisionBkt referenceAt: aKey  otherwise: nil .
  ]
] ifFalse: [ 
  (self compareKey: aKey with: hashKey) ifTrue: [ 
     ref := self _referenceAt: ( 2 * hash - 1) .
   ] 
].
ref ~~ nil ifTrue:[ ^ ref ].
^ aValue 
%

category: 'Accessing'
method
referenceAt: aKey

"Returns the SoftReference corresponding to aKey. 
 Generates an error if no such key exists."

| ref |
ref := self referenceAt: aKey otherwise: nil .
ref ~~ nil ifTrue:[ ^ ref ].
^ self _errorKeyNotFound: aKey
%

category: 'Private
method
_removedElements: elemDelta collisions:  collDelta

"aCount key/value pairs have been removed from a bucket , update
 this dictionary accordingly."

numElements := numElements - elemDelta  .
numElements < 0 ifTrue:[ self error:'numElements underflow' ].
numCollisions := numCollisions - collDelta .
numCollisions < 0 ifTrue:[ self error:'numCollisions underflow' ].
%

category: 'Private
method
_bucketSizeChangeFrom: startNumElem to: newNumElements 
  "a bucket has removed some key/softRef pairs , now update
   dictionary size information."

| elemDelta collDelta |
elemDelta := startNumElem - newNumElements .
elemDelta < 1 ifTrue:[ nil error:'elemDelta underflow' ].
collDelta := elemDelta .
newNumElements <= 0 ifTrue:[  
  newNumElements < 0 ifTrue:[ nil error:'numElem underflow' ].
  collDelta := elemDelta - 1 .
  collDelta < 0 ifTrue:[ nil error:'collDelta underflow' ].
].
self _removedElements: elemDelta collisions: collDelta .
%

! fixed 32863
category: 'Enumerating'
method
keysAndValuesDo: aBlock
 
"Evaluates aBlock with each of the receiver's key/value pairs as the
 arguments.  The argument aBlock must be a two-argument block,
 first argument is the key and the second argument is the value of
 the SoftReference for each non-cleared key/softRef pair in the dictionary.

 SoftReferences which have been cleared by the garbage collector
 are removed from the dictionary during enumeration of the dictionary.
 The useCount of each non-cleared SoftReference will be incremented.
"

| tableLimit |
tableLimit := tableSize * 2 .
1 to: tableLimit by: 2 do: [ :tableIndex | | aKey |
  aKey := self _at: tableIndex .
  aKey == nil ifTrue: [ | collisionBkt |
    collisionBkt := self _at: (tableIndex + 1).
    collisionBkt ~~ nil ifTrue: [  | bktSize bktIdx |
      bktIdx := 1 .
      bktSize := collisionBkt _basicSize . 
      [ bktIdx <= bktSize] whileTrue:[  | bKey |
        bKey := collisionBkt _at: bktIdx .
        bKey ~~ nil ifTrue:[  | oldSize bRef |
          oldSize := bktSize . 
          bRef := collisionBkt _referenceAt: bktIdx . "possible removal"
          bRef ~~ nil ifTrue:[ | val |
            val := bRef value . 
            val ~~ nil ifTrue:[
              aBlock value: bKey value: val
            ].
          ] .
          "advance bktIdx only if no removal done "
          bktSize := collisionBkt _basicSize . 
          bktSize = oldSize ifTrue:[ bktIdx := bktIdx + 2 ].
        ] ifFalse:[
          bktIdx := bktIdx + 2.
        ]
      ]
    ].  
  ] ifFalse: [ | aRef |
    aRef := self _referenceAt: tableIndex .
    aRef ~~ nil ifTrue:[ | val |
      val := aRef value .
      val ~~ nil ifTrue:[
        aBlock value: aKey value: val
      ].
    ].
  ].
].
%

! added for 36675
category: 'Enumerating'
method
inject: anObj keysAndValuesInto: aBlock

"Evaluates aBlock with each of the receiver's key/value pairs as the
 2nd and 3rd arguments.
 aBlock must be a 3 argument block, with arguments anObj, key value .

 SoftReferences which have been cleared by the garbage collector
 are removed from the dictionary during enumeration of the dictionary.
 The useCount of each non-cleared SoftReference will be incremented.
"

| tableLimit |
tableLimit := tableSize * 2 .
1 to: tableLimit by: 2 do: [ :tableIndex | | aKey |
  aKey := self _at: tableIndex .
  aKey == nil ifTrue: [ | collisionBkt |
    collisionBkt := self _at: (tableIndex + 1).
    collisionBkt ~~ nil ifTrue: [  | bktSize bktIdx |
      bktIdx := 1 .
      bktSize := collisionBkt _basicSize . 
      [ bktIdx <= bktSize] whileTrue:[  | bKey |
        bKey := collisionBkt _at: bktIdx .
        bKey ~~ nil ifTrue:[  | oldSize bRef |
          oldSize := bktSize . 
          bRef := collisionBkt _referenceAt: bktIdx . "possible removal"
          bRef ~~ nil ifTrue:[ | val |
            val := bRef value . 
            val ~~ nil ifTrue:[
              aBlock value: anObj value: bKey value: val
            ].
          ] .
          "advance bktIdx only if no removal done "
          bktSize := collisionBkt _basicSize . 
          bktSize = oldSize ifTrue:[ bktIdx := bktIdx + 2 ].
        ] ifFalse:[
          bktIdx := bktIdx + 2.
        ]
      ]
    ].  
  ] ifFalse: [ | aRef |
    aRef := self _referenceAt: tableIndex .
    aRef ~~ nil ifTrue:[ | val |
      val := aRef value .
      val ~~ nil ifTrue:[
        aBlock value: anObj value: aKey value: val
      ].
    ].
  ].
].

%

category: 'Enumerating'
method
keysDo: aBlock
 
"Evaluates aBlock with each of the receiver's keys as the
 argument.  The argument aBlock must be a one-argument block .

 SoftReferences which have been cleared by the garbage collector
 are removed from the dictionary during enumeration of the dictionary,
 and their keys will not be passed to aBlock .

 The useCount of each non-cleared SoftReference is NOT incremented.
"

| tableLimit |
tableLimit := tableSize * 2 .
1 to: tableLimit by: 2 do: [ :tableIndex | | aKey |
  aKey := self _at: tableIndex .
  aKey == nil ifTrue: [ | collisionBkt |
    collisionBkt := self _at: (tableIndex + 1).
    collisionBkt ~~ nil ifTrue: [  | bktSize bktIdx |
      bktIdx := 1 .
      bktSize := collisionBkt _basicSize . 
      [ bktIdx <= bktSize] whileTrue:[  | bKey |
        bKey := collisionBkt _at: bktIdx .
        bKey ~~ nil ifTrue:[  | oldSize bRef |
          oldSize := bktSize . 
          bRef := collisionBkt _referenceAt: bktIdx . "possible removal"
          bRef ~~ nil ifTrue:[ | val |
            val := bRef _value . 
            val ~~ nil ifTrue:[
              aBlock value: bKey .
            ].
          ] .
          "advance bktIdx only if no removal done "
          bktSize := collisionBkt _basicSize . 
          bktSize = oldSize ifTrue:[ bktIdx := bktIdx + 2 ].
        ] ifFalse:[
          bktIdx := bktIdx + 2.
        ]
      ]
    ].  
  ] ifFalse: [ | aRef |
    aRef := self _referenceAt: tableIndex .
    aRef ~~ nil ifTrue:[ | val |
      val := aRef _value .
      val ~~ nil ifTrue:[
        aBlock value: aKey 
      ].
    ].
  ].
].
%

! fixed 32863
category: 'Enumerating'
method
keysAndReferencesDo: aBlock

"Evaluates aBlock with each of the receiver's key/softRef pairs as the
 arguments.  The argument aBlock must be a two-argument block,  
 first argument is the key and the second argument is 
 the SoftReference for each non-cleared key/softRef pair in the dictionary.

 SoftReferences which have been cleared by the garbage collector 
 are removed from the dictionary during enumeration of the dictionary.
 The useCount of each non-cleared SoftReference will NOT be incremented.
"

| tableLimit |
tableLimit := tableSize * 2 .
1 to: tableLimit by: 2 do: [ :tableIndex | | aKey |
  aKey := self _at: tableIndex .
  aKey == nil ifTrue: [ | collisionBkt |
    collisionBkt := self _at: (tableIndex + 1) .
    collisionBkt ~~ nil ifTrue: [  | bktSize bktIdx |
      bktIdx := 1 .
      bktSize := collisionBkt _basicSize .
      [ bktIdx <= bktSize] whileTrue:[  | bKey |
        bKey := collisionBkt _at: bktIdx .
        bKey ~~ nil ifTrue:[  | oldSize bRef |
          oldSize := bktSize . 
          bRef := collisionBkt _referenceAt: bktIdx  . "possible removal"
          bRef ~~ nil ifTrue:[ 
            aBlock value: bKey value: bRef  
	  ].
          "advance bktIdx only if no removal done "
          bktSize := collisionBkt _basicSize .
          bktSize = oldSize ifTrue:[ bktIdx := bktIdx + 2 ].
        ] ifFalse:[
          bktIdx := bktIdx + 2.
        ]
      ].
    ].
  ] ifFalse: [ | aRef |
    aRef := self _referenceAt: tableIndex .
    aRef ~~ nil ifTrue:[ 
      aBlock value: aKey value: aRef 
    ].
  ].
].
%

!  fixed  32785 , 32863
category: 'Accessing'
method
keyAtValue: anObject ifAbsent: aBlock

"(R) Returns the key of the first SoftRef equal to the given object, anObject.
 If no match is found, evaluates and returns the result of the block aBlock."

| tableLimit |
tableLimit := tableSize * 2 .
1 to: tableLimit by: 2 do: [ :tableIndex | | aKey |
  aKey := self _at: tableIndex .
  aKey == nil ifTrue: [ | collisionBkt |
    collisionBkt := self _at: tableIndex + 1.
    collisionBkt ~~ nil ifTrue: [  | bktSize bktIdx |
      bktIdx := 1 .
      bktSize := collisionBkt _basicSize .
      [ bktIdx <= bktSize] whileTrue:[  | bKey |
        bKey := collisionBkt _at: bktIdx .
        bKey ~~ nil ifTrue: [ | oldSize bRef |
          oldSize := bktSize .
          bRef := collisionBkt _referenceAt: bktIdx .  "possible removal"
          bRef ~~ nil ifTrue:[
            anObject = bRef _value ifTrue: [
              ^bKey
            ].
          ].
          "advance bktIdx only if no removal done "
          bktSize := collisionBkt _basicSize .
          bktSize = oldSize ifTrue:[ bktIdx := bktIdx + 2 ].
        ] ifFalse:[
          bktIdx := bktIdx + 2.
        ].
      ].
    ].
  ] ifFalse: [ | aSoftRef |
    aSoftRef := self _referenceAt: tableIndex .
    aSoftRef ~~ nil ifTrue:[
      anObject = aSoftRef _value ifTrue:[
        ^aKey
      ].
    ].
  ].
].
^aBlock value.
%

category: 'Accessing'
method
at: aKey ifAbsent: aBlock

"Returns the value of the SoftReference that corresponds to aKey.  
 If no such key/SoftRef pair exists, returns the result of 
 evaluating the zero-argument block aBlock.

 Does not send setInUse to matching SoftReference.
 The useCount of the matching SoftReference is incremented, if the
 returned value is not special ."

| ref |

ref := self referenceAt: aKey otherwise: nil .
ref == nil ifTrue:[ 
  ^self _reportKeyNotFound: aKey with: aBlock
].
^ ref value
%

category: 'Accessing'
method
at: aKey otherwise: aValue

"Returns the value of the SoftReference that corresponds to aKey.
 If no such key/softRef pair exists, returns the given alternate value.  
 Does not send setInUse to the matching SoftReference. 
 The useCount of the matching SoftReference is incremented, if the
 returned value is not special ."

| ref |
ref := self referenceAt: aKey otherwise: nil .
ref ~~ nil ifTrue:[ ^ ref value ].
^ aValue
%


category: 'Updating'
method
at: aKey putReference: aSoftReference

"Stores the aKey/SoftRef pair in the hash dictionary.  Rebuilds the hash table
 if the addition caused the number of collisions to exceed the limit allowed.
 
 aSoftReference must be a instance of SoftReference , else an error is 
 generated .
 The useCount of aSoftReference is incremented.

 Returns aSoftReference, or nil if the addition could not be completed.
 Returns nil if aSoftReference was cleared by the garbage collector
 before the addition could be completed."

| val |
aSoftReference _validateInstanceOf: SoftReference .
val := aSoftReference value  .  "increment useCount and keep val alive on stack"
val == nil ifTrue:[ ^ nil ].

super at: aKey put: aSoftReference .
^ aSoftReference
%

category: 'Updating'
method
at: aKey put: aValue

"Creates a SoftReference referencing aValue and
 inserts the key/softRef pair into the receiver .

 Rebuilds the hash table
 if the addition caused the number of collisions to exceed the limit allowed.

 Returns aValue. 
"
| ref validRef |
ref := SoftReference new .
ref setValue: aValue .
validRef := self at: aKey putReference: ref .
" should always get the ref back because we have a strong ref to value
  on the stack"
validRef == ref ifFalse:[ self error:'inconsistent softref state' ].
^ aValue
%

category: 'Clustering'
method
clusterDepthFirst

"Instances are non-persistent so this has no effect"

^ true
%


category: 'Accessing'
method
at: aKey ifAbsentPut: aBlock

"disallowed"
^ self shouldNotImplement: #at:ifAbsentPut:
%

! change to not increment use count
category: 'Hashing'
method
rebuildTable: newSize

"Rebuilds the hash table by saving the current state, initializing and
 changing the size of the table, and adding the key value pairs saved
 back to the hash dictionary.

 During the 'saving the current state' phase, cleared SoftReferences
 will be removed from the dictionary.  After 'saving the current state',
 if numCollisions is below the collisionLimit, the rebuild will be skipped. 

 If explicit rebuildTable is desired, you need to set the collisionLimit
 lower than the number of collisions before sending rebuildTable: .
 rebuildTable: will then install a new collision limit based on the
 newSize .  "

|saveTable saveIdx saveCollLimit |

collisionLimit == 536870911 ifTrue:[
  ^ self  "prevent recursive rebuild"
  ].
saveTable := Array new: (self size * 3).
saveIdx := 0.
self keysAndReferencesDo: [ :aKey :aSoftRef |
  saveIdx := saveIdx + 1.
  saveTable at: saveIdx put: aKey.
  saveIdx := saveIdx + 1.
  saveTable at: saveIdx put: aSoftRef.

  "keep values mostly alive"
  saveIdx := saveIdx + 1.
  saveTable at: saveIdx put: (aSoftRef _value)   "avoid incrementing useCount"
  ].
"enumeration of soft dictionaries may return less than total size"
saveTable size: saveIdx + 1 .
numCollisions < collisionLimit ifTrue:[
  "rebuild not needed after removals from soft dictionary during enumeration"
  "GsFile gciLogServer:'--- rebuild not needed for newSize ' + newSize asString
		+ '--------------- ' . ===debugging code not used"
  ^ self
  ].

self tableSize: newSize.  "installs new collision limit"
saveCollLimit := collisionLimit .
collisionLimit := 536870911 . "prevent recursive rebuild"
1 to: saveIdx by: 3 do: [ :j | | aSoftRef |
  aSoftRef := saveTable at: j + 1 "value" .
  aSoftRef _value ~~ nil ifTrue:[     "avoid incrementing useCount"
    super at: (saveTable at: j "key") put: aSoftRef
    ].
  ].
collisionLimit := saveCollLimit .
"GsFile gciLogServer:'--- rebuild for newSize ' + newSize asString
                + '--------------- ' .   ===debugging code not used"
^self
%

