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

removeallmethods DependencyList
removeallclassmethods DependencyList

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

| doc |
doc := GsClassDocumentation _newForPrivateGsClass: self.

doc documentClassWith: (GsDocText new).

self description: doc.
%

category: 'Accessing'
classmethod: DependencyList
for: anObject

"Returns the dependency list for the receiver.  If one does not exist,
 returns nil."

<primitive: 585>
self _primitiveFailed: #for: .
self _uncontinuableError
%

category: 'Updating'
classmethod: DependencyList
set: aDependent for: anObject

"Sets the dependency entry for anObject to be aDependent."

<primitive: 584>
self _primitiveFailed: #set:for: .
self _uncontinuableError
%

category: 'Accessing'
classmethod: DependencyList
depMapKeys
 
"Return an array of objects that have dependents."
 
<primitive: 586>
^self _primitiveFailed: #_depMapKeys .
%

category: 'Accessing'
classmethod: DependencyList
depMapValues
 
"Returns array of objects that are dependents."
 
<primitive: 587>
^self _primitiveFailed: #_depMapValues .
%

category: 'Testing'
classmethod: DependencyList
needsDepList: anObject

"Returns whether anObject needs a dependency list if it is the last
 object along an equality index path."

<primitive: 210>
self _primitiveFailed: #needsDepList: .
self _uncontinuableError
%

category: 'Removing'
classmethod: DependencyList
removePathTerm: pathTerm for: anObject

"Removes the entry (an entry has 2 slots) for the given path term.
 If it is the last remaining entry, then the dependency list becomes
 nil."

| depList |

depList := self for: anObject.
depList == nil
  ifTrue: [ ^ self ].

depList size == 0
  ifTrue: [
    self set: nil for: anObject.
    ^ self
  ].

" if only one entry, set the dependency tag to be nil "
( depList size == 2 _and:
[ (depList includesIdentical: pathTerm) _and:
[ (self needsDepList: anObject) not ] ] )
  ifTrue: [
    self set: nil for: anObject.
    ^ self
  ].

depList := self from: depList.
depList _removePathTerm: pathTerm for: anObject.

self
  set: (SharedDependencyLists at: depList logging: false)
  for: anObject.
%


category: 'Copying'
classmethod: DependencyList
from: aDepList

"Returns a dependency list that is a copy of the given dependency list."

| dl pathTerm pathTerms |
aDepList == nil
  ifTrue: [ ^ self new ].

dl := aDepList copy.
1 to: dl size by: 2 do: [ :i |
  pathTerm := aDepList at: i.
  pathTerm _isObsoletePathTerm
    ifTrue: [
      " lazy initialization of pathTerms set "
      pathTerms == nil
        ifTrue: [ pathTerms := IdentitySet new ].
      pathTerms add: pathTerm.
    ]
].

" remove obsolete path terms if there are any "
pathTerms == nil
  ifFalse: [
    1 to: pathTerms size do: [ :i |
      dl _removeCompletelyPathTerm: (pathTerms at: i)
    ]
  ].
^ dl
%

! ------------------- Instance methods for DependencyList

category: 'Searching'
method: DependencyList
getInstVarOffsetWithPathTerm: pathTerm

"Returns the instance variable offset for the entry at which a path term is
 located in the receiver, or zero if it is not found."

"Performs a linear search."

| i |
(i := self _findOffsetForPathTerm: pathTerm) == nil
    ifTrue: [ ^ 0 ].

^ self at: i + 1
%

category: 'Removing'
method: DependencyList
removePathTerms: pathTerms for: anObject

"Removes the entries for the given collection of path terms.  If they are
 the last remaining entries, then the dependency list becomes nil."

" if it is a byte object "
| depListClass |
depListClass := self class .
1 to: pathTerms size do: [ :j |
  depListClass removePathTerm: (pathTerms at: j) for: anObject
]
%

