This file is indexed.

/usr/include/vl/heap-def.h is in libvlfeat-dev 0.9.20+dfsg0-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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
/** @file   heap-def.h
 ** @brief  Heap preprocessor metaprogram
 ** @author Andrea Vedaldi
 **/

/*
Copyright (C) 2007-12 Andrea Vedaldi and Brian Fulkerson.
All rights reserved.

This file is part of the VLFeat library and is made available under
the terms of the BSD license (see the COPYING file).
*/

/** @file heap-def.h

 A heap organizes an array of objects in a priority queue. This module
 is a template metaprogram that defines heap operations on array of
 generic objects, or even generic object containers.

 - @ref heap-def-overview "Overview"
   - @ref heap-def-overview-general "General usage"
 - @ref heap-def-tech "Technical details"

 <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
 @section heap-def-overview Overview
 <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

 To use @ref heap-def.h one must specify at least a prefix and the data
 type for the heap elements:

 @code
 #define VL_HEAP_prefix  my_heap
 #define VL_HEAP_type    float
 #include <vl/heap-def.h>
 @endcode

 This code fragment defines a number of functions prefixed by
 ::VL_HEAP_prefix, such as @c my_heap_push (::VL_HEAP_push) and @c
 my_heap_pop (::VL_HEAP_pop), that implement the heap operations.
 These functions operate on an array that has type ::VL_HEAP_array.
 By default, this is defined to be:

 @code
 #define VL_HEAP_array VL_HEAP_type*
 #define VL_HEAP_array_const VL_HEAP_type const*
 @endcode

 The array itself is accessed uniquely by means of two functions:

 - ::VL_HEAP_cmp, that compares two array elements. The default
   implementation assumes that ::VL_HEAP_type is numeric.
 - ::VL_HEAP_swap, that swaps two array elements. The default
   implementation assumes that ::VL_HEAP_type can be copied by the @c
   = operator.

 The heap state is a integer @c numElements (of type ::vl_size) counting
 the number of elements of the array that are currently part of the heap
 and the content of the first @c numElements elements of the array. The
 portion of the array that constitutes the heap satisfies a certain
 invariant property (heap property, @ref heap-def-tech). From a user
 viewpoint, the most important consequence is that the first element
 of the array (the one of index 0) is also the smallest (according to
 ::VL_HEAP_cmp).

 Elements are added to the heap by ::VL_HEAP_push and removed from the
 heap by ::VL_HEAP_pop.  A push operation adds to the heap the array
 element immediately after the last element already in the heap
 (i.e. the element of index @c numElements) and increases the number of
 heap elements @c numElements. Elements in the heap are swapped as required in
 order to maintain the heap consistency.  Similarly, a pop operation
 removes the first (smaller) element from the heap and decreases the
 number of heap elements @c numElements.

 The values of nodes currently in the heap can be updated by
 ::VL_HEAP_update. Notice however that using this function requires
 knowing the index of the element that needs to be updated up to the
 swapping operations that the heap performs to maintain
 consistency. Typically, this requires redefining ::VL_HEAP_swap to
 keep track of such changes (@ref heap-def-overview-general).

 <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
 @subsection heap-def-overview-general General usage
 <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

 The heap container may be mapped to any type by reimplementing
 ::VL_HEAP_cmp and ::VL_HEAP_swap explicitly. For instance
 the following code redefines ::VL_HEAP_cmp to deal with the case
 in which the heap is an array of structures:

 @code
 typedef struct _S { int x ; } S ;
 int s_cmp (S const * v, vl_uindex a, vl_uindex b) {
   return v[a].x - v[b].x ;
 }
 #define VL_HEAP_prefix  s_heap
 #define VL_HEAP_type    S
 #define VL_HEAP_cmp     s_cmp
 #include <vl/heap-def.h>
 @endcode

 In the following example, the heap itself is an arbitrary structure:

 @code
 typedef struct _H { int* array ; } H ;
 int h_cmp (H const * h, vl_uindex a, vl_uindex b) {
   return h->array[a] - h->array[b] ;
 }
 int h_swap (H * h, vl_uindex a, vl_uindex b) {
   int t = h->array[a] ;
   h->array[a] = h->array[b] ;
   h->array[b] = t ;
 }
 #define VL_HEAP_prefix  h_heap
 #define VL_HEAP_swap    h_swap
 #define VL_HEAP_cmp     h_cmp
 #include <vl/heap-def.h>
 @endcode

 <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
 @section heap-def-tech Technical details
 <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

 The heap is organised as a binary tree with the property (<em>heap
 property</em>) that any node is not larger than any of its
 children. In particular, the root is the smallest node.

 @ref heap-def.h uses the standard binary tree representation as a linear
 array. Tree nodes are mapped to array elements as follows:
 <code>array[0]</code> corresponds to the root, <code>array[1]</code>
 and <code>array[2]</code> to the root left and right children and so
 on.  In this way, the tree structure is fully specified by the total
 number of nodes <code>N</code>.

 Assuming that the heap has <code>N</code> nodes (from
 <code>array[0]</code> to <code>array[N-1]</code>), adding the node
 <code>array[N]</code> to the heap is done by a <em>push down</em>
 operation: if the node <code>array[N]</code> is smaller than its
 parent (violating the heap property) it is pushed down by swapping it
 with the parent, and so on recursively.

 Removing the smallest element <code>array[0]</code> with an heap of
 <code>N</code> nodes is done by swapping <code>array[0]</code> with
 <code>array[N-1]</code>. If then <code>array[0]</code> is larger than
 any of its children, it is swapped with the smallest of the two and
 so on recursively (<em>push up</em> operation).

 Restoring the heap property after an element <code>array[i]</code>
 has been modified can be done by a push up or push down operation on
 that node.

 **/

