From 6d00600fd0121cd3361843ca803fab0b2b76a7d8 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 3 Feb 2007 13:59:17 +0100 Subject: [PATCH] Moved low-level operations to a separate file. --- lib/sorter/Makefile | 2 +- lib/sorter/common.h | 50 ++++++++------- lib/sorter/govern.c | 137 +--------------------------------------- lib/sorter/sbuck.c | 150 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 180 insertions(+), 159 deletions(-) create mode 100644 lib/sorter/sbuck.c diff --git a/lib/sorter/Makefile b/lib/sorter/Makefile index ad14a927..c2c5b723 100644 --- a/lib/sorter/Makefile +++ b/lib/sorter/Makefile @@ -2,6 +2,6 @@ DIRS+=lib/sorter -LIBUCW_MODS+=sorter/config sorter/govern +LIBUCW_MODS+=sorter/config sorter/govern sorter/sbuck $(o)/lib/sorter/sort-test: $(o)/lib/sorter/sort-test.o $(LIBUCW) diff --git a/lib/sorter/common.h b/lib/sorter/common.h index c0d2e4b2..8affa630 100644 --- a/lib/sorter/common.h +++ b/lib/sorter/common.h @@ -25,27 +25,7 @@ enum sort_debug { SORT_DEBUG_NO_JOIN = 2, }; -struct sort_bucket { - cnode n; - struct sort_context *ctx; - uns flags; - struct fastbuf *fb; - byte *filename; - u64 size; // Size in bytes (not valid when writing) - uns runs; // Number of runs, 0 if not sorted - uns hash_bits; // Remaining bits of the hash function - byte *ident; // Identifier used in debug messages -}; - -enum sort_bucket_flags { - SBF_FINAL = 1, // This bucket corresponds to the final output file (always 1 run) - SBF_SOURCE = 2, // Contains the source file (always 0 runs) - SBF_CUSTOM_PRESORT = 4, // Contains source to read via custom presorter - SBF_OPEN_WRITE = 256, // We are currently writing to the fastbuf - SBF_OPEN_READ = 512, // We are reading from the fastbuf - SBF_DESTROYED = 1024, // Already done with, no further references allowed - SBF_SWAPPED_OUT = 2048, // Swapped out to a named file -}; +struct sort_bucket; struct sort_context { struct fastbuf *in_fb; @@ -72,14 +52,40 @@ struct sort_context { void sorter_run(struct sort_context *ctx); +/* Buffers */ + void *sorter_alloc(struct sort_context *ctx, uns size); void sorter_alloc_buf(struct sort_context *ctx); void sorter_free_buf(struct sort_context *ctx); -// Operations on buckets +/* Buckets */ + +struct sort_bucket { + cnode n; + struct sort_context *ctx; + uns flags; + struct fastbuf *fb; + byte *filename; + u64 size; // Size in bytes (not valid when writing) + uns runs; // Number of runs, 0 if not sorted + uns hash_bits; // Remaining bits of the hash function + byte *ident; // Identifier used in debug messages +}; + +enum sort_bucket_flags { + SBF_FINAL = 1, // This bucket corresponds to the final output file (always 1 run) + SBF_SOURCE = 2, // Contains the source file (always 0 runs) + SBF_CUSTOM_PRESORT = 4, // Contains source to read via custom presorter + SBF_OPEN_WRITE = 256, // We are currently writing to the fastbuf + SBF_OPEN_READ = 512, // We are reading from the fastbuf + SBF_DESTROYED = 1024, // Already done with, no further references allowed + SBF_SWAPPED_OUT = 2048, // Swapped out to a named file +}; + struct sort_bucket *sbuck_new(struct sort_context *ctx); void sbuck_drop(struct sort_bucket *b); int sbuck_have(struct sort_bucket *b); +int sbuck_has_file(struct sort_bucket *b); sh_off_t sbuck_size(struct sort_bucket *b); struct fastbuf *sbuck_read(struct sort_bucket *b); struct fastbuf *sbuck_write(struct sort_bucket *b); diff --git a/lib/sorter/govern.c b/lib/sorter/govern.c index d325a029..738186e3 100644 --- a/lib/sorter/govern.c +++ b/lib/sorter/govern.c @@ -12,142 +12,7 @@ #include "lib/mempool.h" #include "lib/sorter/common.h" -#include - -void * -sorter_alloc(struct sort_context *ctx, uns size) -{ - return mp_alloc_zero(ctx->pool, size); -} - -struct sort_bucket * -sbuck_new(struct sort_context *ctx) -{ - struct sort_bucket *b = sorter_alloc(ctx, sizeof(struct sort_bucket)); - b->ctx = ctx; - return b; -} - -void -sbuck_drop(struct sort_bucket *b) -{ - if (b) - { - ASSERT(!(b->flags & SBF_DESTROYED)); - if (b->n.prev) - clist_remove(&b->n); - bclose(b->fb); - bzero(b, sizeof(*b)); - b->flags = SBF_DESTROYED; - } -} - -sh_off_t -sbuck_size(struct sort_bucket *b) -{ - if ((b->flags & SBF_OPEN_WRITE) && !(b->flags & SBF_SWAPPED_OUT)) - return btell(b->fb); - else - return b->size; -} - -int -sbuck_have(struct sort_bucket *b) -{ - return b && sbuck_size(b); -} - -static int -sbuck_has_file(struct sort_bucket *b) -{ - return (b->fb || (b->flags & SBF_SWAPPED_OUT)); -} - -static void -sbuck_swap_in(struct sort_bucket *b) -{ - if (b->flags & SBF_SWAPPED_OUT) - { - b->fb = bopen(b->filename, O_RDWR, sorter_stream_bufsize); - if (b->flags & SBF_OPEN_WRITE) - bseek(b->fb, 0, SEEK_END); - bconfig(b->fb, BCONFIG_IS_TEMP_FILE, 1); - b->flags &= ~SBF_SWAPPED_OUT; - SORT_XTRACE("Swapped in %s", b->filename); - } -} - -struct fastbuf * -sbuck_read(struct sort_bucket *b) -{ - sbuck_swap_in(b); - if (b->flags & SBF_OPEN_READ) - return b->fb; - else if (b->flags & SBF_OPEN_WRITE) - { - b->size = btell(b->fb); - b->flags = (b->flags & ~SBF_OPEN_WRITE) | SBF_OPEN_READ; - brewind(b->fb); - return b->fb; - } - else - ASSERT(0); -} - -struct fastbuf * -sbuck_write(struct sort_bucket *b) -{ - sbuck_swap_in(b); - if (b->flags & SBF_OPEN_WRITE) - ASSERT(b->fb); - else - { - ASSERT(!(b->flags & (SBF_OPEN_READ | SBF_DESTROYED))); - b->fb = bopen_tmp(sorter_stream_bufsize); - b->flags |= SBF_OPEN_WRITE; - b->filename = mp_strdup(b->ctx->pool, b->fb->name); - } - return b->fb; -} - -void -sbuck_swap_out(struct sort_bucket *b) -{ - if ((b->flags & (SBF_OPEN_READ | SBF_OPEN_WRITE)) && b->fb) - { - if (b->flags & SBF_OPEN_WRITE) - b->size = btell(b->fb); - bconfig(b->fb, BCONFIG_IS_TEMP_FILE, 0); - bclose(b->fb); - b->fb = NULL; - b->flags |= SBF_SWAPPED_OUT; - SORT_XTRACE("Swapped out %s", b->filename); - } -} - -void -sorter_alloc_buf(struct sort_context *ctx) -{ - if (ctx->big_buf) - return; - u64 bs = MAX(sorter_bufsize/2, 1); - bs = ALIGN_TO(bs, (u64)CPU_PAGE_SIZE); - ctx->big_buf = big_alloc(2*bs); - ctx->big_buf_size = 2*bs; - ctx->big_buf_half = ((byte*) ctx->big_buf) + bs; - ctx->big_buf_half_size = bs; - SORT_XTRACE("Allocated sorting buffer (%jd bytes)", (uintmax_t) bs); -} - -void -sorter_free_buf(struct sort_context *ctx) -{ - if (!ctx->big_buf) - return; - big_free(ctx->big_buf, ctx->big_buf_size); - ctx->big_buf = NULL; - SORT_XTRACE("Freed sorting buffer"); -} +#include static int sorter_presort(struct sort_context *ctx, struct sort_bucket *in, struct sort_bucket *out, struct sort_bucket *out_only) { diff --git a/lib/sorter/sbuck.c b/lib/sorter/sbuck.c new file mode 100644 index 00000000..08958401 --- /dev/null +++ b/lib/sorter/sbuck.c @@ -0,0 +1,150 @@ +/* + * UCW Library -- Universal Sorter: Operations on Contexts, Buffers and Buckets + * + * (c) 2007 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#include "lib/lib.h" +#include "lib/fastbuf.h" +#include "lib/mempool.h" +#include "lib/sorter/common.h" + +#include + +void * +sorter_alloc(struct sort_context *ctx, uns size) +{ + return mp_alloc_zero(ctx->pool, size); +} + +struct sort_bucket * +sbuck_new(struct sort_context *ctx) +{ + struct sort_bucket *b = sorter_alloc(ctx, sizeof(struct sort_bucket)); + b->ctx = ctx; + return b; +} + +void +sbuck_drop(struct sort_bucket *b) +{ + if (b) + { + ASSERT(!(b->flags & SBF_DESTROYED)); + if (b->n.prev) + clist_remove(&b->n); + bclose(b->fb); + bzero(b, sizeof(*b)); + b->flags = SBF_DESTROYED; + } +} + +sh_off_t +sbuck_size(struct sort_bucket *b) +{ + if ((b->flags & SBF_OPEN_WRITE) && !(b->flags & SBF_SWAPPED_OUT)) + return btell(b->fb); + else + return b->size; +} + +int +sbuck_have(struct sort_bucket *b) +{ + return b && sbuck_size(b); +} + +int +sbuck_has_file(struct sort_bucket *b) +{ + return (b->fb || (b->flags & SBF_SWAPPED_OUT)); +} + +static void +sbuck_swap_in(struct sort_bucket *b) +{ + if (b->flags & SBF_SWAPPED_OUT) + { + b->fb = bopen(b->filename, O_RDWR, sorter_stream_bufsize); + if (b->flags & SBF_OPEN_WRITE) + bseek(b->fb, 0, SEEK_END); + bconfig(b->fb, BCONFIG_IS_TEMP_FILE, 1); + b->flags &= ~SBF_SWAPPED_OUT; + SORT_XTRACE("Swapped in %s", b->filename); + } +} + +struct fastbuf * +sbuck_read(struct sort_bucket *b) +{ + sbuck_swap_in(b); + if (b->flags & SBF_OPEN_READ) + return b->fb; + else if (b->flags & SBF_OPEN_WRITE) + { + b->size = btell(b->fb); + b->flags = (b->flags & ~SBF_OPEN_WRITE) | SBF_OPEN_READ; + brewind(b->fb); + return b->fb; + } + else + ASSERT(0); +} + +struct fastbuf * +sbuck_write(struct sort_bucket *b) +{ + sbuck_swap_in(b); + if (b->flags & SBF_OPEN_WRITE) + ASSERT(b->fb); + else + { + ASSERT(!(b->flags & (SBF_OPEN_READ | SBF_DESTROYED))); + b->fb = bopen_tmp(sorter_stream_bufsize); + b->flags |= SBF_OPEN_WRITE; + b->filename = mp_strdup(b->ctx->pool, b->fb->name); + } + return b->fb; +} + +void +sbuck_swap_out(struct sort_bucket *b) +{ + if ((b->flags & (SBF_OPEN_READ | SBF_OPEN_WRITE)) && b->fb) + { + if (b->flags & SBF_OPEN_WRITE) + b->size = btell(b->fb); + bconfig(b->fb, BCONFIG_IS_TEMP_FILE, 0); + bclose(b->fb); + b->fb = NULL; + b->flags |= SBF_SWAPPED_OUT; + SORT_XTRACE("Swapped out %s", b->filename); + } +} + +void +sorter_alloc_buf(struct sort_context *ctx) +{ + if (ctx->big_buf) + return; + u64 bs = MAX(sorter_bufsize/2, 1); + bs = ALIGN_TO(bs, (u64)CPU_PAGE_SIZE); + ctx->big_buf = big_alloc(2*bs); + ctx->big_buf_size = 2*bs; + ctx->big_buf_half = ((byte*) ctx->big_buf) + bs; + ctx->big_buf_half_size = bs; + SORT_XTRACE("Allocated sorting buffer (%jd bytes)", (uintmax_t) bs); +} + +void +sorter_free_buf(struct sort_context *ctx) +{ + if (!ctx->big_buf) + return; + big_free(ctx->big_buf, ctx->big_buf_size); + ctx->big_buf = NULL; + SORT_XTRACE("Freed sorting buffer"); +} -- 2.39.2