/*
+ * Copyright (c) 2007, Novell Inc.
+ *
+ * This program is licensed under the BSD license, read LICENSE.BSD
+ * for further information
+ */
+
+/*
* queue.c
*
*/
#include <string.h>
#include "queue.h"
+#include "util.h"
-void
-clonequeue(Queue *t, Queue *s)
+static inline int
+queue_extra_space(int size)
{
- t->alloc = t->elements = malloc((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
-queueinit(Queue *q)
+queue_init(Queue *q)
{
q->alloc = q->elements = 0;
q->count = q->left = 0;
}
void
-queueinit_buffer(Queue *q, Id *buf, int size)
+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;
q->elements = buf;
}
void
-queuefree(Queue *q)
+queue_free(Queue *q)
{
if (q->alloc)
- free(q->alloc);
+ solv_free(q->alloc);
q->alloc = q->elements = 0;
q->count = q->left = 0;
}
-Id
-queueshift(Queue *q)
-{
- if (!q->count)
- return 0;
- q->count--;
- return *q->elements++;
-}
-
+/* make room for one element at the tail of the queue */
void
-queuepush(Queue *q, Id id)
+queue_alloc_one(Queue *q)
{
- if (!q->left)
+ if (q->alloc && q->alloc != q->elements)
{
- 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 = realloc(q->alloc, (q->count + 8) * sizeof(Id));
- q->left += 8;
- }
- else
+ /* 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
+ {
+ int extra_space = queue_extra_space(q->count);
+ if (!q->alloc)
{
- q->alloc = malloc((q->count + 8) * sizeof(Id));
+ q->alloc = solv_malloc2(q->count + extra_space, sizeof(Id));
if (q->count)
memcpy(q->alloc, q->elements, q->count * sizeof(Id));
- q->elements = q->alloc;
- q->left += 8;
}
+ else
+ q->alloc = solv_realloc2(q->alloc, q->count + extra_space, sizeof(Id));
+ q->elements = q->alloc;
+ 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)
+{
+ queue_push(q, id); /* make room */
+ if (pos < q->count - 1)
+ {
+ memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
+ q->elements[pos] = id;
}
- q->elements[q->count++] = id;
- q->left--;
}
void
-queuepushunique(Queue *q, Id id)
+queue_delete(Queue *q, int pos)
{
- int i;
- for (i = q->count; i > 0; )
- if (q->elements[--i] == id)
+ if (pos >= q->count)
+ return;
+ if (pos < q->count - 1)
+ memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
+ q->left++;
+ q->count--;
+}
+
+void
+queue_insert2(Queue *q, int pos, Id id1, Id id2)
+{
+ queue_push(q, id1); /* make room */
+ queue_push(q, id2); /* make room */
+ if (pos < q->count - 2)
+ {
+ memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
+ q->elements[pos] = id1;
+ q->elements[pos + 1] = id2;
+ }
+}
+
+void
+queue_delete2(Queue *q, int pos)
+{
+ if (pos >= q->count)
+ return;
+ if (pos == q->count - 1)
+ {
+ q->left++;
+ q->count--;
return;
- queuepush(q, id);
+ }
+ if (pos < q->count - 2)
+ memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
+ 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;
+}
projects / platform / upstream / libsolv.git / blobdiff