1  package frost.collections
  2  
  3  uses frost.unsafe.Pointer
  4  
  5  ====================================================================================================
  6  A `Map` which compares its keys using identity (`==`) instead of equality (`=`). Unlike `HashMap`,
  7  which requires its keys to implement the `Key` interface, any type of object may be used as a key.
  8  However, it is important that the key not be a subclass of `Value`, as values do not have
  9  well-defined identities and `IdentityMap` will therefore not function properly with value keys.
 10  ====================================================================================================
 11  class IdentityMap<K, V> : Map<K, V> {
 12      @private
 13      class Entry<K, V> {
 14          ============================================================================================
 15          The entry's key.
 16          ============================================================================================
 17          def key:K
 18  
 19          ============================================================================================
 20          The entry's value.
 21          ============================================================================================
 22          var value:V
 23          
 24          var next:Entry<K, V>?
 25          
 26          @private
 27          init(key:K, value:V) {
 28              self.key := key
 29              self.value := value
 30          }
 31      }
 32  
 33      @private
 34      class EntryIterator<K, V> : Iterator<(K, V)> {
 35          def map:IdentityMap<K, V>
 36          var bucket := 0
 37          var entry:Entry<K, V>? := null
 38  
 39          init(map:IdentityMap<K, V>) {
 40              self.map := map
 41              while bucket < map.bucketCount &< map.bucketCount & map.contents[bucket] == null {
 42                  bucket += 1
 43              }
 44              if bucket < map.bucketCount {< map.bucketCount {
 45                  entry := map.contents[bucket]
 46              }
 47          }
 48  
 49          @override
 50          function get_done():Bit {
 51              return bucket = map.bucketCount & entry == null
 52          }
 53  
 54          @override
 55          method next():(K, V) {
 56              assert entry !== null
 57              assert bucket < map.bucketCount
 58              def< map.bucketCount
 59              def result := entry
 60              entry := entry!.next
 61              while entry == null {
 62                  bucket += 1
 63                  if bucket = map.bucketCount {
 64                      break
 65                  }
 66                  entry := map.contents[bucket]
 67              }
 68              return (result.key, result.value)
 69          }
 70      }
 71  
 72      @private
 73      constant DEFAULT_BUCKET_COUNT := 16
 74  
 75      @private
 76      var _count:Int
 77  
 78      @private
 79      var bucketCount:Int
 80  
 81      @private
 82      var contents:Pointer<Entry<K, V>?>
 83  
 84      @private
 85      var threshold:Int
 86  
 87      @private
 88      var changeCount := 0
 89      
 90      ================================================================================================
 91      Creates a new, empty `IdentityMap`.
 92      ================================================================================================
 93      init() {
 94          changeCount += 1
 95          _count := 0
 96          bucketCount := DEFAULT_BUCKET_COUNT
 97          contents := Pointer<Entry<K, V>?>.alloc(bucketCount)
 98          for i in 0 .. bucketCount {
 99              contents[i] := null
100          }
101          threshold := (bucketCount * 3) // 4
102      }
103  
104      @override
105      method cleanup() {
106          for i in 0 .. bucketCount {
107              if contents[i] !== null {
108                  Frost.unrefThreadSafe(contents[i])
109              }
110          }
111          contents.destroy()
112      }
113  
114      ================================================================================================
115      Given a key, returns the bucket in which the key's entry should be stored.
116      ================================================================================================
117      @private
118      function indexFor(key:K):Int {
119          def address := frost.core.Frost.addressOf(key)
120          return address % bucketCount
121      }
122      
123      @override
124      function [](key:K):V? {
125          def index := indexFor(key)
126          var e := contents[index]
127          while e !== null & e.key !== key {
128              e := e.next
129          }
130          if e !== null {
131              return e.value
132          }
133          else {
134              return null
135          }
136      }
137      
138      @override
139      function contains(key:K):Bit {
140          def index := indexFor(key)
141          var e := contents[index]
142          while e !== null & e.key !== key {
143              e := e.next
144          }
145          return e !== null
146      }
147  
148      @override
149      method []:=(key:K, value:V) {
150          changeCount += 1
151          def index := indexFor(key)
152          var e := contents[index]
153          while e !== null & e.key !== key {
154              e := e.next
155          }
156          if e == null {
157              def old := contents[index]
158              e := Entry<K, V>(key, value)
159              e.next := old
160              contents[index] := e
161              incrementCount()
162          }
163          else {
164              e.value := value
165          }
166      }
167      
168      @override
169      method remove(key:K) {
170          changeCount += 1
171          def index := indexFor(key)
172          var e := contents[index]
173          -- not found
174          if e == null {
175              return
176          }
177          -- found in the first slot, need to update the contents array
178          if e.key == key {
179              contents[index] := e.next
180              _count -= 1
181              return
182          }
183          loop {
184              def next := e.next
185              if next == null {
186                  -- not found
187                  return
188              }
189              if next.key == key {
190                  -- it's the next slot in the list
191                  break
192              }
193              e := next
194          }
195          -- we are looking at the entry before it, update its next Pointer to skip over it
196          def next := e.next
197          assert next !== null
198          e.next := next.next
199          _count -= 1
200      }
201  
202      @override
203      method clear() {
204          changeCount += 1
205          _count := 0
206          for i in 0 .. bucketCount {
207              if contents[i] !== null {
208                  Frost.unrefThreadSafe(contents[i])
209              }
210          }
211          contents.destroy()
212          bucketCount := DEFAULT_BUCKET_COUNT
213          contents := Pointer<Entry<K, V>?>.alloc(bucketCount)
214          for i in 0 .. bucketCount {
215              if contents[i] !== null {
216                  contents[i] := null
217              }
218          }
219          threshold := (bucketCount * 3) // 4
220      }
221      
222      @private
223      method incrementCount() {
224          _count += 1
225          if _count >= threshold {
226              def oldContents := contents
227              def oldBucketCount := bucketCount
228              bucketCount *= 2
229              contents := Pointer<Entry<K, V>?>.alloc(bucketCount)
230              for i in 0 .. bucketCount {
231                  contents[i] := null
232              }
233              threshold *= 2
234              _count := 0
235              for i in 0 .. oldBucketCount {
236                  var e := oldContents[i]
237                  while e !== null {
238                      self[e.key] := e.value
239                      e := e.next
240                  }
241              }
242              for i in 0 .. oldBucketCount {
243                  if oldContents[i] !== null {
244                      Frost.unrefThreadSafe(oldContents[i])
245                  }
246              }
247              oldContents.destroy()
248          }
249      }
250  
251      @override
252      function get_count():Int {
253          return _count
254      }
255  
256      @override
257      function get_entries():Iterator<(K, V)> {
258          return EntryIterator<K, V>(self)
259      }
260  
261      @override
262      method filterInPlace(test:(K, V)=>(Bit)) {
263          for i in 0 .. bucketCount {
264              var e := contents[i]
265              while e !== null & !test(e.key, e.value) {
266                  e := e.next
267                  contents[i] := e
268              }
269              var next := e.next
270              while next !== null {
271                  if !test(next.key, next.value) {
272                      e.next := next
273                  }
274                  next := next.next
275              }
276          }
277      }
278  
279      ================================================================================================
280      Returns a string representation of the map.
281  
282      @param fmt the format string
283      @returns a string representation of this object
284      ================================================================================================
285      @override
286      function get_toString():String {
287          def result := MutableString()
288          result.append("{")
289          var separator := ""
290          for i in 0 .. bucketCount {
291              var entry := contents[i]
292              while entry !== null {
293                  result.append(separator)
294                  if entry.key !== null {
295                      result.append(entry.key)
296                  }
297                  else {
298                      result.append("null")
299                  }
300                  result.append(":")
301                  if entry.value !== null {
302                      result.append(entry.value)
303                  }
304                  else {
305                      result.append("null")
306                  }
307                  entry := entry.next
308                  separator := ", "
309              }
310          }
311          result.append("}")
312          return result.finish()
313      }
314  }
315