Commits

John McCall committed cc7938ad217
Implement a trie data structure. Specifically, implement a ternary tree with a fixed-length per-node inline key buffer. I plan to use this for metadata path caches, where it's useful to be able to quickly find the most-derived point along a path that you've already cached, but it should be useful for other things in the compiler as well, like function-with-argument-label lookups and possibly code completion. This is quite a bit more space-efficient (and somewhat faster) than doing scans after a lower_bound on a std::map<std::string, T>. I haven't implemented balancing yet, and I don't need delete at all for metadata paths, so I don't plan to work on that. Swift SVN r32453