rtree.h

Go to the documentation of this file.

/****************************************************************************
 * MODULE:       R-Tree library
 *
 * AUTHOR(S):    Antonin Guttman - original code
 *               Daniel Green (green@superliminal.com) - major clean-up
 *                               and implementation of bounding spheres
 *               Markus Metz - file-based and memory-based R*-tree
 *
 * PURPOSE:      Multidimensional index
 *
 * COPYRIGHT:    (C) 2010-2012 by the GRASS Development Team
 *
 *               This program is free software under the GNU General Public
 *               License (>=v2). Read the file COPYING that comes with GRASS
 *               for details.
 *****************************************************************************/
#ifndef _R_TREE_H_
#define _R_TREE_H_
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <grass/config.h> /* needed for LFS */
 
typedef double RectReal;
 
/*-----------------------------------------------------------------------------
| Global definitions.
-----------------------------------------------------------------------------*/
 
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
 
/* max branching factor of a node */
/* was (PGSIZE-(2 * sizeof(int))) / sizeof(struct Branch)
 * this is LFS dependent, not good
 * on 32 bit without LFS this is 9.69
 * on 32 bit with LFS and on 64 bit this is 9 */
#define MAXCARD          9
#define NODECARD         MAXCARD
#define LEAFCARD         MAXCARD
 
/* maximum no of levels = tree depth */
#define MAXLEVEL         20 /* 8^MAXLEVEL items are guaranteed to fit into the tree */
 
/* number of nodes buffered per level */
#define NODE_BUFFER_SIZE 32
 
struct RTree_Rect {
    RectReal *boundary; /* xmin,ymin,...,xmax,ymax,... */
};
 
struct RTree_Node; /* node for spatial index */
 
union RTree_Child {
    int id;                 /* child id */
    struct RTree_Node *ptr; /* pointer to child node */
    off_t pos;              /* position of child node in file */
};
 
struct RTree_Branch /* branch for spatial index */
{
    struct RTree_Rect rect;
    union RTree_Child child;
};
 
struct RTree_Node /* node for spatial index */
{
    int count; /* number of branches */
    int level; /* 0 is leaf, others positive */
    struct RTree_Branch *branch;
};
 
/*
 * If passed to a tree search, this callback function will be called
 * with the ID of each data rect that overlaps the search rect
 * plus whatever user specific pointer was passed to the search.
 * It can terminate the search early by returning 0 in which case
 * the search will return the number of hits found up to that point.
 */
typedef int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg);
 
struct RTree;
 
typedef int rt_search_fn(struct RTree *, struct RTree_Rect *,
                         SearchHitCallback *, void *);
typedef int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int,
                         struct RTree *);
typedef int rt_delete_fn(struct RTree_Rect *, union RTree_Child,
                         struct RTree *);
typedef int rt_valid_child_fn(union RTree_Child *);
 
/* temp vars for each tree */
/* node stack used for non-recursive insertion/deletion */
struct nstack {
    struct RTree_Node *sn; /* stack node */
    int branch_id;         /* branch number to follow down */
    off_t pos;             /* file position of stack node */
};
 
/* node buffer for file-based index */
struct NodeBuffer {
    struct RTree_Node n; /* buffered node */
    off_t pos;           /* file position of buffered node */
    char dirty;          /* node in buffer was modified */
};
 
/* temp vars for node splitting */
struct RTree_PartitionVars {
    int partition[MAXCARD + 1];
    int total, minfill;
    int taken[MAXCARD + 1];
    int count[2];
    struct RTree_Rect cover[2];
    RectReal area[2];
};
 
struct RTree {
    /* RTree setup info */
    int fd;                    /* file descriptor */
    unsigned char ndims;       /* number of dimensions */
    unsigned char nsides;      /* number of sides = 2 * ndims */
    unsigned char ndims_alloc; /* number of dimensions allocated */
    unsigned char
        nsides_alloc; /* number of sides allocated = 2 * ndims allocated */
    int nodesize;     /* node size in bytes */
    int branchsize;   /* branch size in bytes */
    int rectsize;     /* rectangle size in bytes */
 
