1: #ifndef __PETSCCTABLE_H
  3: #include <petscsys.h>

  5: struct _n_PetscTable {
  6:   PetscInt *keytable;
  7:   PetscInt *table;
  8:   PetscInt count;
  9:   PetscInt tablesize;
 10:   PetscInt head;
 11:   PetscInt maxkey;   /* largest key allowed */
 12: };

 14: typedef struct _n_PetscTable* PetscTable;
 15: typedef PetscInt* PetscTablePosition;

 19: PETSC_STATIC_INLINE unsigned long PetscHash(PetscTable ta,unsigned long x)
 20: {
 21: #define PETSC_HASH_FACT 79943
 23:   PetscFunctionReturn((PETSC_HASH_FACT*x)%ta->tablesize);
 24: }

 26: PETSC_EXTERN PetscErrorCode PetscTableCreate(const PetscInt,PetscInt,PetscTable*);
 27: PETSC_EXTERN PetscErrorCode PetscTableCreateCopy(const PetscTable,PetscTable*);
 28: PETSC_EXTERN PetscErrorCode PetscTableDestroy(PetscTable*);
 29: PETSC_EXTERN PetscErrorCode PetscTableGetCount(const PetscTable,PetscInt*);
 30: PETSC_EXTERN PetscErrorCode PetscTableIsEmpty(const PetscTable,PetscInt*);
 31: PETSC_EXTERN PetscErrorCode PetscTableAddExpand(PetscTable,PetscInt,PetscInt,InsertMode);
 32: PETSC_EXTERN PetscErrorCode PetscTableAddCountExpand(PetscTable,PetscInt);
 33: PETSC_EXTERN PetscErrorCode PetscTableGetHeadPosition(PetscTable,PetscTablePosition*);
 34: PETSC_EXTERN PetscErrorCode PetscTableGetNext(PetscTable,PetscTablePosition*,PetscInt*,PetscInt*);
 35: PETSC_EXTERN PetscErrorCode PetscTableRemoveAll(PetscTable);

 39: PETSC_STATIC_INLINE PetscErrorCode PetscTableAdd(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
 40: {
 42:   PetscInt       i,hash = (PetscInt)PetscHash(ta,key);

 45:   if (key <= 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"key <= 0");
 46:   if (key > ta->maxkey) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"key %D is greater than largest key allowed %D",key,ta->maxkey);
 47:   if (!data) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null data");

 49:   for (i=0; i<ta->tablesize; i++) {
 50:     if (ta->keytable[hash] == key) {
 51:       switch (imode) {
 52:       case INSERT_VALUES:
 53:         ta->table[hash] = data; /* over write */
 54:         break;
 55:       case ADD_VALUES:
 56:         ta->table[hash] += data;
 57:         break;
 58:       case MAX_VALUES:
 59:         ta->table[hash] = PetscMax(ta->table[hash],data);
 60:         break;
 61:       default: SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Unsupported InsertMode");
 62:       }
 63:       return(0);
 64:     } else if (!ta->keytable[hash]) {
 65:       if (ta->count < 5*(ta->tablesize/6) - 1) {
 66:         ta->count++; /* add */
 67:         ta->keytable[hash] = key;
 68:         ta->table[hash] = data;
 69:       } else {
 70:         PetscTableAddExpand(ta,key,data,imode);
 71:       }
 72:       return(0);
 73:     }
 74:     hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
 75:   }
 76:   SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"Full table");
 77:   /* return(0); */
 78: }

 82: PETSC_STATIC_INLINE PetscErrorCode  PetscTableAddCount(PetscTable ta,PetscInt key)
 83: {
 85:   PetscInt       i,hash = (PetscInt)PetscHash(ta,key);

 88:   if (key <= 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"key <= 0");
 89:   if (key > ta->maxkey) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"key %D is greater than largest key allowed %D",key,ta->maxkey);

 91:   for (i=0; i<ta->tablesize; i++) {
 92:     if (ta->keytable[hash] == key) {
 93:       return(0);
 94:     } else if (!ta->keytable[hash]) {
 95:       if (ta->count < 5*(ta->tablesize/6) - 1) {
 96:         ta->count++; /* add */
 97:         ta->keytable[hash] = key;
 98:         ta->table[hash] = ta->count;
 99:       } else {
100:         PetscTableAddCountExpand(ta,key);
101:       }
102:       return(0);
103:     }
104:     hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
105:   }
106:   SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"Full table");
107:   /* return(0); */
108: }


113: /*
114:     PetscTableFind - checks if a key is in the table

116:     If data==0, then no table entry exists.

118: */
119: PETSC_STATIC_INLINE PetscErrorCode  PetscTableFind(PetscTable ta,PetscInt key,PetscInt *data)
120: {
121:   PetscInt hash,ii = 0;

124:   *data = 0;
125:   if (key <= 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Key <= 0");
126:   if (key > ta->maxkey) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"key %D is greater than largest key allowed %D",key,ta->maxkey);

128:   hash  = (PetscInt)PetscHash(ta,key);
129:   while (ii++ < ta->tablesize) {
130:     if (!ta->keytable[hash]) break;
131:     else if (ta->keytable[hash] == key) {
132:       *data = ta->table[hash];
133:       break;
134:     }
135:     hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
136:   }
137:   return(0);
138: }

140: /* Reset __FUNCT__ in case the user does not define it themselves */

144: #endif