Actual source code: ctable.c
petsc-3.10.5 2019-03-28
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:
53: keys are between 1 and maxkey inclusive
55: */
56: PetscErrorCode PetscTableCreate(const PetscInt n,PetscInt maxkey,PetscTable *rta)
57: {
58: PetscTable ta;
62: if (n < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"n < 0");
63: PetscNew(&ta);
64: PetscTableCreateHashSize(n,&ta->tablesize);
65: PetscCalloc1(ta->tablesize,&ta->keytable);
66: PetscMalloc1(ta->tablesize,&ta->table);
67: ta->head = 0;
68: ta->count = 0;
69: ta->maxkey = maxkey;
70: *rta = ta;
71: return(0);
72: }
74: /* PetscTableCreate() ********************************************
75: *
76: * hash table for non-zero data and keys
77: *
78: */
79: PetscErrorCode PetscTableCreateCopy(const PetscTable intable,PetscTable *rta)
80: {
82: PetscInt i;
83: PetscTable ta;
86: PetscNew(&ta);
87: ta->tablesize = intable->tablesize;
88: PetscMalloc1(ta->tablesize,&ta->keytable);
89: PetscMalloc1(ta->tablesize,&ta->table);
90: for (i = 0; i < ta->tablesize; i++) {
91: ta->keytable[i] = intable->keytable[i];
92: ta->table[i] = intable->table[i];
93: #if defined(PETSC_USE_DEBUG)
94: if (ta->keytable[i] < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->keytable[i] < 0");
95: #endif
96: }
97: ta->head = 0;
98: ta->count = intable->count;
99: ta->maxkey = intable->maxkey;
100: *rta = ta;
101: return(0);
102: }
104: /* PetscTableDestroy() ********************************************
105: *
106: *
107: */
108: PetscErrorCode PetscTableDestroy(PetscTable *ta)
109: {
113: if (!*ta) return(0);
114: PetscFree((*ta)->keytable);
115: PetscFree((*ta)->table);
116: PetscFree(*ta);
117: return(0);
118: }
120: /* PetscTableGetCount() ********************************************
121: */
122: PetscErrorCode PetscTableGetCount(const PetscTable ta,PetscInt *count)
123: {
125: *count = ta->count;
126: return(0);
127: }
129: /* PetscTableIsEmpty() ********************************************
130: */
131: PetscErrorCode PetscTableIsEmpty(const PetscTable ta,PetscInt *flag)
132: {
134: *flag = !(ta->count);
135: return(0);
136: }
138: /*
139: PetscTableAddExpand - called by PetscTableAdd() if more space is needed
141: */
142: PetscErrorCode PetscTableAddExpand(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
143: {
145: PetscInt ii = 0;
146: const PetscInt tsize = ta->tablesize,tcount = ta->count;
147: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
150: PetscTableCreateHashSize(ta->tablesize,&ta->tablesize);
151: PetscMalloc1(ta->tablesize,&ta->table);
152: PetscCalloc1(ta->tablesize,&ta->keytable);
154: ta->count = 0;
155: ta->head = 0;
157: PetscTableAdd(ta,key,data,INSERT_VALUES);
158: /* rehash */
159: for (ii = 0; ii < tsize; ii++) {
160: newk = oldkt[ii];
161: if (newk) {
162: ndata = oldtab[ii];
163: PetscTableAdd(ta,newk,ndata,imode);
164: }
165: }
166: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
168: PetscFree(oldtab);
169: PetscFree(oldkt);
170: return(0);
171: }
174: /* PetscTableRemoveAll() ********************************************
175: *
176: *
177: */
178: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
179: {
183: ta->head = 0;
184: if (ta->count) {
185: ta->count = 0;
187: PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));
188: }
189: return(0);
190: }
194: /* PetscTableGetHeadPosition() ********************************************
195: *
196: */
197: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
198: {
199: PetscInt i = 0;
202: *ppos = NULL;
203: if (!ta->count) return(0);
205: /* find first valid place */
206: do {
207: if (ta->keytable[i]) {
208: *ppos = (PetscTablePosition)&ta->table[i];
209: break;
210: }
211: } while (i++ < ta->tablesize);
212: if (!*ppos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"No head");
213: return(0);
214: }
216: /* PetscTableGetNext() ********************************************
217: *
218: * - iteration - PetscTablePosition is always valid (points to a data)
219: *
220: */
221: PetscErrorCode PetscTableGetNext(PetscTable ta,PetscTablePosition *rPosition,PetscInt *pkey,PetscInt *data)
222: {
223: PetscInt idex;
224: PetscTablePosition pos;
227: pos = *rPosition;
228: if (!pos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null position");
229: *data = *pos;
230: if (!*data) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null data");
231: idex = pos - ta->table;
232: *pkey = ta->keytable[idex];
233: if (!*pkey) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null key");
235: /* get next */
236: do {
237: pos++; idex++;
238: if (idex >= ta->tablesize) {
239: pos = 0; /* end of list */
240: break;
241: } else if (ta->keytable[idex]) {
242: pos = ta->table + idex;
243: break;
244: }
245: } while (idex < ta->tablesize);
246: *rPosition = pos;
247: return(0);
248: }
251: PetscErrorCode PetscTableAddCountExpand(PetscTable ta,PetscInt key)
252: {
254: PetscInt ii = 0,hash = PetscHash(ta,key);
255: const PetscInt tsize = ta->tablesize,tcount = ta->count;
256: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
259: /* before making the table larger check if key is already in table */
260: while (ii++ < tsize) {
261: if (ta->keytable[hash] == key) return(0);
262: hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
263: }
265: ta->tablesize = PetscIntMultTruncate(2,ta->tablesize);
266: 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");
267: PetscMalloc1(ta->tablesize,&ta->table);
268: PetscCalloc1(ta->tablesize,&ta->keytable);
270: ta->count = 0;
271: ta->head = 0;
273: /* Build a new copy of the data */
274: for (ii = 0; ii < tsize; ii++) {
275: newk = oldkt[ii];
276: if (newk) {
277: ndata = oldtab[ii];
278: PetscTableAdd(ta,newk,ndata,INSERT_VALUES);
279: }
280: }
281: PetscTableAddCount(ta,key);
282: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
284: PetscFree(oldtab);
285: PetscFree(oldkt);
286: return(0);
287: }