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