Mailinglist Archive: zypp-commit (171 mails)

< Previous Next >
[zypp-commit] <sat-solver> master : - add queue_insertn, queue_deleten, queue_truncate
  • From: Michael Schroeder <mls@xxxxxxx>
  • Date: Tue, 16 Jun 2009 18:52:01 +0200
  • Message-id: <E1MGbtS-000456-UU@xxxxxxxxxxxxxxxx>
ref: refs/heads/master
commit 94fa0f67e5225a4104555bfe34db238114356287
Author: Michael Schroeder <mls@xxxxxxx>
Date: Tue Jun 16 18:51:17 2009 +0200

- 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
--
To unsubscribe, e-mail: zypp-commit+unsubscribe@xxxxxxxxxxxx
For additional commands, e-mail: zypp-commit+help@xxxxxxxxxxxx

< Previous Next >
This Thread
  • No further messages