ADT: Split out simple_ilist, a simple intrusive list

Split out a new, low-level intrusive list type with clear semantics.
Unlike iplist (and ilist), all operations on simple_ilist are intrusive,
and simple_ilist never takes ownership of its nodes.  This enables an
intuitive API that has the right defaults for intrusive lists.
- insert() takes references (not pointers!) to nodes (in iplist/ilist,
  passing a reference will cause the node to be copied).
- erase() takes only iterators (like std::list), and does not destroy
  the nodes.
- remove() takes only references and has the same behaviour as erase().
- clear() does not destroy the nodes.
- The destructor does not destroy the nodes.
- New API {erase,remove,clear}AndDispose() take an extra Disposer
  functor for callsites that want to call some disposal routine (e.g.,
  std::default_delete).

This list is not currently configurable, and has no callbacks.

The initial motivation was to fix iplist<>::sort to work correctly (even
with callbacks in ilist_traits<>).  iplist<> uses simple_ilist<>::sort
directly.  The new test in unittests/IR/ModuleTest.cpp crashes without
this commit.

Fixing sort() via a low-level layer provided a good opportunity to:
- Unit test the low-level functionality thoroughly.
- Modernize the API, largely inspired by other intrusive list
  implementations.

Here's a sketch of a longer-term plan:
- Create BumpPtrList<>, a non-intrusive list implemented using
  simple_ilist<>, and use it for the Token list in
  lib/Support/YAMLParser.cpp.  This will factor out the only real use of
  createNode().
- Evolve the iplist<> and ilist<> APIs in the direction of
  simple_ilist<>, making allocation/deallocation explicit at call sites
  (similar to simple_ilist<>::eraseAndDispose()).
- Factor out remaining calls to createNode() and deleteNode() and remove
  the customization from ilist_traits<>.
- Transition uses of iplist<>/ilist<> that don't need callbacks over to
  simple_ilist<>.

llvm-svn: 280107

0 files changed, 0 insertions, 0 deletions