This file is indexed.

/usr/include/thunderbird/mozilla/layers/BSPTree.h is in thunderbird-dev 1:52.8.0-1~deb8u1.

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
/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * 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 MOZILLA_LAYERS_BSPTREE_H
#define MOZILLA_LAYERS_BSPTREE_H

#include "mozilla/gfx/Polygon.h"
#include "mozilla/Move.h"
#include "mozilla/UniquePtr.h"
#include "nsTArray.h"

#include <deque>

namespace mozilla {
namespace layers {

class Layer;

// Represents a layer that might have a non-rectangular geometry.
struct LayerPolygon {
  explicit LayerPolygon(Layer *aLayer)
    : layer(aLayer) {}

  LayerPolygon(Layer *aLayer,
               gfx::Polygon3D&& aGeometry)
    : layer(aLayer), geometry(Some(aGeometry)) {}

  LayerPolygon(Layer *aLayer,
               nsTArray<gfx::Point3D>&& aPoints, const gfx::Point3D& aNormal)
    : layer(aLayer), geometry(Some(gfx::Polygon3D(Move(aPoints), aNormal))) {}

  Layer *layer;
  Maybe<gfx::Polygon3D> geometry;
};

LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers);

// Represents a node in a BSP tree. The node contains at least one layer with
// associated geometry that is used as a splitting plane, and at most two child
// nodes that represent the splitting planes that further subdivide the space.
struct BSPTreeNode {
  explicit BSPTreeNode(LayerPolygon&& layer)
  {
    layers.push_back(Move(layer));
  }

  const gfx::Polygon3D& First() const
  {
    MOZ_ASSERT(layers[0].geometry);
    return *layers[0].geometry;
  }

  UniquePtr<BSPTreeNode> front;
  UniquePtr<BSPTreeNode> back;
  std::deque<LayerPolygon> layers;
};

// BSPTree class takes a list of layers as an input and uses binary space
// partitioning algorithm to create a tree structure that can be used for
// depth sorting.
//
// Sources for more information:
// https://en.wikipedia.org/wiki/Binary_space_partitioning
// ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
class BSPTree {
public:
  // This constructor takes the ownership of layers in the given list.
  explicit BSPTree(std::deque<LayerPolygon>& aLayers)
  {
    MOZ_ASSERT(!aLayers.empty());
    mRoot.reset(new BSPTreeNode(PopFront(aLayers)));

    BuildTree(mRoot, aLayers);
  }

  // Returns the root node of the BSP tree.
  const UniquePtr<BSPTreeNode>& GetRoot() const
  {
    return mRoot;
  }

  // Builds and returns the back-to-front draw order for the created BSP tree.
  nsTArray<LayerPolygon> GetDrawOrder() const
  {
    nsTArray<LayerPolygon> layers;
    BuildDrawOrder(mRoot, layers);
    return layers;
  }

private:
  UniquePtr<BSPTreeNode> mRoot;

  // BuildDrawOrder and BuildTree are called recursively. The depth of the
  // recursion depends on the amount of polygons and their intersections.
  void BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
                      nsTArray<LayerPolygon>& aLayers) const;
  void BuildTree(UniquePtr<BSPTreeNode>& aRoot,
                 std::deque<LayerPolygon>& aLayers);
};

} // namespace layers
} // namespace mozilla

#endif /* MOZILLA_LAYERS_BSPTREE_H */