lucy-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nwelln...@apache.org
Subject [4/6] lucy git commit: Use custom merge function in SortEx
Date Sat, 07 Nov 2015 17:06:38 GMT
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 <wellnhofer@aevum.de>
Authored: Thu Nov 5 20:10:11 2015 +0100
Committer: Nick Wellnhofer <wellnhofer@aevum.de>
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);


Mime
View raw message