blob: 2cd5de08cc5cf47aace0574f061405db49d908cf [file] [log] [blame]
* DIS Data Management Index
* This file contains the index structures for the DIS R-Tree basline
* application. The two structures defined are for index entries and for
* index nodes.
* An index entry will reference either an index node or a
* data object. All entries which are in the index reside on an index
* node. An entry which resides on a leaf node (level = 0) references a
* data object, while an entry which resides on a non-leaf node (level > 0)
* references an index node. Since the entry may reference two different
* types of objects, the member is a union between the two types. The
* entry contains an index key which is used for traversals of the index.
* For the R-Tree index, the index key is the hyper-cube which minimally
* encloses the object it references. If the child reference is a data
* object, the index key for the entry is the appropriate values of the
* data object. If the child reference is an index node, the index key of
* the entry is the bounding hyper-cube of all of the entries residing on
* that node. The final member of the index entry structure is a pointer
* to another index entry structure which gives linked-list behavior to
* entries.
* An index node is a container of a list of index entries. Each node
* contains an integer level value. Note that the leaf level is zero and
* the level increases as the tree is ascended, i.e., the root level is
* always greater than or equal to the leaf level. The number of entries
* in the list is always between one and the fan or order of the index.
* Note that the fan of the index is read at run-time, so a fixed array of
* entries is not permitted.
* Revision History:
* Date Name Revision
* ------- --------------- ------------------------------
* 24May99 Matthew Rivas Created
* Copyright 1999, Atlantic Aerospace Electronics Corp.
#ifndef DIS_INDEX_H
#define DIS_INDEX_H
#include "dataManagement.h" /* for basic data types */
#include "dataObject.h" /* for data object definition */
#include "indexKey.h" /* for index key definition */
* Index Node
* - contains a list of entries which reside on node
* - has a level specifier where all levels are greater than or equal to
* the LEAF level.
typedef struct
Int level; /* level where node resides in index */
struct IndexEntry *entries; /* list of entries on node */
} IndexNode;
* Prototypes for routines which create, delete, and display IndexNode
* structures.
extern IndexNode *createIndexNode( Int level );
extern void deleteIndexNode( IndexNode * node );
extern void outputIndexNode( IndexNode * node, Int indent );
* Index Entry
* - references a child object, either a data object or index node
* - has a key which "encloses" the child object
* - has a pointer to support single link-list capability
struct IndexEntry
union {
IndexNode *node;
DataObject *dataObject;
} child;
IndexKey key;
struct IndexEntry *next;
typedef struct IndexEntry IndexEntry;
* Prototypes for routines which create, delete, and display IndexEntry
* structures.
extern IndexEntry *createIndexEntry( void );
extern void deleteIndexEntry( IndexEntry * entry, Int level );
extern void outputIndexEntry( IndexEntry * entry, Int level, Int indent );
#endif /* DIS_INDEX_H */