Actual source code: ctable.c
petsc-3.7.7 2017-09-25
2: /* Contributed by - Mark Adams */
4: #include <petscsys.h>
5: #include <petscctable.h>
9: static PetscErrorCode PetscTableCreateHashSize(PetscInt sz, PetscInt *hsz)
10: {
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 SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"A really huge hash is being requested.. cannot process: %D",sz);
44: return(0);
45: }
49: /*
50: PetscTableCreate Creates a PETSc look up table
52: Input Parameters:
53: + n - expected number of keys
54: - maxkey- largest possible key
56: Notes: keys are between 1 and maxkey inclusive
58: */
59: PetscErrorCode PetscTableCreate(const PetscInt n,PetscInt maxkey,PetscTable *rta)
60: {
61: PetscTable ta;
65: if (n < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"n < 0");
66: PetscNew(&ta);
67: PetscTableCreateHashSize(n,&ta->tablesize);
68: PetscCalloc1(ta->tablesize,&ta->keytable);
69: PetscMalloc1(ta->tablesize,&ta->table);
70: ta->head = 0;
71: ta->count = 0;
72: ta->maxkey = maxkey;
73: *rta = ta;
74: return(0);
75: }
79: /* PetscTableCreate() ********************************************
80: *
81: * hash table for non-zero data and keys
82: *
83: */
84: PetscErrorCode PetscTableCreateCopy(const PetscTable intable,PetscTable *rta)
85: {
87: PetscInt i;
88: PetscTable ta;
91: PetscNew(&ta);
92: ta->tablesize = intable->tablesize;
93: PetscMalloc1(ta->tablesize,&ta->keytable);
94: PetscMalloc1(ta->tablesize,&ta->table);
95: for (i = 0; i < ta->tablesize; i++) {
96: ta->keytable[i] = intable->keytable[i];
97: ta->table[i] = intable->table[i];
98: #if defined(PETSC_USE_DEBUG)
99: if (ta->keytable[i] < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->keytable[i] < 0");
100: #endif
101: }
102: ta->head = 0;
103: ta->count = intable->count;
104: ta->maxkey = intable->maxkey;
105: *rta = ta;
106: return(0);
107: }
111: /* PetscTableDestroy() ********************************************
112: *
113: *
114: */
115: PetscErrorCode PetscTableDestroy(PetscTable *ta)
116: {
120: if (!*ta) return(0);
121: PetscFree((*ta)->keytable);
122: PetscFree((*ta)->table);
123: PetscFree(*ta);
124: return(0);
125: }
129: /* PetscTableGetCount() ********************************************
130: */
131: PetscErrorCode PetscTableGetCount(const PetscTable ta,PetscInt *count)
132: {
134: *count = ta->count;
135: return(0);
136: }
140: /* PetscTableIsEmpty() ********************************************
141: */
142: PetscErrorCode PetscTableIsEmpty(const PetscTable ta,PetscInt *flag)
143: {
145: *flag = !(ta->count);
146: return(0);
147: }
151: /*
152: PetscTableAddExpand - called by PetscTableAdd() if more space is needed
154: */
155: PetscErrorCode PetscTableAddExpand(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
156: {
158: PetscInt ii = 0;
159: const PetscInt tsize = ta->tablesize,tcount = ta->count;
160: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
163: PetscTableCreateHashSize(ta->tablesize,&ta->tablesize);
164: PetscMalloc1(ta->tablesize,&ta->table);
165: PetscCalloc1(ta->tablesize,&ta->keytable);
167: ta->count = 0;
168: ta->head = 0;
170: PetscTableAdd(ta,key,data,INSERT_VALUES);
171: /* rehash */
172: for (ii = 0; ii < tsize; ii++) {
173: newk = oldkt[ii];
174: if (newk) {
175: ndata = oldtab[ii];
176: PetscTableAdd(ta,newk,ndata,imode);
177: }
178: }
179: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
181: PetscFree(oldtab);
182: PetscFree(oldkt);
183: return(0);
184: }
189: /* PetscTableRemoveAll() ********************************************
190: *
191: *
192: */
193: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
194: {
198: ta->head = 0;
199: if (ta->count) {
200: ta->count = 0;
202: PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));
203: }
204: return(0);
205: }
211: /* PetscTableGetHeadPosition() ********************************************
212: *
213: */
214: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
215: {
216: PetscInt i = 0;
219: *ppos = NULL;
220: if (!ta->count) return(0);
222: /* find first valid place */
223: do {
224: if (ta->keytable[i]) {
225: *ppos = (PetscTablePosition)&ta->table[i];
226: break;
227: }
228: } while (i++ < ta->tablesize);
229: if (!*ppos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"No head");
230: return(0);
231: }
235: /* PetscTableGetNext() ********************************************
236: *
237: * - iteration - PetscTablePosition is always valid (points to a data)
238: *
239: */
240: PetscErrorCode PetscTableGetNext(PetscTable ta,PetscTablePosition *rPosition,PetscInt *pkey,PetscInt *data)
241: {
242: PetscInt idex;
243: PetscTablePosition pos;
246: pos = *rPosition;
247: if (!pos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null position");
248: *data = *pos;
249: if (!*data) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null data");
250: idex = pos - ta->table;
251: *pkey = ta->keytable[idex];
252: if (!*pkey) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null key");
254: /* get next */
255: do {
256: pos++; idex++;
257: if (idex >= ta->tablesize) {
258: pos = 0; /* end of list */
259: break;
260: } else if (ta->keytable[idex]) {
261: pos = ta->table + idex;
262: break;
263: }
264: } while (idex < ta->tablesize);
265: *rPosition = pos;
266: return(0);
267: }
272: PetscErrorCode PetscTableAddCountExpand(PetscTable ta,PetscInt key)
273: {
275: PetscInt ii = 0,hash = PetscHash(ta,key);
276: const PetscInt tsize = ta->tablesize,tcount = ta->count;
277: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
280: /* before making the table larger check if key is already in table */
281: while (ii++ < tsize) {
282: if (ta->keytable[hash] == key) return(0);
283: hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
284: }
286: ta->tablesize = PetscIntMultTruncate(2,ta->tablesize);
287: if (tsize == ta->tablesize) SETERRQ(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");
288: PetscMalloc1(ta->tablesize,&ta->table);
289: PetscCalloc1(ta->tablesize,&ta->keytable);
291: ta->count = 0;
292: ta->head = 0;
294: /* Build a new copy of the data */
295: for (ii = 0; ii < tsize; ii++) {
296: newk = oldkt[ii];
297: if (newk) {
298: ndata = oldtab[ii];
299: PetscTableAdd(ta,newk,ndata,INSERT_VALUES);
300: }
301: }
302: PetscTableAddCount(ta,key);
303: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
305: PetscFree(oldtab);
306: PetscFree(oldkt);
307: return(0);
308: }