This file is indexed.

/usr/include/ns3.26/ns3/heap-scheduler.h is in libns3-dev 3.26+dfsg-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2005 INRIA
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
 */

#ifndef HEAP_SCHEDULER_H
#define HEAP_SCHEDULER_H

#include "scheduler.h"
#include <stdint.h>
#include <vector>

/**
 * \file
 * \ingroup scheduler
 * Declaration of ns3::HeapScheduler class.
 */

namespace ns3 {

/**
 * \ingroup scheduler
 * \brief a binary heap event scheduler
 *
 * This code started as a c++ translation of a java-based code written in 2005
 * to implement a heap sort. So, this binary heap is really a pretty
 * straightforward implementation of the classic data structure. Not much to say
 * about it.
 *
 * What is smart about this code ?
 *  - it does not use the index 0 in the array to avoid having to convert
 *    C-style array indexes (which start at zero) and heap-style indexes
 *    (which start at 1). This is why _all_ indexes start at 1, and that
 *    the index of the root is 1.
 *  - It uses a slightly non-standard while loop for top-down heapify
 *    to move one if statement out of the loop.
 */
class HeapScheduler : public Scheduler
{
public:
  /**
   *  Register this type.
   *  \return The object TypeId.
   */
  static TypeId GetTypeId (void);

  /** Constructor. */
  HeapScheduler ();
  /** Destructor. */
  virtual ~HeapScheduler ();

  // Inherited
  virtual void Insert (const Scheduler::Event &ev);
  virtual bool IsEmpty (void) const;
  virtual Scheduler::Event PeekNext (void) const;
  virtual Scheduler::Event RemoveNext (void);
  virtual void Remove (const Scheduler::Event &ev);

private:
  /** Event list type:  vector of Events, managed as a heap. */
  typedef std::vector<Scheduler::Event> BinaryHeap;

  /**
   * Get the parent index of a given entry.
   *
   * \param [in] id The child index.
   * \return The index of the parent of \p id.
   */
  inline uint32_t Parent (uint32_t id) const;
  /**
   * Get the next sibling of a given entry.
   *
   * \param [in] id The starting index.
   * \returns The next sibling of \p id.
   */
  uint32_t Sibling (uint32_t id) const;
  /**
   * Get the left child of a given entry.
   *
   * \param [in] id The parent index.
   * \returns The index of the left (first) child.
   */
  inline uint32_t LeftChild (uint32_t id) const;
  /**
   * Get the right child index of a given entry.
   *
   * \param [in] id The parent index.
   * \returns The index of the right (second) child.
   */
  inline uint32_t RightChild (uint32_t id) const;
  /**
   * Get the root index of the heap.
   *
   * \returns The root index.
   */
  inline uint32_t Root (void) const;
  /**
   * Return the index of the last element.
   * \returns The last index.
   */
  uint32_t Last (void) const;
  /**
   * Test if an index is the root.
   *
   * \param [in] id The index to test.
   * \returns \c true if the \p id is the root.
   */
  inline bool IsRoot (uint32_t id) const;
  /**
   * Test if an index is at the bottom of the heap.
   *
   * \param [in] id The index to test.
   * \returns \c true if the index is at the bottom.
   */
  inline bool IsBottom (uint32_t id) const;
  /**
   * Compare (less than) two items.
   *
   * \param [in] a The first item.
   * \param [in] b The second item.
   * \returns \c true if \c a < \c b
   */
  inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
  /**
   * Minimum of two items.
   *
   * \param [in] a The first item.
   * \param [in] b The second item.
   * \returns The smaller of the two items.
   */
  inline uint32_t Smallest (uint32_t a, uint32_t b) const;
  /**
   * Swap two items.
   *
   * \param [in] a The first item.
   * \param [in] b The second item.
   */
  inline void Exch (uint32_t a, uint32_t b);
  /** Percolate a newly inserted Last item to its proper position. */ 
  void BottomUp (void);
  /**
   * Percolate a deletion bubble down the heap.
   *
   * \param [in] start Starting entry.
   */
  void TopDown (uint32_t start);

  /** The event list. */
  BinaryHeap m_heap;
};

} // namespace ns3

#endif /* HEAP_SCHEDULER_H */