/work/obj-fuzz/dist/include/nsTPriorityQueue.h

Source (jump to first uncovered line)
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef NS_TPRIORITY_QUEUE_H_
#define NS_TPRIORITY_QUEUE_H_

#include "nsTArray.h"
#include "nsDebug.h"

/**
 * A templatized priority queue data structure that uses an nsTArray to serve as
 * a binary heap. The default comparator causes this to act like a min-heap.
 * Only the LessThan method of the comparator is used.
 */
template<class T, class Compare = nsDefaultComparator<T, T>>
class nsTPriorityQueue
{
public:
  typedef typename nsTArray<T>::size_type size_type;

  /**
   * Default constructor also creates a comparator object using the default
   * constructor for type Compare.
   */
  nsTPriorityQueue() : mCompare(Compare()) {}

  /**
   * Constructor to allow a specific instance of a comparator object to be
   * used.
   */
  explicit nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) {}

  /**
   * Copy constructor
   */
  nsTPriorityQueue(const nsTPriorityQueue& aOther)
    : mElements(aOther.mElements)
    , mCompare(aOther.mCompare)
  {
  }

  /**
   * @return True if the queue is empty or false otherwise.
   */
  bool IsEmpty() const { return mElements.IsEmpty(); }

  /**
   * @return The number of elements in the queue.
   */
  size_type Length() const { return mElements.Length(); }

  /**
   * @return The topmost element in the queue without changing the queue. This
   * is the element 'a' such that there is no other element 'b' in the queue for
   * which Compare(b, a) returns true. (Since this container does not check
   * for duplicate entries there may exist 'b' for which Compare(a, b) returns
   * false.)
   */
  const T& Top() const
  {
    MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
    return mElements[0];
  }

  /**
   * Adds an element to the queue
   * @param aElement The element to add
   * @return true on success, false on out of memory.
   */
  bool Push(const T& aElement)
  {
    T* elem = mElements.AppendElement(aElement);
    if (!elem) {
      return false;  // Out of memory
    }

    // Sift up
    size_type i = mElements.Length() - 1;
    while (i) {
      size_type parent = (size_type)((i - 1) / 2);
      if (mCompare.LessThan(mElements[parent], mElements[i])) {
        break;
      }
      Swap(i, parent);
      i = parent;
    }

    return true;
  }

  /**
   * Removes and returns the top-most element from the queue.
   * @return The topmost element, that is, the element 'a' such that there is no
   * other element 'b' in the queue for which Compare(b, a) returns true.
   * @see Top()
   */
  T Pop()
  {
    MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
    T pop = mElements[0];

    // Move last to front
    mElements[0] = mElements[mElements.Length() - 1];
    mElements.TruncateLength(mElements.Length() - 1);

    // Sift down
    size_type i = 0;
    while (2 * i + 1 < mElements.Length()) {
      size_type swap = i;
      size_type l_child = 2 * i + 1;
      if (mCompare.LessThan(mElements[l_child], mElements[i])) {
        swap = l_child;
      }
      size_type r_child = l_child + 1;
      if (r_child < mElements.Length() &&
          mCompare.LessThan(mElements[r_child], mElements[swap])) {
        swap = r_child;
      }
      if (swap == i) {
        break;
      }
      Swap(i, swap);
      i = swap;
    }

    return pop;
  }

  /**
   * Removes all elements from the queue.
   */
  void Clear() { mElements.Clear(); }

  /**
   * Provides readonly access to the queue elements as an array. Generally this
   * should be avoided but may be needed in some situations such as when the
   * elements contained in the queue need to be enumerated for cycle-collection.
   * @return A pointer to the first element of the array.  If the array is
   * empty, then this pointer must not be dereferenced.
   */
  const T* Elements() const { return mElements.Elements(); }

protected:
  /**
   * Swaps the elements at the specified indices.
   */
  void Swap(size_type aIndexA, size_type aIndexB)
  {
    T temp = mElements[aIndexA];
    mElements[aIndexA] = mElements[aIndexB];
    mElements[aIndexB] = temp;
  }

  nsTArray<T> mElements;
  Compare mCompare; // Comparator object
};

#endif // NS_TPRIORITY_QUEUE_H_

