HOOPS/3dGS I.M. Interface

     << Back      Full Index      Forward >>


adt.h

00001 /*
00002  * Copyright (c) 1998 by Tech Soft 3D, LLC.
00003  * The information contained herein is confidential and proprietary to
00004  * Tech Soft 3D, LLC., and considered a trade secret as defined under
00005  * civil and criminal statutes.  Tech Soft 3D shall pursue its civil
00006  * and criminal remedies in the event of unauthorized use or misappropriation
00007  * of its trade secrets.  Use of this information by anyone other than
00008  * authorized employees of Tech Soft 3D, LLC. is granted only under a
00009  * written non-disclosure agreement, expressly prescribing the scope and
00010  * manner of such use.
00011  *
00012  * $Id: adt_8h-source.html,v 1.29 2008-03-10 07:09:28 stage Exp $
00013  */
00014 
00015 #ifndef ADT_H
00016 #define ADT_H
00017 
00018 #include "hoops.h"
00019 
00020 /* Abstract Data Types -- type independent data structures based on void pointers */
00021 
00022 
00023 EXTERNAL {
00024 
00025 /* 
00026  * HT_VHASH
00027  * 
00028  * NOTES 
00029  * a) assumes all keys are unique. if not remove the old key/item first or
00030  *      use replace, rather than insert.  Otherwise, when you try to look it up
00031  *      later, you may get the old value, maybe the new one
00032  * b) use each vhash only for strings or keys -- do not mix types 
00033  * c) after a large number of remove items the hash should be rebuilt to restore speed 
00034  * d) this auto resizes at 50% capacity for best performance, so choose a size 2*max 
00035  *      items expected
00036  * e) unless otherwise noted, all functions return 0 on failure
00037  */
00038 struct HT_VHash_Node {
00039     POINTER_SIZED_INT key;
00040     void * item;
00041     unsigned char state;
00042 };
00043 
00044 struct HT_VHash_String_Node {
00045     char * string;
00046     void * item;
00047 };
00048 
00049 struct HT_VHash {
00050     HT_VHash_Node * table;
00051     unsigned long count;
00052     unsigned long table_size;
00053     long key_length;
00054     char *key_string;
00055 };
00056 
00057 struct HT_VHash_Pair {
00058     void * key;
00059     void * item;
00060 };
00061 
00062 #define VHASH_STATUS_FAILED 0
00063 #define VHASH_STATUS_SUCCESS 1
00064 #define VHASH_STATUS_INSERTED 2
00065 
00066 
00067 HT_VHash *HI_New_VHash(
00068     unsigned long table_size);
00069 
00070 void HI_Delete_VHash(HT_VHash * vhash);
00071 void HI_VHash_Flush(HT_VHash * vhash);
00072 
00073 int HI_VHash_Rebuild_Table(
00074     HT_VHash * vhash,
00075     unsigned long table_size);
00076 
00077 unsigned long HI_VHash_Count(HT_VHash* vhash);
00078 
00079 
00080 /* this builds a list of HT_VHash_Pair stucts of the hash content 
00081     these must be cleaned up by the caller using FREE */
00082 
00083 void HI_VHash_To_VList(
00084     HT_VHash * vhash,
00085     HT_VList * vlist);
00086 
00087 /* The following function "map"'s the given function pointer 
00088  * to each of the inserted items.  So another good name 
00089  * might have been HI_VHash_For_Each.  Left this way to match
00090  * nomenclature in original version (see mvo)
00091  * Arguments for the function you supply must be: item, key, user_dat
00092  * your function returns 
00093  *   VHASH_STATUS_SUCCESS to keep mapping
00094  *   VHASH_STATUS_FAILED to stop mapping
00095  */
00096 void HI_VHash_Map_Function(
00097     HT_VHash * v,
00098     int(*function)(void*, void*, void*),
00099     void * user_data);
00100 /* replaced_item is valid only if return status is VHASH_STATUS_SUCCESS */
00101 /* returns VHASH_STATUS_INSERTED if no item with same key existed*/
00102 int HI_VHash_Replace_Item(
00103     HT_VHash * v,
00104     const void * in_key, 
00105     const void * new_item,
00106     void ** replaced_item);
00107 int HI_VHash_Insert_Item(
00108     HT_VHash * v,
00109     const void * in_key,
00110     const void * item);
00111 int HI_VHash_Remove_Item(
00112     HT_VHash * v,
00113     const void * in_key,
00114     void ** removed_item);
00115 int HI_VHash_Lookup_Item(
00116     HT_VHash * v,
00117     const void * in_key,
00118     void ** out_item);
00119 /* hash keys should be nearly unique (for performance reasons), but if they 
00120    are not completely unique, Lookup_Nth_Item can be used to iterate through 
00121    the set.  Lookup_Nth_Item for n==0 is equivalent to Lookup_Item */
00122 int HI_VHash_Lookup_Nth_Item(
00123     HT_VHash * v,
00124     const void * in_key,
00125     int n,
00126     void ** out_item);
00127 
00128 /* 
00129  * String_Key variants of some of the above functions
00130  */
00131 void HI_VHash_String_Key_Map_Function(
00132     HT_VHash * v,
00133     int(*function)(void*, const char *, void*),
00134     void * user_data);
00135 int HI_VHash_Insert_String_Key_Item(
00136     HT_VHash * v,
00137     const char * string, 
00138     void * item);
00139 int HI_VHash_Lookup_Nth_String_Key_Item(
00140     HT_VHash * v,
00141     const char * string, 
00142     int n,
00143     void **out_item);
00144 int HI_VHash_Lookup_String_Key_Item(
00145     HT_VHash * v,
00146     const char * string, 
00147     void **out_item);
00148 int HI_VHash_Remove_String_Key_Item(
00149     HT_VHash * v,
00150     const char * string, 
00151     void **removed_item);
00152 
00153 /* 
00154  * HT_VBSP
00155  */ 
00156 /* bsp_compare_action
00157     compares two objects of some caller-defined types (e.g. face_node_t).  Since the only information that 
00158         the VBSP has about the objects is their bounds, it is assumed that this function will know what to do
00159         with them.  The comparison function is also responsible for doing whatever actions are required when
00160         the conditions are met (e.g. compute_selection_by_shell's test_face_face_callback does a HI_VArray_Append)
00161    \param passthru the value provided as one of the arguments to the various test functions.  
00162         It will generally be a pointer to a structure containing all of the data that is global to an
00163         entire test (e.g. test_bsp_bsp) operation.
00164    \param item1 the first object of the caller-defined type 
00165    \param item2 (as with item1 above) the second object of some caller-defined type 
00166    \returns false if there is no need to do any further tests (e.g. clash detected)
00167  */ 
00168 typedef int (*bsp_compare_action)(void *passthru, void *item1, void *item2);
00169 typedef int (*bsp_compare_action2)(void *passthru, void *item1, int res);
00170 /* bsp_map_action
00171     applies the given function pointer to each of the items that had been inserted via HI_BSP_Insert
00172    \param passthru the value provided as one of the arguments to the various test functions. 
00173    \param item the object of some caller-defined type (e.g. face_node_t)
00174    \returns false if there is no need to continue (e.g. we were searching for something and found it)
00175  */ 
00176 typedef int (*bsp_map_action)(void *item, void *passthru);
00177 
00178 /* contents of the following structure should be considered private.  There should be
00179  * no need to read or write them except through the provided API */
00180 typedef struct bsp_tag {
00181     float                     bbox[6];          /* bounding volume that contains all items inserted */
00182     int                       max_depth;        /* used only when items are inserted */
00183     struct bsp_node_tag *     root;             /* type is defined in vbsp.c */
00184     bsp_compare_action        compare;          /* set every time from arg HI_Test_BSP_* arg list */
00185     bsp_compare_action2       compare2;         /* set every time from arg HI_Test_BSP_* arg list */
00186     void *                    compare_passthru; /* ditto */
00187     bool                  hasDirection;
00188     HT_Point                  dir;
00189     float                     current_distance;
00190     bool                  current_distance_set;
00191 } HT_VBSP;
00192 
00193 /* creates a new HT_VBSP object */
00194 HT_VBSP *HI_New_BSP( float *bbox_in, int max_depth_in );
00195 /* HI_Delete_BSP is responsible only for deletion of the bsp itself.  Deletion of any items that were
00196    inserted into the bsp is the user's responsibility (hint: use HI_BSP_Map_Function) */
00197 void HI_Delete_BSP( HT_VBSP *tree );
00198 /* If possible, start your data type with the 6 floats for bounds and use 
00199       the same pointer for both item and item bounds (null for item_bounds will
00200       have the same effect).  This will avoid the need to copy the bounding box
00201       at the time of insertion (since we can know that the box pointer is not going to
00202       be prematurely freed) 
00203    \param tree the HT_VBSP object, as created by HI_New_BSP
00204    \param item the item to be inserted
00205    \param item bounds an array of 6 floats (min[xyz],max[xyz]) that contain the bounding cuboid of the
00206       inserted item.  If either null or the same address as "item", we assume that "item" starts with the
00207       relevant information and take it from there (thus avoiding a copy)
00208 */
00209 void HI_BSP_Insert( HT_VBSP *tree, void *item, float *item_bounds );
00210 void HI_BSP_AdjustPosition(HT_VBSP *tree, HT_Point pos, bool); 
00211 
00212 /* just like VHash's map function, except your function returns  
00213       1 to keep going
00214       0 to stop */
00215 int HI_BSP_Map_Function(
00216         HT_VBSP *tree,
00217         bsp_map_action function,
00218         void *user_data);
00219 /* these functions are effectively a variant of Map_Function that is simply
00220       conditional on matching a certain criteria (either matching bbox'es or 
00221       intersecting a ray) */
00222 /* test a bsp against provided bounding cuboid */
00223 int HI_Test_BSP( 
00224         HT_VBSP *tree, 
00225         bsp_compare_action compare_callback,
00226         void *passthru, 
00227         void *item2, 
00228         float *bounds, 
00229         bool closest_distance               
00230         );
00231 int HI_Test_BSP_Bounding_Reject( 
00232         HT_VBSP *tree, 
00233         bsp_compare_action compare_callback,
00234         bsp_compare_action2 compare_callback2,
00235         void *passthru, 
00236         void *item2, 
00237         float *bounds
00238         );
00239 /* test the items in one bsp the items in the other one */
00240 int HI_Test_BSP_BSP( 
00241         HT_VBSP *tree, 
00242         bsp_compare_action compare_callback,
00243         void *passthru, 
00244         HT_VBSP *item2_bsp,
00245         bool hasDirection
00246         );
00247 /* test a bsp against a ray */
00248 int HI_Test_BSP_Ray( 
00249         HT_VBSP *tree, 
00250         bsp_compare_action compare_callback,
00251         void *passthru, 
00252         void *item2, 
00253         float *start, 
00254         float *direction  );
00255 
00256 
00257 
00258 float HI_CD_DistanceBoxBox( float *min1, 
00259                             float *max1, 
00260                             float *min2,
00261                             float *max2);
00262  
00263 float HI_CD_MaxDistanceBoxBox(float *min1, 
00264                               float *max1, 
00265                               float *min2, 
00266                               float *max2);
00267 
00268 bool HI_CD_DistancePointLine( HT_Point *Point, 
00269                                    HT_Point *LineStart,  
00270                                    HT_Point *LineEnd, 
00271                                    float *Distance, 
00272                                    HT_Point *res );
00273 
00274 float HI_CD_CalculateDiagLength(float *b);
00275 
00276 
00277 void HI_CD_CalculateMidPoint(float *b, 
00278                              HT_Point *mid);
00279 
00280 
00281 /* 
00282  * HT_VList
00283  */ 
00284 
00285 
00286 struct HT_VList {
00287     struct vlist_node_s * head;
00288     struct vlist_node_s * tail;
00289     struct vlist_node_s * cursor;
00290     struct vlist_node_s * cursor_backlink;
00291     unsigned int cursor_index;
00292     unsigned int count;
00293 };
00294 
00295 HT_VList* HI_New_VList(void);
00296 void HI_Delete_VList( HT_VList* vlist ); 
00297 void HI_VList_Add_First( HT_VList* vlist, void* item );
00298 void HI_VList_Add_Last( HT_VList* vlist, void* item );
00299 void * HI_VList_Remove_First( HT_VList* vlist );
00300 void HI_VList_Reset_Cursor( HT_VList* vlist );
00301 void * HI_VList_Peek_Cursor( HT_VList* vlist );
00302 void * HI_VList_Peek_Cursor_Next( HT_VList* vlist );
00303 void HI_VList_Advance_Cursor( HT_VList* vlist );
00304 void * HI_VList_Peek_First( HT_VList* vlist );
00305 void * HI_VList_Peek_Last( HT_VList* vlist );
00306 unsigned int HI_VList_Count( HT_VList* vlist );
00307 /* This function takes a 0 based index */
00308 void* HI_VList_Nth_Item( HT_VList* vlist, unsigned long index );
00309 void HI_VList_Reverse( HT_VList* vlist );
00310 void * HI_VList_Remove_Cursor_Next( HT_VList* vlist );
00311 int HI_VList_Remove( HT_VList* vlist, void* item );
00312  
00313 void *HI_VList_Remove_At_Cursor(HT_VList* vlist);
00314 void HI_VList_Add_Before_Cursor(HT_VList* vlist, void* item);
00315 void HI_VList_Add_After_Cursor(HT_VList* vlist, void* item);
00316  
00317 /* 
00318  * HT_VHeap and HT_IHeap
00319  *
00320  * IHeap tracks integers.
00321  * VHeap tracks "void *"'s
00322  *
00323  * NOTES
00324  * a) IHeap uses its integers directly for a reverse lookup table.  Therefore:
00325  *      1) integers must be non-negative
00326  *      2) they must be confined to some reasonable range
00327  * b) IHeap is primarily intended to track array indices, which would satisfy
00328  *      both of the above requirements
00329  */ 
00330 
00331 typedef struct ht_iheap_tag {
00332     int used;
00333     int allocated;
00334     POINTER_SIZED_INT *items;
00335     float *values;
00336     int *lookup;
00337 } HT_IHeap;
00338 
00339 typedef struct ht_vheap_tag {
00340     HT_IHeap *iheap;
00341     HT_VHash *vhash;
00342     HT_VHash *reverse_vhash;
00343     int next_index;
00344 } HT_VHeap;
00345 
00346 HT_IHeap *HI_New_IHeap(void);
00347 void HI_Delete_IHeap( HT_IHeap *heap );
00348 void HI_IHeap_Insert( HT_IHeap *heap, int item, float value );
00349 void HI_IHeap_Update( HT_IHeap *heap, int item, float value );
00350 bool HI_IHeap_Kill( HT_IHeap *heap, int item );
00351 bool HI_IHeap_Pop( HT_IHeap *heap, POINTER_SIZED_INT *item, float *value );
00352 bool HI_IHeap_Peek( HT_IHeap *heap, POINTER_SIZED_INT alter *item, float alter *value );
00353 
00354 HT_VHeap *HI_New_VHeap(void);
00355 void HI_Delete_VHeap( HT_VHeap *heap );
00356 void HI_VHeap_Insert( HT_VHeap *heap, void const *item, float value );
00357 void HI_VHeap_Update( HT_VHeap *heap, void const *item, float value );
00358 bool HI_VHeap_Kill( HT_VHeap *heap, void const *item );
00359 bool HI_VHeap_Pop( HT_VHeap *heap, void **item, float *value );
00360 bool HI_VHeap_Peek( HT_VHeap *heap, void alter **item, float alter *value );
00361 
00362 
00363 /* 
00364  * HT_VArray and HT_IArray
00365  *
00366  * IArray tracks integers.
00367  * VArray tracks "void *"'s
00368  */ 
00369 
00370 typedef struct {
00371     int allocated;
00372     int used;
00373     int limit;
00374     void **array;
00375 } HT_IArray, HT_VArray;
00376 
00377 
00378 HT_VArray *HI_New_VArray(void);
00379 void HI_Delete_VArray(HT_VArray *kl);
00380 HT_VArray *HI_VArray_Clone( const HT_VArray *kl );
00381 void HI_VArray_Reverse( HT_VArray *kl );
00382 int HI_VArray_Append( HT_VArray *kl, void *item );
00383 void HI_VArray_Chop( HT_VArray *kl );
00384 
00385 #define HI_New_IArray() ((HT_IArray *)HI_New_VArray())
00386 #define HI_Delete_IArray(kl) (HI_Delete_VArray((HT_Varray *)kl))
00387 #define HI_IArray_Clone(kl) ((HT_IArray *)HI_VArray_Clone((HT_Varray *)kl))
00388 #define HI_IArray_Reverse(kl) (HI_VArray_Reverse((HT_Varray *)kl))
00389 #define HI_IArray_Append(kl,item) (HI_VArray_Append((HT_Varray *)kl, (void *)item))
00390 #define HI_IArray_Chop(kl) (HI_VArray_Chop((HT_Varray *)kl)
00391 
00392 
00393 } // EXTERNAL
00394 
00395 
00396 #endif /*ADT_H*/
00397 
00398 
Main Index
HOOPS/3dGS I.M. Interface

     << Back      Full Index      Forward >>