/usr/lib/grass72/include/grass/rtree.h is in grass-dev 7.2.0-2.
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 | /****************************************************************************
* MODULE: R-Tree library
*
* AUTHOR(S): Antonin Guttman - original code
* Daniel Green (green@superliminal.com) - major clean-up
* and implementation of bounding spheres
* Markus Metz - file-based and memory-based R*-tree
*
* PURPOSE: Multidimensional index
*
* COPYRIGHT: (C) 2010-2012 by the GRASS Development Team
*
* This program is free software under the GNU General Public
* License (>=v2). Read the file COPYING that comes with GRASS
* for details.
*****************************************************************************/
#ifndef _R_TREE_H_
#define _R_TREE_H_
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <grass/config.h> /* needed for LFS */
typedef double RectReal;
/*-----------------------------------------------------------------------------
| Global definitions.
-----------------------------------------------------------------------------*/
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
/* max branching factor of a node */
/* was (PGSIZE-(2 * sizeof(int))) / sizeof(struct Branch)
* this is LFS dependent, not good
* on 32 bit without LFS this is 9.69
* on 32 bit with LFS and on 64 bit this is 9 */
#define MAXCARD 9
#define NODECARD MAXCARD
#define LEAFCARD MAXCARD
/* maximum no of levels = tree depth */
#define MAXLEVEL 20 /* 8^MAXLEVEL items are guaranteed to fit into the tree */
/* number of nodes buffered per level */
#define NODE_BUFFER_SIZE 32
struct RTree_Rect
{
RectReal *boundary; /* xmin,ymin,...,xmax,ymax,... */
};
struct RTree_Node; /* node for spatial index */
union RTree_Child
{
int id; /* child id */
struct RTree_Node *ptr; /* pointer to child node */
off_t pos; /* position of child node in file */
};
struct RTree_Branch /* branch for spatial index */
{
struct RTree_Rect rect;
union RTree_Child child;
};
struct RTree_Node /* node for spatial index */
{
int count; /* number of branches */
int level; /* 0 is leaf, others positive */
struct RTree_Branch *branch;
};
/*
* If passed to a tree search, this callback function will be called
* with the ID of each data rect that overlaps the search rect
* plus whatever user specific pointer was passed to the search.
* It can terminate the search early by returning 0 in which case
* the search will return the number of hits found up to that point.
*/
typedef int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg);
struct RTree;
typedef int rt_search_fn(struct RTree *, struct RTree_Rect *,
SearchHitCallback *, void *);
typedef int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *);
typedef int rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *);
typedef int rt_valid_child_fn(union RTree_Child *);
/* temp vars for each tree */
/* node stack used for non-recursive insertion/deletion */
struct nstack
{
struct RTree_Node *sn; /* stack node */
int branch_id; /* branch number to follow down */
off_t pos; /* file position of stack node */
};
/* node buffer for file-based index */
struct NodeBuffer
{
struct RTree_Node n; /* buffered node */
off_t pos; /* file position of buffered node */
char dirty; /* node in buffer was modified */
};
/* temp vars for node splitting */
struct RTree_PartitionVars {
int partition[MAXCARD + 1];
int total, minfill;
int taken[MAXCARD + 1];
int count[2];
struct RTree_Rect cover[2];
RectReal area[2];
};
struct RTree
{
/* RTree setup info */
int fd; /* file descriptor */
unsigned char ndims; /* number of dimensions */
unsigned char nsides; /* number of sides = 2 * ndims */
unsigned char ndims_alloc; /* number of dimensions allocated */
unsigned char nsides_alloc; /* number of sides allocated = 2 * ndims allocated */
int nodesize; /* node size in bytes */
int branchsize; /* branch size in bytes */
int rectsize; /* rectangle size in bytes */
/* RTree info, useful to calculate space requirements */
int n_nodes; /* number of nodes */
int n_leafs; /* number of data items (level 0 leafs) */
int rootlevel; /* root level = tree depth */
/* settings for RTree building */
int nodecard; /* max number of childs in node */
int leafcard; /* max number of childs in leaf */
int min_node_fill; /* balance criteria for node removal */
int min_leaf_fill; /* balance criteria for leaf removal */
int minfill_node_split; /* balance criteria for splitting */
int minfill_leaf_split; /* balance criteria for splitting */
char overflow; /* enable/disable overflow */
/* free node positions for recycling */
struct _recycle {
int avail; /* number of available positions */
int alloc; /* number of allcoated positions in *pos */
off_t *pos; /* array of available positions */
} free_nodes;
/* node buffer for file-based index */
struct NodeBuffer **nb;
/* usage order of buffered nodes per level
* used[level][0] = most recently used
* used[level][NODE_BUFFER_SIZE - 1] = least recently used */
int **used;
/* insert, delete, search */
rt_insert_fn *insert_rect;
rt_delete_fn *delete_rect;
rt_search_fn *search_rect;
rt_valid_child_fn *valid_child;
struct RTree_Node *root; /* pointer to root node */
/* internal variables, specific for each tree,
* allocated with tree initialization */
/* node stack for tree traversal */
struct nstack *ns;
/* variables for splitting / forced reinsertion */
struct RTree_PartitionVars p;
struct RTree_Branch *BranchBuf;
struct RTree_Branch tmpb1, tmpb2, c;
int BranchCount;
struct RTree_Rect rect_0, rect_1, upperrect, orect;
RectReal *center_n;
off_t rootpos; /* root node position in file */
};
/* RTree main functions */
int RTreeSearch(struct RTree *, struct RTree_Rect *,
SearchHitCallback *, void *);
int RTreeInsertRect(struct RTree_Rect *, int, struct RTree *);
void RTreeSetRect1D(struct RTree_Rect *r, struct RTree *t, double x_min,
double x_max);
void RTreeSetRect2D(struct RTree_Rect *r, struct RTree *t, double x_min,
double x_max, double y_min, double y_max);
void RTreeSetRect3D(struct RTree_Rect *r, struct RTree *t, double x_min,
double x_max, double y_min, double y_max, double z_min,
double z_max);
void RTreeSetRect4D(struct RTree_Rect *r, struct RTree *t, double x_min,
double x_max, double y_min, double y_max, double z_min,
double z_max, double t_min, double t_max);
int RTreeDeleteRect(struct RTree_Rect *, int, struct RTree *);
void RTreePrintRect(struct RTree_Rect *, int, struct RTree *);
struct RTree *RTreeCreateTree(int, off_t, int);
void RTreeSetOverflow(struct RTree *, char);
void RTreeDestroyTree(struct RTree *);
int RTreeOverlap(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
int RTreeContained(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
int RTreeContains(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
/* RTree node management */
struct RTree_Node *RTreeAllocNode(struct RTree *, int);
void RTreeInitNode(struct RTree *, struct RTree_Node *, int);
void RTreeCopyNode(struct RTree_Node *, struct RTree_Node *, struct RTree *);
void RTreeFreeNode(struct RTree_Node *);
void RTreeDestroyNode(struct RTree_Node *, int);
/* RTree rectangle allocation and deletion */
struct RTree_Rect *RTreeAllocRect(struct RTree *t);
void RTreeFreeRect(struct RTree_Rect *r);
RectReal *RTreeAllocBoundary(struct RTree *t);
void RTreeFreeBoundary(struct RTree_Rect *r);
/* RTree IO */
size_t RTreeReadNode(struct RTree_Node *, off_t, struct RTree *);
size_t RTreeWriteNode(struct RTree_Node *, struct RTree *);
off_t RTreeGetNodePos(struct RTree *);
void RTreeFlushBuffer(struct RTree *);
#endif
|