From ac9f5e88cae754434b0edcb8995f0e6b6557695a Mon Sep 17 00:00:00 2001
From: Michael Schroeder <mls@suse.de>
Date: Tue, 16 Jun 2009 18:51:17 +0200
Subject: [PATCH] - add queue_insertn, queue_deleten, queue_truncate

---
 src/queue.c       | 37 +++++++++++++++++++++++++++++++++++++
 src/queue.h       | 30 +++++++++++++++++-------------
 src/transaction.c | 10 +++++-----
 3 files changed, 59 insertions(+), 18 deletions(-)

diff --git a/src/queue.c b/src/queue.c
index 2f9f75a..fa10339 100644
--- a/src/queue.c
+++ b/src/queue.c
@@ -143,3 +143,40 @@ queue_delete2(Queue *q, int pos)
   q->left += 2;
   q->count -= 2;
 }
+
+void
+queue_insertn(Queue *q, int pos, int n)
+{
+  if (n <= 0)
+    return;
+  if (pos > q->count)
+    pos = q->count;
+  if (q->left < n)
+    {
+      int off;
+      if (!q->alloc)
+	queue_alloc_one(q);
+      off = q->elements - q->alloc;
+      q->alloc = sat_realloc2(q->alloc, off + q->count + n + 8, sizeof(Id));
+      q->elements = q->alloc + off;
+      q->left = n + 8;
+    }
+  if (pos < q->count)
+    memmove(q->elements + pos + n, q->elements + pos, (q->count - pos) * sizeof(Id));
+  memset(q->elements + pos, 0, n * sizeof(Id));
+  q->left -= n;
+  q->count += n;
+}
+
+void
+queue_deleten(Queue *q, int pos, int n)
+{
+  if (n <= 0 || pos >= q->count)
+    return;
+  if (pos + n >= q->count)
+    n = q->count - pos;
+  else
+    memmove(q->elements + pos, q->elements + pos + n, (q->count - n - pos) * sizeof(Id));
+  q->left += n;
+  q->count -= n;
+}
diff --git a/src/queue.h b/src/queue.h
index 090799e..01e6a50 100644
--- a/src/queue.h
+++ b/src/queue.h
@@ -23,7 +23,8 @@ typedef struct _Queue {
 } Queue;
 
 
-extern void queue_alloc_one(Queue *q);
+extern void queue_alloc_one(Queue *q);		/* internal */
+extern void queue_alloc_one_head(Queue *q);	/* internal */
 
 /* clear queue */
 static inline void
@@ -60,19 +61,10 @@ queue_pop(Queue *q)
 static inline void
 queue_unshift(Queue *q, Id id)
 {
-  if (q->alloc && q->alloc != q->elements)
-    {
-      *--q->elements = id;
-      q->count++;
-      return;
-    }
-  if (!q->left)
-    queue_alloc_one(q);
-  if (q->count)
-    memmove(q->elements + 1, q->elements, sizeof(Id) * q->count);
+  if (!q->alloc || q->alloc == q->elements)
+    queue_alloc_one_head(q);
+  *--q->elements = id;
   q->count++;
-  q->elements[0] = id;
-  q->left--;
 }
 
 static inline void
@@ -101,6 +93,16 @@ queue_push2(Queue *q, Id id1, Id id2)
   queue_push(q, id2);
 }
 
+static inline void
+queue_truncate(Queue *q, int n)
+{
+  if (q->count > n)
+    {
+      q->left += q->count - n;
+      q->count = n;
+    }
+}
+
 extern void queue_init(Queue *q);
 extern void queue_init_buffer(Queue *q, Id *buf, int size);
 extern void queue_init_clone(Queue *t, Queue *s);
@@ -108,7 +110,9 @@ extern void queue_free(Queue *q);
 
 extern void queue_insert(Queue *q, int pos, Id id);
 extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
+extern void queue_insertn(Queue *q, int pos, int n);
 extern void queue_delete(Queue *q, int pos);
 extern void queue_delete2(Queue *q, int pos);
+extern void queue_deleten(Queue *q, int pos, int n);
 
 #endif /* SATSOLVER_QUEUE_H */
diff --git a/src/transaction.c b/src/transaction.c
index 2706111..a591258 100644
--- a/src/transaction.c
+++ b/src/transaction.c
@@ -1777,9 +1777,8 @@ transaction_add_obsoleted(Transaction *trans)
   /* make room */
   steps = &trans->steps;
   oldcount = steps->count;
-  for (i = 0; i < max; i++)
-    queue_push(steps, 0);
-  memmove(steps->elements + max, steps->elements, oldcount * sizeof(Id));
+  queue_insertn(steps, 0, max);
+
   /* now add em */
   map_init(&done, installed->end - installed->start);
   queue_init(&obsq);
@@ -1805,10 +1804,11 @@ transaction_add_obsoleted(Transaction *trans)
 	  trans->steps.elements[j++] = p;
 	}
     }
+
+  /* free unneeded space */
+  queue_truncate(steps, j);
   map_free(&done);
   queue_free(&obsq);
-  while (steps->count > j)
-    queue_pop(steps);
 }
 
 static void
-- 
2.7.4