Line	Count	Source (jump to first uncovered line)
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 NS_TPRIORITY_QUEUE_H_
8		#define NS_TPRIORITY_QUEUE_H_
9
10		#include "nsTArray.h"
11		#include "nsDebug.h"
12
13		/**
14		* A templatized priority queue data structure that uses an nsTArray to serve as
15		* a binary heap. The default comparator causes this to act like a min-heap.
16		* Only the LessThan method of the comparator is used.
17		*/
18		template<class T, class Compare = nsDefaultComparator<T, T>>
19		class nsTPriorityQueue
20		{
21		public:
22		typedef typename nsTArray<T>::size_type size_type;
23
24		/**
25		* Default constructor also creates a comparator object using the default
26		* constructor for type Compare.
27		*/
28	0	nsTPriorityQueue() : mCompare(Compare()) {} Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::nsTPriorityQueue() Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::nsTPriorityQueue() Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::nsTPriorityQueue() Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::nsTPriorityQueue()
29
30		/**
31		* Constructor to allow a specific instance of a comparator object to be
32		* used.
33		*/
34	0	explicit nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) {}
35
36		/**
37		* Copy constructor
38		*/
39		nsTPriorityQueue(const nsTPriorityQueue& aOther)
40		: mElements(aOther.mElements)
41		, mCompare(aOther.mCompare)
42	0	{
43	0	} Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::nsTPriorityQueue(nsTPriorityQueue<int, nsDefaultComparator<int, int> > const&) Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::nsTPriorityQueue(nsTPriorityQueue<int, MaxCompare<int> > const&)
44
45		/**
46		* @return True if the queue is empty or false otherwise.
47		*/
48	0	bool IsEmpty() const { return mElements.IsEmpty(); } Unexecuted instantiation: nsTPriorityQueue<nsListIter, CookieIterComparator>::IsEmpty() const Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::IsEmpty() const Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::IsEmpty() const Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::IsEmpty() const Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::IsEmpty() const
49
50		/**
51		* @return The number of elements in the queue.
52		*/
53	0	size_type Length() const { return mElements.Length(); } Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::Length() const Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::Length() const Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::Length() const
54
55		/**
56		* @return The topmost element in the queue without changing the queue. This
57		* is the element 'a' such that there is no other element 'b' in the queue for
58		* which Compare(b, a) returns true. (Since this container does not check
59		* for duplicate entries there may exist 'b' for which Compare(a, b) returns
60		* false.)
61		*/
62		const T& Top() const
63	0	{
64	0	MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
65	0	return mElements[0];
66	0	} Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::Top() const Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::Top() const Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::Top() const
67
68		/**
69		* Adds an element to the queue
70		* @param aElement The element to add
71		* @return true on success, false on out of memory.
72		*/
73		bool Push(const T& aElement)
74	0	{
75	0	T* elem = mElements.AppendElement(aElement);
76	0	if (!elem) {
77	0	return false; // Out of memory
78	0	}
79	0
80	0	// Sift up
81	0	size_type i = mElements.Length() - 1;
82	0	while (i) {
83	0	size_type parent = (size_type)((i - 1) / 2);
84	0	if (mCompare.LessThan(mElements[parent], mElements[i])) {
85	0	break;
86	0	}
87	0	Swap(i, parent);
88	0	i = parent;
89	0	}
90	0
91	0	return true;
92	0	} Unexecuted instantiation: nsTPriorityQueue<nsListIter, CookieIterComparator>::Push(nsListIter const&) Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::Push(RefPtr<mozilla::MediaData> const&) Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::Push(nsSMILTimeContainer::MilestoneEntry const&) Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::Push(int const&) Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::Push(int const&)
93
94		/**
95		* Removes and returns the top-most element from the queue.
96		* @return The topmost element, that is, the element 'a' such that there is no
97		* other element 'b' in the queue for which Compare(b, a) returns true.
98		* @see Top()
99		*/
100		T Pop()
101	0	{
102	0	MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
103	0	T pop = mElements[0];
104	0
105	0	// Move last to front
106	0	mElements[0] = mElements[mElements.Length() - 1];
107	0	mElements.TruncateLength(mElements.Length() - 1);
108	0
109	0	// Sift down
110	0	size_type i = 0;
111	0	while (2 * i + 1 < mElements.Length()) {
112	0	size_type swap = i;
113	0	size_type l_child = 2 * i + 1;
114	0	if (mCompare.LessThan(mElements[l_child], mElements[i])) {
115	0	swap = l_child;
116	0	}
117	0	size_type r_child = l_child + 1;
118	0	if (r_child < mElements.Length() &&
119	0	mCompare.LessThan(mElements[r_child], mElements[swap])) {
120	0	swap = r_child;
121	0	}
122	0	if (swap == i) {
123	0	break;
124	0	}
125	0	Swap(i, swap);
126	0	i = swap;
127	0	}
128	0
129	0	return pop;
130	0	} Unexecuted instantiation: nsTPriorityQueue<nsListIter, CookieIterComparator>::Pop() Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::Pop() Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::Pop() Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::Pop() Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::Pop()
131
132		/**
133		* Removes all elements from the queue.
134		*/
135	0	void Clear() { mElements.Clear(); } Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::Clear() Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::Clear() Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::Clear()
136
137		/**
138		* Provides readonly access to the queue elements as an array. Generally this
139		* should be avoided but may be needed in some situations such as when the
140		* elements contained in the queue need to be enumerated for cycle-collection.
141		* @return A pointer to the first element of the array. If the array is
142		* empty, then this pointer must not be dereferenced.
143		*/
144	0	const T* Elements() const { return mElements.Elements(); }
145
146		protected:
147		/**
148		* Swaps the elements at the specified indices.
149		*/
150		void Swap(size_type aIndexA, size_type aIndexB)
151	0	{
152	0	T temp = mElements[aIndexA];
153	0	mElements[aIndexA] = mElements[aIndexB];
154	0	mElements[aIndexB] = temp;
155	0	} Unexecuted instantiation: nsTPriorityQueue<nsListIter, CookieIterComparator>::Swap(unsigned long, unsigned long) Unexecuted instantiation: nsTPriorityQueue<RefPtr<mozilla::MediaData>, mozilla::ReorderQueueComparator>::Swap(unsigned long, unsigned long) Unexecuted instantiation: nsTPriorityQueue<nsSMILTimeContainer::MilestoneEntry, nsDefaultComparator<nsSMILTimeContainer::MilestoneEntry, nsSMILTimeContainer::MilestoneEntry> >::Swap(unsigned long, unsigned long) Unexecuted instantiation: nsTPriorityQueue<int, nsDefaultComparator<int, int> >::Swap(unsigned long, unsigned long) Unexecuted instantiation: nsTPriorityQueue<int, MaxCompare<int> >::Swap(unsigned long, unsigned long)
156
157		nsTArray<T> mElements;
158		Compare mCompare; // Comparator object
159		};
160
161		#endif // NS_TPRIORITY_QUEUE_H_

Coverage Report

Created: 2018-09-25 14:53