Actual source code: ctable.c


  2: /* Contributed by - Mark Adams */

  4: #define PETSC_SKIP_PETSCTABLE_DEPRECATION_WARNING

  6: #include <petsc/private/petscimpl.h>
  7: #include <petscctable.h>

  9: static PetscErrorCode PetscTableCreateHashSize(PetscInt sz, PetscInt *hsz)
 10: {
 11:   PetscFunctionBegin;
 12:   if (sz < 100) *hsz = 139;
 13:   else if (sz < 200) *hsz = 283;
 14:   else if (sz < 400) *hsz = 577;
 15:   else if (sz < 800) *hsz = 1103;
 16:   else if (sz < 1600) *hsz = 2239;
 17:   else if (sz < 3200) *hsz = 4787;
 18:   else if (sz < 6400) *hsz = 9337;
 19:   else if (sz < 12800) *hsz = 17863;
 20:   else if (sz < 25600) *hsz = 37649;
 21:   else if (sz < 51200) *hsz = 72307;
 22:   else if (sz < 102400) *hsz = 142979;
 23:   else if (sz < 204800) *hsz = 299983;
 24:   else if (sz < 409600) *hsz = 599869;
 25:   else if (sz < 819200) *hsz = 1193557;
 26:   else if (sz < 1638400) *hsz = 2297059;
 27:   else if (sz < 3276800) *hsz = 4902383;
 28:   else if (sz < 6553600) *hsz = 9179113;
 29:   else if (sz < 13107200) *hsz = 18350009;
 30:   else if (sz < 26214400) *hsz = 36700021;
 31:   else if (sz < 52428800) *hsz = 73400279;
 32:   else if (sz < 104857600) *hsz = 146800471;
 33:   else if (sz < 209715200) *hsz = 293601569;
 34:   else if (sz < 419430400) *hsz = 587202269;
 35:   else if (sz < 838860800) *hsz = 1175862839;
 36:   else if (sz < 1677721600) *hsz = 2147321881;
 37: #if defined(PETSC_USE_64BIT_INDICES)
 38:   else if (sz < 3355443200l) *hsz = 4695452647l;
 39:   else if (sz < 6710886400l) *hsz = 9384888067l;
 40:   else if (sz < 13421772800l) *hsz = 18787024237l;
 41:   else if (sz < 26843545600l) *hsz = 32416190071l;
 42: #endif
 43:   else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "A really huge hash is being requested.. cannot process: %" PetscInt_FMT, sz);
 44:   PetscFunctionReturn(PETSC_SUCCESS);
 45: }

 47: /*
 48:    PetscTableCreate  Creates a PETSc look up table

 50:    Input Parameters:
 51: +     n - expected number of keys
 52: -     maxkey- largest possible key

 54:    Note:
 55:     keys are between 1 and maxkey inclusive

 57: */
 58: PetscErrorCode PetscTableCreate(PetscInt n, PetscInt maxkey, PetscTable *rta)
 59: {
 60:   PetscTable ta;

 62:   PetscFunctionBegin;
 64:   PetscCheck(n >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "n < 0");
 65:   PetscCall(PetscNew(&ta));
 66:   PetscCall(PetscTableCreateHashSize(n, &ta->tablesize));
 67:   PetscCall(PetscCalloc1(ta->tablesize, &ta->keytable));
 68:   PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
 69:   ta->maxkey = maxkey;
 70:   *rta       = ta;
 71:   PetscFunctionReturn(PETSC_SUCCESS);
 72: }

 74: /* PetscTableCreate() ********************************************
 75:  *
 76:  * hash table for non-zero data and keys
 77:  *
 78:  */
 79: PetscErrorCode PetscTableCreateCopy(const PetscTable intable, PetscTable *rta)
 80: {
 81:   PetscTable ta;

 83:   PetscFunctionBegin;
 86:   PetscCall(PetscNew(&ta));
 87:   ta->tablesize = intable->tablesize;
 88:   PetscCall(PetscMalloc1(ta->tablesize, &ta->keytable));
 89:   PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
 90:   PetscCall(PetscMemcpy(ta->keytable, intable->keytable, ta->tablesize * sizeof(PetscInt)));
 91:   PetscCall(PetscMemcpy(ta->table, intable->table, ta->tablesize * sizeof(PetscInt)));
 92:   for (PetscInt i = 0; i < ta->tablesize; i++) PetscAssert(ta->keytable[i] >= 0, PETSC_COMM_SELF, PETSC_ERR_COR, "ta->keytable[i] < 0");
 93:   ta->count  = intable->count;
 94:   ta->maxkey = intable->maxkey;
 95:   *rta       = ta;
 96:   PetscFunctionReturn(PETSC_SUCCESS);
 97: }

 99: /* PetscTableDestroy() ********************************************
100:  *
101:  *
102:  */
103: PetscErrorCode PetscTableDestroy(PetscTable *ta)
104: {
105:   PetscFunctionBegin;
106:   if (!*ta) PetscFunctionReturn(PETSC_SUCCESS);
107:   PetscCall(PetscFree((*ta)->keytable));
108:   PetscCall(PetscFree((*ta)->table));
109:   PetscCall(PetscFree(*ta));
110:   PetscFunctionReturn(PETSC_SUCCESS);
111: }

113: /* PetscTableGetCount() ********************************************
114:  */
115: PetscErrorCode PetscTableGetCount(const PetscTable ta, PetscInt *count)
116: {
117:   PetscFunctionBegin;
120:   *count = ta->count;
121:   PetscFunctionReturn(PETSC_SUCCESS);
122: }

124: /* PetscTableIsEmpty() ********************************************
125:  */
126: PetscErrorCode PetscTableIsEmpty(const PetscTable ta, PetscInt *flag)
127: {
128:   PetscFunctionBegin;
131:   *flag = !(ta->count);
132:   PetscFunctionReturn(PETSC_SUCCESS);
133: }

