diff options
author | Martin Odersky <odersky@gmail.com> | 2014-02-24 13:21:24 +0100 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2014-02-24 18:56:48 +0100 |
commit | cdeafeafd252b20a0df5440e0420211af95e0cdc (patch) | |
tree | a2112ebe760b54d923f20305f2c29429d7f7cf6b /src/dotty/tools/dotc/util/HashSet.scala | |
parent | 91e74ee45c8cedac279ec66f8277c94d05f2f2e3 (diff) | |
download | dotty-cdeafeafd252b20a0df5440e0420211af95e0cdc.tar.gz dotty-cdeafeafd252b20a0df5440e0420211af95e0cdc.tar.bz2 dotty-cdeafeafd252b20a0df5440e0420211af95e0cdc.zip |
Resetting uniques and hashset reorg.
Uniques are now cleared after each run. Also, HashSets get a more standard API, without a label, but with configurable load factor.
Diffstat (limited to 'src/dotty/tools/dotc/util/HashSet.scala')
-rw-r--r-- | src/dotty/tools/dotc/util/HashSet.scala | 113 |
1 files changed, 64 insertions, 49 deletions
diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala index 44646e2ba..3c8ffa251 100644 --- a/src/dotty/tools/dotc/util/HashSet.scala +++ b/src/dotty/tools/dotc/util/HashSet.scala @@ -1,51 +1,57 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2012 LAMP/EPFL - * @author Martin Odersky - */ - package dotty.tools.dotc.util -object HashSet { - def apply[T >: Null <: AnyRef](): HashSet[T] = this(16) - def apply[T >: Null <: AnyRef](label: String): HashSet[T] = this(label, 16) - def apply[T >: Null <: AnyRef](initialCapacity: Int): HashSet[T] = this("No Label", initialCapacity) - def apply[T >: Null <: AnyRef](label: String, initialCapacity: Int): HashSet[T] = - new HashSet[T](label, initialCapacity) -} - -class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] with scala.collection.generic.Clearable { - private var used = 0 - private var table = new Array[AnyRef](initialCapacity) - private def index(x: Int): Int = math.abs(x % table.length) +/** A hash set that allows some priviliged protected access to its internals + */ +class HashSet[T >: Null <: AnyRef](initialCapacity: Int, loadFactor: Float = 0.25f) extends Set[T] with scala.collection.generic.Clearable { + private var used: Int = _ + private var limit: Int = _ + private var table: Array[AnyRef] = _ - def hash(x: T): Int = x.hashCode + clear() + /** The number of elements in the set */ def size: Int = used + + private def allocate(size: Int) = { + table = new Array[AnyRef](size) + limit = (size * loadFactor).toInt + } + + /** Remove all elements from this set and set back to initial configuration */ def clear(): Unit = { used = 0 - table = new Array[AnyRef](initialCapacity) + allocate(initialCapacity) } + /** Turn hashode `x` into a table index */ + private def index(x: Int): Int = math.abs(x % table.length) + + /** Hashcode, can be overridden */ + def hash(x: T): Int = x.hashCode + + /** Find entry such that `x equals entry`. If it exists, return it. + * If not, enter `x` in set and return `x`. + */ def findEntryOrUpdate(x: T): T = { var h = index(hash(x)) var entry = table(h) while (entry ne null) { - if (x equals entry) - return entry.asInstanceOf[T] - + if (x equals entry) return entry.asInstanceOf[T] h = index(h + 1) entry = table(h) } addEntryAt(h, x) } - private def addEntryAt(h: Int, x: T) = { - table(h) = x + /** Add entry at `x` at index `idx` */ + private def addEntryAt(idx: Int, x: T) = { + table(idx) = x used += 1 - if (used > (table.length >> 2)) growTable() + if (used > limit) growTable() x } + /** The entry in the set such that `x equals entry`, or else `null`. */ def findEntry(x: T): T = { var h = index(hash(x)) var entry = table(h) @@ -58,23 +64,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte private var rover: Int = -1 - protected def findEntryByHash(hashCode: Int): T = { - rover = index(hashCode) - nextEntryByHash(hashCode) - } - - protected def nextEntryByHash(hashCode: Int): T = { - var entry = table(rover) - while (entry ne null) { - rover = index(rover + 1) - if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T] - entry = table(rover) - } - null - } - - protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x) - + /** Add entry `x` to set */ def addEntry(x: T): Unit = { var h = index(hash(x)) var entry = table(h) @@ -87,10 +77,13 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte used += 1 if (used > (table.length >> 2)) growTable() } + + /** Add all entries in `xs` to set */ def addEntries(xs: TraversableOnce[T]): Unit = { xs foreach addEntry } + /** The iterator of all elements in the set */ def iterator = new Iterator[T] { private var i = 0 def hasNext: Boolean = { @@ -102,6 +95,32 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte else null } + /** Privileged access: Find first entry with given hashcode */ + protected def findEntryByHash(hashCode: Int): T = { + rover = index(hashCode) + nextEntryByHash(hashCode) + } + + /** Privileged access: Find next entry with given hashcode. Needs to immediately + * follow a `findEntryByhash` or `nextEntryByHash` operation. + */ + protected def nextEntryByHash(hashCode: Int): T = { + var entry = table(rover) + while (entry ne null) { + rover = index(rover + 1) + if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T] + entry = table(rover) + } + null + } + + /** Privileged access: Add entry `x` at the last position where an unsuccsessful + * `findEntryByHash` or `nextEntryByhash` operation returned. Needs to immediately + * follow a `findEntryByhash` or `nextEntryByHash` operation that was unsucessful, + * i.e. that returned `null`. + */ + protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x) + private def addOldEntry(x: T): Unit = { var h = index(hash(x)) var entry = table(h) @@ -114,12 +133,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte private def growTable(): Unit = { val oldtable = table - val growthFactor = - if (table.length <= initialCapacity) 8 - else if (table.length <= (initialCapacity * 8)) 4 - else 2 - - table = new Array[AnyRef](table.length * growthFactor) + allocate(table.length * 2) var i = 0 while (i < oldtable.length) { val entry = oldtable(i) @@ -127,5 +141,6 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte i += 1 } } - override def toString() = "HashSet %s(%d / %d)".format(label, used, table.length) + + override def toString() = "HashSet(%d / %d)".format(used, table.length) } |