93 lines
2.7 KiB
C
93 lines
2.7 KiB
C
|
//===- llvm/ADT/ilist_base.h - Intrusive List Base --------------*- C++ -*-===//
|
||
|
|
//
|
||
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
||
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
||
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
||
|
|
//
|
||
|
|
//===----------------------------------------------------------------------===//
|
||
|
|
|
||
|
|
#ifndef LLVM_ADT_ILIST_BASE_H
|
||
|
|
#define LLVM_ADT_ILIST_BASE_H
|
||
|
|
|
||
|
|
#include "llvm/ADT/ilist_node_base.h"
|
||
|
|
#include <cassert>
|
||
|
|
|
||
|
|
namespace llvm {
|
||
|
|
|
||
|
|
/// Implementations of list algorithms using ilist_node_base.
|
||
|
|
template <bool EnableSentinelTracking> class ilist_base {
|
||
|
|
public:
|
||
|
|
using node_base_type = ilist_node_base<EnableSentinelTracking>;
|
||
|
|
|
||
|
|
static void insertBeforeImpl(node_base_type &Next, node_base_type &N) {
|
||
|
|
node_base_type &Prev = *Next.getPrev();
|
||
|
|
N.setNext(&Next);
|
||
|
|
N.setPrev(&Prev);
|
||
|
|
Prev.setNext(&N);
|
||
|
|
Next.setPrev(&N);
|
||
|
|
}
|
||
|
|
|
||
|
|
static void removeImpl(node_base_type &N) {
|
||
|
|
node_base_type *Prev = N.getPrev();
|
||
|
|
node_base_type *Next = N.getNext();
|
||
|
|
Next->setPrev(Prev);
|
||
|
|
Prev->setNext(Next);
|
||
|
|
|
||
|
|
// Not strictly necessary, but helps catch a class of bugs.
|
||
|
|
N.setPrev(nullptr);
|
||
|
|
N.setNext(nullptr);
|
||
|
|
}
|
||
|
|
|
||
|
|
static void removeRangeImpl(node_base_type &First, node_base_type &Last) {
|
||
|
|
node_base_type *Prev = First.getPrev();
|
||
|
|
node_base_type *Final = Last.getPrev();
|
||
|
|
Last.setPrev(Prev);
|
||
|
|
Prev->setNext(&Last);
|
||
|
|
|
||
|
|
// Not strictly necessary, but helps catch a class of bugs.
|
||
|
|
First.setPrev(nullptr);
|
||
|
|
Final->setNext(nullptr);
|
||
|
|
}
|
||
|
|
|
||
|
|
static void transferBeforeImpl(node_base_type &Next, node_base_type &First,
|
||
|
|
node_base_type &Last) {
|
||
|
|
if (&Next == &Last || &First == &Last)
|
||
|
|
return;
|
||
|
|
|
||
|
|
// Position cannot be contained in the range to be transferred.
|
||
|
|
assert(&Next != &First &&
|
||
|
|
// Check for the most common mistake.
|
||
|
|
"Insertion point can't be one of the transferred nodes");
|
||
|
|
|
||
|
|
node_base_type &Final = *Last.getPrev();
|
||
|
|
|
||
|
|
// Detach from old list/position.
|
||
|
|
First.getPrev()->setNext(&Last);
|
||
|
|
Last.setPrev(First.getPrev());
|
||
|
|
|
||
|
|
// Splice [First, Final] into its new list/position.
|
||
|
|
node_base_type &Prev = *Next.getPrev();
|
||
|
|
Final.setNext(&Next);
|
||
|
|
First.setPrev(&Prev);
|
||
|
|
Prev.setNext(&First);
|
||
|
|
Next.setPrev(&Final);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T> static void insertBefore(T &Next, T &N) {
|
||
|
|
insertBeforeImpl(Next, N);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T> static void remove(T &N) { removeImpl(N); }
|
||
|
|
template <class T> static void removeRange(T &First, T &Last) {
|
||
|
|
removeRangeImpl(First, Last);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T> static void transferBefore(T &Next, T &First, T &Last) {
|
||
|
|
transferBeforeImpl(Next, First, Last);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
} // end namespace llvm
|
||
|
|
|
||
|
|
#endif // LLVM_ADT_ILIST_BASE_H
|