summaryrefslogtreecommitdiffstats
path: root/bftw.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2016-02-17 20:34:45 -0500
committerTavian Barnes <tavianator@tavianator.com>2016-02-17 20:34:45 -0500
commit21dcf8c0d75bafd6bc99ca390c95795449a1e7d5 (patch)
treebaf3cf50f99b6c618ae0805157df28d5152d2f73 /bftw.c
parent974a79f0fdd6069d2e24e424a3954e2279742e85 (diff)
downloadbfs-21dcf8c0d75bafd6bc99ca390c95795449a1e7d5.tar.xz
bftw: Use a circular buffer to implement the dirqueue.
Diffstat (limited to 'bftw.c')
-rw-r--r--bftw.c83
1 files changed, 37 insertions, 46 deletions
diff --git a/bftw.c b/bftw.c
index edca612..466a9d8 100644
--- a/bftw.c
+++ b/bftw.c
@@ -363,85 +363,76 @@ static void dircache_entry_free(struct dircache *cache, struct dircache_entry *e
}
}
-/** The size of a dirqueue block. */
-#define DIRQUEUE_BLOCK_SIZE 1023
-
-/**
- * A single block in the dirqueue chain.
- */
-struct dirqueue_block {
- /** The next block in the chain. */
- struct dirqueue_block *next;
- /** The elements in the queue. */
- struct dircache_entry *entries[DIRQUEUE_BLOCK_SIZE];
-};
-
/**
* A queue of 'dircache_entry's to examine.
*/
struct dirqueue {
- /** The first block. */
- struct dirqueue_block *head;
- /** The last block. */
- struct dirqueue_block *tail;
- /** The index in 'head' of the next entry to read. */
+ /** The circular buffer of entries. */
+ struct dircache_entry **entries;
+ /** Bitmask for circular buffer indices; one less than the capacity. */
+ size_t mask;
+ /** The index of the front of the queue. */
size_t front;
- /** The index in 'tail' of the next entry to write. */
+ /** The index of the back of the queue. */
size_t back;
};
/** Initialize a dirqueue. */
static void dirqueue_init(struct dirqueue *queue) {
- queue->head = queue->tail = NULL;
+ queue->entries = NULL;
+ queue->mask = 0;
queue->front = 0;
- queue->back = DIRQUEUE_BLOCK_SIZE;
+ queue->back = 0;
}
/** Add an entry to the dirqueue. */
static int dirqueue_push(struct dirqueue *queue, struct dircache_entry *entry) {
- if (queue->back == DIRQUEUE_BLOCK_SIZE) {
- struct dirqueue_block *block = malloc(sizeof(struct dirqueue_block));
- if (!block) {
+ if (queue->front == queue->back) {
+ size_t old_size = queue->mask + 1;
+ struct dircache_entry **old_entries = queue->entries;
+
+ size_t new_size = 2*old_size;
+ struct dircache_entry **new_entries = malloc(new_size*sizeof(struct dircache_entry *));
+ if (!new_entries) {
return -1;
}
- block->next = NULL;
+ 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);
- if (queue->tail) {
- queue->tail->next = block;
+ queue->front = 0;
+ queue->back = old_size;
}
- queue->tail = block;
- if (!queue->head) {
- queue->head = block;
- }
-
- queue->back = 0;
+ queue->entries = new_entries;
+ queue->mask = new_size - 1;
}
- queue->tail->entries[queue->back++] = entry;
+ 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->head) {
+ if (!queue->entries) {
return NULL;
}
- if (queue->head == queue->tail && queue->front == queue->back) {
- free(queue->head);
- dirqueue_init(queue);
- return NULL;
- }
+ struct dircache_entry *entry = queue->entries[queue->front];
+ queue->front += 1;
+ queue->front &= queue->mask;
- struct dirqueue_block *head = queue->head;
- struct dircache_entry *entry = head->entries[queue->front];
- if (++queue->front == DIRQUEUE_BLOCK_SIZE) {
- queue->head = head->next;
- queue->front = 0;
- free(head);
+ if (queue->front == queue->back) {
+ free(queue->entries);
+ queue->entries = NULL;
}
+
return entry;
}