[tracker] TrackerPriorityQueue: Add node-based API

[Xavier Claessens <xclaesse src gnome org>]

commit e3d4fdfe05b828f72af94ec0e658ec6e86418a6d
Author: Xavier Claessens <xavier claessens collabora co uk>
Date:   Thu Feb 6 15:34:25 2014 -0500

    TrackerPriorityQueue: Add node-based API
    
    This exposes the fact that it is implemented using a GList, but
    makes possible to remove a node without iterating the whole queue.
    Those new API will be used in upcoming commits.

 src/libtracker-miner/tracker-priority-queue.c |  128 +++++++++++++++++++++----
 src/libtracker-miner/tracker-priority-queue.h |   12 ++-
 2 files changed, 119 insertions(+), 21 deletions(-)
---
diff --git a/src/libtracker-miner/tracker-priority-queue.c b/src/libtracker-miner/tracker-priority-queue.c
index c360219..42c3d3e 100644
--- a/src/libtracker-miner/tracker-priority-queue.c
+++ b/src/libtracker-miner/tracker-priority-queue.c
@@ -72,14 +72,41 @@ tracker_priority_queue_unref (TrackerPriorityQueue *queue)
        }
 }
 
-static GList *
-priority_segment_alloc_node (TrackerPriorityQueue *queue,
-                             gint                  priority)
+static void
+queue_insert_before_link (GQueue *queue,
+                          GList  *sibling,
+                          GList  *link_)
+{
+       if (sibling == queue->head)
+               g_queue_push_head_link (queue, link_);
+       else {
+               link_->next = sibling;
+               link_->prev = sibling->prev;
+               sibling->prev->next = link_;
+               sibling->prev = link_;
+               queue->length++;
+       }
+}
+
+static void
+queue_insert_after_link (GQueue *queue,
+                         GList  *sibling,
+                         GList  *link_)
+{
+       if (sibling == queue->tail)
+               g_queue_push_tail_link (queue, link_);
+       else
+               queue_insert_before_link (queue, sibling->next, link_);
+}
+
+static void
+insert_node (TrackerPriorityQueue *queue,
+             gint                  priority,
+             GList                *node)
 {
        PrioritySegment *segment = NULL;
        gboolean found = FALSE;
        gint l, r, c;
-       GList *node;
 
        /* Perform binary search to find out the segment for
         * the given priority, create one if it isn't found.
@@ -110,8 +137,8 @@ priority_segment_alloc_node (TrackerPriorityQueue *queue,
                g_assert (segment != NULL);
                g_assert (segment->priority == priority);
 
-               g_queue_insert_after (&queue->queue, segment->last_elem, NULL);
-               node = segment->last_elem = segment->last_elem->next;
+               queue_insert_after_link (&queue->queue, segment->last_elem, node);
+               segment->last_elem = node;
        } else {
                PrioritySegment new_segment = { 0 };
 
@@ -127,12 +154,10 @@ priority_segment_alloc_node (TrackerPriorityQueue *queue,
                         */
                        if (segment->priority > priority) {
                                /* We have to insert to the left of this element */
-                               g_queue_insert_before (&queue->queue, segment->first_elem, NULL);
-                               node = segment->first_elem->prev;
+                               queue_insert_before_link (&queue->queue, segment->first_elem, node);
                        } else {
                                /* We have to insert to the right of this element */
-                               g_queue_insert_after (&queue->queue, segment->last_elem, NULL);
-                               node = segment->last_elem->next;
+                               queue_insert_after_link (&queue->queue, segment->last_elem, node);
                                c++;
                        }
 
@@ -143,15 +168,12 @@ priority_segment_alloc_node (TrackerPriorityQueue *queue,
                        g_assert (queue->segments->len == 0);
                        g_assert (g_queue_get_length (&queue->queue) == 0);
 
-                       node = g_list_alloc ();
                        g_queue_push_head_link (&queue->queue, node);
                        new_segment.first_elem = new_segment.last_elem = node;
 
                        g_array_append_val (queue->segments, new_segment);
                }
        }
-
-       return node;
 }
 
 void
@@ -253,20 +275,63 @@ tracker_priority_queue_get_length (TrackerPriorityQueue *queue)
        return g_queue_get_length (&queue->queue);
 }
 
