SparseSet: Add support for key-derived indexes and arbitrary key types.
authorAndrew Trick <atrick@apple.com>
Fri, 20 Apr 2012 20:05:28 +0000 (20:05 +0000)
committerAndrew Trick <atrick@apple.com>
Fri, 20 Apr 2012 20:05:28 +0000 (20:05 +0000)
commitc0ccb8bb17028fe0dda139c0972c0125d10e6053
tree680c2bd59b9c547b0b90cf30057a5db302ad049d
parent918f38ab2420bbdc350a6ec8c6ba6b09e37126b2
SparseSet: Add support for key-derived indexes and arbitrary key types.

This nicely handles the most common case of virtual register sets, but
also handles anticipated cases where we will map pointers to IDs.

The goal is not to develop a completely generic SparseSet
template. Instead we want to handle the expected uses within llvm
without any template antics in the client code. I'm adding a bit of
template nastiness here, and some assumption about expected usage in
order to make the client code very clean.

The expected common uses cases I'm designing for:
- integer keys that need to be reindexed, and may map to additional
  data
- densely numbered objects where we want pointer keys because no
  number->object map exists.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155227 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/ADT/IndexedMap.h
include/llvm/ADT/STLExtras.h
include/llvm/ADT/SparseSet.h
include/llvm/CodeGen/ScheduleDAGInstrs.h
lib/CodeGen/RegAllocFast.cpp
lib/CodeGen/ScheduleDAGInstrs.cpp
unittests/ADT/SparseSetTest.cpp