GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-112dd97adf
index.h
Go to the documentation of this file.
1 /****************************************************************************
2  * MODULE: R-Tree library
3  *
4  * AUTHOR(S): Antonin Guttman - original code
5  * Daniel Green (green@superliminal.com) - major clean-up
6  * and implementation of bounding spheres
7  * Markus Metz - file-based and memory-based R*-tree
8  *
9  * PURPOSE: Multidimensional index
10  *
11  * COPYRIGHT: (C) 2010 by the GRASS Development Team
12  *
13  * This program is free software under the GNU General Public
14  * License (>=v2). Read the file COPYING that comes with GRASS
15  * for details.
16  *****************************************************************************/
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 
35  struct RTree_Node *node;
36 };
37 
40  off_t node_pos;
41 };
42 
45  struct RTree_Branch b;
46  int level;
47 };
48 
49 /* functions */
50 
51 /* index.c */
52 struct RTree_ListNode *RTreeNewListNode(void);
53 void RTreeFreeListNode(struct RTree_ListNode *);
54 void RTreeReInsertNode(struct RTree_Node *, struct RTree_ListNode **);
56 
57 /* indexm.c */
58 int RTreeSearchM(struct RTree *, struct RTree_Rect *, SearchHitCallback *,
59  void *);
60 int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int,
61  struct RTree *);
62 int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *);
63 int RTreeValidChildM(union RTree_Child *child);
64 
65 /* indexf.c */
66 int RTreeSearchF(struct RTree *, struct RTree_Rect *, SearchHitCallback *,
67  void *);
68 int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int,
69  struct RTree *);
70 int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *);
71 int RTreeValidChildF(union RTree_Child *);
72 
73 /* node.c */
74 void RTreeNodeCover(struct RTree_Node *, struct RTree_Rect *, struct RTree *);
75 int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *,
76  struct RTree_Node **, struct RTree_ListBranch **,
77  struct RTree_Rect *, char *, struct RTree *);
78 int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *);
79 void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *);
80 void RTreePrintNode(struct RTree_Node *, int, struct RTree *);
81 void RTreeTabIn(int);
82 void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *,
83  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 *,
93  struct RTree_Rect *, struct RTree *);
94 int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
95 int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
96 
97 /*-----------------------------------------------------------------------------
98 | Copy second rectangle to first rectangle.
99 -----------------------------------------------------------------------------*/
100 #define RTreeCopyRect(r1, r2, t) \
101  memcpy((r1)->boundary, (r2)->boundary, (t)->rectsize)
102 
103 /* split.c */
104 void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *,
105  struct RTree_Node *, struct RTree *);
106 
107 /* card.c */
108 int RTreeSetNodeMax(int, struct RTree *);
109 int RTreeSetLeafMax(int, struct RTree *);
110 int RTreeGetNodeMax(struct RTree *);
111 int RTreeGetLeafMax(struct RTree *);
112 
113 /* io.c */
114 struct RTree_Node *RTreeGetNode(off_t, int, struct RTree *);
115 void RTreeNodeChanged(struct RTree_Node *, off_t, struct RTree *);
116 size_t RTreeRewriteNode(struct RTree_Node *, off_t, struct RTree *);
117 void RTreeAddNodePos(off_t, int, struct RTree *);
118 
119 #endif /* _INDEX_ */
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *)
Definition: node.c:544
struct RTree_ListNode * RTreeNewListNode(void)
void RTreePrintNode(struct RTree_Node *, int, struct RTree *)
Definition: node.c:619
void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *)
Definition: node.c:270
int RTreeSearchM(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexm.c:33
int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexf.c:213
void RTreeNodeCover(struct RTree_Node *, struct RTree_Rect *, struct RTree *)
Definition: node.c:135
void RTreeFreeListNode(struct RTree_ListNode *)
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:432
int RTreeGetLeafMax(struct RTree *)
Definition: card.c:44
void RTreeTabIn(int)
Definition: node.c:604
RectReal RTreeRectArea(struct RTree_Rect *, struct RTree *)
int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexm.c:352
void RTreeReInsertNode(struct RTree_Node *, struct RTree_ListNode **)
int RTreeSearchF(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexf.c:36
size_t RTreeRewriteNode(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:193
void RTreeNullRect(struct RTree_Rect *, struct RTree *)
Definition: rect.c:225
void RTreeAddNodePos(off_t, int, struct RTree *)
Definition: io.c:31
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:124
int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexm.c:185
RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:323
struct RTree_Node * RTreeGetNode(off_t, int, struct RTree *)
Definition: io.c:111
int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexf.c:408
int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *)
Definition: node.c:236
RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *)
Definition: rect.c:483
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *)
Definition: split.c:613
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:500
void RTreeNodeChanged(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:201
int RTreeSetNodeMax(int, struct RTree *)
Definition: card.c:29
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:536
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:23
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
Definition: rect.c:109
int RTreeGetNodeMax(struct RTree *)
Definition: card.c:39
void RTreeFreeListBranch(struct RTree_ListBranch *)
int RTreeSetLeafMax(int, struct RTree *)
Definition: card.c:34
int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:570
int RTreeValidChildF(union RTree_Child *)
Definition: indexf.c:26
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:86
double RectReal
Definition: rtree.h:26
struct RTree_ListBranch * next
Definition: index.h:44
struct RTree_Branch b
Definition: index.h:45
off_t node_pos
Definition: index.h:40
struct RTree_ListFNode * next
Definition: index.h:39
struct RTree_ListNode * next
Definition: index.h:34
struct RTree_Node * node
Definition: index.h:35
Definition: rtree.h:123