diff options
author | Felix Mulder <felix.mulder@gmail.com> | 2016-11-02 11:08:28 +0100 |
---|---|---|
committer | Guillaume Martres <smarter@ubuntu.com> | 2016-11-22 01:35:07 +0100 |
commit | 8a61ff432543a29234193cd1f7c14abd3f3d31a0 (patch) | |
tree | a8147561d307af862c295cfc8100d271063bb0dd /compiler/src/dotty/tools/dotc/util/HashSet.scala | |
parent | 6a455fe6da5ff9c741d91279a2dc6fe2fb1b472f (diff) | |
download | dotty-8a61ff432543a29234193cd1f7c14abd3f3d31a0.tar.gz dotty-8a61ff432543a29234193cd1f7c14abd3f3d31a0.tar.bz2 dotty-8a61ff432543a29234193cd1f7c14abd3f3d31a0.zip |
Move compiler and compiler tests to compiler dir
Diffstat (limited to 'compiler/src/dotty/tools/dotc/util/HashSet.scala')
-rw-r--r-- | compiler/src/dotty/tools/dotc/util/HashSet.scala | 146 |
1 files changed, 146 insertions, 0 deletions
diff --git a/compiler/src/dotty/tools/dotc/util/HashSet.scala b/compiler/src/dotty/tools/dotc/util/HashSet.scala new file mode 100644 index 000000000..ff470ef5d --- /dev/null +++ b/compiler/src/dotty/tools/dotc/util/HashSet.scala @@ -0,0 +1,146 @@ +package dotty.tools.dotc.util + +/** A hash set that allows some privileged protected access to its internals + */ +class HashSet[T >: Null <: AnyRef](initialCapacity: Int, loadFactor: Float = 0.25f) extends Set[T] { + private var used: Int = _ + private var limit: Int = _ + private var table: Array[AnyRef] = _ + + 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 + 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] + h = index(h + 1) + entry = table(h) + } + addEntryAt(h, x) + } + + /** Add entry at `x` at index `idx` */ + private def addEntryAt(idx: Int, x: T) = { + table(idx) = x + used += 1 + 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) + while ((entry ne null) && !(x equals entry)) { + h = index(h + 1) + entry = table(h) + } + entry.asInstanceOf[T] + } + + private var rover: Int = -1 + + /** Add entry `x` to set */ + def addEntry(x: T): Unit = { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + if (x equals entry) return + h = index(h + 1) + entry = table(h) + } + table(h) = x + 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 = { + while (i < table.length && (table(i) eq null)) i += 1 + i < table.length + } + def next(): T = + if (hasNext) { i += 1; table(i - 1).asInstanceOf[T] } + 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) + while (entry ne null) { + h = index(h + 1) + entry = table(h) + } + table(h) = x + } + + private def growTable(): Unit = { + val oldtable = table + allocate(table.length * 2) + var i = 0 + while (i < oldtable.length) { + val entry = oldtable(i) + if (entry ne null) addOldEntry(entry.asInstanceOf[T]) + i += 1 + } + } + + override def toString() = "HashSet(%d / %d)".format(used, table.length) +} |