    /* RTree info, useful to calculate space requirements */
    int n_nodes;   /* number of nodes */
    int n_leafs;   /* number of data items (level 0 leafs) */
    int rootlevel; /* root level = tree depth */
 
    /* settings for RTree building */
    int nodecard;           /* max number of children in node */
    int leafcard;           /* max number of children in leaf */
    int min_node_fill;      /* balance criteria for node removal */
    int min_leaf_fill;      /* balance criteria for leaf removal */
    int minfill_node_split; /* balance criteria for splitting */
    int minfill_leaf_split; /* balance criteria for splitting */
    char overflow;          /* enable/disable overflow */
 
    /* free node positions for recycling */
    struct _recycle {
        int avail;  /* number of available positions */
        int alloc;  /* number of allocated positions in *pos */
        off_t *pos; /* array of available positions */
    } free_nodes;
 
    /* node buffer for file-based index */
    struct NodeBuffer **nb;
 
    /* usage order of buffered nodes per level
     * used[level][0] = most recently used
     * used[level][NODE_BUFFER_SIZE - 1] = least recently used */
    int **used;
 
    /* insert, delete, search */
    rt_insert_fn *insert_rect;
    rt_delete_fn *delete_rect;
    rt_search_fn *search_rect;
    rt_valid_child_fn *valid_child;
 
    struct RTree_Node *root; /* pointer to root node */
 
    /* internal variables, specific for each tree,
     * allocated with tree initialization */
    /* node stack for tree traversal */
    struct nstack *ns;
 
    /* variables for splitting / forced reinsertion */
    struct RTree_PartitionVars p;
    struct RTree_Branch *BranchBuf;
 
    struct RTree_Branch tmpb1, tmpb2, c;
    int BranchCount;
 
    struct RTree_Rect rect_0, rect_1, upperrect, orect;
    RectReal *center_n;
 
    off_t rootpos; /* root node position in file */
};
 
/* RTree main functions */
int RTreeSearch(struct RTree *, struct RTree_Rect *, SearchHitCallback *,
                void *);
int RTreeInsertRect(struct RTree_Rect *, int, struct RTree *);
void RTreeSetRect1D(struct RTree_Rect *r, struct RTree *t, double x_min,
                    double x_max);
void RTreeSetRect2D(struct RTree_Rect *r, struct RTree *t, double x_min,
                    double x_max, double y_min, double y_max);
void RTreeSetRect3D(struct RTree_Rect *r, struct RTree *t, double x_min,
                    double x_max, double y_min, double y_max, double z_min,
                    double z_max);
void RTreeSetRect4D(struct RTree_Rect *r, struct RTree *t, double x_min,
                    double x_max, double y_min, double y_max, double z_min,
                    double z_max, double t_min, double t_max);
int RTreeDeleteRect(struct RTree_Rect *, int, struct RTree *);
void RTreePrintRect(struct RTree_Rect *, int, struct RTree *);
struct RTree *RTreeCreateTree(int, off_t, int);
void RTreeSetOverflow(struct RTree *, char);
void RTreeDestroyTree(struct RTree *);
int RTreeOverlap(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
int RTreeContained(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
int RTreeContains(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
 
/* RTree node management */
struct RTree_Node *RTreeAllocNode(struct RTree *, int);
void RTreeInitNode(struct RTree *, struct RTree_Node *, int);
void RTreeCopyNode(struct RTree_Node *, struct RTree_Node *, struct RTree *);
void RTreeFreeNode(struct RTree_Node *);
void RTreeDestroyNode(struct RTree_Node *, int);
 
/* RTree rectangle allocation and deletion */
struct RTree_Rect *RTreeAllocRect(struct RTree *t);
void RTreeFreeRect(struct RTree_Rect *r);
RectReal *RTreeAllocBoundary(struct RTree *t);
void RTreeFreeBoundary(struct RTree_Rect *r);
 
/* RTree IO */
size_t RTreeReadNode(struct RTree_Node *, off_t, struct RTree *);
size_t RTreeWriteNode(struct RTree_Node *, struct RTree *);
off_t RTreeGetNodePos(struct RTree *);
void RTreeFlushBuffer(struct RTree *);
 
#endif