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: {
 22:   PetscFunctionReturn(x%(unsigned long)ta->tablesize);
 23: }

 27: PETSC_STATIC_INLINE unsigned long PetscHashStep(PetscTable ta,unsigned long x)
 28: {
 30:   PetscFunctionReturn(1+(x%(unsigned long)(ta->tablesize-1)));
 31: }

 33: PETSC_EXTERN PetscErrorCode PetscTableCreate(const PetscInt,PetscInt,PetscTable*);
 34: PETSC_EXTERN PetscErrorCode PetscTableCreateCopy(const PetscTable,PetscTable*);
 35: PETSC_EXTERN PetscErrorCode PetscTableDestroy(PetscTable*);
 36: PETSC_EXTERN PetscErrorCode PetscTableGetCount(const PetscTable,PetscInt*);
 37: PETSC_EXTERN PetscErrorCode PetscTableIsEmpty(const PetscTable,PetscInt*);
 38: PETSC_EXTERN PetscErrorCode PetscTableAddExpand(PetscTable,PetscInt,PetscInt,InsertMode);
 39: PETSC_EXTERN PetscErrorCode PetscTableAddCountExpand(PetscTable,PetscInt);
 40: PETSC_EXTERN PetscErrorCode PetscTableGetHeadPosition(PetscTable,PetscTablePosition*);
 41: PETSC_EXTERN PetscErrorCode PetscTableGetNext(PetscTable,PetscTablePosition*,PetscInt*,PetscInt*);
 42: PETSC_EXTERN PetscErrorCode PetscTableRemoveAll(PetscTable);

 46: PETSC_STATIC_INLINE PetscErrorCode PetscTableAdd(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
 47: {
 49:   PetscInt       i,hash = (PetscInt)PetscHash(ta,(unsigned long)key);
 50:   PetscInt       hashstep = (PetscInt)PetscHashStep(ta,(unsigned long)key);

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

 57:   for (i=0; i<ta->tablesize; i++) {
 58:     if (ta->keytable[hash] == key) {
 59:       switch (imode) {
 60:       case INSERT_VALUES:
 61:         ta->table[hash] = data; /* over write */
 62:         break;
 63:       case ADD_VALUES:
 64:         ta->table[hash] += data;
 65:         break;
 66:       case MAX_VALUES:
 67:         ta->table[hash] = PetscMax(ta->table[hash],data);
 68:         break;
 69:       case NOT_SET_VALUES:
 70:       case INSERT_ALL_VALUES:
 71:       case ADD_ALL_VALUES:
 72:       case INSERT_BC_VALUES:
 73:       case ADD_BC_VALUES:
 74:         SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Unsupported InsertMode");
 75:       }
 76:       return(0);
 77:     } else if (!ta->keytable[hash]) {
 78:       if (ta->count < 5*(ta->tablesize/6) - 1) {
 79:         ta->count++; /* add */
 80:         ta->keytable[hash] = key;
 81:         ta->table[hash] = data;
 82:       } else {
 83:         PetscTableAddExpand(ta,key,data,imode);
 84:       }
 85:       return(0);
 86:     }
 87:     hash = (hash + hashstep)%ta->tablesize;
 88:   }
 89:   SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"Full table");
 90:   /* return(0); */
 91: }

 95: PETSC_STATIC_INLINE PetscErrorCode  PetscTableAddCount(PetscTable ta,PetscInt key)
 96: {
 98:   PetscInt       i,hash = (PetscInt)PetscHash(ta,(unsigned long)key);
 99:   PetscInt       hashstep = (PetscInt)PetscHashStep(ta,(unsigned long)key);

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

105:   for (i=0; i<ta->tablesize; i++) {
106:     if (ta->keytable[hash] == key) {
107:       return(0);
108:     } else if (!ta->keytable[hash]) {
109:       if (ta->count < 5*(ta->tablesize/6) - 1) {
110:         ta->count++; /* add */
111:         ta->keytable[hash] = key;
112:         ta->table[hash] = ta->count;
113:       } else {
114:         PetscTableAddCountExpand(ta,key);
115:       }
116:       return(0);
117:     }
118:     hash = (hash + hashstep)%ta->tablesize;
119:   }
120:   SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"Full table");
121:   /* return(0); */
122: }


127: /*
128:     PetscTableFind - checks if a key is in the table

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

132: */
133: PETSC_STATIC_INLINE PetscErrorCode  PetscTableFind(PetscTable ta,PetscInt key,PetscInt *data)
134: {
135:   PetscInt       ii = 0;
136:   PetscInt       hash = (PetscInt)PetscHash(ta,(unsigned long)key);
137:   PetscInt       hashstep = (PetscInt)PetscHashStep(ta,(unsigned long)key);

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

144:   while (ii++ < ta->tablesize) {
145:     if (!ta->keytable[hash]) break;
146:     else if (ta->keytable[hash] == key) {
147:       *data = ta->table[hash];
148:       break;
149:     }
150:     hash = (hash + hashstep)%ta->tablesize;
151:   }
152:   return(0);
153: }

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

159: #endif