135: /*
136:     PetscTableAddExpand - called by PetscTableAdd() if more space is needed

138: */
139: PetscErrorCode PetscTableAddExpand(PetscTable ta, PetscInt key, PetscInt data, InsertMode imode)
140: {
141:   const PetscInt tsize = ta->tablesize, tcount = ta->count;
142:   PetscInt      *oldtab = ta->table, *oldkt = ta->keytable;

144:   PetscFunctionBegin;
146:   PetscCall(PetscTableCreateHashSize(ta->tablesize, &ta->tablesize));
147:   PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
148:   PetscCall(PetscCalloc1(ta->tablesize, &ta->keytable));

150:   ta->count = 0;
151:   ta->head  = 0;

153:   PetscCall(PetscTableAdd(ta, key, data, INSERT_VALUES));
154:   /* rehash */
155:   for (PetscInt ii = 0; ii < tsize; ++ii) {
156:     PetscInt newk = oldkt[ii];

158:     if (newk) PetscCall(PetscTableAdd(ta, newk, oldtab[ii], imode));
159:   }
160:   PetscCheck(ta->count == tcount + 1, PETSC_COMM_SELF, PETSC_ERR_COR, "corrupted ta->count");

162:   PetscCall(PetscFree(oldtab));
163:   PetscCall(PetscFree(oldkt));
164:   PetscFunctionReturn(PETSC_SUCCESS);
165: }

167: /* PetscTableRemoveAll() ********************************************
168:  *
169:  *
170:  */
171: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
172: {
173:   PetscFunctionBegin;
175:   ta->head = 0;
176:   if (ta->count) {
177:     ta->count = 0;

179:     PetscCall(PetscArrayzero(ta->keytable, ta->tablesize));
180:   }
181:   PetscFunctionReturn(PETSC_SUCCESS);
182: }

184: /* PetscTableGetHeadPosition() ********************************************
185:  *
186:  */
187: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta, PetscTablePosition *ppos)
188: {
189:   PetscInt i = 0;

191:   PetscFunctionBegin;
194:   *ppos = NULL;
195:   if (!ta->count) PetscFunctionReturn(PETSC_SUCCESS);

197:   /* find first valid place */
198:   do {
199:     if (ta->keytable[i]) {
200:       *ppos = (PetscTablePosition)&ta->table[i];
201:       break;
202:     }
203:   } while (i++ < ta->tablesize);
204:   PetscCheck(*ppos, PETSC_COMM_SELF, PETSC_ERR_COR, "No head");
205:   PetscFunctionReturn(PETSC_SUCCESS);
206: }

208: /* PetscTableGetNext() ********************************************
209:  *
210:  *  - iteration - PetscTablePosition is always valid (points to a data)
211:  *
212:  */
213: PetscErrorCode PetscTableGetNext(PetscTable ta, PetscTablePosition *rPosition, PetscInt *pkey, PetscInt *data)
214: {
215:   PetscInt           idex;
216:   PetscTablePosition pos;

218:   PetscFunctionBegin;
223:   pos = *rPosition;
224:   PetscCheck(pos, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null position");
225:   *data = *pos;
226:   PetscCheck(*data, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null data");
227:   idex  = pos - ta->table;
228:   *pkey = ta->keytable[idex];
229:   PetscCheck(*pkey, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null key");

231:   /* get next */
232:   do {
233:     pos++;
234:     idex++;
235:     if (idex >= ta->tablesize) {
236:       pos = NULL; /* end of list */
237:       break;
238:     } else if (ta->keytable[idex]) {
239:       pos = ta->table + idex;
240:       break;
241:     }
242:   } while (idex < ta->tablesize);
243:   *rPosition = pos;
244:   PetscFunctionReturn(PETSC_SUCCESS);
245: }

247: PetscErrorCode PetscTableAddCountExpand(PetscTable ta, PetscInt key)
248: {
249:   PetscInt       ii = 0, hash = PetscHash(ta, key);
250:   const PetscInt tsize = ta->tablesize, tcount = ta->count;
251:   PetscInt      *oldtab = ta->table, *oldkt = ta->keytable, newk, ndata;

253:   PetscFunctionBegin;
254:   /* before making the table larger check if key is already in table */
255:   while (ii++ < tsize) {
256:     if (ta->keytable[hash] == key) PetscFunctionReturn(PETSC_SUCCESS);
257:     hash = (hash == (ta->tablesize - 1)) ? 0 : hash + 1;
258:   }

260:   ta->tablesize = PetscIntMultTruncate(2, ta->tablesize);
261:   PetscCheck(tsize != ta->tablesize, PETSC_COMM_SELF, PETSC_ERR_SUP, "Table is as large as possible; ./configure with the option --with-64-bit-integers to run this large case");
262:   PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
263:   PetscCall(PetscCalloc1(ta->tablesize, &ta->keytable));

265:   ta->count = 0;
266:   ta->head  = 0;

268:   /* Build a new copy of the data */
269:   for (ii = 0; ii < tsize; ii++) {
270:     newk = oldkt[ii];
271:     if (newk) {
272:       ndata = oldtab[ii];
273:       PetscCall(PetscTableAdd(ta, newk, ndata, INSERT_VALUES));
274:     }
275:   }
276:   PetscCall(PetscTableAddCount(ta, key));
277:   PetscCheck(ta->count == tcount + 1, PETSC_COMM_SELF, PETSC_ERR_COR, "corrupted ta->count");

279:   PetscCall(PetscFree(oldtab));
280:   PetscCall(PetscFree(oldkt));
281:   PetscFunctionReturn(PETSC_SUCCESS);
282: }