GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
index.h
Go to the documentation of this file.
1 
2 /****************************************************************************
3 * MODULE: R-Tree library
4 *
5 * AUTHOR(S): Antonin Guttman - original code
6 * Daniel Green (green@superliminal.com) - major clean-up
7 * and implementation of bounding spheres
8 * Markus Metz - file-based and memory-based R*-tree
9 *
10 * PURPOSE: Multidimensional index
11 *
12 * COPYRIGHT: (C) 2010 by the GRASS Development Team
13 *
14 * This program is free software under the GNU General Public
15 * License (>=v2). Read the file COPYING that comes with GRASS
16 * for details.
17 *****************************************************************************/
18 #ifndef _R_TREE_INDEX_H_
19 #define _R_TREE_INDEX_H_
20 
21 #include "rtree.h"
22 
23 /* internal definitions and functions */
24 
25 /* PGSIZE is normally the natural page size of the machine */
26 #define PGSIZE 512
27 
28 /* R*-tree: number of branches to be force-reinserted when adding a branch */
29 #define FORCECARD 3
30 
31 #define NODETYPE(l, fd) ((l) == 0 ? 0 : ((fd) < 0 ? 1 : 2))
32 
33 
35 {
37  struct RTree_Node *node;
38 };
39 
41 {
43  off_t node_pos;
44 };
45 
47 {
49  struct RTree_Branch b;
50  int level;
51 };
52 
53 /* functions */
54 
55 /* index.c */
56 struct RTree_ListNode *RTreeNewListNode(void);
57 void RTreeFreeListNode(struct RTree_ListNode *);
58 void RTreeReInsertNode(struct RTree_Node *, struct RTree_ListNode **);
60 
61 /* indexm.c */
62 int RTreeSearchM(struct RTree *, struct RTree_Rect *,
63  SearchHitCallback *, void *);
64 int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *);
65 int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *);
66 int RTreeValidChildM(union RTree_Child *child);
67 
68 /* indexf.c */
69 int RTreeSearchF(struct RTree *, struct RTree_Rect *,
70  SearchHitCallback *, void *);
71 int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *);
72 int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *);
73 int RTreeValidChildF(union RTree_Child *);
74 
75 /* node.c */
76 void RTreeNodeCover(struct RTree_Node *, struct RTree_Rect *, struct RTree *);
77 int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **,
78  struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *);
79 int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *);
80 void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *);
81 void RTreePrintNode(struct RTree_Node *, int, struct RTree *);
82 void RTreeTabIn(int);
83 void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *);
84 
85 /* rect.c */
86 void RTreeInitRect(struct RTree_Rect *, struct RTree *);
87 void RTreeNullRect(struct RTree_Rect *, struct RTree *);
88 RectReal RTreeRectArea(struct RTree_Rect *, struct RTree *);
90 RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *);
91 RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *);
92 void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
93 int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
94 int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
95 
96 /*-----------------------------------------------------------------------------
97 | Copy second rectangle to first rectangle.
98 -----------------------------------------------------------------------------*/
99 #define RTreeCopyRect(r1, r2, t) memcpy((r1)->boundary, (r2)->boundary, (t)->rectsize)
100 
101 
102 /* split.c */
103 void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *);
104 
105 /* card.c */
106 int RTreeSetNodeMax(int, struct RTree *);
107 int RTreeSetLeafMax(int, struct RTree *);
108 int RTreeGetNodeMax(struct RTree *);
109 int RTreeGetLeafMax(struct RTree *);
110 
111 /* io.c */
112 struct RTree_Node *RTreeGetNode(off_t, int, struct RTree *);
113 void RTreeNodeChanged(struct RTree_Node *, off_t , struct RTree *);
114 size_t RTreeRewriteNode(struct RTree_Node *, off_t, struct RTree *);
115 void RTreeAddNodePos(off_t, int, struct RTree *);
116 
117 #endif /* _INDEX_ */
double RectReal
Definition: rtree.h:28
struct RTree_Node * node
Definition: index.h:37
int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:576
int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexm.c:354
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:91
void RTreeReInsertNode(struct RTree_Node *, struct RTree_ListNode **)
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:434
struct RTree_ListFNode * next
Definition: index.h:42
int RTreeSetNodeMax(int, struct RTree *)
Definition: card.c:30
RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *)
Definition: rect.c:486
RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:324
int RTreeGetNodeMax(struct RTree *)
Definition: card.c:38
void RTreeNullRect(struct RTree_Rect *, struct RTree *)
Definition: rect.c:226
int RTreeSetLeafMax(int, struct RTree *)
Definition: card.c:34
off_t node_pos
Definition: index.h:43
RectReal RTreeRectArea(struct RTree_Rect *, struct RTree *)
struct RTree_ListBranch * next
Definition: index.h:48
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:24
struct RTree_ListNode * next
Definition: index.h:36
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *)
Definition: split.c:600
struct RTree_ListNode * RTreeNewListNode(void)
void RTreeFreeListBranch(struct RTree_ListBranch *)
int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexf.c:408
int RTreeSearchF(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexf.c:37
double b
Definition: r_raster.c:39
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:504
void RTreeAddNodePos(off_t, int, struct RTree *)
Definition: io.c:32
void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *)
Definition: node.c:270
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
Definition: rect.c:111
int RTreeGetLeafMax(struct RTree *)
Definition: card.c:42
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:541
int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexf.c:214
int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexm.c:186
size_t RTreeRewriteNode(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:190
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *)
Definition: node.c:542
void RTreeFreeListNode(struct RTree_ListNode *)
int RTreeValidChildF(union RTree_Child *)
Definition: indexf.c:27
void RTreeNodeChanged(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:198
void RTreePrintNode(struct RTree_Node *, int, struct RTree *)
Definition: node.c:617
struct RTree_Node * RTreeGetNode(off_t, int, struct RTree *)
Definition: io.c:112
int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *)
Definition: node.c:236
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:126
void RTreeNodeCover(struct RTree_Node *, struct RTree_Rect *, struct RTree *)
Definition: node.c:136
int RTreeSearchM(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexm.c:34
Definition: rtree.h:128
void RTreeTabIn(int)
Definition: node.c:602