1 /* 2 * Copyright 1997, Regents of the University of Minnesota 3 * 4 * macros.h 5 * 6 * This file contains macros used in multilevel 7 * 8 * Started 9/25/94 9 * George 10 * 11 * $Id: macros.h 10060 2011-06-02 18:56:30Z karypis $ 12 * 13 */ 14 15 #ifndef _LIBMETIS_MACROS_H_ 16 #define _LIBMETIS_MACROS_H_ 17 18 /************************************************************************* 19 * The following macro returns a random number in the specified range 20 **************************************************************************/ 21 #define AND(a, b) ((a) < 0 ? ((-(a))&(b)) : ((a)&(b))) 22 #define OR(a, b) ((a) < 0 ? -((-(a))|(b)) : ((a)|(b))) 23 #define XOR(a, b) ((a) < 0 ? -((-(a))^(b)) : ((a)^(b))) 24 25 //#define icopy(n, a, b) (idx_t *)memcpy((void *)(b), (void *)(a), sizeof(idx_t)*(n)) 26 27 #define HASHFCT(key, size) ((key)%(size)) 28 #define SWAP gk_SWAP 29 30 /* gets the appropriate option value */ 31 #define GETOPTION(options, idx, defval) \ 32 ((options) == NULL || (options)[idx] == -1 ? defval : (options)[idx]) 33 34 /* converts a user provided ufactor into a real ubfactor */ 35 #define I2RUBFACTOR(ufactor) (1.0+0.001*(ufactor)) 36 37 /* set/reset the current workspace core */ 38 #define WCOREPUSH wspacepush(ctrl) 39 #define WCOREPOP wspacepop(ctrl) 40 41 42 43 /************************************************************************* 44 * These macros insert and remove nodes from a Direct Access list 45 **************************************************************************/ 46 #define ListInsert(n, lind, lptr, i) \ 47 do { \ 48 ASSERT(lptr[i] == -1); \ 49 lind[n] = i; \ 50 lptr[i] = (n)++;\ 51 } while(0) 52 53 #define ListDelete(n, lind, lptr, i) \ 54 do { \ 55 ASSERT(lptr[i] != -1); \ 56 lind[lptr[i]] = lind[--(n)]; \ 57 lptr[lind[n]] = lptr[i]; \ 58 lptr[i] = -1; \ 59 } while(0) 60 61 62 /************************************************************************* 63 * These macros insert and remove nodes from the boundary list 64 **************************************************************************/ 65 #define BNDInsert(nbnd, bndind, bndptr, vtx) \ 66 ListInsert(nbnd, bndind, bndptr, vtx) 67 68 #define BNDDelete(nbnd, bndind, bndptr, vtx) \ 69 ListDelete(nbnd, bndind, bndptr, vtx) 70 71 72 /************************************************************************* 73 * These macros deal with id/ed updating during k-way refinement 74 **************************************************************************/ 75 #define UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, \ 76 nbnd, bndptr, bndind, bndtype) \ 77 do { \ 78 where[i] = to; \ 79 myrinfo->ed += myrinfo->id-mynbrs[k].ed; \ 80 SWAP(myrinfo->id, mynbrs[k].ed, j); \ 81 if (mynbrs[k].ed == 0) \ 82 mynbrs[k] = mynbrs[--myrinfo->nnbrs]; \ 83 else \ 84 mynbrs[k].pid = from; \ 85 \ 86 /* Update the boundary information. Both deletion and addition is \ 87 allowed as this routine can be used for moving arbitrary nodes. */ \ 88 if (bndtype == BNDTYPE_REFINE) { \ 89 if (bndptr[i] != -1 && myrinfo->ed - myrinfo->id < 0) \ 90 BNDDelete(nbnd, bndind, bndptr, i); \ 91 if (bndptr[i] == -1 && myrinfo->ed - myrinfo->id >= 0) \ 92 BNDInsert(nbnd, bndind, bndptr, i); \ 93 } \ 94 else { \ 95 if (bndptr[i] != -1 && myrinfo->ed <= 0) \ 96 BNDDelete(nbnd, bndind, bndptr, i); \ 97 if (bndptr[i] == -1 && myrinfo->ed > 0) \ 98 BNDInsert(nbnd, bndind, bndptr, i); \ 99 } \ 100 } while(0) 101 102 103 #define UpdateAdjacentVertexInfoAndBND(ctrl, vid, adjlen, me, from, to, \ 104 myrinfo, ewgt, nbnd, bndptr, bndind, bndtype) \ 105 do { \ 106 idx_t k; \ 107 cnbr_t *mynbrs; \ 108 \ 109 if (myrinfo->inbr == -1) { \ 110 myrinfo->inbr = cnbrpoolGetNext(ctrl, adjlen+1); \ 111 myrinfo->nnbrs = 0; \ 112 } \ 113 ASSERT(CheckRInfo(ctrl, myrinfo)); \ 114 \ 115 mynbrs = ctrl->cnbrpool + myrinfo->inbr; \ 116 \ 117 /* Update global ID/ED and boundary */ \ 118 if (me == from) { \ 119 INC_DEC(myrinfo->ed, myrinfo->id, (ewgt)); \ 120 if (bndtype == BNDTYPE_REFINE) { \ 121 if (myrinfo->ed-myrinfo->id >= 0 && bndptr[(vid)] == -1) \ 122 BNDInsert(nbnd, bndind, bndptr, (vid)); \ 123 } \ 124 else { \ 125 if (myrinfo->ed > 0 && bndptr[(vid)] == -1) \ 126 BNDInsert(nbnd, bndind, bndptr, (vid)); \ 127 } \ 128 } \ 129 else if (me == to) { \ 130 INC_DEC(myrinfo->id, myrinfo->ed, (ewgt)); \ 131 if (bndtype == BNDTYPE_REFINE) { \ 132 if (myrinfo->ed-myrinfo->id < 0 && bndptr[(vid)] != -1) \ 133 BNDDelete(nbnd, bndind, bndptr, (vid)); \ 134 } \ 135 else { \ 136 if (myrinfo->ed <= 0 && bndptr[(vid)] != -1) \ 137 BNDDelete(nbnd, bndind, bndptr, (vid)); \ 138 } \ 139 } \ 140 \ 141 /* Remove contribution from the .ed of 'from' */ \ 142 if (me != from) { \ 143 for (k=0; k<myrinfo->nnbrs; k++) { \ 144 if (mynbrs[k].pid == from) { \ 145 if (mynbrs[k].ed == (ewgt)) \ 146 mynbrs[k] = mynbrs[--myrinfo->nnbrs]; \ 147 else \ 148 mynbrs[k].ed -= (ewgt); \ 149 break; \ 150 } \ 151 } \ 152 } \ 153 \ 154 /* Add contribution to the .ed of 'to' */ \ 155 if (me != to) { \ 156 for (k=0; k<myrinfo->nnbrs; k++) { \ 157 if (mynbrs[k].pid == to) { \ 158 mynbrs[k].ed += (ewgt); \ 159 break; \ 160 } \ 161 } \ 162 if (k == myrinfo->nnbrs) { \ 163 mynbrs[k].pid = to; \ 164 mynbrs[k].ed = (ewgt); \ 165 myrinfo->nnbrs++; \ 166 } \ 167 } \ 168 \ 169 ASSERT(CheckRInfo(ctrl, myrinfo));\ 170 } while(0) 171 172 173 #define UpdateQueueInfo(queue, vstatus, vid, me, from, to, myrinfo, oldnnbrs, \ 174 nupd, updptr, updind, bndtype) \ 175 do { \ 176 real_t rgain; \ 177 \ 178 if (me == to || me == from || oldnnbrs != myrinfo->nnbrs) { \ 179 rgain = (myrinfo->nnbrs > 0 ? \ 180 1.0*myrinfo->ed/sqrt(myrinfo->nnbrs) : 0.0) - myrinfo->id; \ 181 \ 182 if (bndtype == BNDTYPE_REFINE) { \ 183 if (vstatus[(vid)] == VPQSTATUS_PRESENT) { \ 184 if (myrinfo->ed-myrinfo->id >= 0) \ 185 rpqUpdate(queue, (vid), rgain); \ 186 else { \ 187 rpqDelete(queue, (vid)); \ 188 vstatus[(vid)] = VPQSTATUS_NOTPRESENT; \ 189 ListDelete(nupd, updind, updptr, (vid)); \ 190 } \ 191 } \ 192 else if (vstatus[(vid)] == VPQSTATUS_NOTPRESENT && myrinfo->ed-myrinfo->id >= 0) { \ 193 rpqInsert(queue, (vid), rgain); \ 194 vstatus[(vid)] = VPQSTATUS_PRESENT; \ 195 ListInsert(nupd, updind, updptr, (vid)); \ 196 } \ 197 } \ 198 else { \ 199 if (vstatus[(vid)] == VPQSTATUS_PRESENT) { \ 200 if (myrinfo->ed > 0) \ 201 rpqUpdate(queue, (vid), rgain); \ 202 else { \ 203 rpqDelete(queue, (vid)); \ 204 vstatus[(vid)] = VPQSTATUS_NOTPRESENT; \ 205 ListDelete(nupd, updind, updptr, (vid)); \ 206 } \ 207 } \ 208 else if (vstatus[(vid)] == VPQSTATUS_NOTPRESENT && myrinfo->ed > 0) { \ 209 rpqInsert(queue, (vid), rgain); \ 210 vstatus[(vid)] = VPQSTATUS_PRESENT; \ 211 ListInsert(nupd, updind, updptr, (vid)); \ 212 } \ 213 } \ 214 } \ 215 } while(0) 216 217 218 219 /*************************************************************************/ 220 /*! This macro determines the set of subdomains that a vertex can move to 221 without increasins the maxndoms. */ 222 /*************************************************************************/ 223 #define SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, vtmp) \ 224 do { \ 225 idx_t j, k, l, nadd, to; \ 226 for (j=0; j<myrinfo->nnbrs; j++) { \ 227 safetos[to = mynbrs[j].pid] = 0; \ 228 \ 229 /* uncompress the connectivity info for the 'to' subdomain */ \ 230 for (k=0; k<nads[to]; k++) \ 231 vtmp[adids[to][k]] = 1; \ 232 \ 233 for (nadd=0, k=0; k<myrinfo->nnbrs; k++) { \ 234 if (k == j) \ 235 continue; \ 236 \ 237 l = mynbrs[k].pid; \ 238 if (vtmp[l] == 0) { \ 239 if (nads[l] > maxndoms-1) { \ 240 nadd = maxndoms; \ 241 break; \ 242 } \ 243 nadd++; \ 244 } \ 245 } \ 246 if (nads[to]+nadd <= maxndoms) \ 247 safetos[to] = 1; \ 248 if (nadd == 0) \ 249 safetos[to] = 2; \ 250 \ 251 /* cleanup the connectivity info due to the 'to' subdomain */ \ 252 for (k=0; k<nads[to]; k++) \ 253 vtmp[adids[to][k]] = 0; \ 254 } \ 255 } while (0) 256 257 258 #endif 259