Red-Black Tree Code Cleanups:
authorJoshua Leung <aligorith@gmail.com>
Sun, 15 Nov 2009 11:20:44 +0000 (11:20 +0000)
committerJoshua Leung <aligorith@gmail.com>
Sun, 15 Nov 2009 11:20:44 +0000 (11:20 +0000)
Added some more methods for the Red-Black Tree implementation in Blender (used for runtime viewing and searching of keyframes) which abstract away some of the lower-level handling of the BST (i.e. adding nodes without balancing and searching for nodes).

Also, improved the implementation of the jump next/prev keyframe operator so that it pops up an error message when the last keyframe in whatever direction is encountered.

source/blender/blenlib/BLI_dlrbTree.h
source/blender/blenlib/intern/DLRB_tree.c
source/blender/editors/animation/keyframes_draw.c
source/blender/editors/armature/poseSlide.c
source/blender/editors/include/ED_keyframes_draw.h
source/blender/editors/screen/screen_ops.c

index a17cbbd19931f203c02ed70d7163d239df387a43..bced738b4e7873ed9f884cb358a0fe4af34d9f21 100644 (file)
@@ -54,10 +54,10 @@ typedef struct DLRBT_Node {
 } DLRBT_Node;
 
 /* Red/Black defines for tree_col */
-enum eDLRBT_Colors {
+typedef enum eDLRBT_Colors {
        DLRBT_BLACK= 0,
        DLRBT_RED,
-};
+} eDLRBT_Colors;
 
 /* -------- */
 
@@ -70,9 +70,30 @@ typedef struct DLRBT_Tree {
        void *root;                                     /* this should be based on DLRBT_Node-s */
 } DLRBT_Tree;
 
+/* Callback Types --------------------------------- */
+
+/* return -1, 0, 1 for whether the given data is less than, equal to, or greater than the given node 
+ *     - node: <DLRBT_Node> the node to compare to
+ *     - data: pointer to the relevant data or values stored in the bitpattern dependant on the function
+ */
+typedef short (*DLRBT_Comparator_FP)(void *node, void *data);
+
+/* return a new node instance wrapping the given data 
+ *     - data: pointer to the relevant data to create a subclass of node from
+ */
+typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data);
+
+/* update an existing node instance accordingly to be in sync with the given data *    
+ *     - node: <DLRBT_Node> the node to update
+ *     - data: pointer to the relevant data or values stored in the bitpattern dependant on the function
+ */
+typedef void (*DLRBT_NUpdate_FP)(void *node, void *data);
+
 /* ********************************************** */
 /* Public API */
 
+/* ADT Management ------------------------------- */
+
 /* Create a new tree, and initialise as necessary */
 DLRBT_Tree *BLI_dlrbTree_new(void);
 
@@ -86,16 +107,52 @@ void BLI_dlrbTree_free(DLRBT_Tree *tree);
 void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
 
 
+/* Searching ------------------------------------ */
 
