TreeOrderedArray.h (1676B)
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_TreeOrderedArray_h 8 #define mozilla_dom_TreeOrderedArray_h 9 10 #include "FastFrontRemovableArray.h" 11 12 class nsINode; 13 template <typename T> 14 class RefPtr; 15 16 namespace mozilla::dom { 17 18 // A sorted tree-ordered list of pointers (either raw or RefPtr) to nodes. 19 template <typename NodePointer> 20 class TreeOrderedArray : public FastFrontRemovableArray<NodePointer, 1> { 21 using Base = FastFrontRemovableArray<NodePointer, 1>; 22 23 template <typename T> 24 struct RawTypeExtractor {}; 25 26 template <typename T> 27 struct RawTypeExtractor<T*> { 28 using type = T; 29 }; 30 31 template <typename T> 32 struct RawTypeExtractor<RefPtr<T>> { 33 using type = T; 34 }; 35 36 using Node = typename RawTypeExtractor<NodePointer>::type; 37 38 public: 39 // Inserts a node into the list, and returns the new index in the array. 40 // 41 // All the nodes in the list should be in the same subtree, and debug builds 42 // assert this. 43 // 44 // It's also forbidden to call Insert() with the same node multiple times, and 45 // it will assert as well. 46 // 47 // You can provide a potential common ancestor to speed up comparisons, see 48 // nsContentUtils::CompareTreePosition. That's only a hint. 49 inline size_t Insert(Node&, nsINode* aCommonAncestor = nullptr); 50 bool RemoveElement(Node& aNode) { return Base::RemoveElement(&aNode); } 51 }; 52 53 } // namespace mozilla::dom 54 55 #endif