Changeset: 658cd94d155f for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=658cd94d155f Modified Files: monetdb5/modules/mal/pqueue.c Branch: default Log Message:
Indent. diffs (truncated from 2366 to 300 lines): diff --git a/monetdb5/modules/mal/pqueue.c b/monetdb5/modules/mal/pqueue.c --- a/monetdb5/modules/mal/pqueue.c +++ b/monetdb5/modules/mal/pqueue.c @@ -3,19 +3,19 @@ * 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. -*/ + */ /* * Nikos Mamoulis, Niels Nes @@ -35,16 +35,17 @@ #include "pqueue.h" -/*returns the parent of a pqueue position*/ -static inline BUN parent(BUN posel) +/* returns the parent of a pqueue position */ +static inline BUN +parent(BUN posel) { - if (posel%2) /*odd*/ - return posel/2; - else - return (posel-1)/2; + if (posel % 2) /*odd */ + return posel / 2; + else + return (posel - 1) / 2; } -/*initialize pqueue*/ +/* initialize pqueue */ static int do_pqueue_init(BAT **h, BAT *b, BUN maxsize) { @@ -55,1178 +56,1205 @@ do_pqueue_init(BAT **h, BAT *b, BUN maxs return GDK_SUCCEED; } -static int +static int pqueue_init(BAT **h, BAT *b, wrd *maxsize) { return do_pqueue_init(h, b, (BUN) *maxsize); } -#define ht_swap(tpe,cur,ins) \ - do { \ - oid htmp = *(oid*)BUNhloc(hi,cur); \ - tpe ttmp = *(tpe*)BUNtloc(hi,cur); \ - *(oid*)BUNhloc(hi,cur) = *(oid*)BUNhloc(hi,ins); \ - *(tpe*)BUNtloc(hi,cur) = *(tpe*)BUNtloc(hi,ins); \ - *(oid*)BUNhloc(hi,ins) = htmp; \ - *(tpe*)BUNtloc(hi,ins) = ttmp; \ +#define ht_swap(tpe,cur,ins) \ + do { \ + oid htmp = *(oid*)BUNhloc(hi,cur); \ + tpe ttmp = *(tpe*)BUNtloc(hi,cur); \ + *(oid*)BUNhloc(hi,cur) = *(oid*)BUNhloc(hi,ins); \ + *(tpe*)BUNtloc(hi,cur) = *(tpe*)BUNtloc(hi,ins); \ + *(oid*)BUNhloc(hi,ins) = htmp; \ + *(tpe*)BUNtloc(hi,ins) = ttmp; \ } while (0) #define any_swap(cur,ins,ts) \ do { \ - unsigned int i; \ - char ch; \ - /* only swap the locations (ie var_t's) */ \ - char *c1 = BUNtloc(hi,cur), *c2 = BUNtloc(hi,ins); \ - oid htmp = *(oid*)BUNhloc(hi,cur); \ - *(oid*)BUNhloc(hi,cur) = *(oid*)BUNhloc(hi,ins); \ - *(oid*)BUNhloc(hi,ins) = htmp; \ - for(i=0;i<ts;i++) { \ - ch= c1[i]; c1[i]=c2[i]; c2[i]=ch; \ - } \ + unsigned int i; \ + char ch; \ + /* only swap the locations (ie var_t's) */ \ + char *c1 = BUNtloc(hi,cur), *c2 = BUNtloc(hi,ins); \ + oid htmp = *(oid*)BUNhloc(hi,cur); \ + *(oid*)BUNhloc(hi,cur) = *(oid*)BUNhloc(hi,ins); \ + *(oid*)BUNhloc(hi,ins) = htmp; \ + for(i=0;i<ts;i++) { \ + ch= c1[i]; c1[i]=c2[i]; c2[i]=ch; \ + } \ } while (0) -#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; \ -} \ - \ -/* removes the root element, puts the last element as root and moves it down */ \ -static int pqueue_dequeue_##NAME(BAT *h) \ -{ \ - BATiter hi = bat_iterator(h); \ - BUN hbase; \ - BUN num_elements; \ - \ - if (!(num_elements = BATcount(h))) { \ - /* pqueue_dequeue: Cannot dequeue from empty queue */ \ - return GDK_FAIL; \ - } \ - \ - hbase = BUNfirst(h); \ - \ - /* copy last element to the first position*/ \ - ht_swap(TYPE,hbase, hbase+(num_elements-1)); \ - \ - /*delete last element*/ \ - BUNdelete(h, hbase+(num_elements-1), FALSE); \ - \ - pqueue_movedowntop_##NAME(h); \ - return GDK_SUCCEED; \ -} \ - \ -/* replaces the top element with the input if it is larger (smaller) and \ - * updates the heap */ \ -static int pqueue_topreplace_##NAME(BAT *h, \ - oid *idx, \ - TYPE *el) \ -{ \ - BATiter hi = bat_iterator(h); \ - BUN hbase; \ - \ - hbase = BUNfirst(h); \ - \ - if (*(TYPE *)BUNtloc(hi,hbase) OPER *el) { \ - *(oid*)BUNhloc(hi,hbase) = *idx; \ - *(TYPE*)BUNtloc(hi,hbase) = *el; \ - pqueue_movedowntop_##NAME(h); \ - } \ - \ - return GDK_SUCCEED; \ -} \ - \ -/* TopN, based on ##NAME-pqueue */ \ - \ -static BAT * \ -heap2bat_##NAME( BAT *h ) \ -{ \ - BAT *r, *n = BATnew(TYPE_oid, TYPE_oid, BATcount(h)); \ - BUN f = BUNfirst(h); \ - oid *o = (oid*)Hloc(h, f), oo = *o; \ - TYPE *v = (TYPE*)Tloc(h, f), ov = *v; \ - \ - for(f = BUNfirst(h); f < BUNlast(h); f = BUNfirst(h)) { \ - o = (oid*)Hloc(h, f); \ - v = (TYPE*)Tloc(h, f); \ - if (ov != *v) { \ - oo = *o; \ - ov = *v; \ - } \ - BUNins(n, o, &oo, FALSE); \ - pqueue_dequeue_##NAME(h); \ - } \ - r = BATrevert(n); \ - return r; \ -} \ - \ -static int pqueue_topn_void##NAME(BAT **H, BAT *t, wrd *N) \ -{ \ - BAT *h = NULL; \ - BATiter ti = bat_iterator(t); \ - TYPE *v; \ - BUN i, n = BATcount(t); \ - oid idx = t->hseqbase; \ - \ - if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N < n) \ - n = (BUN) *N; \ - if (do_pqueue_init(&h,t,n) == GDK_FAIL) \ - return GDK_FAIL; \ - v = (TYPE*)BUNtail(ti,BUNfirst(t)); \ - \ - for(i=0; i<n; i++, idx++, v++) { \ - pqueue_enqueue_##NAME(h, &idx, v); \ - } \ - n = BATcount(t); \ - for(; i<n; i++, idx++, v++) { \ - pqueue_topreplace_##NAME(h, &idx, v); \ - } \ - *H = heap2bat_##NAME(h); \ - BBPunfix(h->batCacheid); \ - return GDK_SUCCEED; \ -} \ - \ -static int pqueue_topn_##NAME(BAT **H, BAT *t, wrd *N) \ -{ \ - BAT *h = NULL; \ - BATiter ti = bat_iterator(t); \ - BUN i, n = BATcount(t); \ - BUN p = BUNfirst(t); \ - \ - if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N < n) \ - n = (BUN) *N; \ - if (do_pqueue_init(&h,t,n) == GDK_FAIL) \ - return GDK_FAIL; \ - \ - for(i=0; i<n; i++, p++) { \ - pqueue_enqueue_##NAME(h, (oid*)BUNhloc(ti,p), (TYPE*)BUNtloc(ti,p)); \ - } \ - n = BATcount(t); \ - for(; i<n; i++, p++) { \ - pqueue_topreplace_##NAME(h, (oid*)BUNhloc(ti,p), (TYPE*)BUNtloc(ti,p)); \ - } \ - *H = heap2bat_##NAME(h); \ - BBPunfix(h->batCacheid); \ - return GDK_SUCCEED; \ -} \ - \ -/* TopN (unique values), based on ##NAME-pqueue */ \ - \ -static int pqueue_utopn_void##NAME(BAT **H, BAT *t, wrd *N) \ -{ \ - BAT *duplicates = NULL, *b; \ - BATiter ti = bat_iterator(t); \ - TYPE *v; \ - BUN i, j, n, cnt = BATcount(t), p; \ - oid idx = t->hseqbase; \ _______________________________________________ checkin-list mailing list checkin-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/checkin-list