-/* Balance the tree after the given element has been added to it 
- * (using custom code, in the Binary Tree way).
+/* Find the node which matches or is the closest to the requested node */
+DLRBT_Node *BLI_dlrbTree_search(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
+
+/* Find the node which exactly matches the required data */
+DLRBT_Node *BLI_dlrbTree_search_exact(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
+
+/* Find the node which occurs immediately before the best matching node */
+DLRBT_Node *BLI_dlrbTree_search_prev(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
+
+/* Find the node which occurs immediately after the best matching node */
+DLRBT_Node *BLI_dlrbTree_search_next(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
+
+
+/* Check whether there is a node matching the requested node */
+short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
+
+
+/* Node Operations (Managed) --------------------- */
+/* These methods automate the process of adding/removing nodes from the BST, 
+ * using the supplied data and callbacks
  */
-void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
+
+/* Add the given data to the tree, and return the node added */
+// NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned
+DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, 
+                       DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data);
+
 
 /* Remove the given element from the tree and balance again */
 // FIXME: this is not implemented yet... 
 void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
 
+/* Node Operations (Manual) --------------------- */
+/* These methods require custom code for creating BST nodes and adding them to the 
+ * tree in special ways, such that the node can then be balanced.
+ *
+ * It is recommended that these methods are only used where the other method is too cumbersome...
+ */
+
+/* Balance the tree after the given node has been added to it 
+ * (using custom code, in the Binary Tree way).
+ */
+void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
+
 /* ********************************************** */
 
 #endif // BLI_DLRB_TREE_H
index af9774c6afd19f6dfc8910f7a8013e54663408b0..8eb743e282cd6d505a4a2c07af2ad4bc662e4af7 100644 (file)
@@ -129,6 +129,155 @@ void BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree)
        linkedlist_sync_add_node(tree, tree->root);
 }
 
+/* *********************************************** */
+/* Tree Search Utilities */
+
+/* Find the node which matches or is the closest to the requested node */
+DLRBT_Node *BLI_dlrbTree_search (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
+{
+       DLRBT_Node *node = (tree) ? tree->root : NULL;
+       short found= 0;
+       
+       /* check that there is a comparator to use */
+       // TODO: if no comparator is supplied, try using the one supplied with the tree...
+       if (cmp_cb == NULL)
+               return NULL;
+       
+       /* iteratively perform this search */
+       while (node && found==0) 
+       {
+               /* check if traverse further or not 
+                * NOTE: it is assumed that the values will be unit values only
+                */
+               switch (cmp_cb(node, search_data)) {
+                       case -1:        /* data less than node */
+                               if (node->left)
+                                       node= node->left;
+                               else
+                                       found= 1;
+                               break;
+                       
+                       case 1:         /* data greater than node */
+                               if (node->right)
+                                       node= node->right;
+                               else
+                                       found= 1;
+                               break;
+                       
+                       default:        /* data equals node */
+                               found= 1;
+                               break;
+               }
+       }
+       
+       /* return the nearest matching node */
+       return node;
+} 
+
+/* Find the node which exactly matches the required data */
+DLRBT_Node *BLI_dlrbTree_search_exact (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
+{
+       DLRBT_Node *node = (tree) ? tree->root : NULL;
+       short found= 0;
+       
+       /* check that there is a comparator to use */
+       // TODO: if no comparator is supplied, try using the one supplied with the tree...
+       if (cmp_cb == NULL)
+               return NULL;
+       
+       /* iteratively perform this search */
+       while (node && found==0) 
+       {
+               /* check if traverse further or not 
+                * NOTE: it is assumed that the values will be unit values only
+                */
+               switch (cmp_cb(node, search_data)) {
+                       case -1:        /* data less than node */
+                               if (node->left)
+                                       node= node->left;
+                               else
+                                       found= -1;
+                               break;
+                       
+                       case 1:         /* data greater than node */
+                               if (node->right)
+                                       node= node->right;
+                               else
+                                       found= -1;
+                               break;
+                       
+                       default:        /* data equals node */
+                               found= 1;
+                               break;
+               }
+       }
+       
+       /* return the nearest matching node */
+       return (found == 1) ? (node) : (NULL);
+}
+
+/* Find the node which occurs immediately before the best matching node */
+DLRBT_Node *BLI_dlrbTree_search_prev (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
+{
+       DLRBT_Node *node;
+       
+       /* check that there is a comparator to use */
+       // TODO: if no comparator is supplied, try using the one supplied with the tree...
+       if (cmp_cb == NULL)
+               return NULL;
+       
+       /* get the node which best matches this description */
+       node= BLI_dlrbTree_search(tree, cmp_cb, search_data);
+       
+       if (node) {
+               /* if the item we're searching for is greater than the node found, we've found the match */
+               if (cmp_cb(node, search_data) > 0)
+                       return node;
+               
+               /* return the previous node otherwise */
+               // NOTE: what happens if there is no previous node?
+               return node->prev;
+       }
+       
+       /* nothing matching was found */
+       return NULL;
+}
+
+/* Find the node which occurs immediately after the best matching node */
+DLRBT_Node *BLI_dlrbTree_search_next (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
+{
+       DLRBT_Node *node;
+       
+       /* check that there is a comparator to use */
+       // TODO: if no comparator is supplied, try using the one supplied with the tree...
+       if (cmp_cb == NULL)
+               return NULL;
+       
+       /* get the node which best matches this description */
+       node= BLI_dlrbTree_search(tree, cmp_cb, search_data);
+       
+       if (node) {
+               /* if the item we're searching for is less than the node found, we've found the match */
+               if (cmp_cb(node, search_data) < 0)
+                       return node;
+               
+               /* return the previous node otherwise */
+               // NOTE: what happens if there is no previous node?
+               return node->next;
+       }
+       
+       /* nothing matching was found */
+       return NULL;
+}
+
+
+/* Check whether there is a node matching the requested node */
+short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
+{
+       /* check if an exact search throws up anything... */
+       return (BLI_dlrbTree_search_exact(tree, cmp_cb, search_data) != NULL);
+}
+
 /* *********************************************** */
 /* Tree Relationships Utilities */
 
@@ -161,6 +310,7 @@ static DLRBT_Node *get_uncle (DLRBT_Node *node)
 /* *********************************************** */
 /* Tree Rotation Utilities */
 
+/* make right child of 'root' the new root */
 static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root)
 {
        DLRBT_Node **root_slot, *pivot;
@@ -194,6 +344,7 @@ static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root)
                *root_slot= pivot;
 }
 
+/* make the left child of the 'root' the new root */
 static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root)
 {
        DLRBT_Node **root_slot, *pivot;
@@ -332,7 +483,7 @@ static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node)
 /* Balance the tree after the given element has been added to it 
  * (using custom code, in the Binary Tree way).
  */
-void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node)
+void BLI_dlrbTree_insert (DLRBT_Tree *tree, DLRBT_Node *node)
 {
        /* sanity checks */
        if ((tree == NULL) || (node == NULL))
@@ -345,6 +496,90 @@ void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node)
        insert_check_1(tree, node);
 }
 
