← Back to branch summary

~ubuntu-branches/debian/sid/scala/sid

« back to all changes in this revision

Viewing changes to src/library/scala/collection/mutable/HashTable.scala

  • Committer: Package Import Robot
  • Author(s): Emmanuel Bourg, Mehdi Dogguy, Lucas Satabin, Frank S. Thomas, Emmanuel Bourg
  • Date: 2015-06-05 23:52:59 UTC
  • mfrom: (1.2.11)
  • Revision ID: package-import@ubuntu.com-20150605235259-wk00vgk83dh8o19g
Tags: 2.10.5-1
http://bugs.debian.org/744278
http://bugs.debian.org/754935
http://bugs.debian.org/724704
* Team upload.

[ Mehdi Dogguy ]
* New upstream release (Closes: #744278).

[ Lucas Satabin ]
* Update patches
* Update the clean target
* Update paths of elements to install
* Update watch file

[ Frank S. Thomas ]
* Remove myself from Uploaders.

[ Emmanuel Bourg ]
* The package has been adopted by the Java Team (Closes: #754935)
* Patched the build to avoid downloading libraries from the Internet
* Replaced the minified JavaScript files with unobfuscated ones
* No longer build scala-partest.jar until diffutils is packaged or replaced
* debian/watch: Fixed the versions matched (x.y.z instead of x.y.z..z)
* debian/rules:
  - Added the missing get-orig-source target (Closes: #724704)
  - Improved the clean target
* debian/control:
  - Build depend on scala (>= 2.10) and bnd
  - Use canonical URLs for the Vcs-* fields
  - Standards-Version updated to 3.9.6 (no changes)
* Switch to debhelper level 9

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/library/scala/collection/mutable/HashTable.scala
1
1
/*                     __                                               *\
2
2
**     ________ ___   / /  ___     Scala API                            **
3
 
**    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
 
3
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
4
4
**  __\ \/ /__/ __ |/ /__/ __ |    http://www.scala-lang.org/           **
5
5
** /____/\___/_/ |_/____/_/ | |                                         **
6
6
**                          |/                                          **
32
32
 *  @tparam A     type of the elements contained in this hash table.
33
33
 */
34
34
trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashUtils[A] {
 
35
  // Replacing Entry type parameter by abstract type member here allows to not expose to public
 
36
  // implementation-specific entry classes such as `DefaultEntry` or `LinkedEntry`.
 
37
  // However, I'm afraid it's too late now for such breaking change.
35
38
  import HashTable._
36
39
 
37
40
  @transient protected var _loadFactor = defaultLoadFactor
52
55
   */
53
56
  @transient protected var sizemap: Array[Int] = null
54
57
 
55
 
  protected def initialSize: Int = HashTable.initialSize
 
58
  @transient protected var seedvalue: Int = tableSizeSeed
 
59
 
 
60
  protected def tableSizeSeed = Integer.bitCount(table.length - 1)
 
61
 
 
62
  /** The initial size of the hash table.
 
63
   */
 
64
  protected def initialSize: Int = 16
 
65
 
 
66
  /** The initial threshold.
 
67
   */
 
68
  private def initialThreshold(_loadFactor: Int): Int = newThreshold(_loadFactor, initialCapacity)
 
69
 
 
70
  private def initialCapacity = capacity(initialSize)
 
71
 
 
72
  private def lastPopulatedIndex = {
 
73
    var idx = table.length - 1
 
74
    while (table(idx) == null && idx > 0)
 
75
      idx -= 1
 
76
 
 
77
    idx
 
78
  }
56
79
 
57
80
  /**
58
 
   * Initializes the collection from the input stream. `f` will be called for each key/value pair
59
 
   * read from the input stream in the order determined by the stream. This is useful for
60
 
   * structures where iteration order is important (e.g. LinkedHashMap).
 
81
   * Initializes the collection from the input stream. `readEntry` will be called for each
 
82
   * entry to be read from the input stream.
61
83
   */
62
 
  private[collection] def init[B](in: java.io.ObjectInputStream, f: (A, B) => Entry) {
 
84
  private[collection] def init(in: java.io.ObjectInputStream, readEntry: => Entry) {
63
85
    in.defaultReadObject
64
86
 
65
 
    _loadFactor = in.readInt
 
87
    _loadFactor = in.readInt()
66
88
    assert(_loadFactor > 0)
67
89
 
68
 
    val size = in.readInt
 
90
    val size = in.readInt()
69
91
    tableSize = 0
70
92
    assert(size >= 0)
71
93
 
72
 
    val smDefined = in.readBoolean
 
94
    seedvalue = in.readInt()
 
95
 
 
96
    val smDefined = in.readBoolean()
73
97
 
74
98
    table = new Array(capacity(sizeForThreshold(_loadFactor, size)))
75
99
    threshold = newThreshold(_loadFactor, table.size)
78
102
 
79
103
    var index = 0
80
104
    while (index < size) {
81
 
      addEntry(f(in.readObject.asInstanceOf[A], in.readObject.asInstanceOf[B]))
 
105
      addEntry(readEntry)
82
106
      index += 1
83
107
    }
84
108
  }
85
109
 
86
110
  /**
87
111
   * Serializes the collection to the output stream by saving the load factor, collection
88
 
   * size, collection keys and collection values. `value` is responsible for providing a value
89
 
   * from an entry.
 
112
   * size and collection entries. `writeEntry` is responsible for writing an entry to the stream.
90
113
   *
91
 
   * `foreach` determines the order in which the key/value pairs are saved to the stream. To
 
114
   * `foreachEntry` determines the order in which the key/value pairs are saved to the stream. To
92
115
   * deserialize, `init` should be used.
93
116
   */
94
 
  private[collection] def serializeTo[B](out: java.io.ObjectOutputStream, value: Entry => B) {
 
117
  private[collection] def serializeTo(out: java.io.ObjectOutputStream, writeEntry: Entry => Unit) {
95
118
    out.defaultWriteObject
96
119
    out.writeInt(_loadFactor)
97
120
    out.writeInt(tableSize)
 
121
    out.writeInt(seedvalue)
98
122
    out.writeBoolean(isSizeMapDefined)
99
 
    foreachEntry { entry =>
100
 
      out.writeObject(entry.key)
101
 
      out.writeObject(value(entry))
102
 
    }
 
123
 
 
124
    foreachEntry(writeEntry)
103
125
  }
104
126
 
105
127
  /** Find entry with given key in table, null if not found.
106
128
   */
107
 
  protected def findEntry(key: A): Entry = {
108
 
    val h = index(elemHashCode(key))
 
129
  protected def findEntry(key: A): Entry =
 
130
    findEntry0(key, index(elemHashCode(key)))
 
131
 
 
132
  private[this] def findEntry0(key: A, h: Int): Entry = {
109
133
    var e = table(h).asInstanceOf[Entry]
110
134
    while (e != null && !elemEquals(e.key, key)) e = e.next
111
135
    e
115
139
   *  pre: no entry with same key exists
116
140
   */
117
141
  protected def addEntry(e: Entry) {
118
 
    val h = index(elemHashCode(e.key))
 
142
    addEntry0(e, index(elemHashCode(e.key)))
 
143
  }
 
144
 
 
145
  private[this] def addEntry0(e: Entry, h: Int) {
119
146
    e.next = table(h).asInstanceOf[Entry]
120
147
    table(h) = e
121
148
    tableSize = tableSize + 1
124
151
      resize(2 * table.length)
125
152
  }
126
153
 
 
154
  /** Find entry with given key in table, or add new one if not found.
 
155
   *  May be somewhat faster then `findEntry`/`addEntry` pair as it
 
156
   *  computes entry's hash index only once.
 
157
   *  Returns entry found in table or null.
 
158
   *  New entries are created by calling `createNewEntry` method.
 
159
   */
 
160
  protected def findOrAddEntry[B](key: A, value: B): Entry = {
 
161
    val h = index(elemHashCode(key))
 
162
    val e = findEntry0(key, h)
 
163
    if (e ne null) e else { addEntry0(createNewEntry(key, value), h); null }
 
164
  }
 
165
 
 
166
  /** Creates new entry to be immediately inserted into the hashtable.
 
167
   *  This method is guaranteed to be called only once and in case that the entry
 
168
   *  will be added. In other words, an implementation may be side-effecting.
 
169
   */
 
170
  protected def createNewEntry[B](key: A, value: B): Entry
 
171
 
127
172
  /** Remove entry from table if present.
128
173
   */
129
174
  protected def removeEntry(key: A) : Entry = {
154
199
 
155
200
  /** An iterator returning all entries.
156
201
   */
157
 
  protected def entriesIterator: Iterator[Entry] = new Iterator[Entry] {
 
202
  protected def entriesIterator: Iterator[Entry] = new AbstractIterator[Entry] {
158
203
    val iterTable = table
159
 
    var idx = table.length - 1
160
 
    var es = iterTable(idx).asInstanceOf[Entry]
161
 
    scan()
 
204
    var idx       = lastPopulatedIndex
 
205
    var es        = iterTable(idx)
 
206
 
162
207
    def hasNext = es != null
163
208
    def next() = {
164
209
      val res = es
165
210
      es = es.next
166
 
      scan()
167
 
      res
168
 
    }
169
 
    def scan() {
170
211
      while (es == null && idx > 0) {
171
212
        idx = idx - 1
172
 
        es = iterTable(idx).asInstanceOf[Entry]
173
 
      }
174
 
    }
175
 
  }
176
 
 
177
 
  /*
178
 
   * We should implement this as a primitive operation over the underlying array, but it can
179
 
   * cause a behaviour change in edge cases where:
180
 
   * - Someone modifies a map during iteration
181
 
   * - The insertion point is close to the iteration point.
182
 
   *
183
 
   * The reason this happens is that the iterator prefetches the following element before
184
 
   * returning from next (to simplify the implementation of hasNext) while the natural
185
 
   * implementation of foreach does not.
186
 
   *
187
 
   * It should be mentioned that modifying a map during iteration leads to unpredictable
188
 
   * results with either implementation.
189
 
   */
190
 
  protected final def foreachEntry[C](f: Entry => C) { entriesIterator.foreach(f) }
191
 
 
192
 
  /** An iterator returning all entries */
193
 
  @deprecated("use entriesIterator instead", "2.8.0")
194
 
  protected def entries: Iterator[Entry] = entriesIterator
 
213
        es = iterTable(idx)
 
214
      }
 
215
      res.asInstanceOf[Entry]
 
216
    }
 
217
  }
 
218
 
 
219
  /** Avoid iterator for a 2x faster traversal. */
 
220
  protected def foreachEntry[U](f: Entry => U) {
 
221
    val iterTable = table
 
222
    var idx       = lastPopulatedIndex
 
223
    var es        = iterTable(idx)
 
224
 
 
225
    while (es != null) {
 
226
      f(es.asInstanceOf[Entry])
 
227
      es = es.next
 
228
 
 
229
      while (es == null && idx > 0) {
 
230
        idx -= 1
 
231
        es = iterTable(idx)
 
232
      }
 
233
    }
 
234
  }
195
235
 
196
236
  /** Remove all entries from table
197
237
   */
311
351
  // this is of crucial importance when populating the table in parallel
312
352
  protected final def index(hcode: Int) = {
313
353
    val ones = table.length - 1
314
 
    val improved = improve(hcode)
 
354
    val improved = improve(hcode, seedvalue)
315
355
    val shifted = (improved >> (32 - java.lang.Integer.bitCount(ones))) & ones
316
356
    shifted
317
357
  }
322
362
      table = c.table
323
363
      tableSize = c.tableSize
324
364
      threshold = c.threshold
 
365
      seedvalue = c.seedvalue
325
366
      sizemap = c.sizemap
326
367
    }
327
368
    if (alwaysInitSizeMap && sizemap == null) sizeMapInitAndRebuild
332
373
    table,
333
374
    tableSize,
334
375
    threshold,
 
376
    seedvalue,
335
377
    sizemap
336
378
  )
337
379
}
342
384
  private[collection] final def defaultLoadFactor: Int = 750 // corresponds to 75%
343
385
  private[collection] final def loadFactorDenum = 1000;
344
386
 
345
 
  /** The initial size of the hash table.
346
 
   */
347
 
  private[collection] final def initialSize: Int = 16
348
 
 
349
 
  /** The initial threshold.
350
 
   */
351
 
  private[collection] final def initialThreshold(_loadFactor: Int): Int = newThreshold(_loadFactor, initialCapacity)
352
 
 
353
 
  private[collection] final def initialCapacity = capacity(initialSize)
354
 
 
355
387
  private[collection] final def newThreshold(_loadFactor: Int, size: Int) = ((size.toLong * _loadFactor) / loadFactorDenum).toInt
356
388
 
357
 
  private[collection] final def sizeForThreshold(_loadFactor: Int, thr: Int) = thr * loadFactorDenum / _loadFactor
 
389
  private[collection] final def sizeForThreshold(_loadFactor: Int, thr: Int) = ((thr.toLong * loadFactorDenum) / _loadFactor).toInt
358
390
 
359
391
  private[collection] final def capacity(expectedSize: Int) = if (expectedSize == 0) 1 else powerOfTwo(expectedSize)
360
392
 
365
397
 
366
398
    protected def elemHashCode(key: KeyType) = key.##
367
399
 
368
 
    protected final def improve(hcode: Int) = {
 
400
    protected final def improve(hcode: Int, seed: Int) = {
369
401
      /* Murmur hash
370
402
       *  m = 0x5bd1e995
371
403
       *  r = 24
391
423
       *
392
424
       * For performance reasons, we avoid this improvement.
393
425
       * */
394
 
      var i = hcode * 0x9e3775cd
395
 
      i = java.lang.Integer.reverseBytes(i)
396
 
      i * 0x9e3775cd
397
 
      // a slower alternative for byte reversal:
398
 
      // i = (i << 16) | (i >> 16)
399
 
      // i = ((i >> 8) & 0x00ff00ff) | ((i << 8) & 0xff00ff00)
 
426
      val i= scala.util.hashing.byteswap32(hcode)
400
427
 
401
428
      /* Jenkins hash
402
429
       * for range 0-10000, output has the msb set to zero */
417
444
      // h = h ^ (h >>> 14)
418
445
      // h = h + (h << 4)
419
446
      // h ^ (h >>> 10)
 
447
 
 
448
      // the rest of the computation is due to SI-5293
 
449
      val rotation = seed % 32
 
450
      val rotated = (i >>> rotation) | (i << (32 - rotation))
 
451
      rotated
420
452
    }
421
453
  }
422
454
 
439
471
    val table: Array[HashEntry[A, Entry]],
440
472
    val tableSize: Int,
441
473
    val threshold: Int,
 
474
    val seedvalue: Int,
442
475
    val sizemap: Array[Int]
443
476
  ) {
444
 
    import collection.DebugUtils._
 
477
    import scala.collection.DebugUtils._
445
478
    private[collection] def debugInformation = buildString {
446
479
      append =>
447
480
      append("Hash table contents")
449
482
      append("Table: [" + arrayString(table, 0, table.length) + "]")
450
483
      append("Table size: " + tableSize)
451
484
      append("Load factor: " + loadFactor)
 
485
      append("Seedvalue: " + seedvalue)
452
486
      append("Threshold: " + threshold)
453
487
      append("Sizemap: [" + arrayString(sizemap, 0, sizemap.length) + "]")
454
488
    }