1: #ifndef PETSCCTABLE_H
  2: #define 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;

 17: static inline unsigned long PetscHash(PetscTable ta,unsigned long x)
 18: {
 19:   return(x%(unsigned long)ta->tablesize);
 20: }

 22: static inline unsigned long PetscHashStep(PetscTable ta,unsigned long x)
 23: {
 24:   return(1+(x%(unsigned long)(ta->tablesize-1)));
 25: }

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

 38: static inline PetscErrorCode PetscTableAdd(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
 39: {
 40:   PetscInt i,hash   = (PetscInt)PetscHash(ta,(unsigned long)key);
 41:   PetscInt hashstep = (PetscInt)PetscHashStep(ta,(unsigned long)key);


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

 86: static inline PetscErrorCode  PetscTableAddCount(PetscTable ta,PetscInt key)
 87: {
 88:   PetscInt i,hash   = (PetscInt)PetscHash(ta,(unsigned long)key);
 89:   PetscInt hashstep = (PetscInt)PetscHashStep(ta,(unsigned long)key);


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

113: /*
114:     PetscTableFind - finds data in table from a given key, if the key is valid but not in the table returns 0
115: */
116: static inline PetscErrorCode  PetscTableFind(PetscTable ta,PetscInt key,PetscInt *data)
117: {
118:   PetscInt ii       = 0;
119:   PetscInt hash     = (PetscInt)PetscHash(ta,(unsigned long)key);
120:   PetscInt hashstep = (PetscInt)PetscHashStep(ta,(unsigned long)key);

122:   *data = 0;

126:   while (ii++ < ta->tablesize) {
127:     if (!ta->keytable[hash]) break;
128:     else if (ta->keytable[hash] == key) {
129:       *data = ta->table[hash];
130:       break;
131:     }
132:     hash = (hash + hashstep)%ta->tablesize;
133:   }
134:   return 0;
135: }

137: #endif