+/* ----- */
+
+/* Add the given data to the tree, and return the node added */
+// NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned
+DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, 
+                       DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data)
+{
+       DLRBT_Node *parNode, *node=NULL;
+       short new_node = 0;
+       
+       /* sanity checks */
+       if (tree == NULL)
+               return NULL;
+               
+       // TODO: if no comparator is supplied, try using the one supplied with the tree...
+       if (cmp_cb == NULL)
+               return NULL;
+       // TODO: if no allocator is supplied, try using the one supplied with the tree...
+       if (new_cb == NULL)
+               return NULL;
+       // TODO: if no updater is supplied, try using the one supplied with the tree...
+               
+       /* try to find the nearest node to this one */
+       parNode= BLI_dlrbTree_search(tree, cmp_cb, data);
+       
+       /* add new node to the BST in the 'standard way' as appropriate 
+        * NOTE: we do not support duplicates in our tree...
+        */
+       if (parNode) {
+               /* check how this new node compares with the existing ones 
+                * NOTE: it is assumed that the values will be unit values only
+                */
+               switch (cmp_cb(parNode, data)) {
+                       case -1:        /* add new node as left child */
+                       {
+                               node= new_cb(data);
+                               new_node= 1;
+                               
+                               parNode->left= node;
+                               node->parent= parNode;
+                       }
+                               break;
+                       
+                       case 1:         /* add new node as right child */
+                       {
+                               node= new_cb(data);
+                               new_node= 1;
+                               
+                               parNode->right= node;
+                               node->parent= parNode;
+                       }
+                               break;
+                       
+                       default:        /* update the duplicate node as appropriate */
+                       {
+                               if (update_cb)
+                                       update_cb(parNode, data);
+                       }
+                               break;
+               }
+       }
+       else {
+               /* no nodes in the tree yet... add a new node as the root */
+               node= new_cb(data);
+               new_node= 1;
+               
+               tree->root= node;
+       }
+       
+       /* if a new node was added, it should be tagged as red, and then balanced as appropriate */
+       if (new_node) {
+               /* tag this new node as being 'red' */
+               node->tree_col= DLRBT_RED;
+               
+               /* perform BST balancing steps:
+                *      start from case 1, an trek through the tail-recursive insertion checks
+                */
+               insert_check_1(tree, node);
+       }
+       
+       /* return the node added */
+       return node;
+}
+
 /* *********************************************** */
 /* Remove */
 
