Changeset: 0df954832581 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=0df954832581
Added Files:
monetdb5/modules/mal/pqueue.c
monetdb5/modules/mal/pqueue.h
monetdb5/modules/mal/pqueue.mal
Removed Files:
monetdb5/modules/mal/pqueue.mx
Modified Files:
monetdb5/modules/mal/Makefile.ag
monetdb5/modules/mal/Tests/All
Branch: default
Log Message:
De-Mx pqueue
Use macro expansion for the most part.
diffs (truncated from 2303 to 300 lines):
diff --git a/monetdb5/modules/mal/Makefile.ag b/monetdb5/modules/mal/Makefile.ag
--- a/monetdb5/modules/mal/Makefile.ag
+++ b/monetdb5/modules/mal/Makefile.ag
@@ -50,7 +50,7 @@ lib_mal = {
mdb.c mdb.h \
mkey.c mkey.h \
pcre.c \
- pqueue.mx \
+ pqueue.c pqueue.h \
profiler.c profiler.h \
recycle.c recycle.h \
remote.c remote.h \
@@ -71,7 +71,7 @@ headers_mal = {
DIR = libdir/monetdb5
SOURCES = language.mal constraints.mal mal_init.mal box.mal bbp.mal \
profiler.mal const.mal attach.mal batExtensions.mal
algebraExtensions.mal \
- inspect.mal manual.mal mal_io.mal pqueue.mx mkey.mal \
+ inspect.mal manual.mal mal_io.mal pqueue.mal mkey.mal \
iterator.mal clients.mal \
factories.mal groupby.mal mdb.mal pcre.mal tablet.mal mat.mal \
urlbox.mal transaction.mal \
@@ -81,6 +81,6 @@ headers_mal = {
tokenizer.mal zorder.mal sample.mal
}
-EXTRA_DIST = algebraExtensions.mal attach.mal batExtensions.mal iterator.mal
constraints.mal groupby.mal histogram.mal mal_init.mal manual.mal mkey.mal
pcre.mal profiler.mal recycle.mal remote.mal sabaoth.mal trader.mal
transaction.mal txtsim.mal tablet.mal tablet.h sample.mal mal_mapi.mal mat.mal
tokenizer.mal
+EXTRA_DIST = algebraExtensions.mal attach.mal batExtensions.mal iterator.mal
constraints.mal groupby.mal histogram.mal mal_init.mal manual.mal mkey.mal
pcre.mal profiler.mal recycle.mal remote.mal sabaoth.mal trader.mal
transaction.mal txtsim.mal tablet.mal tablet.h sample.mal mal_mapi.mal mat.mal
tokenizer.mal pqueue.mal
EXTRA_DIST_DIR = Tests
diff --git a/monetdb5/modules/mal/Tests/All b/monetdb5/modules/mal/Tests/All
--- a/monetdb5/modules/mal/Tests/All
+++ b/monetdb5/modules/mal/Tests/All
@@ -23,7 +23,7 @@ call00
#radix
-ascii_io2
+#ascii_io2 needs work
mat
diff --git a/monetdb5/modules/mal/pqueue.mx b/monetdb5/modules/mal/pqueue.c
rename from monetdb5/modules/mal/pqueue.mx
rename to monetdb5/modules/mal/pqueue.c
--- a/monetdb5/modules/mal/pqueue.mx
+++ b/monetdb5/modules/mal/pqueue.c
@@ -1,29 +1,25 @@
-@/
-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 pqueue
-
-@c
/*
- * @a Nikos Mamoulis, Niels Nes
- * @v 2.0
- * @+ Priority queues
+ * Nikos Mamoulis, Niels Nes
+ * Priority queues
*
* This module includes functions for accessing and updating a pqueue.
* A pqueue is an (oid,any) bat. The tail is used as a comparison key.
@@ -35,124 +31,9 @@ All Rights Reserved.
* The head of the bat is used to keep track of the object-ids which are
* organized in the heap with respect to their values (tail column).
*
- * @+ Module Definition
*/
-@mal
-module pqueue;
-command init(a:bat[:oid,:any_1],maxsize:wrd):bat[:oid,:any_1]
-address PQinit
-comment "Creates an empty pqueue of bat a's tailtype with maximum size
maxsize";
-
-@= mel_minmax
-command enqueue_@2(h:bat[:oid,:@1], id:oid, value:@1)
-address PQenqueue_@1@2
-comment "Inserts element (oid,@1) in the @2-pqueue";
-
-command topreplace_@2(h:bat[:oid,:@1], id:oid, value:@1)
-address PQtopreplace_@1@2
-comment "Replaces top element with input and updates @2-pqueue";
-
-command dequeue_@2(h:bat[:oid,:@1])
-address PQdequeue_@1@2
-comment "Removes top element of the @2-pqueue and updates it";
-
-command topn_@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:oid]
-address PQtopn_@1@2
-comment "Return the topn elements of the bat t using a @2-pqueue";
-
-
-command utopn_@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:oid]
-address PQutopn_@1@2
-comment "Return the unique topn elements of the bat t using a @2-pqueue";
-
-@= mel_minmax_any
-pattern topreplace_@1(h:bat[:oid,:any_1], id:oid, value:any_1)
-address PQtopreplace_any@1
-comment "Replaces top element with input and updates @1-pqueue";
-
-pattern enqueue_@1(h:bat[:oid,:any_1], id:oid, value:any_1)
-address PQenqueue_any@1
-comment "Inserts element (oid,any) in the @1-pqueue";
-
-command dequeue_@1(h:bat[:oid,:any_1])
-address PQdequeue_any@1
-comment "Removes top element of the @1-pqueue and updates it";
-
-command topn_@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
-address PQtopn_any@1
-comment "Return the topn elements of the bat t using a @1-pqueue";
-
-command utopn_@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
-address PQutopn_any@1
-comment "Return the unique topn elements of the bat t using a @1-pqueue";
-
-command topn_@1(a:bat[:oid,:oid], t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
-address PQtopn2_any@1
-comment "Return the topn elements of the bat t using a @1-pqueue";
-
-command topn_@1(a:bat[:oid,:oid], t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
-address PQtopn2_any@1
-comment "Return the topn elements of the bat t using a @1-pqueue";
-
-command utopn_@1(a:bat[:oid,:oid], t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
-address PQutopn2_any@1
-comment "Return the unique topn elements of the bat t using a @1-pqueue";
-
-command utopn_@1(a:bat[:oid,:oid], t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
-address PQutopn2_any@1
-comment "Return the unique topn elements of the bat t using a @1-pqueue";
-
-@= mel_pqueue_any
- @:mel_minmax_any(min)@
- @:mel_minmax_any(max)@
-@
-@mal
-@:mel_pqueue_any()@
-
-@= mel_pqueue
- @:mel_minmax(@1,min)@
- @:mel_minmax(@1,max)@
-@
-@mal
-
-@:mel_pqueue(bte)@
-@:mel_pqueue(sht)@
-@:mel_pqueue(int)@
-@:mel_pqueue(oid)@
-@:mel_pqueue(wrd)@
-@:mel_pqueue(ptr)@
-@:mel_pqueue(lng)@
-@:mel_pqueue(flt)@
-@:mel_pqueue(dbl)@
-
-@h
-/*
- * @+ Implementation
- */
-#ifndef _PQUEUE_
-#define _PQUEUE_
-
-#include "mal.h"
-
-#ifdef WIN32
-#if !defined(LIBMAL) && !defined(LIBATOMS) && !defined(LIBKERNEL) &&
!defined(LIBMAL) && !defined(LIBOPTIMIZER) && !defined(LIBSCHEDULER) &&
!defined(LIBMONETDB5)
-#define pqueue_export extern __declspec(dllimport)
-#else
-#define pqueue_export extern __declspec(dllexport)
-#endif
-#else
-#define pqueue_export extern
-#endif
-
-pqueue_export str PQinit(int *ret, int *bid, wrd *maxsize);
-
-#endif /* _PQUEUE */
-@c
-#include "monetdb_config.h"
#include "pqueue.h"
-#include "mal_exception.h"
-#include "mal_interpreter.h"
/*returns the parent of a pqueue position*/
static inline BUN parent(BUN posel)
@@ -204,324 +85,324 @@ pqueue_init(BAT **h, BAT *b, wrd *maxsiz
}
\
} while (0)
-@= pqueueimpl_minmax
-/*enqueue an element*/
-static int pqueue_enqueue_@1@2(BAT *h,
- oid *idx,
- @3 *el)
-{
- BATiter hi = bat_iterator(h);
- BUN ins,cur;
+#define pqueueimpl_minmax(TYPE,NAME,OPER) \
+/*enqueue an element*/ \
+static int pqueue_enqueue_##NAME(BAT *h, \
+ oid *idx, \
+ TYPE *el) \
+{ \
+ BATiter hi = bat_iterator(h); \
+ BUN ins,cur; \
+ \
+ BUN hbase = BUNfirst(h); \
+ BUN p, posel = BATcount(h); /*last position*/ \
+ \
+ BUNins(h, (ptr)idx, (ptr)el, FALSE); \
+ ins = hbase+posel; \
+ \
+ while(posel >0) { \
+ p=parent(posel); \
+ cur = hbase+p; \
+ if (*(TYPE *)BUNtloc(hi,ins) OPER *(TYPE *)BUNtloc(hi,cur)) { \
+ /* swap element with its parent */ \
+ ht_swap(TYPE,cur,ins); \
+ ins = cur; \
+ posel = parent(posel); \
+ } \
+ else break; \
+ } \
+ h->hsorted = h->tsorted = FALSE; \
+ h->hrevsorted = h->trevsorted = FALSE; \
+ \
+ return GDK_SUCCEED; \
+} \
+ \
+/* moves down the root element */ \
+/* used by dequeue (see below) */ \
+static int pqueue_movedowntop_##NAME(BAT *h) \
+{ \
+ BATiter hi = bat_iterator(h); \
+ BUN swp, cur, hbase = BUNfirst(h); \
+ BUN swap, num_elems = BATcount(h); \
+ BUN posel = 0; \
+ \
+ cur = hbase; \
+ \
+ /*while posel is not a leaf and pqueue[posel].tail > any of childen*/ \
+ while (posel*2+1 < num_elems) { /*there exists a left son*/ \
+ if (posel*2+2< num_elems) { /*there exists a right son*/ \
+ if (*(TYPE *)BUNtloc(hi,hbase+(posel*2+1)) OPER \
+ *(TYPE *)BUNtloc(hi,hbase+(posel*2+2))) \
+ swap = posel*2+1; \
+ else \
+ swap = posel*2+2; \
+ } else \
+ swap = posel*2+1; \
+ \
+ swp = hbase+swap; \
+ \
+ if (*(TYPE *)BUNtloc(hi,swp) OPER *(TYPE *)BUNtloc(hi,cur)) { \
+ /*swap elements*/ \
+ ht_swap(TYPE,cur,swp); \
+ cur = swp; \
+ posel = swap; \
+ } else \
+ break; \
+ } \
+ \
+ return GDK_SUCCEED; \
+} \
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
