!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: rcindexbucket.gs,v 1.16 2008-01-09 22:50:13 stever Exp $
!
! Superclass Hierarchy:
!   RcIndexBucket, RcCollisionBucket, CollisionBucket, Array,
!   SequenceableCollection, Collection, Object.
!
! class created in idxclasses.topaz
!=========================================================================

removeallmethods RcIndexBucket
removeallclassmethods RcIndexBucket

category: 'For Documentation Installation only'
classmethod: RcIndexBucket
installDocumentation

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

txt := (GsDocText new) details:
'An RcIndexBucket is an RcCollisionBucket that is used by the indexing
 subsystem to store a collection of key/value/pathTerm triples.  It provides
 reduced-conflict support for indexes.' .
doc documentClassWith: txt.

self description: doc.
%

category: 'Instance Creation'
classmethod: RcIndexBucket
new

"Returns a new instance of RcIndexBucket."
^ self new: 0
%

category: 'Constants'
classmethod: RcIndexBucket
entrySize

"Returns three, the size of an entry in the bucket (key, term, value)."

^ 3
%

! ------------------- Instance methods for RcIndexBucket
category: 'Searching'
method: RcIndexBucket
_binarySearchCoveringKey: aKey term: pathTerm

"Returns the index for the first entry in which aKey is found utilizing a
 binary search.  This is the first entry whose key >= aKey."

<primitive: 115>
self _primitiveFailed: #_binarySearchCoveringKey:term: .
self _uncontinuableError
%

category: 'Updating'
method: RcIndexBucket
at: aKey put: aValue term: pathTerm root: indexDict logging: aBoolean

"Places the given key/value/pathTerm triplet in the receiver.  Returns whether
 the key/value pair already exists in the receiver."
| index valSet value offset offsetMinus1 offsetMinus2 |
index := self _binarySearchCoveringKey: aKey term: pathTerm.
offset := self valueOffsetFor: index.

" if it goes on the end ... "
index > numElements
  ifTrue: [
    " grow the receiver if necessary "
    self _basicSize < offset
      ifTrue: [
        self _basicSize: (offset + 30).
        " initialize the cache if necessary "
        numElements == 0
          ifTrue: [
            1 to: self _numCacheSlots do: [ :i |
              self _basicAt: i put: 0
            ]
          ]
      ].

    " hard coded for performance "
    self _basicAt: offset - 2 put: aKey.
    self _basicAt: offset - 1 put: pathTerm.
    self _basicAt: offset put: aValue.
    numElements := numElements + 1.
    ^ false
  ].

" if key is already in bucket "
offsetMinus1 := offset - 1 .
offsetMinus2 := offset - 2 .
( aKey == (self _rcAt: offsetMinus2 ) _and:
[ pathTerm == (self _rcAt: offsetMinus1) ] )

  ifTrue: [
    value := self _rcAt: offset.
    " see if there are already multiple values "
    (self _isBucketValueBagAt: offset)
      ifTrue: [  | systm |
        " put the BucketValueBag in the reduced-conflict read set(RcReadSet)  "
        systm := System .
        systm _addToRcReadSet: value includingAllNodes: true.
        " put an entry in the conflict objects dictionary "
        systm redoLog addLargeConflictObject: value for: indexDict.
        value add: aValue
      ]
      ifFalse: [ " create value Bag "
        valSet := BucketValueBag basicNew.
        valSet assignToSegment: self segment.
        valSet add: value.
        valSet add: aValue.
        self _basicAt: offset put: valSet.

        System _addToRcReadSet: valSet includingAllNodes: true.
        " put an entry in the conflict objects dictionary "
        System redoLog addConflictObject: valSet for: indexDict.

        self insertedBucketValueBagAt: offset.
      ].
    ^ true
  ]
  ifFalse: [ " key not found "
    " move entries to the right (hard coded for performance) "
    self _largeInsertAt: offsetMinus2
      from: nil "insert nils" fromStart: 1 fromEnd: 3 
      numToMoveDown: (numElements * 3) + self _numCacheSlots - offsetMinus2 + 1 .

    " hard coded for performance "
    self _basicAt: offsetMinus2 put: aKey.
    self _basicAt: offsetMinus1 put: pathTerm.
    self _basicAt: offset put: aValue.
    " only increment numElements if a key is being added. increment BEFORE insertedEntryAt: called"
    numElements := numElements + 1.
    self insertedEntryAt: offset.
    ^ false
  ]
