#include "queue.h"
#include "util.h"
-#define EXTRA_SPACE 8
-#define EXTRA_SPACE_HEAD 8
+static inline int
+queue_extra_space(int size)
+{
+ if (size < 32)
+ return 8;
+ if (size < 64)
+ return 16;
+ if (size < 128)
+ return 32;
+ return 64;
+}
void
queue_init(Queue *q)
}
void
-queue_init_clone(Queue *t, Queue *s)
+queue_init_clone(Queue *target, const Queue *source)
{
- if (!s->elements)
+ int extra_space;
+ if (!source->elements)
{
- t->alloc = t->elements = 0;
- t->count = t->left = 0;
+ target->alloc = target->elements = 0;
+ target->count = target->left = 0;
return;
}
- t->alloc = t->elements = solv_malloc2(s->count + EXTRA_SPACE, sizeof(Id));
- if (s->count)
- memcpy(t->alloc, s->elements, s->count * sizeof(Id));
- t->count = s->count;
- t->left = EXTRA_SPACE;
+ 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
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 = 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 = EXTRA_SPACE;
- }
- else if (q->alloc != q->elements)
+ if (q->alloc && q->alloc != q->elements)
{
+ /* 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));
}
else
{
- q->elements = q->alloc = solv_realloc2(q->alloc, q->count + EXTRA_SPACE, sizeof(Id));
- q->left = EXTRA_SPACE;
+ 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 = extra_space;
}
}
void
queue_alloc_one_head(Queue *q)
{
- int l;
+ int l, extra_space;
if (!q->alloc || !q->left)
- queue_alloc_one(q);
- l = q->left > EXTRA_SPACE_HEAD ? EXTRA_SPACE_HEAD : 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;
}
void
-queue_insertn(Queue *q, int pos, int n)
+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)
- {
- int off;
- if (!q->alloc)
- queue_alloc_one(q);
- off = q->elements - q->alloc;
- q->alloc = solv_realloc2(q->alloc, off + q->count + n + EXTRA_SPACE, sizeof(Id));
- q->elements = q->alloc + off;
- q->left = n + EXTRA_SPACE;
- }
+ queue_prealloc(q, n);
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));
+ 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;
}
q->count -= n;
}
-/* allocate room for n more elements */
+/* pre-allocate room for n more elements */
void
queue_prealloc(Queue *q, int n)
{
- int off;
+ int off, extra_space;
if (n <= 0 || q->left >= n)
return;
if (!q->alloc)
queue_alloc_one(q);
off = q->elements - q->alloc;
- q->alloc = solv_realloc2(q->alloc, off + q->count + n + EXTRA_SPACE, sizeof(Id));
+ 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;
+ q->left = n + extra_space;
}