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