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