index fb02a88ea2bc70cb6c131b03c71f67773d95dac6..b3d2b12a5a0296d0a76d490dca57942177f53c53 100644 (file)
 
 /* *************************** Keyframe Processing *************************** */
 
-/* Create a ActKeyColumn from a BezTriple */
-static ActKeyColumn *bezt_to_new_actkeycolumn(BezTriple *bezt)
+/* Comparator callback used for ActKeyColumns and cframe float-value pointer */
+short compare_ak_cfraPtr (void *node, void *data)
+{
+       ActKeyColumn *ak= (ActKeyColumn *)node;
+       float *cframe= data;
+       
+       if (*cframe < ak->cfra)
+               return -1;
+       else if (*cframe > ak->cfra)
+               return 1;
+       else
+               return 0;
+}
+
+/* .... */
+
+/* Comparator callback used for ActKeyColumns and BezTriple */
+static short compare_ak_bezt (void *node, void *data)
+{
+       ActKeyColumn *ak= (ActKeyColumn *)node;
+       BezTriple *bezt= (BezTriple *)data;
+       
+       if (bezt->vec[1][0] < ak->cfra)
+               return -1;
+       else if (bezt->vec[1][0] > ak->cfra)
+               return 1;
+       else
+               return 0;
+}
+
+/* New node callback used for building ActKeyColumns from BezTriples */
+static DLRBT_Node *nalloc_ak_bezt (void *data)
 {
        ActKeyColumn *ak= MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn");
+       BezTriple *bezt= (BezTriple *)data;
        
        /* store settings based on state of BezTriple */
        ak->cfra= bezt->vec[1][0];
@@ -105,67 +136,33 @@ static ActKeyColumn *bezt_to_new_actkeycolumn(BezTriple *bezt)
        /* set 'modified', since this is used to identify long keyframes */
        ak->modified = 1;
        
-       return ak;
+       return (DLRBT_Node *)ak;
 }
 
