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
17extern "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
48typedef 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
59typedef struct Leaf {
60 Rect_t rect;
61 void *data;
62} Leaf_t;
63
64typedef 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
112typedef struct ListNode {
113 struct ListNode *next;
114 struct Node *node;
115} ListNode_t;
116
117RTree_t *RTreeOpen(void);
118int RTreeClose(RTree_t * rtp);
119Node_t *RTreeNewIndex(RTree_t * rtp);
120LeafList_t *RTreeSearch(RTree_t *, Node_t *, Rect_t *);
121int RTreeInsert(RTree_t *, Rect_t *, void *, Node_t **, int);
122int RTreeDelete(RTree_t *, Rect_t *, void *, Node_t **);
123
124LeafList_t *RTreeNewLeafList(Leaf_t * lp);
125LeafList_t *RTreeLeafListAdd(LeafList_t * llp, Leaf_t * lp);
126void RTreeLeafListFree(LeafList_t * llp);
127
128#ifdef RTDEBUG
129void PrintNode(Node_t *);
130#endif
131
132#ifdef __cplusplus
133}
134#endif
135
136#endif /*INDEX_H */
137