!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: deplistbucket.gs,v 1.10 2008-01-09 22:50:10 stever Exp $
!
! Superclass Hierarchy:
!   DepListBucket, Array, SequenceableCollection, Collection, Object.
!
! class created in idxclasses.topaz
!=========================================================================

removeallmethods DepListBucket
removeallclassmethods DepListBucket

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

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

txt := (GsDocText new) details:

'A DepListBucket is a collision bucket for a DepListTable.' .
doc documentClassWith: txt.

txt := (GsDocText new) details:
'The number of dependency lists in the instance.'.
doc documentInstVar: #numElements with: txt.

self description: doc.
%

category: 'Instance Creation'
classmethod: DepListBucket
new: aSize

"Returns a DepListBucket with the given capacity of entries."


^ (super new: aSize) initialize
%

category: 'Instance Creation'
classmethod: DepListBucket
new

"Returns a DepListBucket with a default capacity of ten entries."


^ self new: 3
%

! ------------------- Instance methods for DepListBucket

category: 'Initializing'
method: DepListBucket
initialize

"Initializes the instance variable of the receiver."


numElements := 0.
%

category: 'Updating'
method: DepListBucket
at: depList

"Returns the dependency list in the receiver that is equivalent to the given
 dependency list.  If one does not exist, add the given dependency list to the
 receiver and returns the given dependency list.  If one is found, the given
 dependency list is sized to zero."

<primitive: 215>
" primitive will fail if the receiver is a large object; do the work in
  GemStone Smalltalk "
| dl lowPt highPt i |
numElements == 0
  ifTrue: [
    numElements := 1.
    self _at: 1 put: depList.
    depList assignToSegment: self segment.
    ^ depList
  ].

" binary search "
lowPt := 1.
highPt := numElements.
[ lowPt <= highPt ] whileTrue: [
  i := (lowPt + highPt) quo: 2.
  dl := self _rcAt: i.

  dl = depList
    ifTrue: [
      depList size: 0.
      ^ dl
    ].

  depList < dl
    ifTrue: [ highPt := i - 1 ]
    ifFalse: [ lowPt := i + 1 ]
].

depList > (self _rcAt: i)
  ifTrue: [ i := i + 1 ].

" if inserting on the end "
i > numElements
  ifTrue: [
    " see if need to grow the object "
    i > self _basicSize
      ifTrue: [ " make bigger for insertion "
        self size: self _basicSize + self growIncrement
      ]
  ]
  ifFalse: [ " inserting in the middle, make room for new entry "
    self copyFrom: i to: numElements into: self startingAt: i + 1.
  ].

numElements := numElements + 1.
self _at: i put: depList.
depList assignToSegment: self segment.
^ depList
%

category: 'Constants'
method: DepListBucket
growIncrement

"Returns the number of entries to grow when needed."


^ 10
%

category: 'Searching'
method: DepListBucket
_linearSearchFor: aDepList

"Private.  Returns the offset into the receiver where the given dependency list
 can be found.  If not found, returns zero."



1 to: numElements do: [ :j |
  aDepList == (self _at: j)
    ifTrue: [ ^ j ]
].
^ 0
%

category: 'Searching'
method: DepListBucket
_binarySearchFor: aDepList

"Returns the offset into the receiver where the given dependency list
 can be found.  If not found, returns zero."


| lowPt midPt highPt currDL |

numElements == 0
  ifTrue: [ ^ 0 ].

lowPt := 1.
highPt := numElements.
[ lowPt <= highPt ] whileTrue: [
  midPt := (lowPt + highPt) quo: 2.
  currDL := self _rcAt: midPt.

  "use identity-based comparison of elements of dependency lists"
  (currDL hasIdenticalContents: aDepList)
    ifTrue: [ ^ midPt ].

  aDepList < currDL
    ifTrue: [ highPt := midPt - 1 ]
    ifFalse: [ lowPt := midPt + 1 ]
].

^ 0
%

category: 'Removing'
method: DepListBucket
remove: aDepList

"Remove the given dependency list from the receiver.  Returns whether the
 removal occurred."


| offset |
offset := self _linearSearchFor: aDepList.
offset == 0
  ifTrue: [ ^ false ].

self _deleteNoShrinkFrom: offset to: offset .
numElements := numElements - 1.

^ true
%

category: 'Enumerating'
method: DepListBucket
do: aBlock

"For each dependency list in the receiver, evaluates the one-argument block
 aBlock with the dependency list as the argument."


| aDL |
1 to: numElements do: [ :j |
  aDL := self _at: j.
  aDL == nil
    ifFalse: [ aBlock value: aDL ]
]
%

category: 'Updating'
method: DepListBucket
reset

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


super size: 0.
numElements := 0.
super size: self growIncrement.
System _addEntireObjectToRcReadSet: self
%

category: 'Updating'
method: DepListBucket
resizeIfNecessary

"Check the size of the receiver to see if it is unnecessarily greater
 than a page in size.  If so, resize it."


( self _basicSize > 2000 _and: [ numElements < 2000 ] )
  ifTrue: [ super size: (2000 min: numElements + self growIncrement) ].
%

category: 'Accessing'
method: DepListBucket
size

"Returns the value of the numElements instance variable."

^ numElements
%

category: 'Auditing'
method: DepListBucket
_hasEntryOutOfOrder

"Return whether the receiver has any entry out of order."



| depList prevDepList |
self size > 1
  ifTrue: [
    prevDepList := self _at: 1.
    2 to: self size do: [ :j |
      depList := self _at: j.
      depList < prevDepList
        ifTrue: [ ^ true ]
    ]
  ].
^ false
%

