Actual source code: ctable.c

      1: /* Contributed by - Mark Adams */

      3: #define PETSC_SKIP_PETSCTABLE_DEPRECATION_WARNING

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    190:   PetscFunctionBegin;
    191:   PetscAssertPointer(ta, 1);
    192:   PetscAssertPointer(ppos, 2);
    193:   *ppos = NULL;
    194:   if (!ta->count) PetscFunctionReturn(PETSC_SUCCESS);

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

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

    217:   PetscFunctionBegin;
    218:   PetscAssertPointer(ta, 1);
    219:   PetscAssertPointer(rPosition, 2);
    220:   PetscAssertPointer(pkey, 3);
    221:   PetscAssertPointer(data, 4);
    222:   pos = *rPosition;
    223:   PetscCheck(pos, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null position");
    224:   *data = *pos;
    225:   PetscCheck(*data, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null data");
    226:   idex  = (PetscInt)(pos - ta->table);
    227:   *pkey = ta->keytable[idex];
    228:   PetscCheck(*pkey, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null key");

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

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

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

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

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

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

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