1 /* vim:set shiftwidth=4 ts=8: */ 2 3 /************************************************************************* 4 * Copyright (c) 2011 AT&T Intellectual Property 5 * All rights reserved. This program and the accompanying materials 6 * are made available under the terms of the Eclipse Public License v1.0 7 * which accompanies this distribution, and is available at 8 * http://www.eclipse.org/legal/epl-v10.html 9 * 10 * Contributors: See CVS logs. Details at http://www.graphviz.org/ 11 *************************************************************************/ 12 13 #ifndef INDEX_H 14 #define INDEX_H 15 16 #ifdef __cplusplus 17 extern "C" { 18 #endif 19 20 /* 21 * this library is derived from an archived home directory of Antonin Guttman 22 * that implemented the ideas described in 23 * "R-trees: a dynamic index structure for spatial searching" 24 * Antonin Guttman, University of California, Berkeley 25 * SIGMOD '84 Proceedings of the 1984 ACM SIGMOD international conference on Management of data 26 * ISBN:0-89791-128-8 27 * http://dx.doi.org/10.1145/602259.602266 28 * this copy of the code was retrieved from 29 * http://web.archive.org/web/20030210112132/http://www.es.ucsc.edu/~tonig/rtrees/ 30 * we are using the quadratic node splitter only 31 * we made a few cosmetic changes to fit our needs 32 * per Antonin there is no copyright 33 */ 34 35 /* %W% %G% */ 36 /*----------------------------------------------------------------------------- 37 | Global definitions. 38 -----------------------------------------------------------------------------*/ 39 40 #ifndef NUMDIMS 41 #define NUMDIMS 2 42 #endif /*NUMDIMS*/ 43 /* #define NDEBUG */ 44 #define NUMSIDES 2*NUMDIMS 45 /* branching factor of a node */ 46 /* #define NODECARD (int)((PGSIZE-(2*sizeof(int)))/sizeof(struct Branch))*/ 47 #define NODECARD 64 48 typedef struct RTree RTree_t; 49 50 #include <rectangle.h> 51 #include <node.h> 52 #include <split.q.h> 53 54 #define CX(i) (i) 55 #define NX(i) (i+NUMDIMS) 56 #define CY(i) (i+1) 57 #define NY(i) (i+1+NUMDIMS) 58 59 typedef struct Leaf { 60 Rect_t rect; 61 void *data; 62 } Leaf_t; 63 64 typedef struct LeafList { 65 struct LeafList *next; 66 Leaf_t *leaf; 67 } LeafList_t; 68 69 #ifndef METHODS 70 #define METHODS 1 71 #endif /*METHODS*/ 72 struct RTree { 73 Node_t *root; 74 75 SplitQ_t split; 76 77 /* balance criterion for node splitting */ 78 int MinFill; 79 80 /* times */ 81 long ElapsedTime; 82 float UserTime, SystemTime; 83 84 int Deleting; 85 86 /* variables for statistics */ 87 int StatFlag; /* tells if we are counting or not */ 88 /* counters affected only when StatFlag set */ 89 int InsertCount; 90 int DeleteCount; 91 int ReInsertCount; 92 int InSplitCount; 93 int DeSplitCount; 94 int ElimCount; 95 int EvalCount; 96 int InTouchCount; 97 int DeTouchCount; 98 int SeTouchCount; 99 int CallCount; 100 float SplitMeritSum; 101 102 /* counters used even when StatFlag not set */ 103 int RectCount; 104 int NodeCount; 105 int LeafCount, NonLeafCount; 106 int EntryCount; 107 int SearchCount; 108 int HitCount; 109 110 }; 111 112 typedef struct ListNode { 113 struct ListNode *next; 114 struct Node *node; 115 } ListNode_t; 116 117 RTree_t *RTreeOpen(void); 118 int RTreeClose(RTree_t * rtp); 119 Node_t *RTreeNewIndex(RTree_t * rtp); 120 LeafList_t *RTreeSearch(RTree_t *, Node_t *, Rect_t *); 121 int RTreeInsert(RTree_t *, Rect_t *, void *, Node_t **, int); 122 int RTreeDelete(RTree_t *, Rect_t *, void *, Node_t **); 123 124 LeafList_t *RTreeNewLeafList(Leaf_t * lp); 125 LeafList_t *RTreeLeafListAdd(LeafList_t * llp, Leaf_t * lp); 126 void RTreeLeafListFree(LeafList_t * llp); 127 128 #ifdef RTDEBUG 129 void PrintNode(Node_t *); 130 #endif 131 132 #ifdef __cplusplus 133 } 134 #endif 135 136 #endif /*INDEX_H */ 137