Actual source code: ctable.c
petsc-3.13.6 2020-09-29
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: PetscTable ta;
85: PetscNew(&ta);
86: ta->tablesize = intable->tablesize;
87: PetscMalloc1(ta->tablesize,&ta->keytable);
88: PetscMalloc1(ta->tablesize,&ta->table);
89: PetscMemcpy(ta->keytable,intable->keytable,ta->tablesize*sizeof(PetscInt));
90: PetscMemcpy(ta->table,intable->table,ta->tablesize*sizeof(PetscInt));
91: #if defined(PETSC_USE_DEBUG)
92: {
93: PetscInt i;
94: for (i = 0; i < ta->tablesize; i++) {
95: if (ta->keytable[i] < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->keytable[i] < 0");
96: }
97: }
98: #endif
99: ta->head = 0;
100: ta->count = intable->count;
101: ta->maxkey = intable->maxkey;
102: *rta = ta;
103: return(0);
104: }
106: /* PetscTableDestroy() ********************************************
107: *
108: *
109: */
110: PetscErrorCode PetscTableDestroy(PetscTable *ta)
111: {
115: if (!*ta) return(0);
116: PetscFree((*ta)->keytable);
117: PetscFree((*ta)->table);
118: PetscFree(*ta);
119: return(0);
120: }
122: /* PetscTableGetCount() ********************************************
123: */
124: PetscErrorCode PetscTableGetCount(const PetscTable ta,PetscInt *count)
125: {
127: *count = ta->count;
128: return(0);
129: }
131: /* PetscTableIsEmpty() ********************************************
132: */
133: PetscErrorCode PetscTableIsEmpty(const PetscTable ta,PetscInt *flag)
134: {
136: *flag = !(ta->count);
137: return(0);
138: }
140: /*
141: PetscTableAddExpand - called by PetscTableAdd() if more space is needed
143: */
144: PetscErrorCode PetscTableAddExpand(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
145: {
147: PetscInt ii = 0;
148: const PetscInt tsize = ta->tablesize,tcount = ta->count;
149: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
152: PetscTableCreateHashSize(ta->tablesize,&ta->tablesize);
153: PetscMalloc1(ta->tablesize,&ta->table);
154: PetscCalloc1(ta->tablesize,&ta->keytable);
156: ta->count = 0;
157: ta->head = 0;
159: PetscTableAdd(ta,key,data,INSERT_VALUES);
160: /* rehash */
161: for (ii = 0; ii < tsize; ii++) {
162: newk = oldkt[ii];
163: if (newk) {
164: ndata = oldtab[ii];
165: PetscTableAdd(ta,newk,ndata,imode);
166: }
167: }
168: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
170: PetscFree(oldtab);
171: PetscFree(oldkt);
172: return(0);
173: }
176: /* PetscTableRemoveAll() ********************************************
177: *
178: *
179: */
180: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
181: {
185: ta->head = 0;
186: if (ta->count) {
187: ta->count = 0;
189: PetscArrayzero(ta->keytable,ta->tablesize);
190: }
191: return(0);
192: }
196: /* PetscTableGetHeadPosition() ********************************************
197: *
198: */
199: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
200: {
201: PetscInt i = 0;
204: *ppos = NULL;
205: if (!ta->count) return(0);
207: /* find first valid place */
208: do {
209: if (ta->keytable[i]) {
210: *ppos = (PetscTablePosition)&ta->table[i];
211: break;
212: }
213: } while (i++ < ta->tablesize);
214: if (!*ppos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"No head");
215: return(0);
216: }
218: /* PetscTableGetNext() ********************************************
219: *
220: * - iteration - PetscTablePosition is always valid (points to a data)
221: *
222: */
223: PetscErrorCode PetscTableGetNext(PetscTable ta,PetscTablePosition *rPosition,PetscInt *pkey,PetscInt *data)
224: {
225: PetscInt idex;
226: PetscTablePosition pos;
229: pos = *rPosition;
230: if (!pos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null position");
231: *data = *pos;
232: if (!*data) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null data");
233: idex = pos - ta->table;
234: *pkey = ta->keytable[idex];
235: if (!*pkey) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null key");
237: /* get next */
238: do {
239: pos++; idex++;
240: if (idex >= ta->tablesize) {
241: pos = NULL; /* end of list */
242: break;
243: } else if (ta->keytable[idex]) {
244: pos = ta->table + idex;
245: break;
246: }
247: } while (idex < ta->tablesize);
248: *rPosition = pos;
249: return(0);
250: }
253: PetscErrorCode PetscTableAddCountExpand(PetscTable ta,PetscInt key)
254: {
256: PetscInt ii = 0,hash = PetscHash(ta,key);
257: const PetscInt tsize = ta->tablesize,tcount = ta->count;
258: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
261: /* before making the table larger check if key is already in table */
262: while (ii++ < tsize) {
263: if (ta->keytable[hash] == key) return(0);
264: hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
265: }
267: ta->tablesize = PetscIntMultTruncate(2,ta->tablesize);
268: 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");
269: PetscMalloc1(ta->tablesize,&ta->table);
270: PetscCalloc1(ta->tablesize,&ta->keytable);
272: ta->count = 0;
273: ta->head = 0;
275: /* Build a new copy of the data */
276: for (ii = 0; ii < tsize; ii++) {
277: newk = oldkt[ii];
278: if (newk) {
279: ndata = oldtab[ii];
280: PetscTableAdd(ta,newk,ndata,INSERT_VALUES);
281: }
282: }
283: PetscTableAddCount(ta,key);
284: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
286: PetscFree(oldtab);
287: PetscFree(oldkt);
288: return(0);
289: }