category: 'Comparing'
method: DependencyList
= anotherDependencyList
    "If the comparison comes down to the element-wise test, only
    compare path terms and use identity. 

    N.B. a hash method is not required for this class because its use
    is private to Gemstone. If one were desirable, the technique would
    be to OR the path term identities."

    | size |
    self == anotherDependencyList ifTrue:
        [^true].
    self class == anotherDependencyList class ifFalse:
        [^false].
    size := anotherDependencyList size.
    self size == size ifFalse:
        [^false].
    1 to: size do:
        [ :i |
         (self at: i) == (anotherDependencyList at: i) ifFalse:
             [^false]].
    ^true
%
category: 'Comparing'
method: DependencyList
> depList

"Returns whether the receiver follows the argument when sorted based upon
 the OOPs of the path terms."

<primitive: 522>
self _primitiveFailed: #> .
self _uncontinuableError
%

category: 'Comparing'
method: DependencyList
< depList

"Returns whether the receiver precedes the argument when sorted based upon
 the OOPs of the path terms. "

<primitive: 333>
self _primitiveFailed: #< .
self _uncontinuableError
%

category: 'Searching'
method: DependencyList
_findOffsetForPathTerm: pathTerm

"Returns the offset at which a path term is located in the receiver, or nil
 if it is not found.  Performs a linear search."

1 to: self size by: 2 do: [ :i |
  pathTerm == (self at: i)
    ifTrue: [ ^ i ]
].
^ nil
%

category: 'Searching'
method: DependencyList
_findPathTermForOffset: offset

"Returns the path term associated with the given instance variable offset if
 it exists; otherwise returns nil. NOTE: there may be more than one pathTerm for
 the given object this method returns only the first."

2 to: self size by: 2 do: [ :i |
  (self at: i) == offset
    ifTrue: [ ^ self at: i - 1 ]
].
^ nil
%

category: 'Removing'
method: DependencyList
_removePathTerm: pathTerm for: anObject

"Removes the entry with the given path term."

| sz ivOffset |
sz := self size.
1 to: sz by: 2 do: [ :i |
  pathTerm == (self at: i)
    ifTrue: [
      ivOffset := self at: i + 1.
      " see if need to decrement reference count for a byte object "
      ( (DependencyList needsDepList: anObject) _and: [ ivOffset > 1 ] )
        ifTrue: [ self at: i + 1 put: ivOffset - 1 ]
        ifFalse: [
          " see if found in the last entry "
          i == (sz - 1)
            ifFalse: [ " shift remaining entries "
              self copyFrom: i + 2 to: sz into: self startingAt: i
            ].

          self size: sz - 2.
        ].
      ^ self
    ]
]
%

category: 'Removing'
method: DependencyList
_removeCompletelyPathTerm: pathTerm

"Removes the entry with the given path term.  Returns the instance variable
 offset for the given path term."

| sz ivOffset |
sz := self size.
1 to: sz by: 2 do: [ :i |
  pathTerm == (self at: i)
    ifTrue: [
      ivOffset := self at: i + 1.
      " see if found in the last entry "
      i == (sz - 1)
        ifFalse: [ " shift remaining entries "
          self copyFrom: i + 2 to: sz into: self startingAt: i
        ].

      self size: sz - 2.
      ^ ivOffset
    ]
].
^ 0
%

category: 'Removing'
method: DependencyList
removeCompletelyPathTerm: pathTerm for: anObject

"Removes the entry with the given path term.  Returns the instance variable
 offset for the given path term."

| depList ivOffset depListClass |
" if only one entry, set the dependency tag to be nil "
( self size == 2 _and: [ pathTerm == (self at: 1) ] )
  ifTrue: [
    DependencyList set: nil for: anObject.
    ^ self at: 2
  ].

depListClass := self class .
depList := depListClass from: self.
ivOffset := depList _removeCompletelyPathTerm: pathTerm.

depListClass
  set: (SharedDependencyLists at: depList logging: false)
  for: anObject.
^ ivOffset
%

category: 'Testing'
method: DependencyList
containsAnyOf: arrayOfPathTerms

"Returns whether the receiver contains an entry with any path term in
 the Array of path terms."

1 to: self size by: 2 do: [ :i |
  ( arrayOfPathTerms includesIdentical: (self at: i) )
    ifTrue: [ ^ true ]
].
^ false
%

category: 'Updating'
method: DependencyList
addPathTerm: pathTerm
withIVOffset: anInteger
for: anObject