%

category: 'Updating'
method: RcIndexBucket
at: anIndex putKey: aKey

"Stores the key aKey into the key part of the key/value/pathTerm triplet
 referenced by atIndex."

self _basicAt: (anIndex * "self entrySize" 3) - 2 put: aKey
%

category: 'Updating'
method: RcIndexBucket
at: anIndex putTerm: pathTerm

"Stores the pathTerm into the pathTerm part of the key/value/pathTerm triplet
 referenced by atIndex."

self _basicAt: (anIndex * "self entrySize" 3 - 1) put: pathTerm
%

category: 'Updating'
method: RcIndexBucket
at: anIndex putValue: aValue

"Stores the value aValue into the value part of the key/value/pathTerm triplet
 referenced by atIndex."

self _basicAt: (anIndex * "self entrySize" 3) put: aValue
%

category: 'Accessing'
method: RcIndexBucket
at: aKey term: pathTerm ifAbsent: aBlock

"Returns the value that corresponds to aKey/pathTerm by searching the elements
 in the bucket.  If no such key/value/pathTerm triplet exists, returns the
 result of evaluating the zero-argument block aBlock."

| index |
index := self searchForKey: aKey term: pathTerm.
index ~~ nil
    ifTrue: [ ^ self valueAt: index ]
    ifFalse: [
        aBlock _validateClass: BlockClosure.
        ^ aBlock value
    ]
%

category: 'Constants'
method: RcIndexBucket
entrySize

"Returns three, the size of an entry in the bucket (key, term, value)."

^ self class entrySize
%

category: 'Accessing'
method: RcIndexBucket
keyAt: index

"Returns the key at the specified index."

^ self _rcAt: ("self entrySize" 3 * index - 2)
%

category: 'Removing'
method: RcIndexBucket
removeKey: aKey
value: aValue
term: pathTerm
root: indexDict
logging: aBoolean
ifAbsent: aBlock

"Removes the key/value/pathTerm triplet with the given key and path term.
 Executes the zero-argument block if not found.  Returns whether there are any
 more values for the key/term."

| keyIndex valOrSet eSize delOffset offset |

keyIndex := self searchForKey: aKey term: pathTerm.

keyIndex == nil
  ifTrue: [ " key not found "
    aBlock value.
    ^ false
  ]
  ifFalse: [
    valOrSet := self valueAt: keyIndex.
    " do not put in rcReadSet (to fix bug 10796)
    System _addToRcReadSet: valOrSet includingAllNodes: true.
    "

    offset := self valueOffsetFor: keyIndex.
    (self _isBucketValueBagAt: offset)
      ifTrue: [ " remove the value from the bucket value set "

        " put an entry in the conflict objects dictionary "
        System redoLog addLargeConflictObject: valOrSet for: indexDict.

        valOrSet remove: aValue ifAbsent: aBlock.
        "Now put the BucketValueBag into the rcReadSet, since it is a modified index object"
        System _addToRcReadSet: valOrSet includingAllNodes: true.

        " if only 1 left, move it to the receiver "
        valOrSet size == 1
          ifTrue: [
            " do not put in rcReadSet
            System _addToRcReadSet: (valOrSet _at: 1) includingAllNodes: true.
            "
            self at: keyIndex putValue: (valOrSet _at: 1).

            self removedBucketValueBagAt: offset.
          ].
        ^ true
      ]
      ifFalse: [ " key has a single value "
        (aValue == valOrSet)
          ifTrue: [
            eSize := "self entrySize"  3 .
            delOffset := keyIndex - 1 * eSize + self _numCacheSlots + 1 .
            self _deleteNoShrinkFrom: delOffset to: delOffset + eSize - 1 .
            self removedEntryAt: offset.
            "decrement numElements AFTER removedEntryAt: called"
            numElements := numElements - 1.
            ^ false
          ]
          ifFalse: [ " values do not match "
            aBlock value.
            ^ true
          ]
      ]
  ]
