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 PetscTableAddExpand(ta, key, data, imode);
 76:       return 0;
 77:     }
 78:     hash = (hash + hashstep) % ta->tablesize;
 79:   }
 80:   SETERRQ(PETSC_COMM_SELF, PETSC_ERR_COR, "Full table");
 81:   /* return 0; */
 82: }

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


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

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

118:   *data = 0;

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

133: #endif