XML: Small bugfix in xml_merge_chars.

[libucw.git] / lib / sorter / array.h

diff --git a/lib/sorter/array.h b/lib/sorter/array.h
index 76f108cb181b7aa062658d7ac1eaa13503566809..04a27d77e79e52cfbac7db5b82b4c9a01897f573 100644 (file)
--- a/lib/sorter/array.h
+++ b/lib/sorter/array.h
@@ -23,22 +23,24 @@
  *  ASORT_PREFIX(x) [*]        add a name prefix (used on all global names
  *                     defined by the sorter)
  *  ASORT_KEY_TYPE  [*]        data type of a single array entry key
- *  ASORT_LT(x,y)      x < y for ASORT_TYPE (default: "x<y")
- *  ASORT_THRESHOLD    threshold for switching between quicksort and insertsort
- *  ASORT_PAGE_ALIGNED the array is guaranteed to be aligned to a multiple of CPU_PAGE_SIZE  (FIXME: Do we need this?)
+ *  ASORT_LT(x,y)      x < y for ASORT_KEY_TYPE (default: "x<y")
  *  ASORT_HASH(x)      a monotone hash function (safisfying hash(x) < hash(y) => x<y)
  *  ASORT_LONG_HASH    hashes are 64-bit numbers (default is 32 bits)
- *  ASORT_RADIX_BITS   FIXME
- *  ASORT_SWAP         FIXME: probably keep private
+ *
+ *  Fine-tuning parameters: (if you really insist)
+ *
+ *  ASORT_THRESHOLD    threshold for switching between quicksort and insertsort
+ *  ASORT_RADIX_BITS   how many bits of the hash functions are to be used at once for
+ *                     radix-sorting.
  *
  *  After including this file, a function
- *     ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts, ASORT_KEY_TYPE *buf, uns hash_bits)
+ *     ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts [, ASORT_KEY_TYPE *buf, uns hash_bits])
  *  is declared and all parameter macros are automatically undef'd. Here `buf' is an
  *  auxiliary buffer of the same size as the input array, required whenever radix
  *  sorting should be used, and `hash_bits' is the number of significant bits returned
  *  by the hash function. If the buffer is specified, the sorting function returns either
  *  a pointer to the input array or to the buffer, depending on where the result is stored.
- *  If you do not use hashing, these parameters should be NULL and 0, respectively.
+ *  If you do not use hashing, these parameters should be omitted.
  */
 
 #include "lib/sorter/common.h"
@@ -60,10 +62,12 @@ typedef ASORT_KEY_TYPE Q(key);
 #endif
 
 #ifndef ASORT_RADIX_BITS
-#define ASORT_RADIX_BITS 12            // FIXME: Tune automatically?
+#define ASORT_RADIX_BITS CONFIG_UCW_RADIX_SORTER_BITS
 #endif
 #define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
 
+/* QuickSort with optimizations a'la Sedgewick, inspired by qsort() from GNU libc. */
+
 static void Q(quicksort)(void *array_ptr, uns num_elts)
 {
   Q(key) *array = array_ptr;
@@ -75,8 +79,6 @@ static void Q(quicksort)(void *array_ptr, uns num_elts)
   if (num_elts <= 1)
     return;
 
-  /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
-
   left = 0;
   right = num_elts - 1;
   for(;;)
@@ -177,6 +179,49 @@ static void Q(quicksort)(void *array_ptr, uns num_elts)
     }
 }
 
+/* Just the splitting part of QuickSort */
+
+static void Q(quicksplit)(void *array_ptr, uns num_elts, int *leftp, int *rightp)
+{
+  Q(key) *array = array_ptr;
+  int l, r, m;
+  Q(key) pivot;
+
+  l = 0;
+  r = num_elts - 1;
+  m = (l+r)/2;
+  if (ASORT_LT(array[m], array[l]))
+    ASORT_SWAP(l,m);
+  if (ASORT_LT(array[r], array[m]))
+    {
+      ASORT_SWAP(m,r);
+      if (ASORT_LT(array[m], array[l]))
+       ASORT_SWAP(l,m);
+    }
+  pivot = array[m];
+  do
+    {
+      while (ASORT_LT(array[l], pivot))
+       l++;
+      while (ASORT_LT(pivot, array[r]))
+       r--;
+      if (l < r)
+       {
+         ASORT_SWAP(l,r);
+         l++;
+         r--;
+       }
+      else if (l == r)
+       {
+         l++;
+         r--;
+       }
+    }
+  while (l <= r);
+  *leftp = l;
+  *rightp = r;
+}
+
 #ifdef ASORT_HASH
 
 static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
@@ -239,16 +284,21 @@ static void Q(radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptr
 
 #endif
 
-static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bits)
+static Q(key) *Q(sort)(Q(key) *array, uns num_elts
+#ifdef ASORT_HASH
+  , Q(key) *buffer, uns hash_bits
+#endif
+  )
 {
   struct asort_context ctx = {
     .array = array,
-    .buffer = buffer,
     .num_elts = num_elts,
-    .hash_bits = hash_bits,
     .elt_size = sizeof(Q(key)),
     .quicksort = Q(quicksort),
+    .quicksplit = Q(quicksplit),
 #ifdef ASORT_HASH
+    .buffer = buffer,
+    .hash_bits = hash_bits,
     .radix_count = Q(radix_count),
     .radix_split = Q(radix_split),
     .radix_bits = ASORT_RADIX_BITS,
@@ -258,15 +308,14 @@ static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bit
   return ctx.array;
 }
 
-/* FIXME */
-#undef ASORT_PREFIX
+#undef ASORT_HASH
 #undef ASORT_KEY_TYPE
+#undef ASORT_LONG_HASH
 #undef ASORT_LT
-#undef ASORT_SWAP
-#undef ASORT_THRESHOLD
 #undef ASORT_PAGE_ALIGNED
-#undef ASORT_HASH
+#undef ASORT_PREFIX
 #undef ASORT_RADIX_BITS
 #undef ASORT_RADIX_MASK
-#undef ASORT_LONG_HASH
+#undef ASORT_SWAP
+#undef ASORT_THRESHOLD
 #undef Q