%

category: 'Searching'
method: RcIndexBucket
searchForKey: aKey term: pathTerm

"Returns the index that matches the given key/pathTerm.  If not found, returns
 nil."

<primitive: 175>
self _primitiveFailed: #searchForKey:term: .
self _uncontinuableError
%

category: 'Accessing'
method: RcIndexBucket
tableSize

"Returns the number of key/value/pathTerm pairs my current size has the
 capacity for."

^ ((self _basicSize - self _numCacheSlots) // 3) max: 0
%

category: 'Accessing'
method: RcIndexBucket
termAt: index

"Returns the term at the specified index."

^ self _rcAt: ("self entrySize" 3 * index - 1)
%

category: 'Accessing'
method: RcIndexBucket
valueAt: index

"Returns the value at the specified index."

^ self _rcAt: ("self entrySize" 3 * index)
%

category: 'Accessing'
method: RcIndexBucket
valueOffsetFor: index

"Returns the value at the specified index."

^ "self entrySize" 3 * index
%

category: 'Accessing'
method: RcIndexBucket
at: aKey term: pathTerm otherwise: aValue

"Returns the value that corresponds aKey/pathTerm by searching the elements in
 the bucket.  If no such key/value/pathTerm triplet exists, returns aValue."

<primitive: 180>
self _primitiveFailed: #at:term:otherwise: .
self _uncontinuableError
%

category: 'Accessing'
method: RcIndexBucket
firstAt: aKey term: pathTerm otherwise: aValue

"Returns the value that corresponds aKey/pathTerm by searching the elements in
 the bucket.  If no such key/value/pathTerm triplet exists, returns aValue.
 If the value is a BucketValueBag, returns the first object in the Bag."

| val |
val := self at: aKey term: pathTerm otherwise: aValue.
(BucketValueBag _hasInstance: val)
  ifTrue: [ ^ val _at: 1 ]
  ifFalse: [ ^ val ]
%

category: 'Accessing'
method: RcIndexBucket
at: aKey term: pathTerm

"Returns the value that corresponds aKey/pathTerm by searching the elements in
 the bucket.  if no such key/value/pathTerm triplet exists, raise an error."

| index |
index := self searchForKey: aKey term: pathTerm.
index ~~ nil
    ifTrue: [ ^ self valueAt: index ]
    ifFalse: [ ^ self _errorKeyNotFound: aKey ]
%

category: 'Constants'
method: RcIndexBucket
_numCacheSlots

"Returns the number of initial slots reserved for cached values."

^ 0
%

category: 'Testing'
method: RcIndexBucket
_isBucketValueBagAt: offset

"Returns whether the object at the given offset in the receiver is a
BucketValueBag."

^ BucketValueBag _hasInstance: (self _rcAt: offset)
%

category: 'Updating'
method: RcIndexBucket
insertedBucketValueBagAt: offset

"Does nothing."

%

category: 'Updating'
method: RcIndexBucket
removedBucketValueBagAt: offset

"Does nothing."

%

category: 'Updating'
method: RcIndexBucket
reset

"Resets all entries to nil and the number of elements to zero."

super size: self _numCacheSlots.
numElements := 0.
1 to: self _numCacheSlots do: [ :i |
  self _basicAt: i put: 0
].
System _addToRcReadSet: self includingAllNodes: false.
%

category: 'Updating'
method: RcIndexBucket
insertedEntryAt: offset

"Does nothing."

%

category: 'Updating'
method: RcIndexBucket
removedEntryAt: offset

"Does nothing."

%

category: 'Updating'
method: RcIndexBucket
_refreshBucketCacheReportingInto: aString

"Does nothing."

%

! Deleted:  _obj: anObject isIdenticalTo: anotherObject

! deleted _canonicalizeSymbolAt: offset oldSymbol: old newSymbol: newSymbol