"Adds an entry containing the path term, and instance variable offset to the
 receiver. Primitive will grow receiver if necessary."

<primitive: 523>
self _primitiveFailed: #addPathTerm:withIVOffset:for: .
self _uncontinuableError
%

category: 'Reduced Conflict Support'
method: DependencyList
_replaceReferencesWith: aDepList

"Scans the write set, looking for objects that have the receiver for a
 dependency tag.  For each one, replace the dependency tag with aDepList."

| writeSet obj depListClass |
writeSet := System _hiddenSetAsArray: 8.
depListClass := self class .
1 to: writeSet size do: [ :i |
  obj := writeSet _at: i.
  self == (depListClass for: obj)
    ifTrue: [ depListClass set: aDepList for: obj ]
]
%

category: 'Testing'
method: DependencyList
_hasObsoletePathTerm

"Returns whether the receiver has an obsolete path term
 (one whose size is zero)."

1 to: self size by: 2 do: [ :i |
  ( (self at: i + 1) > 0 _and: [ (self at: i) size == 0 ] )
    ifTrue: [ ^ true ]
].
^ false
%

category: 'Updating'
method: DependencyList
copyAndAddPathTerm: pathTerm withIVOffset: ivOffset for: object

"Makes a copy of the receiver that has an additional entry containing the
 path term, and instance variable offset."

| sz dl ptOop thisTerm |

ptOop := pathTerm asOop.
sz := self size.
1 to: sz by: 2 do: [ :i |
  thisTerm := self at: i.
  (pathTerm == thisTerm)
    ifTrue: [
      dl := self copy.
      (self class needsDepList: object)
        ifTrue: [
          dl at: i + 1 put: (self at: i + 1) + 1.
        ].
      ^ dl
    ]
    ifFalse: [
      ptOop < thisTerm asOop
        ifTrue: [
          dl := self class new: sz + 2.
          i == 1
            ifTrue: [
              self copyFrom: 1 to: sz into: dl startingAt: 3.
            ]
            ifFalse: [
              self copyFrom: 1 to: i - 1 into: dl startingAt: 1.
              self copyFrom: i to: sz into: dl startingAt: i + 2.
            ].
          dl at: i put: pathTerm.
          dl at: i + 1 put: ivOffset.
          ^ dl
        ]
    ]
].

dl := self class new: sz + 2.
sz > 0
  ifTrue: [ self copyFrom: 1 to: sz into: dl startingAt: 1 ].
dl at: sz + 1 put: pathTerm.
dl at: sz + 2 put: ivOffset.
^ dl
%

category: 'Updating'
method: DependencyList
copyAndAddTracker: tracker withId: anInteger for: object

"Adds the tracking object and the integer offset to the receiver."

| sz dl trackerOop thisTerm |

trackerOop := tracker asOop.
sz := self size.
1 to: sz by: 2 do: [ :i |
  thisTerm := self at: i.
  (tracker == thisTerm)
    ifTrue: [ ^ self copy ]
    ifFalse: [
      trackerOop < thisTerm asOop
        ifTrue: [
          dl := self class new: sz + 2.
          i == 1
            ifTrue: [
              self copyFrom: 1 to: sz into: dl startingAt: 3.
            ]
            ifFalse: [
              self copyFrom: 1 to: i - 1 into: dl startingAt: 1.
              self copyFrom: i to: sz into: dl startingAt: i + 2.
            ].
          dl at: i put: tracker.
          dl at: i + 1 put: anInteger.
          ^ dl
        ]
    ]
].

dl := self class new: sz + 2.
sz > 0
  ifTrue: [ self copyFrom: 1 to: sz into: dl startingAt: 1 ].
dl at: sz + 1 put: tracker.
dl at: sz + 2 put: anInteger.
^ dl
%

category: 'Removing'
classmethod: DependencyList
removeTracker: tracker for: anObject

"Removes the given tracking object from the receiver."

| depList |

depList := self for: anObject.
depList == nil
  ifTrue: [ ^ self ].

" if only one entry, set the dependency tag to be nil "
(depList size <= 2 _and: [ tracker == (depList at: 1) ])
  ifTrue: [
    self set: nil for: anObject.
    ^ self
  ].

