Actual source code: ctable.c


  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: }

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

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

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

191: /* PetscTableGetHeadPosition() ********************************************
192:  *
193:  */
194: PetscErrorCode  PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
195: {
196:   PetscInt i = 0;

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

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

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

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

232:   /* get next */
233:   do {
234:     pos++;  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:   return(0);
245: }

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

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

261:   ta->tablesize = PetscIntMultTruncate(2,ta->tablesize);
262:   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");
263:   PetscMalloc1(ta->tablesize,&ta->table);
264:   PetscCalloc1(ta->tablesize,&ta->keytable);

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

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

280:   PetscFree(oldtab);
281:   PetscFree(oldkt);
282:   return(0);
283: }