Use custom merge function in SortEx
Project: http://git-wip-us.apache.org/repos/asf/lucy/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy/commit/670e0133 Tree: http://git-wip-us.apache.org/repos/asf/lucy/tree/670e0133 Diff: http://git-wip-us.apache.org/repos/asf/lucy/diff/670e0133 Branch: refs/heads/master Commit: 670e0133f64031d967acff9513a96e76bcd88d94 Parents: 781700d Author: Nick Wellnhofer <[email protected]> Authored: Thu Nov 5 20:10:11 2015 +0100 Committer: Nick Wellnhofer <[email protected]> Committed: Thu Nov 5 20:10:11 2015 +0100 ---------------------------------------------------------------------- core/Lucy/Util/SortExternal.c | 46 +++++++++++++++++++++++++++++++++----- 1 file changed, 41 insertions(+), 5 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy/blob/670e0133/core/Lucy/Util/SortExternal.c ---------------------------------------------------------------------- diff --git a/core/Lucy/Util/SortExternal.c b/core/Lucy/Util/SortExternal.c index 03f0722..976cab4 100644 --- a/core/Lucy/Util/SortExternal.c +++ b/core/Lucy/Util/SortExternal.c @@ -30,6 +30,12 @@ static void S_absorb_slices(SortExternal *self, SortExternalIVARS *ivars, Obj **endpost); +static void +S_merge(SortExternal *self, + Obj **left_ptr, size_t left_size, + Obj **right_ptr, size_t right_size, + Obj **dest, SortEx_Compare_t compare); + // Return the address for the item in one of the runs' buffers which is the // highest in sort order, but which we can guarantee is lower in sort order // than any item which has yet to enter a run buffer. @@ -260,8 +266,7 @@ S_absorb_slices(SortExternal *self, SortExternalIVARS *ivars, Obj ***slice_starts = ivars->slice_starts; uint32_t *slice_sizes = ivars->slice_sizes; Class *klass = SortEx_get_class(self); - CFISH_Sort_Compare_t compare - = (CFISH_Sort_Compare_t)METHOD_PTR(klass, LUCY_SortEx_Compare); + SortEx_Compare_t compare = METHOD_PTR(klass, LUCY_SortEx_Compare); if (ivars->buf_max != 0) { THROW(ERR, "Can't refill unless empty"); } @@ -315,9 +320,10 @@ S_absorb_slices(SortExternal *self, SortExternalIVARS *ivars, if (num_slices - i >= 2) { // Merge two consecutive slices. const uint32_t merged_size = slice_sizes[i] + slice_sizes[i + 1]; - Sort_merge(slice_starts[i], slice_sizes[i], - slice_starts[i + 1], slice_sizes[i + 1], dest, - sizeof(Obj*), compare, self); + S_merge(self, + slice_starts[i], slice_sizes[i], + slice_starts[i + 1], slice_sizes[i + 1], + dest, compare); slice_sizes[j] = merged_size; slice_starts[j] = dest; dest += merged_size; @@ -345,6 +351,36 @@ S_absorb_slices(SortExternal *self, SortExternalIVARS *ivars, } } +// Assumes left_size > 0 and right_size > 0. +static void +S_merge(SortExternal *self, + Obj **left_ptr, size_t left_size, + Obj **right_ptr, size_t right_size, + Obj **dest, SortEx_Compare_t compare) { + + Obj **left_limit = left_ptr + left_size; + Obj **right_limit = right_ptr + right_size; + + while (1) { + if (compare(self, left_ptr, right_ptr) <= 0) { + *dest++ = *left_ptr++; + if (left_ptr >= left_limit) { + right_size = right_limit - right_ptr; + memcpy(dest, right_ptr, right_size * sizeof(Obj*)); + break; + } + } + else { + *dest++ = *right_ptr++; + if (right_ptr >= right_limit) { + left_size = left_limit - left_ptr; + memcpy(dest, left_ptr, left_size * sizeof(Obj*)); + break; + } + } + } +} + void SortEx_Grow_Buffer_IMP(SortExternal *self, uint32_t cap) { SortExternalIVARS *const ivars = SortEx_IVARS(self);
