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/. */
6
7 #ifndef mozilla_dom_TreeOrderedArrayInlines_h
8 #define mozilla_dom_TreeOrderedArrayInlines_h
9
10 #include "mozilla/dom/TreeOrderedArray.h"
11 #include "mozilla/BinarySearch.h"
12 #include "nsContentUtils.h"
13 #include <type_traits>
14
15 namespace mozilla {
16 namespace dom {
17
18 template <typename Node>
Insert(Node & aNode)19 size_t TreeOrderedArray<Node>::Insert(Node& aNode) {
20 static_assert(std::is_base_of<nsINode, Node>::value, "Should be a node");
21
22 #ifdef DEBUG
23 for (Node* n : mList) {
24 MOZ_ASSERT(n->SubtreeRoot() == aNode.SubtreeRoot(),
25 "Should only insert nodes on the same subtree");
26 }
27 #endif
28
29 if (mList.IsEmpty()) {
30 mList.AppendElement(&aNode);
31 return 0;
32 }
33
34 struct PositionComparator {
35 Node& mNode;
36 explicit PositionComparator(Node& aNode) : mNode(aNode) {}
37
38 int operator()(void* aNode) const {
39 auto* curNode = static_cast<Node*>(aNode);
40 MOZ_DIAGNOSTIC_ASSERT(curNode != &mNode,
41 "Tried to insert a node already in the list");
42 if (nsContentUtils::PositionIsBefore(&mNode, curNode)) {
43 return -1;
44 }
45 return 1;
46 }
47 };
48
49 size_t idx;
50 BinarySearchIf(mList, 0, mList.Length(), PositionComparator(aNode), &idx);
51 mList.InsertElementAt(idx, &aNode);
52 return idx;
53 }
54
55 } // namespace dom
56 } // namespace mozilla
57 #endif
58