st/HashedCollection.st

   1
   2
   3 HashedCollection classMethod!
   4 new
   5         ^ self new: self defaultCapacity!
   6
   7 HashedCollection classMethod!
   8 new: initialCapacity
   9         ^ self basicNew initialize: initialCapacity!
  10
  11 HashedCollection method!
  12 includes: anObject
  13         | index |
  14
  15         index := self find: anObject.
  16         (array at: index) ifNil: [^ false].
  17
  18         ^ true!
  19
  20 HashedCollection method!
  21 add: anObject
  22         | index |
  23
  24         anObject == self
  25                 ifTrue: [ self error: 'cannot insert self into dictionary' ].
  26
  27         index := self find: anObject.
  28         (array at: index) ifNotNil: [ ^ anObject ].
  29
  30         array at: index put: anObject.
  31         size := size + 1.
  32
  33         self growIfNeeded.
  34
  35         ^ anObject!
  36
  37 HashedCollection method!
  38 remove: anObject
  39         ^ self remove: anObject ifAbsent: []!
  40
  41 HashedCollection method!
  42 remove: anObject ifAbsent: aBlock
  43         | index |
  44
  45         anObject == self
  46                 ifTrue: [ self error: 'cannot remove self from dictionary' ].
  47
  48         index := self find: anObject.
  49
  50         (array at: index) ifNil: [^ aBlock value].
  51
  52         array at: index put: self.
  53         size := size - 1.
  54         deleted := deleted + 1.
  55
  56         ^ anObject!
  57
  58 HashedCollection method!
  59 find: anObject
  60         ^ self find: anObject in: array!
  61
  62 HashedCollection method!
  63 find: anObject in: anArray
  64         | i mask |
  65
  66         mask := anArray size - 1.
  67
  68         i := ((self keyFor: anObject) hash bitAnd: mask) + 1.
  69
  70         [ |  object |
  71
  72           object := anArray at: i.
  73
  74           (object = (self valueFor: anObject)) | (object == nil)
  75                   ifTrue: [ ^ i].
  76
  77           i := (i + 106720 bitAnd: mask) + 1.
  78
  79         ] repeat!
  80
  81 HashedCollection method!
  82 grow
  83         | newArray i |
  84
  85         newArray := Array new: (array size + array size).
  86
  87         self contents do: [ :object |
  88                 newArray at: (self find: object in: newArray) put: object].
  89
  90         array := newArray.
  91         deleted := 0!
  92
  93
  94 HashedCollection method!
  95 growIfNeeded
  96         "maximum 50% load factor"
  97         (self occupiedCount * 2) > array size
  98                 ifTrue: [ self grow ]!
  99
 100
 101 HashedCollection method!
 102 size
 103         ^ size!
 104
 105 HashedCollection method!
 106 capacity
 107         ^ array size // 2!
 108
 109
 110 "private"
 111
 112 HashedCollection classMethod!
 113 minimumCapacity
 114         ^ 4!
 115
 116 HashedCollection classMethod!
 117 defaultCapacity
 118         ^ 8!
 119
 120 HashedCollection method!
 121 keyFor: anObject
 122         ^ anObject!
 123
 124 HashedCollection method!
 125 valueFor: anObject
 126         ^ anObject!
 127
 128 HashedCollection method!
 129 arraySizeForCapacity: capacity
 130         | size |
 131
 132         size := HashedCollection minimumCapacity.
 133
 134         [ size < capacity ]
 135                 whileTrue: [ size := size + size ].
 136
 137         ^ size!
 138
 139 HashedCollection method!
 140 occupiedCount
 141         ^ size + deleted!
 142
 143 HashedCollection method!
 144 initialize: initialCapacity
 145         array := Array new: (self arraySizeForCapacity: initialCapacity).
 146         size := 0.
 147         deleted := 0!
 148
 149 HashedCollection method!
 150 loadFactor
 151         ^ self occupiedCount / array size!
 152
 153 HashedCollection method!
 154 contents
 155         ^ array select: [ :object | (object ~~ nil) & (object ~~ self) ]!