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: Notes:
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++; idex++;
222: if (idex >= ta->tablesize) {
223: pos = NULL; /* end of list */
224: break;
225: } else if (ta->keytable[idex]) {
226: pos = ta->table + idex;
227: break;
228: }
229: } while (idex < ta->tablesize);
230: *rPosition = pos;
231: return 0;
232: }
234: PetscErrorCode PetscTableAddCountExpand(PetscTable ta,PetscInt key)
235: {
236: PetscInt ii = 0,hash = PetscHash(ta,key);
237: const PetscInt tsize = ta->tablesize,tcount = ta->count;
238: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
240: /* before making the table larger check if key is already in table */
241: while (ii++ < tsize) {
242: if (ta->keytable[hash] == key) return 0;
243: hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
244: }
246: ta->tablesize = PetscIntMultTruncate(2,ta->tablesize);
248: PetscMalloc1(ta->tablesize,&ta->table);
249: PetscCalloc1(ta->tablesize,&ta->keytable);
251: ta->count = 0;
252: ta->head = 0;
254: /* Build a new copy of the data */
255: for (ii = 0; ii < tsize; ii++) {
256: newk = oldkt[ii];
257: if (newk) {
258: ndata = oldtab[ii];
259: PetscTableAdd(ta,newk,ndata,INSERT_VALUES);
260: }
261: }
262: PetscTableAddCount(ta,key);
265: PetscFree(oldtab);
266: PetscFree(oldkt);
267: return 0;
268: }