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

removeallmethods KeyValueDictionary
removeallclassmethods KeyValueDictionary

category: 'For Documentation Installation only'
classmethod
installDocumentation

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

txt := (GsDocText new) details:
'KeyValueDictionary is a concrete subclass of AbstractDictionary.  In a
 KeyValueDictionary, keys may be of mixed classes.

 A KeyValueDictionary stores key-value pairs under an index that is generated by
 applying a hash function to the key; it does not use Associations.  The hashing
 improves retrieval speed.  However, you must observe an important restriction:
 after a key/value pair has been added to a KeyValueDictionary, you must not
 modify the key.  Doing so renders the value inaccessible.

 A KeyValueDictionary is also an equality-based collection.  That is, two keys
 or two values are considered to be the same if they are equivalent; they need
 not be identical to be the same.  Thus, if you add two key-value pairs to a
 KeyValueDictionary but the keys are equivalent, even if they are not identical,
 then the result is that the second pair overwrites the first one, because the
 keys are the same.

 Some other kinds of dictionaries are identity-based rather than equality-based.
 These other kinds of dictionaries exhibit better performance than
 KeyValueDictionary and are to be preferred where they are appropriate.

 For multiuser applications that involve a lot of concurrent use of
 dictionaries, use RcKeyValueDictionary.' .
doc documentClassWith: txt.

txt := (GsDocText new) details:
'A SmallInteger that represents the number of key/value pairs in the
 dictionary.'.
doc documentInstVar: #numElements with: txt.

txt := (GsDocText new) details:
'A SmallInteger that represents the cumulative number of collisions that have
 occurred during the addition of the elements to the dictionary since the last
 rebuild.'.
doc documentInstVar: #numCollisions with: txt.

txt := (GsDocText new) details:
'A SmallInteger that represents the number of collisions allowed before
 rebuilding the hash table.'.
doc documentInstVar: #collisionLimit with: txt.

txt := (GsDocText new) details:
'A SmallInteger that represents the size of the primary hash table.'.
doc documentInstVar: #tableSize with: txt.

self description: doc.
%

category: 'Private'
method
rebuildIfNeeded

"Private.  If the receiver has too many collisions, rebuild it with a larger
 hash table.  Returns true if the receiver was rebuilt, false otherwise."

| newSize |

numCollisions > collisionLimit ifTrue:[
  [ numCollisions > collisionLimit ] whileTrue: [
    newSize := 
       Integer _selectedPrimeGreaterThan: ( numElements max: tableSize + 1) .
    self rebuildTable: newSize .
    ].
  ^ true .
  ].
^ false
%

category: 'Private'
method
_rebuild

"Rebuild to the next higher size because the internal data structures like
 the collision buckets would like it to happen."

  | newSize |

  newSize := Integer 
	     _selectedPrimeGreaterThan: ( numElements max: tableSize + 1) .
  self rebuildTable: newSize .
  ^ self.
%

category: 'Instance Creation'
classmethod
new

"Creates an instance of KeyValueDictionary with a default table size."

^self new: 5
%

category: 'Instance Creation'
classmethod
new: tableSize

"Creates an instance of KeyValueDictionary based upon the specified table size."

| newSize newDict |

newSize := Integer _selectedPrimeGreaterThan: tableSize.
newDict := super _basicNew: (newSize * 2).

newDict _initializeWithoutClear: newSize.
^ newDict.
%

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.  The
 first argument is the key and the second argument is the value of
 each key/value pair."

| aKey collisionBkt |

1 to: tableSize * 2 by: 2 do: [ :tableIndex |
  nil == (aKey := self _at: tableIndex) ifTrue: [
    nil == (collisionBkt := self _at: (tableIndex + 1)) ifFalse: [
      1 to: collisionBkt _basicSize by: 2 do: [ :j |
        nil == (aKey := collisionBkt _at: j) ifFalse: [
          aBlock value: aKey value: (collisionBkt _at: j + 1).
          ].
        ].
      ].
    ]
  ifFalse: [
    aBlock value: aKey value: (self _at: tableIndex + 1).
    ].
  ].
%
! 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 ."

| aKey collisionBkt |

1 to: tableSize * 2 by: 2 do: [ :tableIndex |
  nil == (aKey := self _at: tableIndex) ifTrue: [
    nil == (collisionBkt := self _at: (tableIndex + 1)) ifFalse: [
      1 to: collisionBkt _basicSize by: 2 do: [ :j |
        nil == (aKey := collisionBkt _at: j) ifFalse: [
          aBlock value: anObj value: aKey value: (collisionBkt _at: j + 1).
          ].
        ].
      ].
    ]
  ifFalse: [
    aBlock value: anObj value: aKey value: (self _at: tableIndex + 1).
    ].
  ].
%

