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

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