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 34 struct RTree_ListNode 35 { 36 struct RTree_ListNode *next; 37 struct RTree_Node *node; 38 }; 39 40 struct RTree_ListFNode 41 { 42 struct RTree_ListFNode *next; 43 off_t node_pos; 44 }; 45 46 struct RTree_ListBranch 47 { 48 struct RTree_ListBranch *next; 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 **); 59 void RTreeFreeListBranch(struct RTree_ListBranch *); 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 *); 89 RectReal RTreeRectSphericalVolume(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_ */ 118