Changeset: 230ee2c2b00c for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=230ee2c2b00c
Modified Files:
gdk/Makefile.ag
gdk/gdk_qsort.c
gdk/gdk_qsort.mx
gdk/gdk_qsort_impl.h
Branch: headless
Log Message:
Converted gdk_qsort.mx to C file.
Note how the type expansion is done without MX: include the header
file multiple times with certain tokens defined to different values
each time.
diffs (truncated from 1178 to 300 lines):
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -41,7 +41,7 @@
gdk_scanselect.mx gdk_batop.mx \
gdk_search.mx gdk_tm.c gdk_align.mx gdk_bbp.c \
gdk_heap.c gdk_setop.mx gdk_utils.c gdk_atoms.mx \
- gdk_qsort.mx gdk_ssort.c gdk_storage.c gdk_bat.mx \
+ gdk_qsort.c gdk_ssort.c gdk_storage.c gdk_bat.mx \
gdk_delta.c gdk_relop.mx gdk_system.c gdk_value.mx \
gdk_rangejoin.mx \
gdk_posix.c gdk_logger.mx bat.feps bat1.feps bat2.feps \
@@ -53,4 +53,4 @@
$(MALLOC_LIBS) $(PTHREAD_LIBS) $(DL_LIBS)
}
-EXTRA_DIST = gdk.h gdk_bbp.h gdk_delta.h gdk_posix.h gdk_ssort_impl.h
gdk_storage.h gdk_system.h gdk_tm.h gdk_utils.h
+EXTRA_DIST = gdk.h gdk_bbp.h gdk_delta.h gdk_posix.h gdk_qsort_impl.h
gdk_ssort_impl.h gdk_storage.h gdk_system.h gdk_tm.h gdk_utils.h
diff --git a/gdk/gdk_qsort.mx b/gdk/gdk_qsort.c
rename from gdk/gdk_qsort.mx
rename to gdk/gdk_qsort.c
--- a/gdk/gdk_qsort.mx
+++ b/gdk/gdk_qsort.c
@@ -1,88 +1,56 @@
-@/
-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://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
+/*
+ * 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://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
+ *
+ * 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-2011 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-2011 MonetDB B.V.
-All Rights Reserved.
-@
-
-@f gdk_qsort
-@a Peter Boncz, Niels Nes et al
-@* Qsort
-There were two problems with the OS provided qsort() library routine:
-@table @samp
-@item unreliable
-on certain OSs (e.g. SunOS), the qsort somehow degenerates
-if there are a very small number of different values (on
-132K elements with 7 values, I never saw it return).
-This is a serious bug.
-@item atom format
- when comparing GDK atoms (e.g. in BATs) it was not
-possible to use qsort on varsized atoms (as monet stores them
-as integer offsets from a global base pointer that qsort does
-not know about), nor if the values were not placed at the start
-of the record (e.g. if the column is the tail column of a BAT).
-@end table
-
-Both these problems are fixed in the new GDKqsort function, that
-is based on the standard Berkeley qsort (see copyright notice below).
-
-The routine was "monet"-ified with macro code expansions for the specific
-data types to obtain extra speed (we know more about our data than the stdlib
-qsort() ever can).
-@{
-@c
+/*
+ * @f gdk_qsort
+ * @a Peter Boncz, Niels Nes et al
+ * @* Qsort
+ * There were two problems with the OS provided qsort() library routine:
+ * @table @samp
+ * @item unreliable
+ * on certain OSs (e.g. SunOS), the qsort somehow degenerates
+ * if there are a very small number of different values (on
+ * 132K elements with 7 values, I never saw it return).
+ * This is a serious bug.
+ * @item atom format
+ * when comparing GDK atoms (e.g. in BATs) it was not
+ * possible to use qsort on varsized atoms (as monet stores them
+ * as integer offsets from a global base pointer that qsort does
+ * not know about), nor if the values were not placed at the start
+ * of the record (e.g. if the column is the tail column of a BAT).
+ * @end table
+ *
+ * Both these problems are fixed in the new GDKqsort function, that
+ * is based on the standard Berkeley qsort (see copyright notice below).
+ *
+ * The routine was "monet"-ified with macro code expansions for the specific
+ * data types to obtain extra speed (we know more about our data than the
stdlib
+ * qsort() ever can).
+ */
#include "monetdb_config.h"
#include "gdk.h"
-/*-
- * Copyright (c) 1992, 1993
- * The Regents of the University of California. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * This product includes software developed by the University of
- * California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-@-
-Record containing all data-specific info.
-Introduced to reduce number of qsort parameters
-@c
+/*
+ * @-
+ * Record containing all data-specific info.
+ * Introduced to reduce number of qsort parameters
+ */
typedef struct {
int (*cmp) (ptr, ptr); /* routine that compares two atoms */
char *offst; /* NULL or start of varsized heap */
@@ -100,39 +68,52 @@
#define DIV_WIDTH(d) ((d) >> buf->hshift)
#define MULT_TS(d) ((d) << buf->tshift)
-@= register_swap
/* fast record swapping */
-#define @1_SWAP(TYPE, a, b, s) \
+
+#define generic_SWAP(TYPE, a, b) \
do { \
- @1 *_pa = (@1 *) (a); \
- @1 *_pb = (@1 *) (b); \
- @1 _tmp = *_pa; \
+ TYPE *_pa = (TYPE *) (a); \
+ TYPE *_pb = (TYPE *) (b); \
+ TYPE _tmp = *_pa; \
*_pa = *_pb; \
*_pb = _tmp; \
} while (0)
-#define direct_@1_SWAP(TYPE, a, b, s) \
- @1_SWAP(TYPE, a, b, s)
-#define offset_@1_SWAP(TYPE, a, b, s) offset_any_SWAP(TYPE, a, b, s)
+#define chr_SWAP(TYPE, a, b, s) generic_SWAP(chr, a, b)
+#define direct_chr_SWAP(TYPE, a, b, s) chr_SWAP(TYPE, a, b, s)
+#define chr_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_chr_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
-#define @1_multi_SWAP(TYPE, a, b, n, nt, s) \
- tpe_SWAP(TYPE, a, b, n)
+#define bte_SWAP(TYPE, a, b, s) generic_SWAP(bte, a, b)
+#define direct_bte_SWAP(TYPE, a, b, s) bte_SWAP(TYPE, a, b, s)
+#define bte_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_bte_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
-#define direct_@1_multi_SWAP(TYPE, a, b, n, nt, s) \
- tpe_SWAP(TYPE, a, b, n)
+#define sht_SWAP(TYPE, a, b, s) generic_SWAP(sht, a, b)
+#define direct_sht_SWAP(TYPE, a, b, s) sht_SWAP(TYPE, a, b, s)
+#define sht_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_sht_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
-#define offset_@1_multi_SWAP(TYPE, a, b, n, nt, s) offset_any_multi_SWAP(TYPE,
a, b, n, nt, s)
+#define int_SWAP(TYPE, a, b, s) generic_SWAP(int, a, b)
+#define direct_int_SWAP(TYPE, a, b, s) int_SWAP(TYPE, a, b, s)
+#define int_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_int_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
-@c
-@:register_swap(chr)@
-@:register_swap(bte)@
-@:register_swap(sht)@
-@:register_swap(int)@
-@:register_swap(lng)@
-@:register_swap(flt)@
-@:register_swap(dbl)@
+#define lng_SWAP(TYPE, a, b, s) generic_SWAP(lng, a, b)
+#define direct_lng_SWAP(TYPE, a, b, s) lng_SWAP(TYPE, a, b, s)
+#define lng_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_lng_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
-#define iterate_SWAP(TYPE, a, b, s) tpe_SWAP(bte, a, b, s)
+#define flt_SWAP(TYPE, a, b, s) generic_SWAP(flt, a, b)
+#define direct_flt_SWAP(TYPE, a, b, s) flt_SWAP(TYPE, a, b, s)
+#define flt_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_flt_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+
+#define dbl_SWAP(TYPE, a, b, s) generic_SWAP(dbl, a, b)
+#define direct_dbl_SWAP(TYPE, a, b, s) dbl_SWAP(TYPE, a, b, s)
+#define dbl_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+#define direct_dbl_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(TYPE, a, b, n)
+
#define direct_any_SWAP(TYPE, a, b, s) tpe_SWAP(bte, a, b, s)
#define offset_any_SWAP(TYPE, a, b, s) \
do { \
@@ -144,7 +125,6 @@
default: assert(0); \
} \
} while (0)
-#define iterate_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(bte, a, b, nt)
#define direct_any_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(bte, a, b, nt)
#define offset_any_multi_SWAP(TYPE, a, b, n, nt, s) \
do { \
@@ -173,34 +153,38 @@
} \
} while (0)
-@}
-@-
-qsort is macro expanded in four dimensions:
-@table @samp
-@item direction:2
- L: from lesser to greater is standard.
- G: from greater to lesser is the _rev version of quicksort.
-@item type:7
- in order to factor out a type-specific check, or a function call for
each
- value comparison, we separate different qsort implementations by the
comparison
- type, of which each has the comparison hard-coded. We factor out the
types
- @{chr,bte,sht,int,wrd,flt,lng,dbl,any@} (the latter uses an adt
function call).
-@item storage:2
- denoted @{direct,offset@}, means whether the array to be sorted
contains the
- (fixed-width) values itself, or whether it contains integer
byte-offsets, that point
- into some heap. Note that we support byte-offset qsort also on
fixed-size types,
- as this is handy in many cases.
-@item swapmethod:2
- qsort sorts an array by continually swapping entries. To do this, two
- implementations of the swap action are supported: @{iterate,register@}.
- The default implementation takes the comparison type and does the
swapping by
- iterating a number of times per entry, copying one comparison value per
iteration.
- One often-occurring special case is when the entry width is 8 (two
integers). These
- can be copied by one long integer load and store; without the loop
overhead.
-@end table
-Thus, there are 2 * 7 * 2 * 2 = 56 GDKqsort implementation routines.
-@{
-@c
+/*
+ * @-
+ * qsort is macro expanded in four dimensions:
+ * @table @samp
+ * @item direction:2
+ * L: from lesser to greater is standard.
+ * G: from greater to lesser is the _rev version of quicksort.
+ * @item type:7
+ * in order to factor out a type-specific check, or a function
+ * call for each value comparison, we separate different qsort
+ * implementations by the comparison type, of which each has the
+ * comparison hard-coded. We factor out the types
+ * @{chr,bte,sht,int,wrd,flt,lng,dbl,any@} (the latter uses an
+ * adt function call).
+ * @item storage:2
+ * denoted @{direct,offset@}, means whether the array to be
+ * sorted contains the (fixed-width) values itself, or whether it
+ * contains integer byte-offsets, that point into some heap. Note
+ * that we support byte-offset qsort also on fixed-size types, as
+ * this is handy in many cases.
+ * @item swapmethod:2
+ * qsort sorts an array by continually swapping entries. To do
+ * this, two implementations of the swap action are supported:
+ * @{iterate,register@}. The default implementation takes the
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
