TreeOrderedArrayInlines.h (1699B)
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 <type_traits> 11 12 #include "mozilla/BinarySearch.h" 13 #include "mozilla/dom/TreeOrderedArray.h" 14 #include "nsContentUtils.h" 15 16 namespace mozilla::dom { 17 18 template <typename Node> 19 size_t TreeOrderedArray<Node>::Insert(Node& aNode, nsINode* aCommonAncestor) { 20 static_assert(std::is_base_of_v<nsINode, Node>, "Should be a node"); 21 22 auto span = Base::AsSpan(); 23 auto len = span.Length(); 24 if (!len) { 25 Base::AppendElement(&aNode); 26 return 0; 27 } 28 29 struct PositionComparator { 30 Node& mNode; 31 nsINode* mCommonAncestor = nullptr; 32 mutable nsContentUtils::NodeIndexCache mCache; 33 34 int operator()(void* aNode) const { 35 auto* curNode = static_cast<Node*>(aNode); 36 MOZ_DIAGNOSTIC_ASSERT(curNode != &mNode, 37 "Tried to insert a node already in the list"); 38 return nsContentUtils::CompareTreePosition<TreeKind::DOM>( 39 &mNode, curNode, mCommonAncestor, &mCache); 40 } 41 }; 42 43 PositionComparator cmp{aNode, aCommonAncestor}; 44 if (cmp(span[len - 1]) > 0) { 45 // Appending is a really common case, optimize for it. 46 Base::AppendElement(&aNode); 47 return len; 48 } 49 50 size_t idx; 51 BinarySearchIf(span, 0, len, cmp, &idx); 52 Base::InsertElementAt(idx, &aNode); 53 return idx; 54 } 55 56 } // namespace mozilla::dom 57 #endif