Nick, You may want to check out the red-black tree in LIBBU for this instead of a custom linked list or other search tree. They're ideally suited for situations where you want bounded insertion, deletion, and lookup times. They are O(log n) time, making them great for things like a run loops and work queues with dynamic levels.
The red-black tree interface has a manual page (brlman redblack) as well as a few examples sprinkled throughout. Cheers! Sean On Monday, July 27, 2009, at 04:58PM, <[email protected]> wrote: >Revision: 35314 > http://brlcad.svn.sourceforge.net/brlcad/?rev=35314&view=rev >Author: n_reed >Date: 2009-07-27 20:58:36 +0000 (Mon, 27 Jul 2009) > >Log Message: >----------- >starting to add support for point heirarchy > >Modified Paths: >-------------- > brlcad/trunk/include/dm-rtgl.h > brlcad/trunk/src/libdm/dm-rtgl.c > >Modified: brlcad/trunk/include/dm-rtgl.h >=================================================================== >--- brlcad/trunk/include/dm-rtgl.h 2009-07-27 20:12:59 UTC (rev 35313) >+++ brlcad/trunk/include/dm-rtgl.h 2009-07-27 20:58:36 UTC (rev 35314) >@@ -83,6 +83,20 @@ > float color[3]; > }; > >+struct objTree { >+ char *treeName; >+ int numChildren; >+ struct objTree **children; >+ struct ptInfoList *ptInfo; >+}; >+ >+#define INIT_OBJTREE(p) { \ >+(struct objTree *)(p)->name = NULL; \ >+(struct objTree *)(p)->numChildren = 0; \ >+(struct objTree *)(p)->children = NULL; \ >+(struct objTree *)(p)->ptInfo = NULL; \ >+} >+ > #endif /* __DM_RTGL__ */ > > /** @} */ > >Modified: brlcad/trunk/src/libdm/dm-rtgl.c >=================================================================== >--- brlcad/trunk/src/libdm/dm-rtgl.c 2009-07-27 20:12:59 UTC (rev 35313) >+++ brlcad/trunk/src/libdm/dm-rtgl.c 2009-07-27 20:58:36 UTC (rev 35314) >@@ -899,7 +899,7 @@ > double startScale = 1; > > /* >- * O G L _ L O A D M A T R I X >+ * R T G L _ L O A D M A T R I X > * > * Load a new transformation matrix. This will be followed by > * many calls to rtgl_drawVList(). >@@ -1109,6 +1109,8 @@ > > } > >+ >+ > /* add all hit point info to info list */ > int recordHit(struct application *app, struct partition *partH, struct seg > *segs) > { >@@ -1208,6 +1210,31 @@ > glPointSize(1); > } > >+struct objTree objects; >+ >+void buildTree(struct ged *gedp) { >+ int i, len; >+ char *curr, *result, *name; >+ >+ /* get names of tree tops */ >+ ged_tops(gedp, 2, "tops -n"); >+ result = bu_vls_strdup(&(gedp->ged_result_str)); >+ >+ /* extract individual names */ >+ len = strcspn(result, "/ "); /* num chars before '/' or ' ' */ >+ >+ name = malloc(sizeof(char) * (len + 1)); >+ name[len] = '\0'; >+ >+ strncpy(name, result, len); >+ >+ /* skip to next name */ >+ while(result[len] != ' ') len++; >+ while(result[len++] == ' '); >+ >+ result = &(result[len]); >+} >+ > /* > * R T G L _ D R A W V L I S T > * >@@ -1217,8 +1244,8 @@ > { > static int call; > >- int i, j, numTrees, new, newTrees; >- char *currTree, *trees[RT_MAXARGS]; >+ int i, j, new, numVisible, numNew; >+ char *currTree, *visibleTrees[RT_MAXARGS]; > struct ptInfoList *curr; > > /* get ged struct */ >@@ -1239,6 +1266,7 @@ > if (rtip == RTI_NULL) > return TCL_ERROR; > >+ /* initialize list */ > if (ptInfo.l.forw == BU_LIST_NULL) { > /* initialize head */ > BU_LIST_INIT(&(ptInfo.l)); >@@ -1248,13 +1276,20 @@ > BU_GETSTRUCT(currItem, ptInfoList); > BU_LIST_PUSH(&(ptInfo.l), currItem); > currItem->used = 0; >+ >+ call = 1; > } > >+ >+ if (call == 1) { >+ buildTree(gedp); >+ } >+ > /* get number and names of visible tree tops */ >- numTrees = ged_build_tops(gedp, trees, &trees[RT_MAXARGS]); >+ numVisible = ged_build_tops(gedp, visibleTrees, >&visibleTrees[RT_MAXARGS]); > > /* no objects are visible */ >- if (numTrees == 0) { >+ if (numVisible == 0) { > > /* drop all display points */ > freeInfoList(); >@@ -1268,10 +1303,10 @@ > } > > /* look for new trees in need of ray tracing */ >- newTrees = 0; >+ numNew = 0; > >- for (i = 0; i < numTrees; i++) { >- currTree = trees[i]; >+ for (i = 0; i < numVisible; i++) { >+ currTree = visibleTrees[i]; > new = 1; > > /* if this tree is in the old tree list, it's not new */ >@@ -1286,14 +1321,13 @@ > return TCL_ERROR; > > /* add new tree to list of displayed */ >- newTrees++; >+ numNew++; > oldTrees[oldNumTrees++] = currTree; > } > } > > /* get points for new trees */ >- if (newTrees) { >- call = 1; >+ if (numNew > 0) { > > /* set up application */ > RT_APPLICATION_INIT(&app); > > >This was sent by the SourceForge.net collaborative development platform, the >world's largest Open Source development site. > >------------------------------------------------------------------------------ >_______________________________________________ >BRL-CAD Source Commits mailing list >[email protected] >https://lists.sourceforge.net/lists/listinfo/brlcad-commits > > ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ BRL-CAD Developer mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/brlcad-devel