category: 'Enumerating'
method
do: aBlock

"(R) Iteratively evaluates the one argument block aBlock, using the value of
 each Association or key-value pair as the argument of the block."

self keysAndValuesDo: [:aKey :aValue | aBlock value: aValue].
^self
%

category: 'Enumerating'
method
associationsDo: aBlock

"Evaluates aBlock with each of the receiver's key/value pairs as the
 argument by creating an Association for each key/value pair.  The
 argument aBlock must be a one-argument block."

self keysAndValuesDo: [:aKey :aValue |
   aBlock value: (Association newWithKey: aKey value: aValue)
].
^self
%

category: 'Enumerating'
method
keysDo: aBlock

"For each key/value pair in the receiver, evaluates the one-argument block
 aBlock with the key as the argument."

self keysAndValuesDo: [:aKey :aValue |
   aBlock value: aKey
].
^self
%

category: 'Enumerating'
method
valuesDo: aBlock

"For each key/value pair in the receiver, evaluates the one-argument block
 aBlock with the value as the argument."

self keysAndValuesDo: [:aKey :aValue |
   aBlock value: aValue
].
^self
%

! _asCollection removed in v4.0

category: 'Accessing'
method
keyAtValue: anObject ifAbsent: aBlock

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

"Note: In GemStone 4.1, this method checked for a value identical to anObject
 as opposed to checking for equality."

| aKey collisionBkt |

1 to: tableSize * 2 by: 2 do: [ :tableIndex |
  nil == (aKey := self _at: tableIndex) ifTrue: [
    nil == (collisionBkt := self _at: (tableIndex + 1)) ifFalse: [
      1 to: collisionBkt _basicSize by: 2 do: [ :j |
        nil == (aKey := collisionBkt _at: j) ifFalse: [
          anObject = (collisionBkt _at: j + 1) ifTrue: [
            ^aKey
            ].
          ].
        ].
      ].
    ]
  ifFalse: [
    anObject = (self _at: tableIndex + 1) ifTrue: [
      ^aKey
      ].
    ].
  ].

^aBlock value.
%

category: 'Removing'
method
removeKey: aKey ifAbsent: aBlock

"Removes the key/value pair with key aKey from the receiver and returns
 the value.  If no key/value pair is present with key aKey, evaluates
 the zero-argument block aBlock and returns the result of that evaluation."

| hash thisKey collisionBkt aValue lastPair |

hash := self hashFunction: aKey.
nil == (thisKey := (self keyAt: hash))

   ifTrue: [ "It might be in a collision bucket"
      collisionBkt := self valueAt: hash.
      nil == collisionBkt
         ifTrue: [ ^ self _reportKeyNotFound: aKey with: aBlock ] .
      aValue := collisionBkt
         removeKey: aKey
         ifAbsent: [ ^ self _reportKeyNotFound: aKey with: aBlock]. "fix 11884"
      "If we got this far, a key/value pair was removed from collisionBkt"
      numCollisions := numCollisions - 1.
      (collisionBkt size <= 1) ifTrue: [
         "We don't need the collision bucket anymore.
          Put its last key/value pair in our table."
         lastPair := collisionBkt firstPair.
         self atHash: hash putKey: lastPair key.
         self atHash: hash putValue: lastPair value.
         collisionBkt _removeAll ]]

   ifFalse: [ "There is a key/value pair in this slot"
      (self compareKey: aKey with: thisKey)
         ifFalse: [ ^ self _reportKeyNotFound: aKey with: aBlock ] .
      "The key matches - remove it"
      aValue := self valueAt: hash.
      self atHash: hash putKey: nil.
      self atHash: hash putValue: nil ].

numElements := numElements - 1.
^aValue
%

! added for 36675
category: 'Removing'
method
removeKey: aKey otherwise: notFoundValue

"Removes the key/value pair with key aKey from the receiver and returns
 the value.  If no key/value pair is present with key aKey, 
 returns the notFoundValue ."

| hash thisKey collisionBkt aValue lastPair |

hash := self hashFunction: aKey.
nil == (thisKey := (self keyAt: hash))

   ifTrue: [ "It might be in a collision bucket"
      collisionBkt := self valueAt: hash.
      nil == collisionBkt
         ifTrue: [ ^ notFoundValue ] .
      aValue := collisionBkt
         removeKey: aKey otherwise: notFoundValue .
      "If we got this far, a key/value pair was removed from collisionBkt"
      numCollisions := numCollisions - 1.
      (collisionBkt size <= 1) ifTrue: [
         "We don't need the collision bucket anymore.
          Put its last key/value pair in our table."
         lastPair := collisionBkt firstPair.
         self atHash: hash putKey: lastPair key.
         self atHash: hash putValue: lastPair value.
         collisionBkt _removeAll ]]

   ifFalse: [ "There is a key/value pair in this slot"
      (self compareKey: aKey with: thisKey)
         ifFalse: [ ^ notFoundValue ].
      "The key matches - remove it"
      aValue := self valueAt: hash.
      self atHash: hash putKey: nil.
      self atHash: hash putValue: nil ].

