From b106325c782bef79e10c3f8997b7e3557c726ab9 Mon Sep 17 00:00:00 2001
From: Florian Forster <octo@leeloo.home.verplant.org>
Date: Tue, 24 Jun 2008 13:54:38 +0200
Subject: [PATCH] src/rrd_daemon.c: Updated the enqueueing function to provide
 insertion at the head.

---
 src/rrd_daemon.c | 73 +++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 59 insertions(+), 14 deletions(-)

diff --git a/src/rrd_daemon.c b/src/rrd_daemon.c
index d738c73..7423088 100644
--- a/src/rrd_daemon.c
+++ b/src/rrd_daemon.c
@@ -116,6 +116,13 @@ struct cache_item_s
   cache_item_t *next;
 };
 
+enum queue_side_e
+{
+  HEAD,
+  TAIL
+};
+typedef enum queue_side_e queue_side_t;
+
 /*
  * Variables
  */
@@ -160,7 +167,8 @@ static void sig_term_handler (int s __attribute__((unused))) /* {{{ */
  * enqueue_cache_item:
  * `cache_lock' must be acquired before calling this function!
  */
-static int enqueue_cache_item (cache_item_t *ci) /* {{{ */
+static int enqueue_cache_item (cache_item_t *ci, /* {{{ */
+    queue_side_t side)
 {
   RRDD_LOG (LOG_DEBUG, "enqueue_cache_item: Adding %s to the update queue.",
       ci->file);
@@ -168,21 +176,58 @@ static int enqueue_cache_item (cache_item_t *ci) /* {{{ */
   if (ci == NULL)
     return (-1);
 
-  if ((ci->flags & CI_FLAGS_IN_QUEUE) != 0)
-    return (-1);
-
-  assert (ci->next == NULL);
-
   if (ci->values_num == 0)
     return (0);
 
-  if (cache_queue_tail == NULL)
-    cache_queue_head = ci;
-  else
-    cache_queue_tail->next = ci;
-  cache_queue_tail = ci;
+  if (side == HEAD)
+  {
+    if ((ci->flags & CI_FLAGS_IN_QUEUE) == 0)
+    {
+      assert (ci->next == NULL);
+      ci->next = cache_queue_head;
+      cache_queue_head = ci;
 
-  ci->flags |= CI_FLAGS_IN_QUEUE;
+      if (cache_queue_tail == NULL)
+        cache_queue_tail = cache_queue_head;
+    }
+    else if (cache_queue_head == ci)
+    {
+      /* do nothing */
+    }
+    else /* enqueued, but not first entry */
+    {
+      cache_item_t *prev;
+
+      /* find previous entry */
+      for (prev = cache_queue_head; prev != NULL; prev = prev->next)
+        if (prev->next == ci)
+          break;
+      assert (prev != NULL);
+
+      /* move to the front */
+      prev->next = ci->next;
+      ci->next = cache_queue_head;
+      cache_queue_head = ci;
+
+      /* check if we need to adapt the tail */
+      if (cache_queue_tail == ci)
+        cache_queue_tail = prev;
+    }
+  }
+  else /* (side == TAIL) */
+  {
+    /* We don't move values back in the list.. */
+    if ((ci->flags & CI_FLAGS_IN_QUEUE) != 0)
+      return (0);
+
+    assert (ci->next == NULL);
+
+    if (cache_queue_tail == NULL)
+      cache_queue_head = ci;
+    else
+      cache_queue_tail->next = ci;
+    cache_queue_tail = ci;
+  }
 
   ci->flags |= CI_FLAGS_IN_QUEUE;
 
@@ -208,7 +253,7 @@ static gboolean tree_callback_flush (gpointer key /* {{{ */
   if (((now - ci->last_flush_time) >= config_write_interval)
       && ((ci->flags & CI_FLAGS_IN_QUEUE) == 0)
       && (ci->values_num > 0))
-    enqueue_cache_item (ci);
+    enqueue_cache_item (ci, TAIL);
 
   return (TRUE);
 } /* }}} gboolean tree_callback_flush */
@@ -470,7 +515,7 @@ static int handle_request_update (int fd, /* {{{ */
       && ((ci->flags & CI_FLAGS_IN_QUEUE) == 0)
       && (ci->values_num > 0))
   {
-    enqueue_cache_item (ci);
+    enqueue_cache_item (ci, TAIL);
     pthread_cond_signal (&cache_cond);
   }
 
-- 
2.11.0