#include "host.h"
#include <assert.h>

#ifndef VL_HEAP_prefix
#error "VL_HEAP_prefix must be defined"
#endif

#ifndef VL_HEAP_array
#ifndef VL_HEAP_type
#error "VL_HEAP_type must be defined if VL_HEAP_array is not"
#endif
#define VL_HEAP_array       VL_HEAP_type*
#define VL_HEAP_array_const VL_HEAP_type const*
#endif

#ifndef VL_HEAP_array_const
#define VL_HEAP_array_const VL_HEAP_array
#endif

#ifdef __DOXYGEN__
#define VL_HEAP_prefix  HeapObject       /**< Prefix of the heap functions */
#define VL_HEAP_type    HeapType         /**< Data type of the heap elements */
#define VL_HEAP_array   HeapType*        /**< Data type of the heap container */
#define VL_HEAP_array   HeapType const*  /**< Const data type of the heap container */
#endif

/* ---------------------------------------------------------------- */

#ifndef VL_HEAP_DEF_H
#define VL_HEAP_DEF_H

/** @internal @brief Get index of parent node
 ** @param index a node index.
 ** @return index of the parent node.
 **/

VL_INLINE vl_uindex
vl_heap_parent (vl_uindex index)
{
  if (index == 0) return 0 ;
  return (index - 1) / 2 ;
}

/** @internal @brief Get index of left child
 ** @param index a node index.
 ** @return index of the left child.
 **/

VL_INLINE vl_uindex
vl_heap_left_child (vl_uindex index)
{
  return 2 * index + 1 ;
}

/** @internal @brief Get index of right child
 ** @param index a node index.
 ** @return index of the right child.
 **/

VL_INLINE vl_uindex
vl_heap_right_child (vl_uindex index)
{
  return vl_heap_left_child (index) + 1 ;
}

/* VL_HEAP_DEF_H */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_cmp) || defined(__DOXYGEN__)
#define VL_HEAP_cmp VL_XCAT(VL_HEAP_prefix, _cmp)

/** @brief Compare two heap elements
 ** @param array heap array.
 ** @param indexA index of the first element @c A to compare.
 ** @param indexB index of the second element @c B to comapre.
 ** @return a negative number if @c A<B, 0 if @c A==B, and
 ** a positive number if if @c A>B.
 **/

VL_INLINE VL_HEAP_type
VL_HEAP_cmp
(VL_HEAP_array_const array,
 vl_uindex indexA,
 vl_uindex indexB)
{
  return array[indexA] - array[indexB] ;
}

/* VL_HEAP_cmp */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_swap) || defined(__DOXYGEN__)
#define VL_HEAP_swap VL_XCAT(VL_HEAP_prefix, _swap)

/** @brief Swap two heap elements
 ** @param array array of nodes.
 ** @param array heap array.
 ** @param indexA index of the first node to swap.
 ** @param indexB index of the second node to swap.
 **
 ** The function swaps the two heap elements @a a and @ b. The function
 ** uses a temporary element and the copy operator, which must be
 ** well defined for the heap elements.
 **/

VL_INLINE void
VL_HEAP_swap
(VL_HEAP_array array,
 vl_uindex indexA,
 vl_uindex indexB)
{
  VL_HEAP_type t = array [indexA] ;
  array [indexA] = array [indexB] ;
  array [indexB] = t ;
}

/* VL_HEAP_swap */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_up) || defined(__DOXYGEN__)
#define VL_HEAP_up VL_XCAT(VL_HEAP_prefix, _up)

/** @brief Heap up operation
 ** @param array pointer to the heap array.
 ** @param heapSize size of the heap.
 ** @param index index of the node to push up.
 **/