numElements := numElements - 1.
^aValue
%

category: 'Removing'
method
_removeKey: aKey 

"Removes the key/value pair with key aKey from the receiver ,
 without accessing the value of the key/value pair.
 If no key/value pair is present with key aKey, generates an error.
 Does not remove empty collision buckets."

| hash thisKey collisionBkt |

hash := self hashFunction: aKey.
nil == (thisKey := (self keyAt: hash))

   ifTrue: [ "It might be in a collision bucket"
      collisionBkt := self valueAt: hash.
      nil == collisionBkt
         ifTrue: [ ^ self _errorKeyNotFound: aKey ] .
      collisionBkt _removeKey: aKey  .
      "If we got this far, a key/value pair was removed from collisionBkt"
      numCollisions := numCollisions - 1.
   ]
   ifFalse: [ "There is a key/value pair in this slot"
      (self compareKey: aKey with: thisKey)
         ifFalse: [ ^ self _errorKeyNotFound: aKey ] .
      "The key matches - remove it"
      self atHash: hash putKey: nil.
      self atHash: hash putValue: nil 
   ].
numElements := numElements - 1
%

category: 'Private'
method
_removeKey: aKey ifAbsent: aBlock

"Removes the key/value pair with key aKey from the receiver and returns
 the value.  If no key/value pair is present with key aKey, evaluates
 the zero-argument block aBlock and returns the result of that evaluation."

"Reimplemented for direct inheritance by IdentityDictionary and below.
 Do not reimplement below KeyValueDictionary."

| hash thisKey collisionBkt aValue lastPair |

hash := self hashFunction: aKey.
nil == (thisKey := (self keyAt: hash))

   ifTrue: [ "It might be in a collision bucket"
      collisionBkt := self valueAt: hash.
      nil == collisionBkt
         ifTrue: [ ^ self _reportKeyNotFound: aKey with: aBlock ] .
      aValue := collisionBkt
         removeKey: aKey
         ifAbsent: [ ^ self _reportKeyNotFound: aKey with: aBlock]. "fix 11884"
      "If we got this far, a key/value pair was removed from collisionBkt"
      numCollisions := numCollisions - 1.
      (collisionBkt size <= 1) ifTrue: [
         "We don't need the collision bucket anymore.
          Put its last key/value pair in our table."
         lastPair := collisionBkt firstPair.
         self atHash: hash putKey: lastPair key.
         self atHash: hash putValue: lastPair value ]]

   ifFalse: [ "There is a key/value pair in this slot"
      (self compareKey: aKey with: thisKey)
         ifFalse: [ ^ self _reportKeyNotFound: aKey with: aBlock ] .
      "The key matches - remove it"
      aValue := self valueAt: hash.
      self atHash: hash putKey: nil.
      self atHash: hash putValue: nil ].

numElements := numElements - 1.
^aValue
%

category: 'Accessing'
method
collisionLimit

"Returns the value of the collisionLimit instance variable."

^collisionLimit
%

category: 'Private'
method
keyAt: hashOffset

"Private.  Returns the key at the specified hash offset."

^ self _at: (2 * hashOffset - 1)
%

category: 'Accessing'
method
tableSize

"Returns the size of the primary hash table."

^tableSize
%

category: 'Accessing'
method
numCollisions

"Returns the total number of collisions, the sum of the number of key/value
 pairs in all collision buckets."

^ numCollisions
%

category: 'Private'
method
valueAt: hash

"Returns the value at the specified hash offset."

^self _basicAt: (2 * hash)
%

category: 'Accessing'
method
size

"(R) Returns the number of key/value pairs in the receiver."

^numElements
%

category: 'Accessing'
method
numElements

"Same as the size method."

^numElements
%

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

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

| hash hashKey collisionBkt |

nil == aKey ifTrue:[ ^self _reportKeyNotFound: aKey with: aBlock ].
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey
  ifTrue: [ collisionBkt := self valueAt: hash.
            nil == collisionBkt
              ifFalse: [ ^collisionBkt at: aKey ifAbsent: aBlock ]
          ]
  ifFalse: [ (self compareKey: aKey with: hashKey)
               ifTrue: [ ^self valueAt: hash ] ].
^ self _reportKeyNotFound: aKey with: aBlock
%

category: 'Accessing'
method
keys

"Returns an IdentitySet containing the receiver's keys."

| result |
result := IdentitySet new .
self keysDo:[ :aKey | result add: aKey ].
^ result
%

category: 'Private'
method
atHash: hashIndex putKey: aKey

