Actual source code: ctable.c

      1: #define PETSC_DLL
      2: /* Contributed by - Mark Adams */

     4:  #include petsc.h
     5:  #include src/sys/ctable.h
      6: #if defined (PETSC_HAVE_LIMITS_H)
      7: #include <limits.h>
      8: #endif
      9: #define HASH_FACT 79943
     10: #define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned long)x)%ta->tablesize))

     14: /* PetscTableCreate() ********************************************
     15:  *
     16:  * hash table for non-zero data and keys
     17:  *
     18:  */
     19: PetscErrorCode PETSC_DLLEXPORT PetscTableCreate(const PetscInt n,PetscTable *rta)
     20: {
     21:   PetscTable     ta;

     25:   if (n < 0) SETERRQ(PETSC_ERR_ARG_OUTOFRANGE,"n < 0");
     26:   PetscNew(struct _p_PetscTable,&ta);
     27:   ta->tablesize = (3*n)/2 + 17;
     28:   if (ta->tablesize < n) ta->tablesize = INT_MAX/4; /* overflow */
     29:   PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->keytable);
     30:   PetscMemzero(ta->keytable,sizeof(PetscInt)*ta->tablesize);
     31:   PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->table);
     32:   ta->head      = 0;
     33:   ta->count     = 0;
     34:   *rta          = ta;
     35:   return(0);
     36: }

     40: /* PetscTableCreate() ********************************************
     41:  *
     42:  * hash table for non-zero data and keys
     43:  *
     44:  */
     45: PetscErrorCode PETSC_DLLEXPORT PetscTableCreateCopy(const PetscTable intable,PetscTable *rta)
     46: {
     48:   PetscInt       i;
     49:   PetscTable     ta;

     52:   PetscNew(struct _p_PetscTable,&ta);
     53:   ta->tablesize = intable->tablesize;
     54:   PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->keytable);
     55:   PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->table);
     56:   for(i = 0 ; i < ta->tablesize ; i++){
     57:     ta->keytable[i] = intable->keytable[i];
     58:     ta->table[i]    = intable->table[i];
     59: #if defined(PETSC_USE_DEBUG)
     60:     if (ta->keytable[i] < 0) SETERRQ(PETSC_ERR_COR,"ta->keytable[i] < 0");
     61: #endif
     62:  }
     63:   ta->head  = 0;
     64:   ta->count = intable->count;
     65:   *rta      = ta;
     66:   return(0);
     67: }

     71: /* PetscTableDelete() ********************************************
     72:  *
     73:  *
     74:  */
     75: PetscErrorCode PETSC_DLLEXPORT PetscTableDelete(PetscTable ta)
     76: {

     80:   PetscFree(ta->keytable);
     81:   PetscFree(ta->table);
     82:   PetscFree(ta);
     83:   return(0);
     84: }
     87: /* PetscTableGetCount() ********************************************
     88:  */
     89: PetscErrorCode PETSC_DLLEXPORT PetscTableGetCount(const PetscTable ta,PetscInt *count)
     90: {
     92:   *count = ta->count;
     93:   return(0);
     94: }

     98: /* PetscTableIsEmpty() ********************************************
     99:  */
    100: PetscErrorCode PETSC_DLLEXPORT PetscTableIsEmpty(const PetscTable ta,PetscInt *flag)
    101: {
    103:   *flag = !(ta->count);
    104:   return(0);
    105: }

    109: /* PetscTableAdd() ********************************************
    110:  *
    111:  */
    112: PetscErrorCode PETSC_DLLEXPORT PetscTableAdd(PetscTable ta,const PetscInt key,const PetscInt data)
    113: {
    115:   PetscInt       ii = 0,hash = HASHT(ta,key);
    116:   const PetscInt tsize = ta->tablesize,tcount = ta->count;
    117:
    119:   if (key <= 0) SETERRQ(PETSC_ERR_COR,"key <= 0");
    120:   if (!data) SETERRQ(PETSC_ERR_COR,"Null data");
    121:
    122:   if (ta->count < 5*(ta->tablesize/6) - 1) {
    123:     while (ii++ < ta->tablesize){
    124:       if (ta->keytable[hash] == key) {
    125:         ta->table[hash] = data; /* over write */
    126:         return(0);
    127:       } else if (!ta->keytable[hash]) {
    128:         ta->count++; /* add */
    129:         ta->keytable[hash] = key; ta->table[hash] = data;
    130:         return(0);
    131:       }
    132:       hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
    133:     }
    134:     SETERRQ(PETSC_ERR_COR,"Full table");
    135:   } else {
    136:     PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;

    138:     /* alloc new (bigger) table */
    139:     if (ta->tablesize == INT_MAX/4) SETERRQ(PETSC_ERR_COR,"ta->tablesize < 0");
    140:     ta->tablesize = 2*tsize;
    141:     if (ta->tablesize <= tsize) ta->tablesize = INT_MAX/4;

    143:     PetscMalloc(ta->tablesize*sizeof(PetscInt),&ta->table);
    144:     PetscMalloc(ta->tablesize*sizeof(PetscInt),&ta->keytable);
    145:     PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));

    147:     ta->count     = 0;
    148:     ta->head      = 0;
    149:
    150:     PetscTableAdd(ta,key,data);
    151:     /* rehash */
    152:     for (ii = 0; ii < tsize; ii++) {
    153:       newk = oldkt[ii];
    154:       if (newk) {
    155:         ndata = oldtab[ii];
    156:         PetscTableAdd(ta,newk,ndata);
    157:       }
    158:     }
    159:     if (ta->count != tcount + 1) SETERRQ(PETSC_ERR_COR,"corrupted ta->count");
    160:
    161:     PetscFree(oldtab);
    162:     PetscFree(oldkt);
    163:   }
    164:   return(0);
    165: }

    169: /* PetscTableRemoveAll() ********************************************
    170:  *
    171:  *
    172:  */
    173: PetscErrorCode PETSC_DLLEXPORT PetscTableRemoveAll(PetscTable ta)
    174: {

    178:   ta->head = 0;
    179:   if (ta->count) {
    180:     ta->count = 0;
    181:     PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));
    182:   }
    183:   return(0);
    184: }

    188: /* PetscTableFind() ********************************************
    189:  *
    190:  * returns data. If data==0, then no table entry exists.
    191:  *
    192:  */
    193: PetscErrorCode PETSC_DLLEXPORT PetscTableFind(PetscTable ta,const PetscInt key,PetscInt *data)
    194: {
    195:   PetscInt hash,ii = 0;

    198:   if (!key) SETERRQ(PETSC_ERR_COR,"Null key");
    199:   hash  = HASHT(ta,key);
    200:   *data = 0;
    201:   while (ii++ < ta->tablesize) {
    202:     if (!ta->keytable[hash]) break;
    203:     else if (ta->keytable[hash] == key) {
    204:       *data = ta->table[hash];
    205:       break;
    206:     }
    207:     hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
    208:   }
    209:   return(0);
    210: }

    214: /* PetscTableGetHeadPosition() ********************************************
    215:  *
    216:  */
    217: PetscErrorCode PETSC_DLLEXPORT PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
    218: {
    219:   PetscInt i = 0;

    222:   *ppos = NULL;
    223:   if (!ta->count) return(0);
    224:
    225:   /* find first valid place */
    226:   do {
    227:     if (ta->keytable[i]) {
    228:       *ppos = (PetscTablePosition)&ta->table[i];
    229:       break;
    230:     }
    231:   } while (i++ < ta->tablesize);
    232:   if (!*ppos) SETERRQ(PETSC_ERR_COR,"No head");
    233:   return(0);
    234: }

    238: /* PetscTableGetNext() ********************************************
    239:  *
    240:  *  - iteration - PetscTablePosition is always valid (points to a data)
    241:  *
    242:  */
    243: PetscErrorCode PETSC_DLLEXPORT PetscTableGetNext(PetscTable ta,PetscTablePosition *rPosition,PetscInt *pkey,PetscInt *data)
    244: {
    245:   PetscInt           idex;
    246:   PetscTablePosition pos;

    249:   pos = *rPosition;
    250:   if (!pos) SETERRQ(PETSC_ERR_COR,"Null position");
    251:   *data = *pos;
    252:   if (!*data) SETERRQ(PETSC_ERR_COR,"Null data");
    253:   idex = pos - ta->table;
    254:   *pkey = ta->keytable[idex];
    255:   if (!*pkey) SETERRQ(PETSC_ERR_COR,"Null key");

    257:   /* get next */
    258:   do {
    259:     pos++;  idex++;
    260:     if (idex >= ta->tablesize) {
    261:       pos = 0; /* end of list */
    262:       break;
    263:     } else if (ta->keytable[idex]) {
    264:       pos = ta->table + idex;
    265:       break;
    266:     }
    267:   } while (idex < ta->tablesize);
    268:   *rPosition = pos;
    269:   return(0);
    270: }