depList := self from: depList.
depList _removeTracker: tracker for: anObject.

self
  set: (SharedDependencyLists at: depList logging: false)
  for: anObject.
%

category: 'Removing'
method: DependencyList
_removeTracker: tracker for: anObject

"Removes the given tracking object from the receiver."

| sz |
sz := self size.
1 to: sz by: 2 do: [ :i |
  tracker == (self at: i)
    ifTrue: [
      " see if found in the last entry "
      i == (sz - 1)
        ifFalse: [ " shift remaining entries "
          self copyFrom: i + 2 to: sz into: self startingAt: i
        ].
      self size: sz - 2.
      ^ self
    ]
]
%

category: 'Searching'
method: DependencyList
_findTrackerOfClass: aClass

"Returns the first tracker object of the given class.  If none is found,
 returns nil."

2 to: self size by: 2 do: [ :i |
  ( (self at: i) <= 0 _and: [ (self at: i - 1) class == aClass ] )
    ifTrue: [ ^ self at: i - 1 ]
].
^ nil
%

category: 'Searching'
method: DependencyList
_getAllTrackers

"Returns an Array of all tracker objects of the given class."


| result |
result := Array new.
2 to: self size by: 2 do: [ :i |
  (self at: i) <= 0
    ifTrue: [ result add: (self at: i - 1) ]
].
^ result
%

category: 'Searching'
method: DependencyList
_findAllTrackersOfClass: aClass

"Returns an Array of all tracker objects of the given class."

| result |
result := Array new.
2 to: self size by: 2 do: [ :i |
  ( (self at: i) <= 0 _and: [ (self at: i - 1) class == aClass ] )
    ifTrue: [ result add: (self at: i - 1) ]
].
^ result
%

category: 'Finalization'
method: DependencyList
_finalize: pathTerm at: offset

"The given path term is a candidate to be garbage collected.  Remove the
entry from the receiver, and remove the receiver from the shared
dependency list table."

| sz |

" must first remove from table "
SharedDependencyLists remove: self logging: true.

" now remove path term from receiver "
sz := self size.
offset == (sz - 1)
  ifFalse: [ " shift remaining entries "
    self copyFrom: offset + 2 to: sz into: self startingAt: offset
  ].

self size: sz - 2.

" indicate ok to garbage collect "
^ true
%

category: 'Auditing'
method: DependencyList
_needsSorting

"Return whether all pathterms in the receiver are in the correct order."

| hash prevHash |
prevHash := 0.
1 to: self size by: 2 do: [ :i |
  hash := (self at: i) asOop.
  hash < prevHash
    ifTrue: [ ^ true ]
    ifFalse: [ prevHash := hash ].
].
^ false
%

category: 'Auditing'
method: DependencyList
_sortEntries: aBucket

"Find entries that are not in order, then reinsert them in the
correct position.  Remove the receiver from the given bucket and
reinsert it in the shared dependency lists table.  Return the number
of entries sorted."

| hash prevHash entriesToMove |
prevHash := 0.
1 to: self size by: 2 do: [ :i |
  hash := (self at: i) asOop.
  hash < prevHash
    ifTrue: [
      entriesToMove == nil
        ifTrue: [ entriesToMove := Array new ].
      entriesToMove add: i; add: (self at: i); add: (self at: i + 1)
    ]
    ifFalse: [ prevHash := hash ].
].
entriesToMove size > 0
  ifTrue: [
    aBucket remove: self.
    1 to: entriesToMove size by: 3 do: [ :i |
      self _removeEntryAtOffset: (entriesToMove at: i).
      self addPathTerm: (entriesToMove at: i + 1)
        withIVOffset: (entriesToMove at: i + 2)
        for: nil.
    ].
    SharedDependencyLists at: self logging: false
  ].
^ entriesToMove size
%

category: 'Auditing'
method: DependencyList
_removeEntryAtOffset: offset

"Remove the entry at the given offset."

| sz |
offset odd
  ifFalse: [ ^ self ].

sz := self size.
offset == (sz - 1)
  ifFalse: [ self copyFrom: offset + 2 to: sz into: self startingAt: offset ].
self size: sz - 2.
%

unprotectmethods

