Jeff Law <l...@redhat.com> writes: > On 11/13/20 1:15 AM, Richard Sandiford via Gcc-patches wrote: >> We already have two splay tree implementations: the old C one in >> libiberty and a templated reimplementation of it in typed-splay-tree.h. >> However, they have some drawbacks: >> >> - They hard-code the assumption that nodes should have both a key and >> a value, which isn't always true. >> >> - They use the two-phase method of lookup, and so nodes need to store >> a temporary back pointer. We can avoid that overhead by using the >> top-down method (as e.g. the bitmap tree code already does). >> >> - The tree node has to own the key and the value. For some use cases >> it's more convenient to embed the tree links in the value instead. >> >> Also, a later patch wants to use splay trees to represent an >> adaptive total order: the splay tree itself records whether node N1 >> is less than node N2, and (in the worst case) comparing nodes is >> a splay operation. >> >> This patch therefore adds an alternative implementation. The main >> features are: >> >> - Nodes can optionally point back to their parents. >> >> - An Accessors class abstracts accessing child nodes and (where >> applicable) parent nodes, so that the information can be embedded >> in larger data structures. >> >> - There is no fixed comparison function at the class level. Instead, >> individual functions that do comparisons take a comparison function >> argument. >> >> - There are two styles of comparison function, optimised for different >> use cases. (See the comments in the patch for details.) >> >> - It's possible to do some operations directly on a given node, >> without knowing whether it's the root. This includes the comparison >> use case described above. >> >> This of course has its own set of drawbacks. It's really providing >> splay utility functions rather than a true ADT, and so is more low-level >> than the existing routines. It's mostly geared for cases in which the >> client code wants to participate in the splay operations to some extent. >> >> gcc/ >> * Makefile.in (OBJS): Add splay-tree-utils.o. >> * system.h: Include <array> when INCLUDE_ARRAY is defined. >> * selftest.h (splay_tree_cc_tests): Declare. >> * selftest-run-tests.c (selftest::run_tests): Run splay_tree_cc_tests. >> * splay-tree-utils.h: New file. >> * splay-tree-utils.tcc: Likewise. >> * splay-tree-utils.cc: Likewise. > I must admit, I'm not a fan of adding another splay tree. Though I > suspect the one in libiberty will be there forever since there could > well be clients outside our source base. > > The typed_splay_tree implementation however is internal to GCC and only > has a couple users (the JIT and fixit hints). Is there any chance we > could convert those two users to the new one? Your cover hints that's > not the case, but I'm going to explicitly ask :-)
Yeah, I agree it's not great to have three versions. I had a look at converting the uses of typed_splay_tree, and all of them seem to be a natural fit for the new scheme. In particular, although typed_splay_tree maps keys to values, in practice the keys are already part of the values. However, I think a natural conversion would need a couple of new helpers for “get or insert” type operations. Would it be OK to wait until GCC 12 stage 1 for that? Thanks, Richard
