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