-/* Add the given BezTriple to the given 'list' of Keyframes */
-static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt)
+/* Node updater callback used for building ActKeyColumns from BezTriples */
+static void nupdate_ak_bezt (void *node, void *data)
 {
-       ActKeyColumn *new_ak=NULL;
+       ActKeyColumn *ak= (ActKeyColumn *)node;
+       BezTriple *bezt= (BezTriple *)data;
        
-       if ELEM(NULL, keys, bezt) return;
+       /* set selection status and 'touched' status */
+       if (BEZSELECTED(bezt)) ak->sel = SELECT;
+       ak->modified += 1;
        
-       /* if there are no keys already, just add as root */
-       if (keys->root == NULL) {
-               /* just add this as the root, then call the tree-balancing functions to validate */
-               new_ak= bezt_to_new_actkeycolumn(bezt);
-               keys->root= (DLRBT_Node *)new_ak;
-       }
-       else {
-               ActKeyColumn *ak, *akp=NULL, *akn=NULL;
-               
-               /* traverse tree to find an existing entry to update the status of, 
-                * or a suitable point to add at
-                */
-               for (ak= keys->root; ak; akp= ak, ak= akn) {
-                       /* check if this is a match, or whether we go left or right */
-                       if (ak->cfra == bezt->vec[1][0]) {
-                               /* set selection status and 'touched' status */
-                               if (BEZSELECTED(bezt)) ak->sel = SELECT;
-                               ak->modified += 1;
-                               
-                               /* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
-                               if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME)
-                                       ak->key_type= BEZT_KEYTYPE_KEYFRAME;
-                               
-                               /* done... no need to insert */
-                               return;
-                       }
-                       else {
-                               ActKeyColumn **aknp= NULL; 
-                               
-                               /* check if go left or right, but if not available, add new node */
-                               if (ak->cfra < bezt->vec[1][0]) 
-                                       aknp= &ak->right;
-                               else
-                                       aknp= &ak->left;
-                                       
-                               /* if this does not exist, add a new node, otherwise continue... */
-                               if (*aknp == NULL) {
-                                       /* add a new node representing this, and attach it to the relevant place */
-                                       new_ak= bezt_to_new_actkeycolumn(bezt);
-                                       new_ak->parent= ak;
-                                       *aknp= new_ak;
-                                       break;
-                               }
-                               else
-                                       akn= *aknp;
-                       }
-               }
-       }
-       
-       /* now, balance the tree taking into account this newly added node */
-       BLI_dlrbTree_insert(keys, (DLRBT_Node *)new_ak);
+       /* for keyframe type, 'proper' keyframes have priority over breakdowns (and other types for now) */
+       if (BEZKEYTYPE(bezt) == BEZT_KEYTYPE_KEYFRAME)
+               ak->key_type= BEZT_KEYTYPE_KEYFRAME;
+}
+
+/* --------------- */
+
+/* Add the given BezTriple to the given 'list' of Keyframes */
+static void add_bezt_to_keycolumns_list(DLRBT_Tree *keys, BezTriple *bezt)
+{
+       if ELEM(NULL, keys, bezt) 
+               return;
+       else
+               BLI_dlrbTree_add(keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
 }
 
 
@@ -317,47 +314,6 @@ static void set_touched_actkeyblock (ActKeyBlock *ab)
 
 /* *************************** Keyframe Drawing *************************** */
 
-/* helper function - find actkeycolumn that occurs on cframe */
-ActKeyColumn *cfra_find_actkeycolumn (ActKeyColumn *ak, float cframe)
-{
-       /* sanity checks */
-       if (ak == NULL)
-               return NULL;
-       
-       /* check if this is a match, or whether it is in some subtree */
-       if (cframe < ak->cfra)
-               return cfra_find_actkeycolumn(ak->left, cframe);
-       else if (cframe > ak->cfra)
-               return cfra_find_actkeycolumn(ak->right, cframe);
-       else
-               return ak; /* match */
-}
-
-/* helper function - find actkeycolumn that occurs on cframe, or the nearest one if not found */
-// FIXME: this is buggy... next() is ignored completely...
-ActKeyColumn *cfra_find_nearest_next_ak (ActKeyColumn *ak, float cframe, short next)
-{
-       ActKeyColumn *akn= NULL;
-       
-       /* sanity checks */
-       if (ak == NULL)
-               return NULL;
-       
-       /* check if this is a match, or whether it is in some subtree */
-       if (cframe < ak->cfra)
-               akn= cfra_find_nearest_next_ak(ak->left, cframe, next);
-       else if (cframe > ak->cfra)
-               akn= cfra_find_nearest_next_ak(ak->right, cframe, next);
-               
-       /* if no match found (or found match), just use the current one */
-       if (akn == NULL)
-               return ak;
-       else
-               return akn;
-}
-
-/* -------- */
-
 /* coordinates for diamond shape */
 static const float _unit_diamond_shape[4][2] = {
        {0.0f, 1.0f},   /* top vert */
@@ -471,10 +427,10 @@ static void draw_keylist(View2D *v2d, DLRBT_Tree *keys, DLRBT_Tree *blocks, floa
                        short startCurves, endCurves, totCurves;
                        
                        /* find out how many curves occur at each keyframe */
-                       ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->start);
+                       ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->start);
                        startCurves = (ak)? ak->totcurve: 0;
                        
-                       ak= cfra_find_actkeycolumn((ActKeyColumn *)keys->root, ab->end);
+                       ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(keys, compare_ak_cfraPtr, &ab->end);
                        endCurves = (ak)? ak->totcurve: 0;
                        
                        /* only draw keyblock if it appears in at all of the keyframes at lowest end */
@@ -676,7 +632,6 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree
                if ((sce->adt) && !(filterflag & ADS_FILTER_NOSCE)) {
                        adt= sce->adt;
                        
-                       // TODO: when we adapt NLA system, this needs to be the NLA-scaled version
                        if (adt->action) 
                                action_to_keylist(adt, adt->action, keys, blocks);
                }
@@ -685,7 +640,6 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree
                if ((sce->world) && (sce->world->adt) && !(filterflag & ADS_FILTER_NOWOR)) {
                        adt= sce->world->adt;
                        
-                       // TODO: when we adapt NLA system, this needs to be the NLA-scaled version
                        if (adt->action) 
                                action_to_keylist(adt, adt->action, keys, blocks);
                }
@@ -694,7 +648,6 @@ void scene_to_keylist(bDopeSheet *ads, Scene *sce, DLRBT_Tree *keys, DLRBT_Tree
                if ((sce->nodetree) && (sce->nodetree->adt) && !(filterflag & ADS_FILTER_NONTREE)) {
                        adt= sce->nodetree->adt;
                        
-                       // TODO: when we adapt NLA system, this needs to be the NLA-scaled version
                        if (adt->action) 
                                action_to_keylist(adt, adt->action, keys, blocks);
                }
@@ -810,7 +763,6 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, DLRBT_Tree *keys, DLRBT_Tree
                }
                
                /* update the number of curves that elements have appeared in  */
-               // FIXME: this is broken with the new tree structure for now...
                if (keys)
                        set_touched_actkeycolumn(keys->root);
                if (blocks)
index e5d334e4d06049e86ebf332d168a20974c93eab5..eb15d00c8cea0aa21f758c869b22afdda3ad06bb 100644 (file)
@@ -614,12 +614,12 @@ static int pose_slide_invoke_common (bContext *C, wmOperator *op, tPoseSlideOp *
                ActKeyColumn *ak;
                
                /* firstly, check if the current frame is a keyframe... */
-               ak= cfra_find_actkeycolumn(pso->keys.root, pso->cframe);
+               ak= (ActKeyColumn *)BLI_dlrbTree_search_exact(&pso->keys, compare_ak_cfraPtr, &pso->cframe);
                
                if (ak == NULL) {
                        /* current frame is not a keyframe, so search */
-                       ActKeyColumn *pk= cfra_find_nearest_next_ak(pso->keys.root, pso->cframe, 0);
-                       ActKeyColumn *nk= cfra_find_nearest_next_ak(pso->keys.root, pso->cframe, 1);
+                       ActKeyColumn *pk= (ActKeyColumn *)BLI_dlrbTree_search_prev(&pso->keys, compare_ak_cfraPtr, &pso->cframe);
+                       ActKeyColumn *nk= (ActKeyColumn *)BLI_dlrbTree_search_next(&pso->keys, compare_ak_cfraPtr, &pso->cframe);
                        
                        /* check if we found good keyframes */
                        if ((pk == nk) && (pk != NULL)) {
index 699502eb9ebb795bbae76b1ec338b5938b2bf64f..8002918b870348185e5969eb81176c04ee194a7a 100644 (file)
@@ -104,27 +104,43 @@ void draw_keyframe_shape(float x, float y, float xscale, float hsize, short sel,
 
 /* ******************************* Methods ****************************** */
 
-/* Channel Drawing */
+/* Channel Drawing ------------------ */
+/* F-Curve */
 void draw_fcurve_channel(struct View2D *v2d, struct AnimData *adt, struct FCurve *fcu, float ypos);
+/* Action Group Summary */
 void draw_agroup_channel(struct View2D *v2d, struct AnimData *adt, struct bActionGroup *agrp, float ypos);
+/* Action Summary */
 void draw_action_channel(struct View2D *v2d, struct AnimData *adt, struct bAction *act, float ypos);
+/* Object Summary */
 void draw_object_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Object *ob, float ypos);
+/* Scene Summary */
 void draw_scene_channel(struct View2D *v2d, struct bDopeSheet *ads, struct Scene *sce, float ypos);
+/* DopeSheet Summary */
 void draw_summary_channel(struct View2D *v2d, struct bAnimContext *ac, float ypos);
+/* Grease Pencil Layer */ 
+// XXX not restored 
 void draw_gpl_channel(struct View2D *v2d, struct bDopeSheet *ads, struct bGPDlayer *gpl, float ypos);
 
-/* Keydata Generation */
+/* Keydata Generation --------------- */
+/* F-Curve */
 void fcurve_to_keylist(struct AnimData *adt, struct FCurve *fcu, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+/* Action Group */
 void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+/* Action */
 void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+/* Object */
 void ob_to_keylist(struct bDopeSheet *ads, struct Object *ob, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+/* Scene */
 void scene_to_keylist(struct bDopeSheet *ads, struct Scene *sce, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+/* DopeSheet Summary */
 void summary_to_keylist(struct bAnimContext *ac, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
+/* Grease Pencil Layer */
+// XXX not restored
 void gpl_to_keylist(struct bDopeSheet *ads, struct bGPDlayer *gpl, struct DLRBT_Tree *keys, struct DLRBT_Tree *blocks);
 
-/* Keyframe Finding */
-ActKeyColumn *cfra_find_actkeycolumn(ActKeyColumn *ak, float cframe);
-ActKeyColumn *cfra_find_nearest_next_ak(ActKeyColumn *ak, float cframe, short next);
+/* ActKeyColumn API ---------------- */
+/* Comparator callback used for ActKeyColumns and cframe float-value pointer */
+short compare_ak_cfraPtr(void *node, void *data);
 
 #endif  /*  ED_KEYFRAMES_DRAW_H */
 
index f90c15131163a0bc2ef48e165d978706eda7e36f..6f0faf9d8083917bd084b52e007333a444fe226f 100644 (file)
@@ -1468,6 +1468,7 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
        Object *ob= CTX_data_active_object(C);
        DLRBT_Tree keys;
        ActKeyColumn *ak;
+       float cfra= (scene)? (float)(CFRA) : 0.0f;
        short next= RNA_boolean_get(op->ptr, "next");
        
        /* sanity checks */
@@ -1486,21 +1487,18 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
        /* build linked-list for searching */
        BLI_dlrbTree_linkedlist_sync(&keys);
        
-       /* find nearest keyframe in the right direction */
-       ak= cfra_find_nearest_next_ak(keys.root, (float)scene->r.cfra, next);
+       /* find matching keyframe in the right direction */
+       if (next)
+               ak= (ActKeyColumn *)BLI_dlrbTree_search_next(&keys, compare_ak_cfraPtr, &cfra);
+       else
+               ak= (ActKeyColumn *)BLI_dlrbTree_search_prev(&keys, compare_ak_cfraPtr, &cfra);
        
        /* set the new frame (if keyframe found) */
-       if (ak) {
-               if (next && ak->next)
-                       scene->r.cfra= (int)ak->next->cfra;
-               else if (!next && ak->prev)
-                       scene->r.cfra= (int)ak->prev->cfra;
-               else {
-                       printf("ERROR: no suitable keyframe found. Using %f as new frame \n", ak->cfra);
-                       scene->r.cfra= (int)ak->cfra; // XXX
-               }
-       }
-               
+       if (ak) 
+               CFRA= (int)ak->cfra;
+       else
+               BKE_report(op->reports, RPT_ERROR, "No more keyframes to jump to in this direction");
+       
        /* free temp stuff */
        BLI_dlrbTree_free(&keys);