1  package frost.collections
  2  
  3  uses frost.unsafe.Pointer
  4  
  5  ====================================================================================================
  6  Standard implementation of the [Map] interface, which associates keys with values. An arbitrary
  7  number of values can be stored in a `HashMap` and then retrieved in constant average time:
  8  
  9      -- testcase HashMap(Simple)
 10      def alignment := HashMap<String, String>()
 11      alignment["faerie"] := "good"
 12      alignment["orc"]    := "evil"
 13      alignment["golem"]  := "neutral"
 14      Console.printLine(alignment["faerie"])
 15  
 16  This will display the value `"good"`.
 17  ====================================================================================================
 18  class HashMap<K:HashKey<K>, V> : Map<K, V> {
 19      @private
 20      class Entry<K:HashKey<K>, V> {
 21          ============================================================================================
 22          The entry's key.
 23          ============================================================================================
 24          def key:K
 25  
 26          ============================================================================================
 27          The entry's value.
 28          ============================================================================================
 29          var value:V
 30  
 31          var next:Entry<K, V>?
 32  
 33          @private
 34          init(key:K, value:V) {
 35              self.key := key
 36              self.value := value
 37          }
 38      }
 39  
 40      @private
 41      class EntryIterator<K:HashKey<K>, V> : Iterator<(K, V)> {
 42          def map:HashMap<K, V>
 43          var bucket := 0
 44          var entry:Entry<K, V>? := null
 45  
 46          init(map:HashMap<K, V>) {
 47              self.map := map
 48              while bucket < map.bucketCount &< map.bucketCount & map.contents[bucket] == null {
 49                  bucket += 1
 50              }
 51              if bucket < map.bucketCount {< map.bucketCount {
 52                  entry := map.contents[bucket]
 53              }
 54          }
 55  
 56          @override
 57          function get_done():Bit {
 58              return bucket = map.bucketCount & entry == null
 59          }
 60  
 61          @override
 62          method next():(K, V) {
 63              assert entry !== null
 64              assert bucket < map.bucketCount
 65              def< map.bucketCount
 66              def result := entry!
 67              entry := entry!.next
 68              while entry == null {
 69                  bucket += 1
 70                  if bucket = map.bucketCount {
 71                      break
 72                  }
 73                  entry := map.contents[bucket]
 74              }
 75              return (result.key, result.value)
 76          }
 77      }
 78  
 79      @private
 80      constant DEFAULT_BUCKET_COUNT := 16
 81  
 82      @private
 83      var _count:Int
 84  
 85      @private
 86      -- must be a power of 2 (see indexFor)
 87      var bucketCount:Int
 88  
 89      @private
 90      var contents:Pointer<Entry<K, V>?>
 91  
 92      @private
 93      var threshold:Int
 94  
 95      @private
 96      var changeCount := 0
 97      
 98      ================================================================================================
 99      Creates a new, empty `HashMap`.
100      ================================================================================================
101      init() {
102          changeCount += 1
103          _count := 0
104          bucketCount := DEFAULT_BUCKET_COUNT
105          contents := Pointer<Entry<K, V>?>.alloc(bucketCount)
106          for i in 0 .. bucketCount {
107              contents[i] := null
108          }
109          threshold := (bucketCount * 3) // 4
110      }
111  
112      init(map:MapView<K, V>) {
113          init()
114          for (k, v) in map.entries {
115              self[k] := v
116          }
117      }
118  
119      init(entries:CollectionView<(K, V)>) {
120          init()
121          for e in entries {
122              self[e[0]] := e[1]
123          }
124      }
125  
126      @override
127      method cleanup() {
128          for i in 0 .. bucketCount {
129              if contents[i] !== null {
130                  Frost.unrefThreadSafe(contents[i])
131              }
132          }
133          contents.destroy()
134      }
135  
136      ================================================================================================
137      Given a key, returns the bucket in which the key's entry should be stored.
138      ================================================================================================
139      @private
140      function indexFor(key:K):Int {
141          var h:Int
142          if key == null {
143              h := 0
144          }
145          else {
146              h := key.hash
147          }
148          -- supplemental hash function to defend against poor hash codes, as we do not use a prime
149          -- table length
150          h ~~= (h >> 20) ~~ (h >> 12) ~~ (h >> 7) ~~ (h >> 4)
151          -- the bitwise and below is equivalent to mod if length is a power of 2, which is why we
152          -- require that
153          h &&= bucketCount - 1
154          return h
155      }
156      
157      @override
158      function [](key:K):V? {
159          def index := indexFor(key)
160          var e := contents[index]
161          while e !== null & e.key != key {
162              e := e.next
163          }
164          if e !== null {
165              return e.value
166          }
167          else {
168              return null
169          }
170      }
171      
172      @override
173      function contains(key:K):Bit {
174          def index := indexFor(key)
175          var e := contents[index]
176          while e !== null & e.key != key {
177              e := e.next
178          }
179          return e !== null
180      }
181  
182      @override
183      method []:=(key:K, value:V) {
184          changeCount += 1
185          def index := indexFor(key)
186          var e := contents[index]
187          while e !== null & e.key != key {
188              e := e.next
189          }
190          if e == null {
191              def old := contents[index]
192              e := Entry<K, V>(key, value)
193              e.next := old
194              contents[index] := e
195              incrementCount()
196          }
197          else {
198              e.value := value
199          }
200      }
201      
202      @override
203      method remove(key:K) {
204          changeCount += 1
205          def index := indexFor(key)
206          var e := contents[index]
207          -- not found
208          if e == null {
209              return
210          }
211          -- found in the first slot, need to update the contents array
212          if e.key = key {
213              contents[index] := e.next
214              _count -= 1
215              return
216          }
217          loop {
218              def next := e.next
219              if next == null {
220                  -- not found
221                  return
222              }
223              if next.key = key {
224                  -- it's the next slot in the list
225                  break
226              }
227              e := next
228          }
229          -- we are looking at the entry before it, update its next Pointer to skip over it
230          def next := e.next
231          assert next !== null
232          e.next := next.next
233          _count -= 1
234      }
235  
236      @override
237      method clear() {
238          changeCount += 1
239          _count := 0
240          for i in 0 .. bucketCount {
241              if contents[i] !== null {
242                  Frost.unrefThreadSafe(contents[i])
243              }
244          }
245          contents.destroy()
246          bucketCount := DEFAULT_BUCKET_COUNT
247          contents := Pointer<Entry<K, V>?>.alloc(bucketCount)
248          for i in 0 .. bucketCount {
249              if contents[i] !== null {
250                  contents[i] := null
251              }
252          }
253          threshold := (bucketCount * 3) // 4
254      }
255      
256      @private
257      method incrementCount() {
258          _count += 1
259          if _count >= threshold {
260              def oldContents := contents
261              def oldBucketCount := bucketCount
262              bucketCount *= 2
263              contents := Pointer<Entry<K, V>?>.alloc(bucketCount)
264              for i in 0 .. bucketCount {
265                  contents[i] := null
266              }
267              threshold *= 2
268              _count := 0
269              for i in 0 .. oldBucketCount {
270                  var e := oldContents[i]
271                  while e !== null {
272                      self[e.key] := e.value
273                      e := e.next
274                  }
275              }
276              for i in 0 .. oldBucketCount {
277                  if oldContents[i] !== null {
278                      Frost.unrefThreadSafe(oldContents[i])
279                  }
280              }
281              oldContents.destroy()
282          }
283      }
284  
285      @override
286      function get_entries():Iterator<(K, V)> {
287          return EntryIterator<K, V>(self)
288      }
289  
290      @override
291      function get_count():Int {
292          return _count
293      }
294  
295      @override
296      method filterInPlace(test:(K, V)=>(Bit)) {
297          for i in 0 .. bucketCount {
298              var e := contents[i]
299              while e !== null & !test(e.key, e.value) {
300                  e := e.next
301                  contents[i] := e
302                  _count -= 1
303              }
304              if e !== null {
305                  var next := e.next
306                  while next !== null {
307                      if !test(next.key, next.value) {
308                          e.next := next.next
309                          _count -= 1
310                      }
311                      next := next.next
312                  }
313              }
314          }
315      }
316  
317      ================================================================================================
318      Returns a string representation of the map.
319  
320      @param fmt the format string
321      @returns a string representation of this object
322      ================================================================================================
323      @override
324      function get_toString():String {
325          def result := MutableString()
326          result.append("{")
327          var separator := ""
328          for i in 0 .. bucketCount {
329              var entry := contents[i]
330              while entry !== null {
331                  result.append(separator)
332                  if entry.key !== null {
333                      result.append(entry.key)
334                  }
335                  else {
336                      result.append("null")
337                  }
338                  result.append(":")
339                  if entry.value !== null {
340                      result.append(entry.value)
341                  }
342                  else {
343                      result.append("null")
344                  }
345                  entry := entry.next
346                  separator := ", "
347              }
348          }
349          result.append("}")
350          return result.finish()
351      }
352  }
353