1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef mozilla_dom_TreeOrderedArrayInlines_h
8 #define mozilla_dom_TreeOrderedArrayInlines_h
10 #include "mozilla/dom/TreeOrderedArray.h"
11 #include "mozilla/BinarySearch.h"
12 #include "nsContentUtils.h"
13 #include <type_traits>
15 namespace mozilla::dom
{
17 template <typename Node
>
18 size_t TreeOrderedArray
<Node
>::Insert(Node
& aNode
) {
19 static_assert(std::is_base_of
<nsINode
, Node
>::value
, "Should be a node");
22 for (Node
* n
: mList
) {
23 MOZ_ASSERT(n
->SubtreeRoot() == aNode
.SubtreeRoot(),
24 "Should only insert nodes on the same subtree");
28 if (mList
.IsEmpty()) {
29 mList
.AppendElement(&aNode
);
33 struct PositionComparator
{
35 explicit PositionComparator(Node
& aNode
) : mNode(aNode
) {}
37 int operator()(void* aNode
) const {
38 auto* curNode
= static_cast<Node
*>(aNode
);
39 MOZ_DIAGNOSTIC_ASSERT(curNode
!= &mNode
,
40 "Tried to insert a node already in the list");
41 if (nsContentUtils::PositionIsBefore(&mNode
, curNode
)) {
49 BinarySearchIf(mList
, 0, mList
.Length(), PositionComparator(aNode
), &idx
);
50 mList
.InsertElementAt(idx
, &aNode
);
54 } // namespace mozilla::dom