Changeset: 88a12b5c355c for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=88a12b5c355c
Added Files:
gdk/gdk_ssort.c
gdk/gdk_ssort_impl.h
Removed Files:
gdk/gdk_ssort.mx
Modified Files:
gdk/Makefile.ag
Branch: default
Log Message:
De-MX gdk_ssort.
Note that the file gdk_ssort_impl.h is included multiple times.
diffs (truncated from 2212 to 300 lines):
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -21,7 +21,7 @@ INCLUDES = ../common/options ../common/s
EXTRA_DIST = gdk_scanselect_defs.mx
-lib_gdk = {
+lib_gdk = {
VERSION = $(GDK_VERSION)
NAME = bat
SOURCES = \
@@ -37,7 +37,7 @@ lib_gdk = {
gdk_scanselect.mx gdk.h gdk_batop.mx \
gdk_search.mx gdk_tm.c gdk_align.c gdk_bbp.mx \
gdk_heap.c gdk_setop.mx gdk_utils.c gdk_utils.h gdk_atoms.c
gdk_atoms.h \
- gdk_qsort.mx gdk_ssort.mx gdk_storage.c gdk_bat.c gdk_bat.h \
+ gdk_qsort.mx gdk_ssort.c gdk_ssort_impl.h gdk_storage.c
gdk_bat.c gdk_bat.h \
gdk_delta.c gdk_relop.mx gdk_system.c gdk_value.c \
gdk_rangejoin.mx \
gdk_posix.c gdk_logger.c gdk_sample.c \
diff --git a/gdk/gdk_ssort.mx b/gdk/gdk_ssort.c
rename from gdk/gdk_ssort.mx
rename to gdk/gdk_ssort.c
--- a/gdk/gdk_ssort.mx
+++ b/gdk/gdk_ssort.c
@@ -1,25 +1,22 @@
-@/
-The contents of this file are subject to the MonetDB Public License
-Version 1.1 (the "License"); you may not use this file except in
-compliance with the License. You may obtain a copy of the License at
-http://www.monetdb.org/Legal/MonetDBLicense
+/*
+ * The contents of this file are subject to the MonetDB Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.monetdb.org/Legal/MonetDBLicense
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
+ * License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * The Original Code is the MonetDB Database System.
+ *
+ * The Initial Developer of the Original Code is CWI.
+ * Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
+ * Copyright August 2008-2012 MonetDB B.V.
+ * All Rights Reserved.
+ */
-Software distributed under the License is distributed on an "AS IS"
-basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
-License for the specific language governing rights and limitations
-under the License.
-
-The Original Code is the MonetDB Database System.
-
-The Initial Developer of the Original Code is CWI.
-Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
-Copyright August 2008-2012 MonetDB B.V.
-All Rights Reserved.
-@
-
-@f gdk_ssort
-
-@c
/*
* @a Sjoerd Mullender
* @* Ssort
@@ -31,22 +28,26 @@ All Rights Reserved.
#include "gdk.h"
#include "gdk_private.h"
-/* The maximum number of entries in a MergeState's pending-runs stack.
- This is enough to sort arrays of size up to about
- 32 * phi ** MAX_MERGE_PENDING
- where phi ~= 1.618. 85 is ridiculously large enough, good for an array
- with 2**64 elements. */
+/* The maximum number of entries in a MergeState's pending-runs
+ * stack. This is enough to sort arrays of size up to about
+ *
+ * 32 * phi ** MAX_MERGE_PENDING
+ *
+ * where phi ~= 1.618. 85 is ridiculously large enough, good for an
+ * array with 2**64 elements. */
#define MAX_MERGE_PENDING 85
-/* When we get into galloping mode, we stay there until both runs win less
- often than MIN_GALLOP consecutive times. See listsort.txt for more info. */
+/* When we get into galloping mode, we stay there until both runs win
+ * less often than MIN_GALLOP consecutive times. See listsort.txt for
+ * more info. */
#define MIN_GALLOP 7
/* Avoid malloc for small temp arrays. */
#define MERGESTATE_TEMP_SIZE (256 * sizeof(void *))
-/* One MergeState exists on the stack per invocation of mergesort. It's just
- a convenient way to pass state around among the helper functions. */
+/* One MergeState exists on the stack per invocation of mergesort.
+ * It's just a convenient way to pass state around among the helper
+ * functions. */
struct slice {
size_t base;
ssize_t len;
@@ -61,46 +62,46 @@ typedef struct {
void *bh;
void *bt;
/* Temporary storage for a single entry. If an entry is at
- most 2 lng's, we don't need to allocate anything. */
+ * most 2 lng's, we don't need to allocate anything. */
void *th;
void *tt;
lng tempstorageh[2]; /* 16 bytes should be wide enough ... */
lng tempstoraget[2]; /* ... for all our fixed-sized data */
/* This controls when we get *into* galloping mode. It's
- initialized to MIN_GALLOP. merge_lo and merge_hi tend to
- nudge it higher for random data, and lower for highly
- structured data. */
+ * initialized to MIN_GALLOP. merge_lo and merge_hi tend to
+ * nudge it higher for random data, and lower for highly
+ * structured data. */
ssize_t min_gallop;
- /* 'ah' and 'at' are temp storage to help with merges. They contain
room
- for alloced[ht] entries. */
+ /* 'ah' and 'at' are temp storage to help with merges. They
+ * contain room for alloced[ht] entries. */
void **ah;
ssize_t allocedh;
void **at;
ssize_t allocedt;
/* A stack of n pending runs yet to be merged. Run #i starts
- at address base[i] and extends for len[i] elements. It's
- always true (so long as the indices are in bounds) that
-
- pending[i].base + pending[i].len == pending[i+1].base
-
- so we could cut the storage for this, but it's a minor
- amount, and keeping all the info explicit simplifies the
- code. */
+ * at address base[i] and extends for len[i] elements. It's
+ * always true (so long as the indices are in bounds) that
+ *
+ * pending[i].base + pending[i].len == pending[i+1].base
+ *
+ * so we could cut the storage for this, but it's a minor
+ * amount, and keeping all the info explicit simplifies the
+ * code. */
int n;
struct slice pending[MAX_MERGE_PENDING];
- /* 'ah' and 'at' point to this when possible, rather than muck with
- malloc. */
+ /* 'ah' and 'at' point to this when possible, rather than muck
+ * with malloc. */
char temparrayh[MERGESTATE_TEMP_SIZE];
char temparrayt[MERGESTATE_TEMP_SIZE];
} MergeState;
-/* Free all the temp memory owned by the MergeState. This must be called
- when you're done with a MergeState, and may be called before then if
- you want to free the temp memory early. */
+/* Free all the temp memory owned by the MergeState. This must be
+ * called when you're done with a MergeState, and may be called before
+ * then if you want to free the temp memory early. */
static void
merge_freemem(MergeState *ms)
{
@@ -115,24 +116,23 @@ merge_freemem(MergeState *ms)
ms->allocedt = MERGESTATE_TEMP_SIZE;
}
-@= merge_getmem
/* Ensure enough temp memory for 'need' array slots is available.
- Returns 0 on success and -1 if the memory can't be gotten. */
+ * Returns 0 on success and -1 if the memory can't be gotten. */
static int
-merge_getmem@1(MergeState *ms, ssize_t need)
+merge_getmem(MergeState *ms, ssize_t need, void ***ap,
+ ssize_t *allocedp, int s, char *temparray)
{
assert(ms != NULL);
- need *= ms->@1s;
- if (need <= ms->alloced@1)
+ need *= s;
+ if (need <= *allocedp)
return 0;
- /* Don't realloc! That can cost cycles to copy the old data, but
- we don't care what's in the block.
- */
- if (ms->a@1 != (void *) ms->temparray@1)
- GDKfree(ms->a@1);
- ms->a@1 = GDKmalloc(need);
- if (ms->a@1) {
- ms->alloced@1 = need;
+ /* Don't realloc! That can cost cycles to copy the old data,
+ * but we don't care what's in the block. */
+ if (*ap != (void *) temparray)
+ GDKfree(*ap);
+ *ap = GDKmalloc(need);
+ if (*ap) {
+ *allocedp = need;
return 0;
}
GDKerror("GDKssort: not enough memory\n");
@@ -140,83 +140,101 @@ merge_getmem@1(MergeState *ms, ssize_t n
return -1;
}
-#define MERGE_GETMEM@2(MS, NEED) ((NEED) * (MS)->@1s <= (MS)->alloced@1 ? 0 :
\
- merge_getmem@1(MS, NEED))
-@
-@c
-@:merge_getmem(h,H)@
-@:merge_getmem(t,T)@
+#define MERGE_GETMEMH(MS, NEED) \
+ ((NEED) * (MS)->hs <= (MS)->allocedh ? 0 : \
+ merge_getmem(MS, NEED, &(MS)->ah, &(MS)->allocedh, (MS)->hs, \
+ (MS)->temparrayh))
+#define MERGE_GETMEMT(MS, NEED) \
+ ((NEED) * (MS)->ts <= (MS)->allocedt ? 0 : \
+ merge_getmem(MS, NEED, &(MS)->at, &(MS)->allocedt, (MS)->ts, \
+ (MS)->temparrayt))
#define PTRADD(p, n, w) ((void *) ((char *) (p) + (n) * (w)))
-@= copy
-#define COPY_@1(d,s,w) (* (@1 *) (d) = * (@1 *) (s))
-@
-@c
-#define COPY_any(d,s,w) do { \
- switch (w) { \
- case 0: \
- break; \
- case sizeof(bte): \
- * (bte *) (d) = * (bte *) (s); \
- break; \
- case sizeof(sht): \
- * (sht *) (d) = * (sht *) (s); \
- break; \
- case sizeof(int): \
- * (int *) (d) = * (int *) (s); \
- break; \
- case sizeof(lng): \
- * (lng *) (d) = * (lng *) (s); \
- break; \
- case 2 * sizeof(lng): \
- * (lng *) (d) = * (lng *) (s); \
+#define COPY_bte(d,s,w) (* (bte *) (d) = * (bte *) (s))
+#define COPY_sht(d,s,w) (* (sht *) (d) = * (sht *) (s))
+#define COPY_int(d,s,w) (* (int *) (d) = * (int *) (s))
+#define COPY_lng(d,s,w) (* (lng *) (d) = * (lng *) (s))
+#define COPY_flt(d,s,w) (* (flt *) (d) = * (flt *) (s))
+#define COPY_dbl(d,s,w) (* (dbl *) (d) = * (dbl *) (s))
+#define COPY_oid(d,s,w) (* (oid *) (d) = * (oid *) (s))
+
+#define COPY_any(d,s,w)
\
+ do { \
+ switch (w) { \
+ case 0: \
+ break; \
+ case sizeof(bte): \
+ * (bte *) (d) = * (bte *) (s); \
+ break; \
+ case sizeof(sht): \
+ * (sht *) (d) = * (sht *) (s); \
+ break; \
+ case sizeof(int): \
+ * (int *) (d) = * (int *) (s); \
+ break; \
+ case sizeof(lng): \
+ * (lng *) (d) = * (lng *) (s); \
+ break; \
+ case 2 * sizeof(lng): \
+ * (lng *) (d) = * (lng *) (s); \
* ((lng *) (d) + 1) = * ((lng *) (s) + 1); \
- break; \
- default: \
- memcpy((d), (s), (size_t) (w)); \
- break; \
- } \
+ break; \
+ default: \
+ memcpy((d), (s), (size_t) (w)); \
+ break; \
+ } \
} while (0)
-#define COPY_anyN(d,s,w,N) do { \
- int i; \
- switch (w) { \
- case 0: \
- break; \
- case sizeof(bte): \
- for(i=0; i<N; i++) \
- ((bte*)(d))[i] = ((bte*)(s))[i];\
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
