Imported Upstream version 0.7.12

[platform/upstream/libsolv.git] / src / queue.c

diff --git a/src/queue.c b/src/queue.c
index 38fd765..6d5e531 100644 (file)
--- a/src/queue.c
+++ b/src/queue.c
@@ -16,14 +16,16 @@
 #include "queue.h"
 #include "util.h"
 
-void
-queue_init_clone(Queue *t, Queue *s)
+static inline int
+queue_extra_space(int size)
 {
-  t->alloc = t->elements = sat_malloc2(s->count + 8, sizeof(Id));
-  if (s->count)
-    memcpy(t->alloc, s->elements, s->count * sizeof(Id));
-  t->count = s->count;
-  t->left = 8;
+  if (size < 32)
+    return 8;
+  if (size < 64)
+    return 16;
+  if (size < 128)
+    return 32;
+  return 64;
 }
 
 void
@@ -34,6 +36,24 @@ queue_init(Queue *q)
 }
 
 void
+queue_init_clone(Queue *target, const Queue *source)
+{
+  int extra_space;
+  if (!source->elements)
+    {
+      target->alloc = target->elements = 0;
+      target->count = target->left = 0;
+      return;
+    }
+  extra_space = queue_extra_space(source->count);
+  target->alloc = target->elements = solv_malloc2(source->count + extra_space, sizeof(Id));
+  if (source->count)
+    memcpy(target->alloc, source->elements, source->count * sizeof(Id));
+  target->count = source->count;
+  target->left = extra_space;
+}
+
+void
 queue_init_buffer(Queue *q, Id *buf, int size)
 {
   q->alloc = 0;
@@ -46,35 +66,55 @@ void
 queue_free(Queue *q)
 {
   if (q->alloc)
-    sat_free(q->alloc);
+    solv_free(q->alloc);
   q->alloc = q->elements = 0;
   q->count = q->left = 0;
 }
 
+/* make room for one element at the tail of the queue */
 void
 queue_alloc_one(Queue *q)
 {
   if (q->alloc && q->alloc != q->elements)
     {
-      memmove(q->alloc, q->elements, q->count * sizeof(Id));
-      q->left += q->elements - q->alloc;
-      q->elements = q->alloc;
-    }
-  else if (q->alloc)
-    {
-      q->elements = q->alloc = sat_realloc2(q->alloc, q->count + 8, sizeof(Id));
-      q->left += 8;
+      /* there's room at the front. just move data */
+      int l = q->elements - q->alloc;
+      if (q->count)
+        memmove(q->alloc, q->elements, q->count * sizeof(Id));
+      q->elements -= l;
+      q->left += l;
     }
   else
     {
-      q->alloc = sat_malloc2(q->count + 8, sizeof(Id));
-      if (q->count)
-       memcpy(q->alloc, q->elements, q->count * sizeof(Id));
+      int extra_space = queue_extra_space(q->count);
+      if (!q->alloc)
+       {
+         q->alloc = solv_malloc2(q->count + extra_space, sizeof(Id));
+         if (q->count)
+           memcpy(q->alloc, q->elements, q->count * sizeof(Id));
+       }
+      else
+       q->alloc = solv_realloc2(q->alloc, q->count + extra_space, sizeof(Id));
       q->elements = q->alloc;
-      q->left += 8;
+      q->left = extra_space;
     }
 }
 
+/* make room for an element in front of queue */
+void
+queue_alloc_one_head(Queue *q)
+{
+  int l, extra_space;
+  if (!q->alloc || !q->left)
+    queue_alloc_one(q);                /* easy way to make room */
+  extra_space = queue_extra_space(q->count);
+  l = q->left > extra_space ? extra_space : q->left;
+  if (q->count)
+    memmove(q->elements + l, q->elements, q->count * sizeof(Id));
+  q->elements += l;
+  q->left -= l;
+}
+
 void
 queue_insert(Queue *q, int pos, Id id)
 {
@@ -106,7 +146,7 @@ queue_insert2(Queue *q, int pos, Id id1, Id id2)
     {
       memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
       q->elements[pos] = id1;
-      q->elements[pos] = id2;
+      q->elements[pos + 1] = id2;
     }
 }
 
@@ -126,3 +166,52 @@ queue_delete2(Queue *q, int pos)
   q->left += 2;
   q->count -= 2;
 }
+
+void
+queue_insertn(Queue *q, int pos, int n, const Id *elements)
+{
+  if (n <= 0)
+    return;
+  if (pos > q->count)
+    pos = q->count;
+  if (q->left < n)
+    queue_prealloc(q, n);
+  if (pos < q->count)
+    memmove(q->elements + pos + n, q->elements + pos, (q->count - pos) * sizeof(Id));
+  if (elements)
+    memcpy(q->elements + pos, elements, n * sizeof(Id));
+  else
+    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;
+}
+
+/* pre-allocate room for n more elements */
+void
+queue_prealloc(Queue *q, int n)
+{
+  int off, extra_space;
+  if (n <= 0 || q->left >= n)
+    return;
+  if (!q->alloc)
+    queue_alloc_one(q);
+  off = q->elements - q->alloc;
+  extra_space = queue_extra_space(q->count + n);
+  q->alloc = solv_realloc2(q->alloc, off + q->count + n + extra_space, sizeof(Id));
+  q->elements = q->alloc + off;
+  q->left = n + extra_space;
+}
+