// // $Id: index.cpp 5027 2010-02-18 19:41:48Z rares $ // // Copyright (C) 2004 - 2007 by The Regents of the University of // California // // Redistribution of this file is permitted under the terms of the // BSD license // // Date: October, 2004 // // Author: // Liang Jin // // #include "stdafx.h" #include #include #include #include "assert.h" #include "index.h" //#include "card.h" // Make a new index, empty. Consists of a single node. // struct Node * RTreeNewIndex() { struct Node *x; x = RTreeNewNode(); x->level = 0; /* leaf */ return x; } // Search in an index tree or subtree for all data retangles that // overlap the argument rectangle. // Return the number of qualifying data rects. // /*int RTreeQuery(struct Node *N, struct Query *Q, SearchHitCallback shcb, void* cbarg) { register struct Node *n = N; register struct Query *q = Q; // NOTE: Suspected bug was R sent in as Node* and cast to Rect* here. Fix not yet tested. register int hitCount = 0; register int i; assert(n); assert(n->level >= 0); assert(q); if (n->level > 0) // this is an internal node in the tree { for (i=0; ibranch[i].child && QueryOverlap(q,&n->branch[i].rect)) { hitCount += RTreeQuery(n->branch[i].child, Q, shcb, cbarg); } } else // this is a leaf node { for (i=0; ibranch[i].child && QueryOverlap(q,&n->branch[i].rect)) { hitCount++; if(shcb) // call the user-provided callback if( !shcb((int)n->branch[i].child, cbarg)) return hitCount; // callback wants to terminate search early } } return hitCount; }*/ // Search in an index tree or subtree for all data retangles that // overlap the argument rectangle. // Return the number of qualifying data rects. // /*int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb, void* cbarg) { register struct Node *n = N; register struct Rect *r = R; // NOTE: Suspected bug was R sent in as Node* and cast to Rect* here. Fix not yet tested. register int hitCount = 0; register int i; assert(n); assert(n->level >= 0); assert(r); if (n->level > 0) // this is an internal node in the tree { for (i=0; ibranch[i].child && RTreeOverlap(r,&n->branch[i].rect)) { hitCount += RTreeSearch(n->branch[i].child, R, shcb, cbarg); } } else // this is a leaf node { for (i=0; ibranch[i].child && RTreeOverlap(r,&n->branch[i].rect)) { hitCount++; if(shcb) // call the user-provided callback if( ! shcb((int)n->branch[i].child, cbarg)) return hitCount; // callback wants to terminate search early } } return hitCount; }*/ // Inserts a new data rectangle into the index structure. // Recursively descends tree, propagates splits back up. // Returns 0 if node was not split. Old node updated. // If node was split, returns 1 and sets the pointer pointed to by // new_node to point to the new node. Old node updated to become one of two. // The level argument specifies the number of steps up from the leaf // level to insert; e.g. a data rectangle goes in at level = 0. // /*static int RTreeInsertRect2(struct Rect *r, int tid, struct Node *n, struct Node **new_node, int level) { register int i; struct Branch b; struct Node *n2; assert(r && n && new_node); assert(level >= 0 && level <= n->level); // Still above level for insertion, go down tree recursively // if (n->level > level) { i = RTreePickBranch(r, n); if (!RTreeInsertRect2(r, tid, n->branch[i].child, &n2, level)) { // child was not split // n->branch[i].rect = RTreeCombineRect(r,&(n->branch[i].rect)); return 0; } else // child was split { n->branch[i].rect = RTreeNodeCover(n->branch[i].child); b.child = n2; b.rect = RTreeNodeCover(n2); return RTreeAddBranch(&b, n, new_node); } } // Have reached level for insertion. Add rect, split if necessary // else if (n->level == level) { b.rect = *r; b.child = (struct Node *) tid; // child field of leaves contains tid of data record return RTreeAddBranch(&b, n, new_node); } else { // Not supposed to happen assert (FALSE); return 0; } }*/ // Insert a data rectangle into an index structure. // RTreeInsertRect provides for splitting the root; // returns 1 if root was split, 0 if it was not. // The level argument specifies the number of steps up from the leaf // level to insert; e.g. a data rectangle goes in at level = 0. // RTreeInsertRect2 does the recursion. // /*int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level) { register struct Rect *r = R; register int tid = Tid; register struct Node **root = Root; register int level = Level; register int i; register struct Node *newroot; struct Node *newnode; struct Branch b; int result; assert(r && root); assert(level >= 0 && level <= (*root)->level); assert(r->boundary[0] <= r->boundary[NUMDIMS-1]); assert(strcmp(r->strbound[0],r->strbound[NUMDIMS-1]) <= 0); if (RTreeInsertRect2(r, tid, *root, &newnode, level)) // root split { newroot = RTreeNewNode(); // grow a new root, & tree taller newroot->level = (*root)->level + 1; b.rect = RTreeNodeCover(*root); b.child = *root; RTreeAddBranch(&b, newroot, NULL); b.rect = RTreeNodeCover(newnode); b.child = newnode; RTreeAddBranch(&b, newroot, NULL); *root = newroot; result = 1; } else result = 0; return result; }*/ // Allocate space for a node in the list used in DeletRect to // store Nodes that are too empty. // /*static struct ListNode * RTreeNewListNode() { return (struct ListNode *) malloc(sizeof(struct ListNode)); //return new ListNode; } static void RTreeFreeListNode(struct ListNode *p) { free(p); //delete(p); }*/ // Add a node to the reinsertion list. All its branches will later // be reinserted into the index structure. // /*static void RTreeReInsert(struct Node *n, struct ListNode **ee) { register struct ListNode *l; l = RTreeNewListNode(); l->node = n; l->next = *ee; *ee = l; }*/ // Delete a rectangle from non-root part of an index structure. // Called by RTreeDeleteRect. Descends tree recursively, // merges branches on the way back up. // Returns 1 if record not found, 0 if success. // /*static int RTreeDeleteRect2(struct Rect *R, int Tid, struct Node *N, struct ListNode **Ee) { register struct Rect *r = R; register int tid = Tid; register struct Node *n = N; register struct ListNode **ee = Ee; register int i; assert(r && n && ee); assert(tid >= 0); assert(n->level >= 0); if (n->level > 0) // not a leaf node { for (i = 0; i < NODECARD; i++) { if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect))) { if (!RTreeDeleteRect2(r, tid, n->branch[i].child, ee)) { if (n->branch[i].child->count >= MinNodeFill) n->branch[i].rect = RTreeNodeCover( n->branch[i].child); else { // not enough entries in child, // eliminate child node // RTreeReInsert(n->branch[i].child, ee); RTreeDisconnectBranch(n, i); } return 0; } } } return 1; } else // a leaf node { for (i = 0; i < LEAFCARD; i++) { if (n->branch[i].child && n->branch[i].child == (struct Node *) tid) { RTreeDisconnectBranch(n, i); return 0; } } return 1; } }*/ // Delete a data rectangle from an index structure. // Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node. // Returns 1 if record not found, 0 if success. // RTreeDeleteRect provides for eliminating the root. // /*int RTreeDeleteRect(struct Rect *R, int Tid, struct Node**Nn) { register struct Rect *r = R; register int tid = Tid; register struct Node **nn = Nn; register int i; register struct Node *tmp_nptr; struct ListNode *reInsertList = NULL; register struct ListNode *e; assert(r && nn); assert(*nn); assert(tid >= 0); if (!RTreeDeleteRect2(r, tid, *nn, &reInsertList)) { //found and deleted a data item // reinsert any branches from eliminated nodes while (reInsertList) { tmp_nptr = reInsertList->node; for (i = 0; i < MAXKIDS(tmp_nptr); i++) { if (tmp_nptr->branch[i].child) { RTreeInsertRect( &(tmp_nptr->branch[i].rect), (int)tmp_nptr->branch[i].child, nn, tmp_nptr->level); } } e = reInsertList; reInsertList = reInsertList->next; RTreeFreeNode(e->node); RTreeFreeListNode(e); } // check for redundant root (not leaf, 1 child) and eliminate if ((*nn)->count == 1 && (*nn)->level > 0) { for (i = 0; i < NODECARD; i++) { tmp_nptr = (*nn)->branch[i].child; if(tmp_nptr) break; } assert(tmp_nptr); RTreeFreeNode(*nn); *nn = tmp_nptr; } return 0; } else { return 1; } }*/