store actions as a tree internally, to have better

accounting of the dependencies between action. Not tested yet,
so probably doesn't work.

1 files changed, 260 insertions, 53 deletions

diff --git a/src/pop-transaction.c b/src/pop-transaction.c
index 387102f..055b846 100644
--- a/src/pop-transaction.c
+++ b/src/pop-transaction.c
@@ -55,6 +55,9 @@ typedef enum _PopTransactionState
   POP_TRANSACTION_STATE_FINISHED,
 } PopTransactionState;
 
+typedef struct _PopAction PopAction;
+typedef struct _PopActionTree PopActionTree;
+
 struct _PopTransactionPrivate
 {
   /* The transaction state is what the transaction
@@ -71,8 +74,7 @@ struct _PopTransactionPrivate
    * transaction api, or potentially by other actions during 
    * the run.
    */
-  GQueue *actions;
-  GList  *current_action_node;
+  PopActionTree *action_tree;
 
   /* which event loop to hook up with.  This is normally NULL,
    * which means "use the default context".
@@ -121,7 +123,33 @@ struct _PopTransactionPrivate
   GError *error;
 };
 
-typedef struct
+typedef enum 
+{
+  POP_ACTION_TREE_WALK_DIRECTION_FORWARD = 0,
+  POP_ACTION_TREE_WALK_DIRECTION_BACKWARD,
+} PopActionTreeWalkDirection;
+
+struct _PopActionTree
+{
+  GNode *root;
+  GNode *current_action_node;
+};
+
+static PopActionTree *pop_action_tree_new (void);
+static void pop_action_tree_reset (PopActionTree *action_tree);
+static gboolean pop_action_tree_is_at_first_action (PopActionTree *action_tree);
+static gboolean pop_action_tree_is_empty (PopActionTree *action_tree);
+static gboolean pop_action_tree_seek (PopActionTree              *action_tree,
+                                      PopActionTreeWalkDirection  direction);
+static  void pop_action_tree_add_action (PopActionTree *action_tree,
+                                         PopAction     *action);
+static PopAction *pop_action_tree_get_current_action (PopActionTree *tree);
+static void pop_action_tree_foreach (PopActionTree *action_tree,
+                                     GFunc          func,
+                                     gpointer       user_data);
+static void pop_action_tree_free (PopActionTree *action_tree);
+
+struct _PopAction
 {
   PopActionProcessFunc process_func;
   PopActionProcessStatus process_status;
@@ -131,7 +159,7 @@ typedef struct
 
   gpointer user_data;
   GDestroyNotify free_func;
-} PopAction;
+};
 
 static PopAction *pop_action_new (PopActionProcessFunc  action_process_func,
                                   PopActionRollbackFunc action_rollback_func,
@@ -307,7 +335,7 @@ pop_transaction_init (PopTransaction *transaction)
   transaction->priv = G_TYPE_INSTANCE_GET_PRIVATE (transaction,
                                                    POP_TYPE_TRANSACTION,
                                                    PopTransactionPrivate);
-  transaction->priv->actions = g_queue_new ();
+  transaction->priv->action_tree = pop_action_tree_new ();
 
   transaction->priv->status = POP_TRANSACTION_STATUS_NOT_FINISHED;
 }
@@ -323,8 +351,9 @@ pop_transaction_finalize (GObject *object)
 
   parent_class = G_OBJECT_CLASS (pop_transaction_parent_class);
 
-  g_queue_foreach (transaction->priv->actions, (GFunc) pop_action_free, NULL);
-  g_queue_free (transaction->priv->actions);
+  pop_action_tree_foreach (transaction->priv->action_tree, 
+                           (GFunc) pop_action_free, NULL);
+  pop_action_tree_free (transaction->priv->action_tree);
 
   pop_transaction_set_result (transaction, NULL, NULL);
 
@@ -402,6 +431,217 @@ pop_transaction_set_status (PopTransaction       *transaction,
     }
 }
 
+static PopActionTree *
+pop_action_tree_new (void)
+{
+  PopActionTree *action_tree;
+
+  action_tree = g_slice_new (PopActionTree);
+  action_tree->root = g_node_new (NULL);
+
+  pop_action_tree_reset (action_tree);
+
+  return action_tree;
+}
+
+static void
+pop_action_tree_reset (PopActionTree *action_tree)
+{
+  action_tree->current_action_node = NULL;
+}
+
+static gboolean 
+pop_action_tree_is_at_first_action (PopActionTree *action_tree)
+{
+  return action_tree->current_action_node == NULL;
+}
+
+static gboolean 
+pop_action_tree_is_empty (PopActionTree *action_tree)
+{
+  return g_node_n_children (action_tree->root) == 0;
+}
+
+static GNode *
+pop_action_tree_walk_one_step (PopActionTree              *action_tree,
+                               GNode                      *current_node,
+                               PopActionTreeWalkDirection  direction)
+{
+  GNode *node;
+
+  if (direction == POP_ACTION_TREE_WALK_DIRECTION_FORWARD)
+    {
+      /* go to the next sibling at the current level.  
+       * If there aren't anymore at the current level, 
+       * go to the parent.
+       */
+      node = g_node_next_sibling (current_node);
+
+      if (node == NULL)
+        {
+          node = current_node->parent;
+
+          /* if we ever hit the root, we're done
+          */
+          if (node == action_tree->root)
+            return NULL;
+        }
+    }
+  else 
+    {
+      /* go to the last child of the current node.
+       * if current node doesn't have any children,
+       * go to the next sibling in the direction
+       * we're walking (backward).
+       */
+
+      node = g_node_last_child (current_node);
+
+      if (node == NULL)
+        {
+          node = g_node_prev_sibling (current_node);
+
+          if (node == NULL)
+            return NULL;
+        }
+    }
+
+  return node;
+}
+
+static GNode *
+pop_action_tree_walk_to_leaf (PopActionTree              *action_tree,
+                              GNode                      *current_node,
+                              PopActionTreeWalkDirection  direction)
+{
+  GNode *node;
+
+  node = current_node;
+  while (node->children != NULL)
+    {
+      if (direction == POP_ACTION_TREE_WALK_DIRECTION_FORWARD)
+        {
+          node = g_node_first_child (node);
+        }
+      else 
+        {
+          node = g_node_last_child (node);
+        }
+    }
+
+  return node;
+}
+
+static gboolean
+pop_action_tree_seek (PopActionTree              *action_tree,
+                      PopActionTreeWalkDirection  direction)
+{
+  GNode *node;
+
+  g_assert ((direction == POP_ACTION_TREE_WALK_DIRECTION_FORWARD)
+            || (direction == POP_ACTION_TREE_WALK_DIRECTION_BACKWARD));
+
+  /* if current_action_node is NULL then we haven't started yet,
+   * so set node to a child of the root. Otherwise, walk node
+   * one step in the tree (to the next sibling, or the parent 
+   * if there are no more siblings)
+   */
+  if (action_tree->current_action_node == NULL)
+    {
+      node = action_tree->root;
+
+      if (node->children == NULL)
+        return FALSE;
+
+      if (direction == POP_ACTION_TREE_WALK_DIRECTION_BACKWARD)
+        node = g_node_last_child (node);
+    }
+  else
+    {
+      node = pop_action_tree_walk_one_step (action_tree, 
+                                            action_tree->current_action_node,
+                                            direction);
+
+      if (node == NULL)
+        return FALSE;
+    }
+
+  /* we walked one step in the direction we care about above.
+   * now from our new location walk the left outside path to 
+   * it's leaf.
+   *
+   * Note, if we're already at a leaf node, then this function is
+   * a no-op
+   */
+  if (direction == POP_ACTION_TREE_WALK_DIRECTION_FORWARD)
+    node = pop_action_tree_walk_to_leaf (action_tree, node, direction);
+
+  action_tree->current_action_node = node;
+
+  return TRUE;
+}
+
+static void 
+pop_action_tree_add_action (PopActionTree *action_tree,
+                            PopAction     *action)
+{
+  g_node_insert_data (action_tree->current_action_node, -1, action);
+}
+
+static PopAction *
+pop_action_tree_get_current_action (PopActionTree *tree)
+{
+  g_assert (tree->current_action_node != NULL);
+
+  return (PopAction *) tree->current_action_node->data;
+}
+
+typedef struct
+{
+  PopActionTree *action_tree;
+  GFunc callback;
+  gpointer user_data;
+} PopActionTreeForeachClosure;
+
+static gboolean
+pop_action_tree_on_each_node (GNode                       *node,
+                              PopActionTreeForeachClosure *closure)
+{
+  if (node == closure->action_tree->root)
+    return FALSE;
+
+  closure->callback (node->data, closure->user_data);
+
+  return FALSE;
+}
+
+static void 
+pop_action_tree_foreach (PopActionTree *action_tree,
+                         GFunc          func,
+                         gpointer       user_data)
+{
+  PopActionTreeForeachClosure closure;
+
+  closure.action_tree = action_tree;
+  closure.callback = func;
+  closure.user_data = user_data;
+
+  /* FIXME: think about just using the _step function and a
+   * loop, for consistency with the seek function, and so 
+   * we can drop the ugly ad-hoc closure.
+   */
+  g_node_traverse (action_tree->root, G_PRE_ORDER, G_TRAVERSE_ALL, -1,
+                   (GNodeTraverseFunc) pop_action_tree_on_each_node,
+                   &closure);
+}
+
+static void 
+pop_action_tree_free (PopActionTree *action_tree)
+{
+  g_node_destroy (action_tree->root);
+  g_slice_free (PopActionTree, action_tree);
+}
+
 static PopAction *
 pop_action_new (PopActionProcessFunc  action_process_func,
                 PopActionRollbackFunc action_rollback_func,
@@ -563,27 +803,17 @@ pop_transaction_rewind (PopTransaction *transaction)
 {
   g_assert (POP_IS_TRANSACTION (transaction));
 
-  if (pop_transaction_is_at_first_action (transaction))
-    {
-      return FALSE;
-    }
-
-  transaction->priv->current_action_node =
-    transaction->priv->current_action_node->prev;
-
-  return TRUE;
+  return pop_action_tree_seek (transaction->priv->action_tree,
+                               POP_ACTION_TREE_WALK_DIRECTION_BACKWARD);
 }
 
 static gboolean
 pop_transaction_seek_forward (PopTransaction *transaction)
 {
   g_assert (POP_IS_TRANSACTION (transaction));
-  g_assert (transaction->priv->current_action_node != NULL);
 
-  transaction->priv->current_action_node =
-    transaction->priv->current_action_node->next;
-
-  return transaction->priv->current_action_node != NULL;
+  return pop_action_tree_seek (transaction->priv->action_tree,
+                               POP_ACTION_TREE_WALK_DIRECTION_FORWARD);
 }
 
 static void
@@ -614,7 +844,6 @@ pop_transaction_process_action_and_seek_forward (PopTransaction *transaction)
   gboolean should_continue;
 
   g_assert (POP_IS_TRANSACTION (transaction));
-  g_assert (transaction->priv->current_action_node != NULL);
 
   if (transaction->priv->state == POP_TRANSACTION_STATE_COMMITED)
     {
@@ -624,7 +853,7 @@ pop_transaction_process_action_and_seek_forward (PopTransaction *transaction)
 
   g_assert (transaction->priv->state == POP_TRANSACTION_STATE_PROCESSING);
 
-  action = (PopAction *) transaction->priv->current_action_node->data;
+  action = pop_action_tree_get_current_action (transaction->priv->action_tree);
 
   if (action->process_status != POP_ACTION_PROCESS_STATUS_NOT_FINISHED)
     return FALSE;
@@ -686,8 +915,8 @@ pop_transaction_process_on_idle (PopTransaction *transaction)
 {
   g_assert (POP_IS_TRANSACTION (transaction));
 
-  transaction->priv->current_action_node =
-    g_queue_peek_head_link (transaction->priv->actions);
+  pop_action_tree_reset (transaction->priv->action_tree);
+  pop_transaction_seek_forward (transaction);
 
   transaction->priv->process_idle_id =
     pop_transaction_call_on_idle (transaction,
@@ -701,7 +930,6 @@ pop_transaction_rollback_action_and_rewind (PopTransaction *transaction)
   gboolean should_continue;
 
   g_assert (POP_IS_TRANSACTION (transaction));
-  g_assert (transaction->priv->current_action_node != NULL);
 
   if (transaction->priv->state == POP_TRANSACTION_STATE_PROCESSING)
     {
@@ -710,7 +938,7 @@ pop_transaction_rollback_action_and_rewind (PopTransaction *transaction)
 
   g_assert (transaction->priv->state == POP_TRANSACTION_STATE_ROLLING_BACK);
 
-  action = (PopAction *) transaction->priv->current_action_node->data;
+  action = pop_action_tree_get_current_action (transaction->priv->action_tree);
 
   if (action->rollback_status != POP_ACTION_ROLLBACK_STATUS_NOT_FINISHED)
     return FALSE;
@@ -735,7 +963,7 @@ pop_transaction_rollback_action_and_rewind (PopTransaction *transaction)
       default:
         g_warning ("status %d is not valid rollback status\n", (int) action->rollback_status);
 
-        /* Fall through and finish the action because it's not behaving
+        /* fall through and finish the action because it's not behaving
          */
 
       case POP_ACTION_ROLLBACK_STATUS_FINISHED:
@@ -762,8 +990,7 @@ pop_transaction_rollback_on_idle (PopTransaction *transaction)
 {
   g_assert (POP_IS_TRANSACTION (transaction));
 
-  transaction->priv->current_action_node = transaction->priv->
-                                           current_action_node->prev;
+  pop_transaction_rewind (transaction);
 
   transaction->priv->rollback_idle_id =
     pop_transaction_call_on_idle (transaction,
@@ -801,14 +1028,8 @@ pop_transaction_is_running_action (PopTransaction *transaction)
 static gboolean
 pop_transaction_is_at_first_action (PopTransaction *transaction)
 {
-  GList *first_action_node;
-
   g_assert (POP_IS_TRANSACTION (transaction));
-  g_assert (transaction->priv->current_action_node != NULL);
-
-  first_action_node = g_queue_peek_head_link (transaction->priv->actions);
-
-  return first_action_node == transaction->priv->current_action_node;
+  return pop_action_tree_is_at_first_action (transaction->priv->action_tree);
 }
 
 static gboolean
@@ -824,7 +1045,7 @@ pop_transaction_is_empty (PopTransaction *transaction)
 {
   g_assert (POP_IS_TRANSACTION (transaction));
 
-  return g_queue_is_empty (transaction->priv->actions);
+  return pop_action_tree_is_empty (transaction->priv->action_tree);
 }
 
 static gboolean
@@ -874,21 +1095,7 @@ pop_transaction_add_action_full (PopTransaction       *transaction,
   action = pop_action_new (action_process_func, action_rollback_func, user_data,
                            free_func);
 
-  if (transaction->priv->current_action_node == NULL)
-    {
-      g_queue_push_tail (transaction->priv->actions, action);
-    }
-  else
-    {
-      gboolean can_rewind;
-
-      g_queue_insert_before (transaction->priv->actions,
-                             transaction->priv->current_action_node,
-                             action);
-      can_rewind = pop_transaction_rewind (transaction);
-
-      g_assert (can_rewind);
-    }
+  pop_action_tree_add_action (transaction->priv->action_tree, action);
 }
 
 void