"Updates the hash table by storing aKey at the specified hashIndex.

 Note: This method overwrites the key value at the given hashIndex and
 destroys the ordering of the keys in the receiver.  Returns aKey."

((hashIndex <= 0) | (hashIndex > tableSize))
  ifTrue: [hashIndex _error: #rtErrArgOutOfRange ].
self _basicAt: (2 * hashIndex - 1) put: aKey
%

category: 'Private'
method
keyAtHash: hashIndex 

((hashIndex <= 0) | (hashIndex > tableSize))
  ifTrue: [hashIndex _error: #rtErrArgOutOfRange ].
^self _basicAt: (2 * hashIndex - 1)
%

category: 'Private'
method
atHash: hashIndex putValue: aValue

"Updates the hash table by storing aValue at the specified hashIndex.
 Returns aValue."

((hashIndex <= 0) | (hashIndex > tableSize))
  ifTrue: [ ^ hashIndex _error: #rtErrArgOutOfRange ].
^self _basicAt: (2 * hashIndex) put: aValue
%

category: 'Private'
method
valueAtHash: hashIndex 

((hashIndex <= 0) | (hashIndex > tableSize))
  ifTrue: [hashIndex _error: #rtErrArgOutOfRange ].
^self _basicAt: (2 * hashIndex)
%

category: 'Updating'
method
collisionLimit: aLimit

"Sets the collision limit to aLimit."

"the value 536870911 is special and may only be installed by instance methods.
 This value is used to prevent recursive rebuild."

aLimit _isSmallInteger ifFalse:[  "gemstone64 explicit constraint check"
  ^ aLimit _error: #rtErrBadArgKind args: #[SmallInteger]
  ].
aLimit > 0 ifFalse:[ ^ aLimit _error: #rtErrArgNotPositive ].
aLimit >= 536870911 
  ifTrue:[ collisionLimit := 536870910 ]
  ifFalse:[ collisionLimit := aLimit ]
%

! Fix 33779
category: 'Private'
method
_at: aKey put: aValue

"Stores the aKey/aValue pair in the hash dictionary.  Rebuilds the hash table
 if the addition caused the number of collisions to exceed the limit allowed."

"Duplicate of at:put: for direct inheritance by subclasses of
 IdentityDictionary.  Do not reimplement in subclasses of KeyValueDictionary."

| hash hashKey hashValue collisionBkt numAdd |
nil == aKey ifTrue: [ ^ self _error: #rtErrNilKey ].
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey ifTrue: [ 
  collisionBkt := self valueAt: hash.
  nil == collisionBkt ifTrue: [ 
    self atHash: hash putKey: aKey.
    self atHash: hash putValue: aValue.
    numElements := numElements + 1 
  ] ifFalse: [  | numAdd2 |
    numAdd2 := collisionBkt at: aKey put: aValue keyValDict_coll: self.
    numAdd2 > 0 ifTrue:[
      numElements := numElements + 1.
      collisionBkt size > 1 ifTrue:[ 
        numCollisions := numCollisions + 1
      ].
    ].
  ]
] ifFalse: [ 
  (self compareKey: aKey with: hashKey) ifTrue: [ 
    self atHash: hash putKey: aKey.
    self atHash: hash putValue: aValue 
  ] ifFalse: [ 
    hashValue := self valueAt: hash.
    collisionBkt := self collisionBucketClass new.
    collisionBkt assignToSegment: self segment.
    collisionBkt keyValueDictionary: self.
    self atHash: hash putKey: nil.
    self atHash: hash putValue: collisionBkt.
    collisionBkt at: hashKey put: hashValue keyValDict_coll: self.
    numElements := numElements + 1.
    numAdd := collisionBkt at: aKey put: aValue keyValDict_coll: self.
    numAdd > 0 ifTrue:[
      collisionBkt size > 1 ifTrue:[
        numCollisions := numCollisions + 1 
      ].
    ]
  ] 
].
(numCollisions > collisionLimit) ifTrue: [
  self rebuildTable: (Integer _selectedPrimeGreaterThan: tableSize * 2)
].
^aValue
%

! Fix 33779
category: 'Updating'
method
at: aKey put: aValue

"Stores the aKey/aValue pair in the hash dictionary.  Rebuilds the hash table
 if the addition caused the number of collisions to exceed the limit allowed."

"Code is duplicated in _at:put:"

| hash hashKey hashValue collisionBkt numAdd |
nil == aKey ifTrue: [ ^ self _error: #rtErrNilKey ].
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey ifTrue: [ 
  collisionBkt := self valueAt: hash.
  nil == collisionBkt ifTrue: [ 
    self atHash: hash putKey: aKey.
    self atHash: hash putValue: aValue.
    numElements := numElements + 1 
  ] ifFalse: [  | numAdd2 |
    numAdd2 := collisionBkt at: aKey put: aValue keyValDict_coll: self.
    numAdd2 > 0 ifTrue:[
      numElements := numElements + 1.
      collisionBkt size > 1 ifTrue:[ 
        numCollisions := numCollisions + 1
      ].
    ].
  ]
] ifFalse: [ 
  (self compareKey: aKey with: hashKey) ifTrue: [ 
    self atHash: hash putKey: aKey.
    self atHash: hash putValue: aValue 
  ] ifFalse: [ 
    hashValue := self valueAt: hash.
    collisionBkt := self collisionBucketClass new.
    collisionBkt assignToSegment: self segment.
    collisionBkt keyValueDictionary: self.
    self atHash: hash putKey: nil.
    self atHash: hash putValue: collisionBkt.
    collisionBkt at: hashKey put: hashValue keyValDict_coll: self.
    numElements := numElements + 1.
    numAdd := collisionBkt at: aKey put: aValue keyValDict_coll: self.
    numAdd > 0 ifTrue:[
      collisionBkt size > 1 ifTrue:[
        numCollisions := numCollisions + 1 
      ].
    ]
  ] 
].
(numCollisions > collisionLimit) ifTrue: [
  self rebuildTable: (Integer _selectedPrimeGreaterThan: tableSize * 2)
].
^aValue
%

category: 'Clustering'
method
clusterDepthFirst

"This method clusters the receiver and its named instance variables and the
 key/value pairs in depth-first order.  Returns true if the receiver has
 already been clustered during the current transaction; returns false
 otherwise."

self cluster ifTrue: [ ^ true ].

1 to: self class instSize do:[ :i | 
  (self instVarAt: i) clusterDepthFirst 
  ].
1 to: tableSize * 2 by: 2 do: [ :tableIndex | | aKey collisionBkt |
  nil == (aKey := self _at: tableIndex) ifTrue: [
    nil == (collisionBkt := self _at: (tableIndex + 1)) ifFalse: [
      collisionBkt cluster .
      1 to: collisionBkt _basicSize by: 2 do: [ :j |
        nil == (aKey := collisionBkt _at: j) ifFalse: [
          aKey clusterDepthFirst. 
          (collisionBkt _at: j + 1) clusterDepthFirst.
          ].
        ].
      ].
    ]
  ifFalse: [
    aKey clusterDepthFirst .
    (self _at: tableIndex + 1) clusterDepthFirst.
    ].
  ].
^ false
%

category: 'Copying'
method
copy

"Returns a copy of the receiver."

|newKeyValueDict collisionBkt|
newKeyValueDict := super copy.
1 to: tableSize do:
  [ :index | nil == (self keyAt: index)
      ifTrue: [ collisionBkt := self valueAt: index.
         nil == collisionBkt
           ifFalse: [ collisionBkt := (self valueAt: index) copy.
                      collisionBkt keyValueDictionary: newKeyValueDict.
                      newKeyValueDict atHash: index putValue: collisionBkt. ]  ]
  ].
^newKeyValueDict
%

! selectValuesAsArray: inherited
! select:  inherited
! collect: inherited
! inherited: detectValues: aBlock ifNone: exceptionBlock

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."

|saveTable index saveCollLimit|

collisionLimit == 536870911 ifTrue:[ 
  ^ self  "prevent recursive rebuild"
  ].

saveTable := Array new: (self size * 2).
index := 0.
self keysAndValuesDo: [ :aKey :aValue |  
  index := index + 1.
  saveTable at: index put: aKey.
  index := index + 1.
  saveTable at: index put: aValue  
  ].
self tableSize: newSize.  "installs new collision limit "
saveCollLimit := collisionLimit . "save new collision limit "
collisionLimit := 536870911 . "prevent recursive rebuild"
1 to: index by: 2 do: [ :i |
  self at: (saveTable at: i "key") put: (saveTable at: i + 1 "value") 
  ].
collisionLimit := saveCollLimit .
				"deleted   'reduce garbage' code"
^self
%

category: 'Initializing'
method
_gciInitialize

"Private."

tableSize == nil
  ifTrue: [ self initialize: 5 ]
  ifFalse: [ self initialize: tableSize ]
%

category: 'Private'
method
_initializeWithoutClear: newSize

"Private. Initializes the instance variables of the receiver to be an empty
 KeyValueDictionary of the specified size. Does not clear the contents
 of the receiver - assumes they are all nil."

tableSize := newSize.
numElements := 0.
numCollisions := 0.
collisionLimit := newSize . "OC_KEY_VALUE_DICT_COLL_LIMIT_RATIO is 1"

^self
%

category: 'Initializing'
method
initialize: itsSize

"Initializes the instance variables of the receiver to be an empty
 KeyValueDictionary of the specified size."

| newSize |

newSize := itsSize .

(newSize <= 0)
  ifTrue: [
    newSize _error: #rtErrArgNotPositive.  
    newSize := 3 
    ].

self _basicSize: 0.  "Set size to 0 and restore to nil any entries"
self _basicSize: newSize * 2. 
self _initializeWithoutClear: newSize.
^self
%

category: 'Initializing'
method
tableSize: newSize

"Sets the table size to a new value."

"When used during rehashing a dictionary the sender must have already
 copied all key/value pairs to a temporary object to save the contents
 of the dictionary."

| physSize aBucket |

(newSize <= 0)
  ifTrue: [newSize _error: #rtErrArgNotPositive  .  ^ self ].

"dereference old collision buckets from their parent to avoid problems
 when resolving symbol canonicalization at commit."
1 to: self _basicSize by: 2 do:[:j |
  (self basicAt: j) == nil ifTrue:[ "no key present, so check for a bucket"
    (aBucket := self basicAt: j + 1) ~~ nil ifTrue:[
       aBucket _removeAll . "dereference from parent"
      ].
    ].
  ].

physSize := newSize * 2 .

self _basicSize: physSize .
self _copyNilIntoSelfFrom: 1 to: physSize.
numElements := 0.
numCollisions := 0.
collisionLimit := newSize . "OC_KEY_VALUE_DICT_COLL_LIMIT_RATIO is 1"
tableSize := newSize .
				"deleted   'reduce garbage' code"
%

category: 'Initializing'
method
_copyNilIntoSelfFrom: index1 to: index2

    <primitive: 607>

(index1 > index2)
  ifTrue:[ index1 _error: #rtErrBadCopyFromTo args: #[index2]].

(index1 < 1) ifTrue:[ self _errorIndexOutOfRange: index1].

(index2 > (self size + 1)) ifTrue:[ self _errorIndexOutOfRange: index2].

self _primitiveFailed: #_copyNilIntoSelfFrom:to: 
%

category: 'Statistics'
method
statistics

"Returns a Dictionary containing statistics that can be useful in determining
 the performance of a hash dictionary.  The dictionary contains the following
 information:

 TotalCollisionBuckets - The number of collision buckets required to
                         implement the hash dictionary.

 AveragePairsPerBucket - The average number of key/value pairs in each bucket.

 LargestBucket         - The bucket having the most key/value pairs.  This
                         bucket contains the most keys for which the hash
                         function did not provide a good distribution over the
                         range of values in the table."

| hashKey collisionBkt bktCount pairCount maxBkt maxBktSize result|

bktCount := 0.
pairCount :=0.
maxBktSize := 0.
1 to: tableSize do: [ :tableIndex |
  hashKey := self keyAt: tableIndex.
  collisionBkt := self valueAt: tableIndex.
  (nil == hashKey _and:[ nil ~~ collisionBkt]) ifTrue:[ 
    bktCount := bktCount + 1.
    pairCount := pairCount + collisionBkt size.
    (collisionBkt size > maxBktSize) ifTrue: [ 
      maxBktSize := collisionBkt size.
      maxBkt := collisionBkt
      ] 
    ]
  ].
result := SymbolDictionary new.
result at: #TotalCollisionBuckets put: bktCount.
(bktCount > 0)
  ifTrue: [result at: #AveragePairsPerBucket put: pairCount // bktCount]
  ifFalse: [result at: #AveragePairsPerBucket put: 0].
result at: #LargestBucket put: maxBkt.
^result
%

category: 'Private'
method
_at: aKey otherwise: defaultValue

"Returns the value that corresponds to aKey.  If no such key/value pair
 exists, returns the given alternate value."

"Duplicate of at:otherwise: for direct inheritance by things 
 below IdentityDictionary.  Do not reimplement below KeyValueDictionary."

| hash hashKey collisionBkt |

nil == aKey ifTrue:[ ^ defaultValue ].
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey
  ifTrue: [ collisionBkt := self valueAt: hash.
            nil == collisionBkt
              ifFalse: [ ^collisionBkt at: aKey otherwise: defaultValue ]
          ]
  ifFalse: [ (self compareKey: aKey with: hashKey)
               ifTrue: [ ^self valueAt: hash ] ].
^ defaultValue
%

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

"Returns the value that corresponds to aKey.  If no such key/value pair
 exists, returns the given alternate value."

| hash hashKey collisionBkt |

nil == aKey ifTrue:[ ^ aValue ].
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey
  ifTrue: [ collisionBkt := self valueAt: hash.
            nil == collisionBkt
              ifFalse: [ ^collisionBkt at: aKey otherwise: aValue ]
          ]
  ifFalse: [ (self compareKey: aKey with: hashKey)
               ifTrue: [ ^self valueAt: hash ] ].
^ aValue
%

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

"Returns the key that corresponds to aKey.  If no such key/value pair
 exists, returns the given alternate value.

 Note that the keyAt: method is private and does not have behavior that is
 compatible with this method."

| hash hashKey collisionBkt |

nil == aKey ifTrue:[ ^ self _error: #rtErrNilKey ] .
hash := self hashFunction: aKey.
hashKey := self keyAt: hash.
nil == hashKey
  ifTrue: [ collisionBkt := self valueAt: hash.
            nil == collisionBkt
              ifFalse: [ ^ collisionBkt keyAt: aKey otherwise: aValue ]
          ]
  ifFalse: [ (self compareKey: aKey with: hashKey)
               ifTrue: [ ^ hashKey ] ].
^ aValue
%

category: 'Private'
method
collisionBucketClass

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

^ CollisionBucket
%

category: 'Private'
method
compareKey: key1 with: key2

"Returns whether key1 is equivalent to key2."

^ key1 = key2
%

category: 'Locking Support'
method
_lockableValues

"Returns an Array of the receiver's keys and values."

| result |

result := Array new .
self keysAndValuesDo: [:aKey :aValue |
  result add: aKey .
  result add: aValue .
] .
^ result
%

category: 'Searching'
method
_idxOccurrencesOf: aValue

"Dictionaries can only contain Associations."

^ 0
%

! remove duplicate implementation of firstPublic...

category: 'Accessing the Class Format'
classmethod
firstPublicInstVar

"Returns the index of the first user-visible instance variable defined in this
 class, whether or not this class actually has user-visible instance variables."

^ 5
%

category: 'Storing and Loading'
classmethod
loadFrom: passiveObj mappingToClass: newClass

"Reads from passiveObj the passive form of an object with named instance
 variable format.  Converts the object to its active form by loading the
 information into a new instance of the receiver.  Returns the new instance."

| newDict oldDict size |
(passiveObj version >= 500 _or:[ newClass == self]) ifTrue:[ 
  size := passiveObj readSize.
  newDict := self new.
  newDict loadFrom: passiveObj size: size.
  ]
ifFalse:[
  "handle activation of objects written by 4.1.3"

  (self instSize - self firstPublicInstVar) > 
  (newClass instSize - newClass firstPublicInstVar) ifTrue:[
    self _halt:'Unable to map subclass of ' + self name +
               ' to class ' + newClass name  .
    ].
  newDict := newClass new .
  passiveObj hasRead: newDict .
  size := passiveObj readSize. 
  oldDict := self new .
  oldDict basicLoadFromNoRead: passiveObj size: size .
  oldDict keysAndValuesDo:[:aKey :aValue | newDict at: aKey put: aValue ].
  oldDict initialize: 1 .
].
^ newDict
%

category: 'Storing and Loading'
method
loadVaryingFrom: passiveObj size: varyingSize

"Reads the varying part of the receiver from the given passive object.
 Does not record the receiver as having been read.  Does not read the
 receiver's named instance variables, if any."

passiveObj version >= 500 ifTrue:[
  1 to: varyingSize do: [:i |
    self at: passiveObj readObject"aKey" put: passiveObj readObject"aValue"
    ].
  ] 
ifFalse:[ super loadVaryingFrom: passiveObj size: varyingSize ].
%

category: 'Storing and Loading'
method
basicWriteTo: passiveObj

"Converts the receiver to its passive form and writes that information on
 passiveObj."

| s cls ivs c |
  cls := self class.
  passiveObj writeClass: cls.

  ivs := cls _instVarNames .

  passiveObj writeSize: (s := self size) .

  cls firstPublicInstVar to: cls instSize do: [:i |
    (self shouldWriteInstVar: (ivs at: i)) ifTrue: [
      passiveObj writeObject: (self instVarAt: i) named: (ivs at: i)
    ].
  ].

  passiveObj endNamedInstVars.

  c := 0.
  self keysAndValuesDo:[ :aKey :aValue | 
    passiveObj writeObject: aKey; writeObject: aValue .
    c := c + 1.
    c > 49 ifTrue: [
      passiveObj lf.
      c := 0.
      ].
    ].

  passiveObj cr
%

category: 'Private'
method
_deferredGciUpdateWith: valueArray

"Private."

1 to: valueArray size by: 2 do:[:j |
  self at: (valueArray at: j) put: (valueArray at: j + 1)
  ].
%

category: 'Private'
method
_collisionBucketsDo: aBlock

"Private.  Executes the given one-argument block for each collision bucket
 in the receiver."

| collisionBkt |

1 to: tableSize * 2 by: 2 do: [ :tableIndex |
  nil == (self _at: tableIndex)
    ifTrue: [
      nil == (collisionBkt := self _at: (tableIndex + 1))
        ifFalse: [ aBlock value: collisionBkt ]
    ]
]
%

category: 'Storing and Loading'
method
loadNamedIVsFrom: passiveObj

"Reads named instance variables from the given passive object.  The
 first instance variable should already have been parsed and be
 available in the passiveObj argument."

| name offset nameSym aValue |

passiveObj version >= 500 ifTrue:[ ^ super loadNamedIVsFrom: passiveObj ].

[ name := passiveObj ivName.
  name ~~ nil ifTrue: [
    nameSym := Symbol _existingWithAll: name .
    nameSym ~~ nil ifTrue:[
      offset := self class _ivOffsetOf: nameSym.
      offset ~~ nil ifTrue:[
        aValue := passiveObj ivValue .
        offset == 3 "collisionLimit" ifTrue:[
          aValue := (tableSize * 100) min: 500000000 .
          ].
        self instVarAt: offset put: aValue .
        ]
      ifFalse:[ self obsoleteInstVar: nameSym value: passiveObj ivValue].
    ]
    ifFalse:[ 
      self obsoleteInstVar: name value: passiveObj ivValue
    ].
    passiveObj readNamedIV
  ]
  ifFalse: [
    false
  ]
] untilFalse.

passiveObj skipNamedInstVars.
%

category: 'Repository Conversion'
method
rehashForConversion

"Private. Rehashes the receiver because the hash values of some of its keys
 may have changed.  Returns true if the rehashing is successful.  Returns false
 otherwise."

| newSize |

newSize := (Integer _selectedPrimeGreaterThan: numElements) max: 
           (Integer _selectedPrimeGreaterThan: (tableSize - 1)).
"The following helps bypass a bug in one customer's repository."
(numElements < 0) ifTrue: [ numElements := 0 ].
self rebuildTable: newSize .
^ true.
%

category: 'Searching'
method
includesIdenticalAssociation: anAssociation

"(R) Returns true if anAssociation is identical to one of the Associations of 
 the receiver.  Returns false otherwise.

 KeyValueDictionaries do not store Associations. So this message is not
 meaningful for this class."

^ self shouldNotImplement: #includesIdenticalAssociation.
%

category: 'Private'
method
_resetParentRef

"Private. After a become:, the parent refs of the collisionBuckets must 
 be reset to point to the correct parent."

self _collisionBucketsDo: [:collisionBkt |
  collisionBkt keyValueDictionary: self].
%

category: 'Private'
method
_checkNumCollisions

"Provided for use in testing only. Checks the consistency of
 the collision count in the dictionary against the contents of its buckets.
 Returns self of the dictionary is ok, otherwise generates an error."

| tableLimit mySize totalCollis totalElem |
tableLimit := tableSize * 2 .
totalCollis := 0 .
totalElem := 0 .
1 to: tableLimit by: 2 do: [ :tableIndex | | aKey |
  aKey := self _at: tableIndex .
  aKey == nil ifTrue: [ | collisionBkt |
    collisionBkt := self _at: (tableIndex + 1) .
    collisionBkt ~~ nil ifTrue: [
      collisionBkt numElements > 0 ifTrue:[
        totalCollis := totalCollis + (collisionBkt numElements - 1).
        totalElem := totalElem + collisionBkt numElements .
      ] ifFalse: [
        collisionBkt numElements < 0 ifTrue:[ nil error:'underflow' ].
      ]
    ].
  ] ifFalse:[ 
    totalElem := totalElem + 1 . 
  ].
].
totalCollis = numCollisions ifFalse:[ nil error:'bad numCollisions'].
mySize := self size .
totalElem = mySize ifFalse:[ nil error:'bad size'].
^ self
%

! added _markDirty to fix 35598
category: 'Private'
method
_markDirty

  "used to make the root object of a dictionary written, when
   replacing a value for an existing key in a collision bucket."

  numElements := numElements
%

category: 'Updating'
method: KeyValueDictionary
changeToSegment: segment

"(R) Assigns the receiver and all its components to the given segment. Returns
 the receiver."

| collisionBkt |

self assignToSegment: segment.
1 to: tableSize * 2 by: 2 do: [ :tableIndex |
  ( nil == (self _at: tableIndex) _and:
  [ (collisionBkt := self _at: (tableIndex + 1)) ~~ nil ] )
    ifTrue: [ collisionBkt assignToSegment: segment ]
].
^ self.
%

category: 'Repository Conversion'
method: KeyValueDictionary
fixReferencesInFirstPass

"Return whether this object should have references to Float, SmallFloat, 
 LargePositiveInteger and LargeNegativeInteger fixed inthe first pass.
 false means fix them in the 2nd pass.  KeyValueDictionary object can 
 be part of a Set or Bag, so we do those later"

^self class ~~ KeyValueDictionary
%
