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