V4: Add headers from LLVM that define an intrusive list template

These intrusive list is used in the follow-up patch, where it is used to
hold a list of basic blocks in a function, and a list of instructions in
the basic block.

The advantage of this implementation is that it there is an easy and
direct access to iterators when you have an element, it defines STL-like
iterators, is double-linked, and you can easily insert before and after
elements. We don't have something like this in Qt, and it's better to
take an existing and well-tested implementation that making a home-grown
one.

Change-Id: Ie8c726eafe6d7558ae6a3550e8ecc2f15f362b17
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>

1 files changed, 53 insertions, 0 deletions

diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h
new file mode 100644
index 0000000000..e5062ac4ea
--- /dev/null
+++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h
@@ -0,0 +1,53 @@
+//===- llvm/ADT/ilist_node_base.h - Intrusive List Node Base -----*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_ILIST_NODE_BASE_H
+#define LLVM_ADT_ILIST_NODE_BASE_H
+
+#include "llvm/ADT/PointerIntPair.h"
+
+namespace llvm {
+
+/// Base class for ilist nodes.
+///
+/// Optionally tracks whether this node is the sentinel.
+template <bool EnableSentinelTracking> class ilist_node_base;
+
+template <> class ilist_node_base<false> {
+  ilist_node_base *Prev = nullptr;
+  ilist_node_base *Next = nullptr;
+
+public:
+  void setPrev(ilist_node_base *Prev) { this->Prev = Prev; }
+  void setNext(ilist_node_base *Next) { this->Next = Next; }
+  ilist_node_base *getPrev() const { return Prev; }
+  ilist_node_base *getNext() const { return Next; }
+
+  bool isKnownSentinel() const { return false; }
+  void initializeSentinel() {}
+};
+
+template <> class ilist_node_base<true> {
+  PointerIntPair<ilist_node_base *, 1> PrevAndSentinel;
+  ilist_node_base *Next = nullptr;
+
+public:
+  void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); }
+  void setNext(ilist_node_base *Next) { this->Next = Next; }
+  ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); }
+  ilist_node_base *getNext() const { return Next; }
+
+  bool isSentinel() const { return PrevAndSentinel.getInt(); }
+  bool isKnownSentinel() const { return isSentinel(); }
+  void initializeSentinel() { PrevAndSentinel.setInt(true); }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_ILIST_NODE_BASE_H