summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2016-02-19 23:58:22 -0500
committerTavian Barnes <tavianator@tavianator.com>2016-02-19 23:58:22 -0500
commit806e8504a374c7cf546a1ce0a81ed2ba954c3096 (patch)
tree55c25b6345f248bcf75e608e64dfc9e4d2d05306
parent8ac7f4f334668a9ad966f36bcf125e1b7652af80 (diff)
downloadbfs-806e8504a374c7cf546a1ce0a81ed2ba954c3096.tar.xz
bftw: Clean up dirqueue implementation a bit.
-rw-r--r--bftw.c48
1 files changed, 28 insertions, 20 deletions
diff --git a/bftw.c b/bftw.c
index eb745fe..22dfe41 100644
--- a/bftw.c
+++ b/bftw.c
@@ -411,7 +411,24 @@ static void dirqueue_init(struct dirqueue *queue) {
/** Add an entry to the dirqueue. */
static int dirqueue_push(struct dirqueue *queue, struct dircache_entry *entry) {
- if (queue->front == queue->back) {
+ if (!queue->entries) {
+ size_t size = 256;
+
+ queue->entries = malloc(size*sizeof(struct dircache_entry *));
+ if (!queue->entries) {
+ return -1;
+ }
+
+ queue->mask = size - 1;
+ }
+
+ size_t back = queue->back;
+
+ queue->entries[back] = entry;
+ back += 1;
+ back &= queue->mask;
+
+ if (back == queue->front) {
size_t old_size = queue->mask + 1;
struct dircache_entry **old_entries = queue->entries;
@@ -421,30 +438,26 @@ static int dirqueue_push(struct dirqueue *queue, struct dircache_entry *entry) {
return -1;
}
- if (old_entries) {
- size_t tail = queue->front;
- size_t head = old_size - tail;
- memcpy(new_entries, old_entries + queue->front, head*sizeof(struct dircache_entry *));
- memcpy(new_entries + head, old_entries, tail*sizeof(struct dircache_entry *));
- free(old_entries);
-
- queue->front = 0;
- queue->back = old_size;
- }
+ size_t mid = old_size - back;
+ memcpy(new_entries, old_entries + back, mid*sizeof(struct dircache_entry *));
+ memcpy(new_entries + mid, old_entries, back*sizeof(struct dircache_entry *));
+ free(old_entries);
queue->entries = new_entries;
queue->mask = new_size - 1;
+ queue->front = 0;
+ queue->back = old_size;
+ } else {
+ queue->back = back;
}
- queue->entries[queue->back] = entry;
- queue->back += 1;
- queue->back &= queue->mask;
return 0;
}
/** Remove an entry from the dirqueue. */
static struct dircache_entry *dirqueue_pop(struct dirqueue *queue) {
- if (!queue->entries) {
+ if (queue->front == queue->back) {
+ free(queue->entries);
return NULL;
}
@@ -452,11 +465,6 @@ static struct dircache_entry *dirqueue_pop(struct dirqueue *queue) {
queue->front += 1;
queue->front &= queue->mask;
- if (queue->front == queue->back) {
- free(queue->entries);
- queue->entries = NULL;
- }
-
return entry;
}