summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorXavier Claessens <xavier.claessens@collabora.co.uk>2014-02-06 20:34:25 (GMT)
committerXavier Claessens <xavier.claessens@collabora.com>2014-02-20 02:33:32 (GMT)
commite3d4fdfe05b828f72af94ec0e658ec6e86418a6d (patch)
tree3a5b293cf11476f29f5792e00196409995e6fd13
parent25fb3e2867a8ef7be6da64b5c815613cc0c49588 (diff)
downloadtracker-e3d4fdfe05b828f72af94ec0e658ec6e86418a6d.tar.gz
tracker-e3d4fdfe05b828f72af94ec0e658ec6e86418a6d.tar.xz
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.
-rw-r--r--src/libtracker-miner/tracker-priority-queue.c128
-rw-r--r--src/libtracker-miner/tracker-priority-queue.h12
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