VL_INLINE void
VL_HEAP_up
(VL_HEAP_array array, vl_size heapSize, vl_uindex index)
{
  vl_uindex leftIndex  = vl_heap_left_child (index) ;
  vl_uindex rightIndex = vl_heap_right_child (index) ;

  /* no childer: stop */
  if (leftIndex >= heapSize) return ;

  /* only left childer: easy */
  if (rightIndex >= heapSize) {
    if (VL_HEAP_cmp (array, index, leftIndex) > 0) {
      VL_HEAP_swap (array, index, leftIndex) ;
    }
    return ;
  }

  /* both childern */
  {
    if (VL_HEAP_cmp (array, leftIndex, rightIndex) < 0) {
      /* swap with left */
      if (VL_HEAP_cmp (array, index, leftIndex) > 0) {
        VL_HEAP_swap (array, index, leftIndex) ;
        VL_HEAP_up (array, heapSize, leftIndex) ;
      }
    } else {
      /* swap with right */
      if (VL_HEAP_cmp (array, index, rightIndex) > 0) {
        VL_HEAP_swap (array, index, rightIndex) ;
        VL_HEAP_up (array, heapSize, rightIndex) ;
      }
    }
  }
}

/* VL_HEAP_up */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_down) || defined(__DOXYGEN__)
#define VL_HEAP_down VL_XCAT(VL_HEAP_prefix, _down)

/** @brief Heap down operation
 ** @param array pointer to the heap node array.
 ** @param index index of the node to push up.
 **/

VL_INLINE void
VL_HEAP_down
(VL_HEAP_array array, vl_uindex index)
{
  vl_uindex parentIndex ;

  if (index == 0) return  ;

  parentIndex = vl_heap_parent (index) ;

  if (VL_HEAP_cmp (array, index, parentIndex) < 0) {
    VL_HEAP_swap (array, index, parentIndex) ;
    VL_HEAP_down (array, parentIndex) ;
  }
}

/* VL_HEAP_down */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_push) || defined(__DOXYGEN__)
#define VL_HEAP_push VL_XCAT(VL_HEAP_prefix, _push)

/** @brief Heap push operation
 ** @param array pointer to the heap array.
 ** @param heapSize (in/out) size of the heap.
 **
 ** The function adds to the heap the element of index @c heapSize
 ** and increments @c heapSize.
 **/

VL_INLINE void
VL_HEAP_push
(VL_HEAP_array array, vl_size *heapSize)
{
  VL_HEAP_down (array, *heapSize) ;
  *heapSize += 1 ;
}

/* VL_HEAP_push */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_pop) || defined(__DOXYGEN__)
#define VL_HEAP_pop VL_XCAT(VL_HEAP_prefix, _pop)

/** @brief Heap pop operation
 ** @param array pointer to the heap array.
 ** @param heapSize (in/out) size of the heap.
 ** @return index of the popped element.
 **
 ** The function extracts from the heap the element of index 0
 ** (the smallest element) and decreases @c heapSize.
 **
 ** The element extracted is moved as the first element after
 ** the heap end (thus it has index @c heapSize). For convenience,
 ** this index is returned by the function.
 **
 ** Popping from an empty heap is undefined.
 **/

VL_INLINE vl_uindex
VL_HEAP_pop
(VL_HEAP_array array, vl_size *heapSize)
{
  assert (*heapSize) ;

  *heapSize -= 1 ;

  VL_HEAP_swap (array, 0, *heapSize) ;

  if (*heapSize > 1) {
    VL_HEAP_up (array, *heapSize, 0) ;
  }

  return *heapSize ;
}

/* VL_HEAP_pop */
#endif

/* ---------------------------------------------------------------- */

#if ! defined(VL_HEAP_update) || defined(__DOXYGEN__)
#define VL_HEAP_update VL_XCAT(VL_HEAP_prefix, _update)

/** @brief Heap update operation
 ** @param array pointer to the heap array.
 ** @param heapSize size of the heap.
 ** @param index index of the node to update.
 **
 ** The function updates the heap to account for a change to the
 ** element of index @c index in the heap.
 **
 ** Notice that using this
 ** function requires knowing the index of the heap index of
 ** element that was changed. Since the heap swaps elements in the
 ** array, this is in general different from the index that that
 ** element had originally.
 **/

VL_INLINE void
VL_HEAP_update
(VL_HEAP_array array,
 vl_size heapSize,
 vl_uindex index)
{
  VL_HEAP_up (array, heapSize, index) ;
  VL_HEAP_down (array, index) ;
}

/* VL_HEAP_update */
#endif

/* ---------------------------------------------------------------- */

#undef VL_HEAP_cmp
#undef VL_HEAP_swap
#undef VL_HEAP_up
#undef VL_HEAP_down
#undef VL_HEAP_push
#undef VL_HEAP_pop
#undef VL_HEAP_update
#undef VL_HEAP_prefix
#undef VL_HEAP_type
#undef VL_HEAP_array
#undef VL_HEAP_array_const