Actual source code: ctable.c
2: /* Contributed by - Mark Adams */
4: #define PETSC_SKIP_PETSCTABLE_DEPRECATION_WARNING
6: #include <petsc/private/petscimpl.h>
7: #include <petscctable.h>
9: static PetscErrorCode PetscTableCreateHashSize(PetscInt sz, PetscInt *hsz)
10: {
11: PetscFunctionBegin;
12: if (sz < 100) *hsz = 139;
13: else if (sz < 200) *hsz = 283;
14: else if (sz < 400) *hsz = 577;
15: else if (sz < 800) *hsz = 1103;
16: else if (sz < 1600) *hsz = 2239;
17: else if (sz < 3200) *hsz = 4787;
18: else if (sz < 6400) *hsz = 9337;
19: else if (sz < 12800) *hsz = 17863;
20: else if (sz < 25600) *hsz = 37649;
21: else if (sz < 51200) *hsz = 72307;
22: else if (sz < 102400) *hsz = 142979;
23: else if (sz < 204800) *hsz = 299983;
24: else if (sz < 409600) *hsz = 599869;
25: else if (sz < 819200) *hsz = 1193557;
26: else if (sz < 1638400) *hsz = 2297059;
27: else if (sz < 3276800) *hsz = 4902383;
28: else if (sz < 6553600) *hsz = 9179113;
29: else if (sz < 13107200) *hsz = 18350009;
30: else if (sz < 26214400) *hsz = 36700021;
31: else if (sz < 52428800) *hsz = 73400279;
32: else if (sz < 104857600) *hsz = 146800471;
33: else if (sz < 209715200) *hsz = 293601569;
34: else if (sz < 419430400) *hsz = 587202269;
35: else if (sz < 838860800) *hsz = 1175862839;
36: else if (sz < 1677721600) *hsz = 2147321881;
37: #if defined(PETSC_USE_64BIT_INDICES)
38: else if (sz < 3355443200l) *hsz = 4695452647l;
39: else if (sz < 6710886400l) *hsz = 9384888067l;
40: else if (sz < 13421772800l) *hsz = 18787024237l;
41: else if (sz < 26843545600l) *hsz = 32416190071l;
42: #endif
43: else SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "A really huge hash is being requested.. cannot process: %" PetscInt_FMT, sz);
44: PetscFunctionReturn(PETSC_SUCCESS);
45: }
47: /*
48: PetscTableCreate Creates a PETSc look up table
50: Input Parameters:
51: + n - expected number of keys
52: - maxkey- largest possible key
54: Note:
55: keys are between 1 and maxkey inclusive
57: */
58: PetscErrorCode PetscTableCreate(PetscInt n, PetscInt maxkey, PetscTable *rta)
59: {
60: PetscTable ta;
62: PetscFunctionBegin;
64: PetscCheck(n >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "n < 0");
65: PetscCall(PetscNew(&ta));
66: PetscCall(PetscTableCreateHashSize(n, &ta->tablesize));
67: PetscCall(PetscCalloc1(ta->tablesize, &ta->keytable));
68: PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
69: ta->maxkey = maxkey;
70: *rta = ta;
71: PetscFunctionReturn(PETSC_SUCCESS);
72: }
74: /* PetscTableCreate() ********************************************
75: *
76: * hash table for non-zero data and keys
77: *
78: */
79: PetscErrorCode PetscTableCreateCopy(const PetscTable intable, PetscTable *rta)
80: {
81: PetscTable ta;
83: PetscFunctionBegin;
86: PetscCall(PetscNew(&ta));
87: ta->tablesize = intable->tablesize;
88: PetscCall(PetscMalloc1(ta->tablesize, &ta->keytable));
89: PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
90: PetscCall(PetscMemcpy(ta->keytable, intable->keytable, ta->tablesize * sizeof(PetscInt)));
91: PetscCall(PetscMemcpy(ta->table, intable->table, ta->tablesize * sizeof(PetscInt)));
92: for (PetscInt i = 0; i < ta->tablesize; i++) PetscAssert(ta->keytable[i] >= 0, PETSC_COMM_SELF, PETSC_ERR_COR, "ta->keytable[i] < 0");
93: ta->count = intable->count;
94: ta->maxkey = intable->maxkey;
95: *rta = ta;
96: PetscFunctionReturn(PETSC_SUCCESS);
97: }
99: /* PetscTableDestroy() ********************************************
100: *
101: *
102: */
103: PetscErrorCode PetscTableDestroy(PetscTable *ta)
104: {
105: PetscFunctionBegin;
106: if (!*ta) PetscFunctionReturn(PETSC_SUCCESS);
107: PetscCall(PetscFree((*ta)->keytable));
108: PetscCall(PetscFree((*ta)->table));
109: PetscCall(PetscFree(*ta));
110: PetscFunctionReturn(PETSC_SUCCESS);
111: }
113: /* PetscTableGetCount() ********************************************
114: */
115: PetscErrorCode PetscTableGetCount(const PetscTable ta, PetscInt *count)
116: {
117: PetscFunctionBegin;
120: *count = ta->count;
121: PetscFunctionReturn(PETSC_SUCCESS);
122: }
124: /* PetscTableIsEmpty() ********************************************
125: */
126: PetscErrorCode PetscTableIsEmpty(const PetscTable ta, PetscInt *flag)
127: {
128: PetscFunctionBegin;
131: *flag = !(ta->count);
132: PetscFunctionReturn(PETSC_SUCCESS);
133: }
135: /*
136: PetscTableAddExpand - called by PetscTableAdd() if more space is needed
138: */
139: PetscErrorCode PetscTableAddExpand(PetscTable ta, PetscInt key, PetscInt data, InsertMode imode)
140: {
141: const PetscInt tsize = ta->tablesize, tcount = ta->count;
142: PetscInt *oldtab = ta->table, *oldkt = ta->keytable;
144: PetscFunctionBegin;
146: PetscCall(PetscTableCreateHashSize(ta->tablesize, &ta->tablesize));
147: PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
148: PetscCall(PetscCalloc1(ta->tablesize, &ta->keytable));
150: ta->count = 0;
151: ta->head = 0;
153: PetscCall(PetscTableAdd(ta, key, data, INSERT_VALUES));
154: /* rehash */
155: for (PetscInt ii = 0; ii < tsize; ++ii) {
156: PetscInt newk = oldkt[ii];
158: if (newk) PetscCall(PetscTableAdd(ta, newk, oldtab[ii], imode));
159: }
160: PetscCheck(ta->count == tcount + 1, PETSC_COMM_SELF, PETSC_ERR_COR, "corrupted ta->count");
162: PetscCall(PetscFree(oldtab));
163: PetscCall(PetscFree(oldkt));
164: PetscFunctionReturn(PETSC_SUCCESS);
165: }
167: /* PetscTableRemoveAll() ********************************************
168: *
169: *
170: */
171: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
172: {
173: PetscFunctionBegin;
175: ta->head = 0;
176: if (ta->count) {
177: ta->count = 0;
179: PetscCall(PetscArrayzero(ta->keytable, ta->tablesize));
180: }
181: PetscFunctionReturn(PETSC_SUCCESS);
182: }
184: /* PetscTableGetHeadPosition() ********************************************
185: *
186: */
187: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta, PetscTablePosition *ppos)
188: {
189: PetscInt i = 0;
191: PetscFunctionBegin;
194: *ppos = NULL;
195: if (!ta->count) PetscFunctionReturn(PETSC_SUCCESS);
197: /* find first valid place */
198: do {
199: if (ta->keytable[i]) {
200: *ppos = (PetscTablePosition)&ta->table[i];
201: break;
202: }
203: } while (i++ < ta->tablesize);
204: PetscCheck(*ppos, PETSC_COMM_SELF, PETSC_ERR_COR, "No head");
205: PetscFunctionReturn(PETSC_SUCCESS);
206: }
208: /* PetscTableGetNext() ********************************************
209: *
210: * - iteration - PetscTablePosition is always valid (points to a data)
211: *
212: */
213: PetscErrorCode PetscTableGetNext(PetscTable ta, PetscTablePosition *rPosition, PetscInt *pkey, PetscInt *data)
214: {
215: PetscInt idex;
216: PetscTablePosition pos;
218: PetscFunctionBegin;
223: pos = *rPosition;
224: PetscCheck(pos, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null position");
225: *data = *pos;
226: PetscCheck(*data, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null data");
227: idex = pos - ta->table;
228: *pkey = ta->keytable[idex];
229: PetscCheck(*pkey, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Null key");
231: /* get next */
232: do {
233: pos++;
234: idex++;
235: if (idex >= ta->tablesize) {
236: pos = NULL; /* end of list */
237: break;
238: } else if (ta->keytable[idex]) {
239: pos = ta->table + idex;
240: break;
241: }
242: } while (idex < ta->tablesize);
243: *rPosition = pos;
244: PetscFunctionReturn(PETSC_SUCCESS);
245: }
247: PetscErrorCode PetscTableAddCountExpand(PetscTable ta, PetscInt key)
248: {
249: PetscInt ii = 0, hash = PetscHash(ta, key);
250: const PetscInt tsize = ta->tablesize, tcount = ta->count;
251: PetscInt *oldtab = ta->table, *oldkt = ta->keytable, newk, ndata;
253: PetscFunctionBegin;
254: /* before making the table larger check if key is already in table */
255: while (ii++ < tsize) {
256: if (ta->keytable[hash] == key) PetscFunctionReturn(PETSC_SUCCESS);
257: hash = (hash == (ta->tablesize - 1)) ? 0 : hash + 1;
258: }
260: ta->tablesize = PetscIntMultTruncate(2, ta->tablesize);
261: PetscCheck(tsize != ta->tablesize, PETSC_COMM_SELF, PETSC_ERR_SUP, "Table is as large as possible; ./configure with the option --with-64-bit-integers to run this large case");
262: PetscCall(PetscMalloc1(ta->tablesize, &ta->table));
263: PetscCall(PetscCalloc1(ta->tablesize, &ta->keytable));
265: ta->count = 0;
266: ta->head = 0;
268: /* Build a new copy of the data */
269: for (ii = 0; ii < tsize; ii++) {
270: newk = oldkt[ii];
271: if (newk) {
272: ndata = oldtab[ii];
273: PetscCall(PetscTableAdd(ta, newk, ndata, INSERT_VALUES));
274: }
275: }
276: PetscCall(PetscTableAddCount(ta, key));
277: PetscCheck(ta->count == tcount + 1, PETSC_COMM_SELF, PETSC_ERR_COR, "corrupted ta->count");
279: PetscCall(PetscFree(oldtab));
280: PetscCall(PetscFree(oldkt));
281: PetscFunctionReturn(PETSC_SUCCESS);
282: }