Actual source code: ctable.c


  2: /* Contributed by - Mark Adams */

  4: #include <petsc/private/petscimpl.h>
  5: #include <petscctable.h>

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

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

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

 51:    Note:
 52:     keys are between 1 and maxkey inclusive

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

 61:   PetscNew(&ta);
 62:   PetscTableCreateHashSize(n, &ta->tablesize);
 63:   PetscCalloc1(ta->tablesize, &ta->keytable);
 64:   PetscMalloc1(ta->tablesize, &ta->table);
 65:   ta->maxkey = maxkey;
 66:   *rta       = ta;
 67:   return 0;
 68: }

 70: /* PetscTableCreate() ********************************************
 71:  *
 72:  * hash table for non-zero data and keys
 73:  *
 74:  */
 75: PetscErrorCode PetscTableCreateCopy(const PetscTable intable, PetscTable *rta)
 76: {
 77:   PetscTable ta;

 81:   PetscNew(&ta);
 82:   ta->tablesize = intable->tablesize;
 83:   PetscMalloc1(ta->tablesize, &ta->keytable);
 84:   PetscMalloc1(ta->tablesize, &ta->table);
 85:   PetscMemcpy(ta->keytable, intable->keytable, ta->tablesize * sizeof(PetscInt));
 86:   PetscMemcpy(ta->table, intable->table, ta->tablesize * sizeof(PetscInt));
 87:   for (PetscInt i = 0; i < ta->tablesize; i++) PetscAssert(ta->keytable[i] >= 0, PETSC_COMM_SELF, PETSC_ERR_COR, "ta->keytable[i] < 0");
 88:   ta->count  = intable->count;
 89:   ta->maxkey = intable->maxkey;
 90:   *rta       = ta;
 91:   return 0;
 92: }

 94: /* PetscTableDestroy() ********************************************
 95:  *
 96:  *
 97:  */
 98: PetscErrorCode PetscTableDestroy(PetscTable *ta)
 99: {
100:   if (!*ta) return 0;
101:   PetscFree((*ta)->keytable);
102:   PetscFree((*ta)->table);
103:   PetscFree(*ta);
104:   return 0;
105: }

107: /* PetscTableGetCount() ********************************************
108:  */
109: PetscErrorCode PetscTableGetCount(const PetscTable ta, PetscInt *count)
110: {
113:   *count = ta->count;
114:   return 0;
115: }

117: /* PetscTableIsEmpty() ********************************************
118:  */
119: PetscErrorCode PetscTableIsEmpty(const PetscTable ta, PetscInt *flag)
120: {
123:   *flag = !(ta->count);
124:   return 0;
125: }

127: /*
128:     PetscTableAddExpand - called by PetscTableAdd() if more space is needed

130: */
131: PetscErrorCode PetscTableAddExpand(PetscTable ta, PetscInt key, PetscInt data, InsertMode imode)
132: {
133:   const PetscInt tsize = ta->tablesize, tcount = ta->count;
134:   PetscInt      *oldtab = ta->table, *oldkt = ta->keytable;

137:   PetscTableCreateHashSize(ta->tablesize, &ta->tablesize);
138:   PetscMalloc1(ta->tablesize, &ta->table);
139:   PetscCalloc1(ta->tablesize, &ta->keytable);

141:   ta->count = 0;
142:   ta->head  = 0;

144:   PetscTableAdd(ta, key, data, INSERT_VALUES);
145:   /* rehash */
146:   for (PetscInt ii = 0; ii < tsize; ++ii) {
147:     PetscInt newk = oldkt[ii];

149:     if (newk) PetscTableAdd(ta, newk, oldtab[ii], imode);
150:   }

153:   PetscFree(oldtab);
154:   PetscFree(oldkt);
155:   return 0;
156: }

158: /* PetscTableRemoveAll() ********************************************
159:  *
160:  *
161:  */
162: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
163: {
165:   ta->head = 0;
166:   if (ta->count) {
167:     ta->count = 0;

169:     PetscArrayzero(ta->keytable, ta->tablesize);
170:   }
171:   return 0;
172: }

174: /* PetscTableGetHeadPosition() ********************************************
175:  *
176:  */
177: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta, PetscTablePosition *ppos)
178: {
179:   PetscInt i = 0;

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

186:   /* find first valid place */
187:   do {
188:     if (ta->keytable[i]) {
189:       *ppos = (PetscTablePosition)&ta->table[i];
190:       break;
191:     }
192:   } while (i++ < ta->tablesize);
194:   return 0;
195: }

197: /* PetscTableGetNext() ********************************************
198:  *
199:  *  - iteration - PetscTablePosition is always valid (points to a data)
200:  *
201:  */
202: PetscErrorCode PetscTableGetNext(PetscTable ta, PetscTablePosition *rPosition, PetscInt *pkey, PetscInt *data)
203: {
204:   PetscInt           idex;
205:   PetscTablePosition pos;

211:   pos = *rPosition;
213:   *data = *pos;
215:   idex  = pos - ta->table;
216:   *pkey = ta->keytable[idex];

219:   /* get next */
220:   do {
221:     pos++;
222:     idex++;
223:     if (idex >= ta->tablesize) {
224:       pos = NULL; /* end of list */
225:       break;
226:     } else if (ta->keytable[idex]) {
227:       pos = ta->table + idex;
228:       break;
229:     }
230:   } while (idex < ta->tablesize);
231:   *rPosition = pos;
232:   return 0;
233: }

235: PetscErrorCode PetscTableAddCountExpand(PetscTable ta, PetscInt key)
236: {
237:   PetscInt       ii = 0, hash = PetscHash(ta, key);
238:   const PetscInt tsize = ta->tablesize, tcount = ta->count;
239:   PetscInt      *oldtab = ta->table, *oldkt = ta->keytable, newk, ndata;

241:   /* before making the table larger check if key is already in table */
242:   while (ii++ < tsize) {
243:     if (ta->keytable[hash] == key) return 0;
244:     hash = (hash == (ta->tablesize - 1)) ? 0 : hash + 1;
245:   }

247:   ta->tablesize = PetscIntMultTruncate(2, ta->tablesize);
249:   PetscMalloc1(ta->tablesize, &ta->table);
250:   PetscCalloc1(ta->tablesize, &ta->keytable);

252:   ta->count = 0;
253:   ta->head  = 0;

255:   /* Build a new copy of the data */
256:   for (ii = 0; ii < tsize; ii++) {
257:     newk = oldkt[ii];
258:     if (newk) {
259:       ndata = oldtab[ii];
260:       PetscTableAdd(ta, newk, ndata, INSERT_VALUES);
261:     }
262:   }
263:   PetscTableAddCount(ta, key);

266:   PetscFree(oldtab);
267:   PetscFree(oldkt);
268:   return 0;
269: }