Actual source code: ctable.c

petsc-3.14.6 2021-03-30
Report Typos and Errors

  2: /* Contributed by - Mark Adams */

  4: #include <petscsys.h>
  5: #include <petscctable.h>

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

 45: /*
 46:    PetscTableCreate  Creates a PETSc look up table

 48:    Input Parameters:
 49: +     n - expected number of keys
 50: -     maxkey- largest possible key

 52:    Notes:
 53:     keys are between 1 and maxkey inclusive

 55: */
 56: PetscErrorCode  PetscTableCreate(const PetscInt n,PetscInt maxkey,PetscTable *rta)
 57: {
 58:   PetscTable     ta;

 62:   if (n < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"n < 0");
 63:   PetscNew(&ta);
 64:   PetscTableCreateHashSize(n,&ta->tablesize);
 65:   PetscCalloc1(ta->tablesize,&ta->keytable);
 66:   PetscMalloc1(ta->tablesize,&ta->table);
 67:   ta->head   = 0;
 68:   ta->count  = 0;
 69:   ta->maxkey = maxkey;
 70:   *rta       = ta;
 71:   return(0);
 72: }

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

 85:   PetscNew(&ta);
 86:   ta->tablesize = intable->tablesize;
 87:   PetscMalloc1(ta->tablesize,&ta->keytable);
 88:   PetscMalloc1(ta->tablesize,&ta->table);
 89:   PetscMemcpy(ta->keytable,intable->keytable,ta->tablesize*sizeof(PetscInt));
 90:   PetscMemcpy(ta->table,intable->table,ta->tablesize*sizeof(PetscInt));
 91:   if (PetscDefined(USE_DEBUG)) {
 92:     PetscInt i;
 93:     for (i = 0; i < ta->tablesize; i++) {
 94:       if (ta->keytable[i] < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->keytable[i] < 0");
 95:     }
 96:   }
 97:   ta->head   = 0;
 98:   ta->count  = intable->count;
 99:   ta->maxkey = intable->maxkey;
100:   *rta       = ta;
101:   return(0);
102: }

104: /* PetscTableDestroy() ********************************************
105:  *
106:  *
107:  */
108: PetscErrorCode  PetscTableDestroy(PetscTable *ta)
109: {

113:   if (!*ta) return(0);
114:   PetscFree((*ta)->keytable);
115:   PetscFree((*ta)->table);
116:   PetscFree(*ta);
117:   return(0);
118: }

120: /* PetscTableGetCount() ********************************************
121:  */
122: PetscErrorCode  PetscTableGetCount(const PetscTable ta,PetscInt *count)
123: {
125:   *count = ta->count;
126:   return(0);
127: }

129: /* PetscTableIsEmpty() ********************************************
130:  */
131: PetscErrorCode  PetscTableIsEmpty(const PetscTable ta,PetscInt *flag)
132: {
134:   *flag = !(ta->count);
135:   return(0);
136: }

138: /*
139:     PetscTableAddExpand - called by PetscTableAdd() if more space is needed

141: */
142: PetscErrorCode  PetscTableAddExpand(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
143: {
145:   PetscInt       ii      = 0;
146:   const PetscInt tsize   = ta->tablesize,tcount = ta->count;
147:   PetscInt       *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;

150:   PetscTableCreateHashSize(ta->tablesize,&ta->tablesize);
151:   PetscMalloc1(ta->tablesize,&ta->table);
152:   PetscCalloc1(ta->tablesize,&ta->keytable);

154:   ta->count = 0;
155:   ta->head  = 0;

157:   PetscTableAdd(ta,key,data,INSERT_VALUES);
158:   /* rehash */
159:   for (ii = 0; ii < tsize; ii++) {
160:     newk = oldkt[ii];
161:     if (newk) {
162:       ndata = oldtab[ii];
163:       PetscTableAdd(ta,newk,ndata,imode);
164:     }
165:   }
166:   if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");

168:   PetscFree(oldtab);
169:   PetscFree(oldkt);
170:   return(0);
171: }


174: /* PetscTableRemoveAll() ********************************************
175:  *
176:  *
177:  */
178: PetscErrorCode  PetscTableRemoveAll(PetscTable ta)
179: {

183:   ta->head = 0;
184:   if (ta->count) {
185:     ta->count = 0;

187:     PetscArrayzero(ta->keytable,ta->tablesize);
188:   }
189:   return(0);
190: }



194: /* PetscTableGetHeadPosition() ********************************************
195:  *
196:  */
197: PetscErrorCode  PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
198: {
199:   PetscInt i = 0;

202:   *ppos = NULL;
203:   if (!ta->count) return(0);

205:   /* find first valid place */
206:   do {
207:     if (ta->keytable[i]) {
208:       *ppos = (PetscTablePosition)&ta->table[i];
209:       break;
210:     }
211:   } while (i++ < ta->tablesize);
212:   if (!*ppos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"No head");
213:   return(0);
214: }

216: /* PetscTableGetNext() ********************************************
217:  *
218:  *  - iteration - PetscTablePosition is always valid (points to a data)
219:  *
220:  */
221: PetscErrorCode  PetscTableGetNext(PetscTable ta,PetscTablePosition *rPosition,PetscInt *pkey,PetscInt *data)
222: {
223:   PetscInt           idex;
224:   PetscTablePosition pos;

227:   pos = *rPosition;
228:   if (!pos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null position");
229:   *data = *pos;
230:   if (!*data) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null data");
231:   idex  = pos - ta->table;
232:   *pkey = ta->keytable[idex];
233:   if (!*pkey) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null key");

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


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

259:   /* before making the table larger check if key is already in table */
260:   while (ii++ < tsize) {
261:     if (ta->keytable[hash] == key) return(0);
262:     hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
263:   }

265:   ta->tablesize = PetscIntMultTruncate(2,ta->tablesize);
266:   if (tsize == ta->tablesize) SETERRQ(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");
267:   PetscMalloc1(ta->tablesize,&ta->table);
268:   PetscCalloc1(ta->tablesize,&ta->keytable);

270:   ta->count = 0;
271:   ta->head  = 0;

273:   /* Build a new copy of the data */
274:   for (ii = 0; ii < tsize; ii++) {
275:     newk = oldkt[ii];
276:     if (newk) {
277:       ndata = oldtab[ii];
278:       PetscTableAdd(ta,newk,ndata,INSERT_VALUES);
279:     }
280:   }
281:   PetscTableAddCount(ta,key);
282:   if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");

284:   PetscFree(oldtab);
285:   PetscFree(oldkt);
286:   return(0);
287: }