-void
+GList *
 tracker_priority_queue_add (TrackerPriorityQueue *queue,
                             gpointer              data,
                             gint                  priority)
 {
        GList *node;
 
+       g_return_val_if_fail (queue != NULL, NULL);
+       g_return_val_if_fail (data != NULL, NULL);
+
+       node = g_list_alloc ();
+       node->data = data;
+       insert_node (queue, priority, node);
+
+       return node;
+}
+
+void
+tracker_priority_queue_add_node (TrackerPriorityQueue *queue,
+                                 GList                *node,
+                                 gint                  priority)
+{
        g_return_if_fail (queue != NULL);
-       g_return_if_fail (data != NULL);
+       g_return_if_fail (node != NULL);
 
-       node = priority_segment_alloc_node (queue, priority);
-       g_assert (node != NULL);
+       insert_node (queue, priority, node);
+}
 
-       node->data = data;
+void
+tracker_priority_queue_remove_node (TrackerPriorityQueue *queue,
+                                    GList                *node)
+{
+       guint i;
+
+       g_return_if_fail (queue != NULL);
+
+       /* Check if it is the first or last of a segment */
+       for (i = 0; i < queue->segments->len; i++) {
+               PrioritySegment *segment;
+
+               segment = &g_array_index (queue->segments, PrioritySegment, i);
+
+               if (segment->first_elem == node) {
+                       if (segment->last_elem == node)
+                               g_array_remove_index (queue->segments, i);
+                       else
+                               segment->first_elem = node->next;
+                       break;
+               }
+
+               if (segment->last_elem == node) {
+                       segment->last_elem = node->prev;
+                       break;
+               }
+       }
+
+       g_queue_delete_link (&queue->queue, node);
 }
 
 gpointer
@@ -330,6 +395,23 @@ gpointer
 tracker_priority_queue_pop (TrackerPriorityQueue *queue,
                             gint                 *priority_out)
 {
+       GList *node;
+       gpointer data;
+
+       node = tracker_priority_queue_pop_node (queue, priority_out);
+       if (node == NULL)
+               return NULL;
+
+       data = node->data;
+       g_list_free_1 (node);
+
+       return data;
+}
+
+GList *
+tracker_priority_queue_pop_node (TrackerPriorityQueue *queue,
+                                 gint                 *priority_out)
+{
        PrioritySegment *segment;
        GList *node;
 
@@ -360,5 +442,13 @@ tracker_priority_queue_pop (TrackerPriorityQueue *queue,
                segment->first_elem = segment->first_elem->next;
        }
 
-       return g_queue_pop_head (&queue->queue);
+       return g_queue_pop_head_link (&queue->queue);
+}
+
+GList *
+tracker_priority_queue_get_head (TrackerPriorityQueue *queue)
+{
+       g_return_val_if_fail (queue != NULL, NULL);
+
+       return queue->queue.head;
 }
diff --git a/src/libtracker-miner/tracker-priority-queue.h b/src/libtracker-miner/tracker-priority-queue.h
index ee2e79a..0dbc9b8 100644
--- a/src/libtracker-miner/tracker-priority-queue.h
+++ b/src/libtracker-miner/tracker-priority-queue.h
@@ -37,10 +37,9 @@ gboolean tracker_priority_queue_is_empty           (TrackerPriorityQueue *queue)
 
 guint    tracker_priority_queue_get_length         (TrackerPriorityQueue *queue);
 
-void     tracker_priority_queue_add     (TrackerPriorityQueue *queue,
+GList *  tracker_priority_queue_add     (TrackerPriorityQueue *queue,
                                          gpointer              data,
                                          gint                  priority);
-
 void     tracker_priority_queue_foreach (TrackerPriorityQueue *queue,
                                          GFunc                 func,
                                          gpointer              user_data);
@@ -60,6 +59,15 @@ gpointer tracker_priority_queue_peek    (TrackerPriorityQueue *queue,
 gpointer tracker_priority_queue_pop     (TrackerPriorityQueue *queue,
                                          gint                 *priority_out);
 
+GList *  tracker_priority_queue_get_head    (TrackerPriorityQueue *queue);
+void     tracker_priority_queue_add_node    (TrackerPriorityQueue *queue,
+                                             GList                *node,
+                                             gint                  priority);
+void     tracker_priority_queue_remove_node (TrackerPriorityQueue  *queue,
+                                             GList                 *node);
+GList *  tracker_priority_queue_pop_node    (TrackerPriorityQueue *queue,
+                                             gint                 *priority_out);
+
 
 G_END_DECLS