1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
|
/* ----- RStarTree.h ----- */
#ifndef __RStarTree_h
#define __RStarTree_h
/** R*-tree
======= **/
/** Implementation: Norbert Beckmann
Version: R.2.0
Date: 6/93 **/
/** Praktische Informatik,
Universitaet Bremen, D-2800 Bremen 33, Germany **/
/* ---------------------- operating system version --------------------- */
/*
#ifndef SVR4
# define SVR4
#endif
*/
#include <stddef.h>
#include <sys/file.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <sys/stat.h>
#include <fcntl.h>
/* padding on 32 bits systems (to match automatic 64 bits padding) */
#if defined (__LP64__) || defined (__64BIT__) || defined (_LP64) || (__WORDSIZE == 64)
#define PADDING_32_BITS
#else
#define PADDING_32_BITS int padding
#endif
/* ----------------------------- constants ----------------------------- */
#define byte unsigned char
#define boolean int
#define FALSE 0
#define TRUE 1
#define int int /**V**/ /* large data sets require a 32 bit int */
#define MaxNameLength 160 /* including less than 10 bytes for a suffix */
#define MaxNumbOfEntriesPerPage 512 /**V**/
#define NumbOfDim 2 /**V**/
/* ------------------------------- types ------------------------------- */
typedef int File;
typedef float typatomkey; /**V**/
/* typatomkey may be of any type as far as the standard comparisons
apply */
typedef struct {
typatomkey l, h;
} typinterval;
typedef typinterval typrect[NumbOfDim];
/* A typrect is the key type an R*-tree handles. The smallest
entity which may be used as a key is an interval,
i.e. a typrect[1]. */
typedef struct {
float height;
} typinfo, *refinfo;
/* A typinfo is a struct which may contain arbitrary information
associated with a data record.
RESTRICTION: sizeof(typinfo) >= sizeof(int) must hold! */
typedef struct {
double m01, m02, m03;
double m11, m13;
double m22, m23, m33;
double m44, m55, m66, m77;
double m67, m76;
double H0, H1, H2, H3, H4;
double H5, H6;
float Hmin, Hmax;
int n;
PADDING_32_BITS;
} typdirinfo;
/* A typdirinfo is a struct which may contain arbitrary information
associated with a directory record. */
typedef int (* Check) (typrect rect, void * data, int depth);
/* ------------------------- private includes -------------------------- */
#include "RSTBase.h"
/* ----------------------------- R*-tree ------------------------------- */
typedef rstree *RSTREE; /* R*-tree identifier */
/* ------------------------- procedure types --------------------------- */
typedef boolean (*DirQueryProc) (RSTREE /* rst */,
typrect /* dirrect */,
typrect /* queryrect1 */,
typrect /* queryrect2 */);
/* rst:
contains the R*-tree identifier as passed to the procedures
RegionQuery, ExistsRegion and RegionCount respectively.
dirrect:
contains a multidimensional directory rectangle.
queryrect1, queryrect2:
contain queryrect1 and queryrect2 as passed to the procedures
RegionQuery, ExistsRegion and RegionCount respectively.
This type is also used in the JoinXX procedures to perform the
join. Then the parameters will have a slightly different
contents, see the JoinXX procedures. */
typedef boolean (*DataQueryProc) (RSTREE /* rst */,
typrect /* datarect */,
typrect /* queryrect1 */,
typrect /* queryrect2 */);
/* rst:
contains the R*-tree identifier as passed to the procedures
RegionQuery, ExistsRegion and RegionCount respectively.
datarect:
contains a multidimensional data rectangle.
queryrect1, queryrect2:
contain queryrect1 and queryrect2 as passed to the procedures
RegionQuery, ExistsRegion and RegionCount respectively.
This type is also used in the JoinXX procedures to perform the
join. Then the parameters will have a slightly different
contents, see the JoinXX procedures. */
typedef void (*QueryManageProc) (RSTREE /* rst */,
typrect /* rectangle */,
refinfo /* info */,
void* /* pointer */,
boolean* /* modify */,
boolean* /* finish */);
/* rst:
contains the R*-tree identifier as passed to the procedure
RegionQuery.
rectangle:
contains the multidimensional data rectangle currently found.
info:
points to the concerning information part.
pointer:
is an arbitrary pointer as passed to the procedure RegionQuery.
It may be used as a pointer to a buffer structure.
modify:
points to a flag labeling the node to be written back.
BEWARE:
record modified | modify | result
--------------------------------------------------------
no | FALSE | record is not modified
no | TRUE | undefined
yes | FALSE | undefined
yes | TRUE | record is modified
(See also RegionQuery)
finish:
points to a flag labeling the query to be finished when the
procedure is left. */
typedef void (*JoinManageProc) (RSTREE /* rst1 */,
RSTREE /* rst2 */,
typrect /* rectangle1 */,
typrect /* rectangle2 */,
refinfo /* info1 */ ,
refinfo /* info2 */,
void* /* pointer1 */,
void* /* pointer2 */,
boolean* /* finish */);
/* rst1, rst2:
contain the R*-tree identifiers as passed to the JoinXX
procedures.
rectangle1, rectangle2:
contain the two rectangles currently found by the join.
info1, info2:
point to the concerning information parts.
pointer1, pointer2:
are arbitrary pointers as passed to the JoinXX procedures.
They may be used as pointers to buffer structures.
finish:
points to a flag labeling the join to be finished when the
procedure is left. */
/* ---------------------- procedure declarations ----------------------- */
/*
Almost all procedures return a boolean result.
If a procedure returns FALSE an error has occured. The implementation
attempts to detect errors before any update operations are performed.
*/
void NoRSTree(RSTREE *rst);
/* Initializes an R*-tree identifier (at least sets *rst to NULL).
Each procedure which requires an R*-tree identifier checks the
value of this identifier at its entry.
OpenRST for example demands a NULL identifier while CloseRST
demands a non NULL identifier. */
boolean CreateRST(const char *name,
int pagesize,
boolean unique);
/* CreateRST creates an R*-tree on secondary memory.
To work on it, it has to be opened by the procedure OpenRST.
name:
is the main filename under which the created R*-tree will be
stored, additionally a few files named filename.suffix with
different suffixes will be created. name is not fixed in the
internal parameter table, thus after renaming the files, the
R*-tree may be opened under another name.
pagesize:
is the size in bytes, a page (directory or data) will occupy.
unique:
if unique is set TRUE the procedure InsertRecord will not store
more than one record with the same rectangle (key) in the
R*-tree (rectangles will be real keys).
The unique flag may be reset with the procedure SetUnique
without further internal tests. */
boolean RemoveRST(const char *name);
/* RemoveRST removes all files corresponding to an R*-tree. */
boolean OpenRST(RSTREE *rst,
const char *name,
const char *mode);
/* OpenRST opens the R*-tree named name. */
boolean CloseRST(RSTREE *rst);
/* CloseRST closes the R*-tree referenced by rst. */
boolean SetUnique(RSTREE rst,
boolean mode);
/* The unique state, defined in procedure CreateRST may be reset
by this procedure (see also CreateRST). The unique flag is set
without internal checks (even to TRUE). */
boolean InquireRSTDesc(RSTREE rst,
char *name,
int *numbofdim,
int *sizedirentry,
int *sizedataentry,
int *sizeinfo,
int *maxdirfanout,
int *maxdatafanout,
int *pagesize,
int *numbofdirpages,
int *numbofdatapages,
int pagesperlevel[],
int *numbofrecords,
int *height,
boolean *unique);
/* InquireRSTDesc provides some useful information about the
R*-tree referenced by rst.
name: see CreateRST.
numbofdim:
contains the number of dimensions of the R*-tree referenced by
rst, i.e. the value the constant NumbOfDim was set to when it
was created.
sizedirentry, sizedataentry:
contain the size (in bytes) of a directory and data entry
respectively.
sizeinfo:
contains the size (in bytes) of an information part.
maxdirfanout, maxdatafanout:
contain the maximum possible number of entries a directory
and data node respectively can store.
pagesize: see CreateRST.
numbofdirpages, numbofdatapages:
total number of directory and data pages respectively in use.
pagesperlevel:
For each level i, beginning at the root, pagesperlevel[i]
contains the number of pages in use.
numbofrecords:
total number of data records stored in the R*-tree.
height:
height of the tree, the lowest height is "1" (only the root
exists).
unique: see CreateRST. */
boolean InsertRecord(RSTREE rst,
typrect rectangle,
typinfo *info,
boolean *inserted);
/* InsertRecord inserts a new record in the R*-tree.
If the unique flag is set TRUE (see CreateRST) a new record is
not inserted if a record with the same rectangle is found. In
this case inserted yields FALSE, but the return value is TRUE
(if no error occurred).
rectangle:
is the rectangle part of the new record.
info:
is the information part of the new record. */
boolean DeleteRecord(RSTREE rst,
typrect rectangle,
boolean *deleted);
/* DeleteRecord deletes the first record with the given rectangle
it finds. It provides a fast deletion in trees where entries
are unique and may be used in trees where entries are not
unique, to delete iteratively all entries with the same
rectangle as passed. */
boolean ExistsRegion(RSTREE rst,
typrect queryrect1,
typrect queryrect2,
DirQueryProc DirQuery,
DataQueryProc DataQuery,
boolean *recordfound);
/* ExistsRegion performs a RegionQuery on the R*-tree referenced
by rst. It stops after the first record satisfying the query
condition is found.
See also RegionQuery.
recordfound:
is set to TRUE if a record satisfying the query condition
exists, otherwise FALSE. */
boolean RegionCount(RSTREE rst,
typrect queryrect1,
typrect queryrect2,
DirQueryProc DirQuery,
DataQueryProc DatQuery,
int *recordcount);
/* RegionCount performs a RegionQuery on the R*-tree referenced
by rst. It does not return records but only counts the number
of records found.
See also RegionQuery.
recordcount:
is set to the number of records satisfying the query
condition. */
boolean RegionQuery(RSTREE rst,
typrect queryrect1,
typrect queryrect2,
DirQueryProc DirQuery,
DataQueryProc DatQuery,
QueryManageProc Manage,
void *pointer);
/* RegionQuery performs a RegionQuery on the R*-tree referenced
by rst. Up to two query rectangles may be passed by queryrect1
and queryrect2. Two different procedures have two be provided
(DirQuery, DataQuery) which perform the query in the directory
and the data level respectively. A third procedure (Manage) must
be provided to deal with the records successively found.
A query is closed either if it did not find an additional
record satisfying the query condition or if the finish flag is
set by the procedure Manage.
See also DirQueryProc, DataQueryProc, QueryManageProc.
queryrect1, queryrect2:
query rectangles to be compared with directory rectangles and
data rectangles respectively.
DirQuery, DataQuery:
Procedure parameters passing comparison procedures of type
boolean.
Manage:
Procedure parameter passing a management procedure.
Manage is called each time a new data rectangle satisfying the
query condition is found.
Procedures of type QueryManageProc may provide the following
facilities:
Inspection of the data records rectangle and info part.
Communication to another structure, pointed to by pointer.
To modify the info part (the rectangle cannot be modified), and
label the node to be written back.
To finish the query.
pointer:
Arbitrary pointer passed through to the procedure Manage. */
boolean RegionQueryInfo(RSTREE R,
Check includes,
Check intersects,
void * data,
typrect rect,
typdirinfo * info);
boolean AllQuery(RSTREE rst,
QueryManageProc Manage,
void *pointer);
/* AllQuery performs a fast query which returns all records stored
in the R*-tree referenced by rst.
Manage:
Procedure parameter passing a management procedure.
Manage is called each time a new data rectangle satisfying the
query condition is found.
The type QueryManageProc provides the following functions:
To inspect a data records rectangle and info part.
To copy a record to the location pointer points to.
To modify the info part (the rectangle cannot be modified),
and label the node to be written back.
To finish the query.
pointer:
Arbitrary pointer passed through to the procedure Manage.
Since AllQuery is designed to be fast it does not support the
complete counting facility.
See also RegionQuery. */
boolean Update(RSTREE rst);
/* Updates the directory nodes typdirinfo. */
boolean JoinCountNv(RSTREE rst1,
RSTREE rst2,
typrect R1queryrect1,
typrect R1queryrect2,
typrect R2queryrect1,
typrect R2queryrect2,
DirQueryProc Dir1Query,
DataQueryProc Data1Query,
DirQueryProc Dir2Query,
DataQueryProc Data2Query,
DirQueryProc DirJoin,
DataQueryProc DataJoin,
int *paircount);
/* JoinCountNv performs a Join on the two R*-trees referenced by
rst1 and rst2. It does not return record pairs but only counts
the number of record pairs found.
See also JoinNv.
paircount:
is set to the number of recordpairs satisfying the join
condition. */
boolean JoinNv(RSTREE rst1,
RSTREE rst2,
typrect rst1queryrect1,
typrect rst1queryrect2,
typrect rst2queryrect1,
typrect rst2queryrect2,
DirQueryProc Dir1Query,
DataQueryProc Data1Query,
DirQueryProc Dir2Query,
DataQueryProc Data2Query,
DirQueryProc DirJoin,
DataQueryProc DataJoin,
JoinManageProc Manage,
void *pointer1,
void *pointer2);
/* The functionality of the join can be considered as follows:
On each of the two R*-trees to be joined a query is performed.
On the resulting restricted sets of records of the two R*-trees
the join is applied depending on the given join condition.
Join performs a join on the two R*-trees referenced by rst1 and
rst2. A join is closed either if it did not find an additional
pair of records satisfying the join condition or if the finish
flag is set by the procedure Manage.
See also DirQueryProc, DataQueryProc, JoinManageProc.
rst1queryrect1, rst1queryrect2:
Used in connection with the pre-query on rst1;
query rectangles to be compared with directory and data
rectangles respectively of rst1.
rst2queryrect1, rst2queryrect2:
Used in connection with the pre-query on rst2;
query rectangles to be compared with directory and data
rectangles respectively of rst2.
Dir1Query, Data1Query:
Procedure parameters passing comparison procedures of type
boolean.
The two procedures have to perform the pre-query on rst1.
See also DirQueryProc, DataQueryProc and RegionQuery.
Dir2Query, Data2Query:
Procedure parameters passing comparison procedures of type
boolean.
The two procedures have to perform the pre-query on rst2.
See also DirQueryProc, DataQueryProc and RegionQuery.
DirJoin, DataJoin:
Procedure parameters passing comparison procedures of type
boolean.
DirJoin has to determine if two directory rectangles, one of
rst1 the other of rst2 have to be joined,
DataJoin has to determine if two data rectangles, one of
rst1 the other of rst2 have to be joined.
Here the types DirQueryProc and DataQueryProc are used as
follows:
DQP(RSTREE rst1,
typrect rst1rect,
typrect rst2rect,
typrect unused);
rst1 contains rst1.
rst1rect contains a directory or data rectangle respectively
of rst1.
rst2rect contains a directory or data rectangle respectively
of rst2.
The last parameter is unused.
Manage:
Procedure parameter passing a management procedure.
Manage is called each time a new pair of data rectangles
satisfying the join condition is found.
Procedures of type JoinManageProc may provide the following
facilities:
Inspection of the data records' rectangles and info parts.
Communication to two other structures, pointed to by pointer1
and pointer2.
To finish the join.
pointer1, pointer2:
Arbitrary pointers passed through to the procedure Manage. */
/*************** ----- Performance Controll Routines ----- ***************/
/* ------ Counts-Switch: */
boolean CountsOn0(RSTREE rst);
/* put ON, set 0 */
boolean CountsOn(RSTREE rst);
/* put ON */
boolean CountsOff(RSTREE rst);
/* put OFF */
/* the Counts-Switch applies to the variables set by the
procedures GetCountRead, GetCountWrite.
The procedure OpenRST initializes counting:
the count variables are set to 0, the count switch is set to
OFF. */
boolean GetCountRead(RSTREE rst,
int *DirVisitCount,
int *DataVisitCount,
int *DirReadCount,
int *DataReadCount);
/* DirVisitCount is set to the number of directory nodes visited
traversing the tree.
DataVisitCount is set to the number of data nodes visited
traversing the tree.
DirReadCount directory nodes and DataReadCount data nodes had
actually to be read from secondary memory.
If the function returns FALSE these variables are set to 0.
DirVisitCount, DataVisitCount is counted:
for all query, join and update procedures.
DirReadCount, DataReadCount is counted:
whenever a read occurs. */
boolean GetCountWrite(RSTREE rst,
int *DirModifyCount,
int *DataModifyCount,
int *DirWriteCount,
int *DataWriteCount);
/* DirModifyCount is set to the number of directory nodes
modified.
DataModifyCount is set to the number of data nodes modified.
DirWriteCount is set to the number of directory nodes written
to secondary memory.
DataWriteCount is set to the number of data nodes written to
secondary memory.
If the function returns FALSE these variables are set to 0.
DirModifyCount, DataModifyCount is counted:
for all update procedures.
DirWriteCount, DataWriteCount is counted:
whenever a write occurs. */
boolean GetMemory(RSTREE rst,
int *numbofdirpages,
int *numbofdatapages);
/* numbofdirpages and numbofdatapages are set to the number of
pages in use for the directory and the data level respectively.
If the function returns FALSE these variables are set to 0. */
boolean GetHeight(RSTREE rst,
int *height);
/* height is set to the height of the tree, the lowest height
is "1" (only the root exists).
If the function returns FALSE these variables are set to 0. */
/*************************************************************************/
/* Layout of a directory and data node respectively (pidgin C)
-----------------------------------------------------------
directory node layout:
struct {
typrect rectangle;
int subtree_pointer;
} directory_entry;
struct {
int n;
directory_entry entries[M];
} directory_node;
The maximum number of entries M varies with different page sizes. The
minimum is M = 3.
The minimum number of entries m is calculated as max(round(0.4 * M), 2).
data node layout:
struct {
typrect rectangle;
typinfo information_part;
} data_entry;
struct {
int n;
data_entry entries[M];
} data_node;
The maximum number of entries M varies with different page sizes. The
minimum is M = 1.
The minimum number of entries m is calculated as max(round(0.4 * M), 1).
*/
/*************************************************************************/
/* BUGS:
The implementation does not provide packing, thus depending on the
design of the machine and the compiler, and the choice of typatomkey and
typinfo nodes may have gaps, i.e. the fanout may be smaller than you
expect.
Alignment problems, i.e. gaps between the entities stored in the nodes
cause warning messages on stdout (with one restriction):
The implementation does not know the internal structure of typinfo (it
only knows its size). Thus, if typinfo intrinsically contains gaps, this
cannot be detected. Information about the actual values of important
parameters may be obtained by calling InquireRSTDesc.
R*-tree identifiers are only checked for NULL and non NULL. Though
passing a non NULL invalid identifier is not detected as an error.
To open an R*-tree twice may damage consistency. But the implementation
does not detect this mistake.
Early detection of memory limitations is not available. If accidentally
the file system fills up during an update operation, the tree may be
left in an inconsistent state.
Although (aside from the lacks mentioned above) internal error detection
is nearly exhaustive, all you get is a boolean return value.
Passing the same R*-tree identifier twice to the JoinXX procedures is
save. If a join is performed on one and the same R*-tree, a second
R*-tree is opened virtually, but the performance control parameters are
only available for one of them. Since the join internally does not work
symmetrically this information generally is useless.
If deletions are performed the files holding the directory and data
pages will not shrink. Free pages are reoccupied by following
insertions. A file reorganization algorithm is not implemented.
The procedures of type QueryManageProc and JoinManageProc permit
unprotected access to parts of the internal data structure of the
R*-tree. This avoids copying but is unsafe of course.
The implementation restricts the informational part of a data record to
contain at least an integer sized contents.
*/
/*************************************************************************/
/*************** ----- For Private Test Purpose Only ----- ***************/
boolean Find(RSTREE rst,
typrect rectangle,
boolean *found,
void *buf,
int nbytes);
#endif /* !__RStarTree_h */
|
