Actual source code: ctable.c
petsc-3.3-p7 2013-05-11
2: /* Contributed by - Mark Adams */
4: #include <petscsys.h>
9: /*
10: PetscTableCreate Creates a PETSc look up table
12: Input Parameters:
13: + n - expected number of keys
14: - maxkey- largest possible key
16: Notes: keys are between 1 and N inclusive
18: */
19: PetscErrorCode PetscTableCreate(const PetscInt n,PetscInt maxkey,PetscTable *rta)
20: {
21: PetscTable ta;
25: if (n < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"n < 0");
26: PetscNew(struct _n_PetscTable,&ta);
27: ta->tablesize = (3*n)/2 + 17;
28: if (ta->tablesize < n) ta->tablesize = PETSC_MAX_INT/4; /* overflow */
29: PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->keytable);
30: PetscMemzero(ta->keytable,sizeof(PetscInt)*ta->tablesize);
31: PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->table);
32: ta->head = 0;
33: ta->count = 0;
34: ta->maxkey = maxkey;
35: *rta = ta;
36: return(0);
37: }
41: /* PetscTableCreate() ********************************************
42: *
43: * hash table for non-zero data and keys
44: *
45: */
46: PetscErrorCode PetscTableCreateCopy(const PetscTable intable,PetscTable *rta)
47: {
49: PetscInt i;
50: PetscTable ta;
53: PetscNew(struct _n_PetscTable,&ta);
54: ta->tablesize = intable->tablesize;
55: PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->keytable);
56: PetscMalloc(sizeof(PetscInt)*ta->tablesize,&ta->table);
57: for(i = 0; i < ta->tablesize ; i++){
58: ta->keytable[i] = intable->keytable[i];
59: ta->table[i] = intable->table[i];
60: #if defined(PETSC_USE_DEBUG)
61: if (ta->keytable[i] < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->keytable[i] < 0");
62: #endif
63: }
64: ta->head = 0;
65: ta->count = intable->count;
66: ta->maxkey = intable->maxkey;
67: *rta = ta;
68: return(0);
69: }
73: /* PetscTableDestroy() ********************************************
74: *
75: *
76: */
77: PetscErrorCode PetscTableDestroy(PetscTable *ta)
78: {
82: if (!*ta) return(0);
83: PetscFree((*ta)->keytable);
84: PetscFree((*ta)->table);
85: PetscFree(*ta);
86: return(0);
87: }
91: /* PetscTableGetCount() ********************************************
92: */
93: PetscErrorCode PetscTableGetCount(const PetscTable ta,PetscInt *count)
94: {
96: *count = ta->count;
97: return(0);
98: }
102: /* PetscTableIsEmpty() ********************************************
103: */
104: PetscErrorCode PetscTableIsEmpty(const PetscTable ta,PetscInt *flag)
105: {
107: *flag = !(ta->count);
108: return(0);
109: }
113: /*
114: PetscTableAddExpand - called PetscTableAdd() if more space needed
116: */
117: PetscErrorCode PetscTableAddExpand(PetscTable ta,PetscInt key,PetscInt data,InsertMode imode)
118: {
120: PetscInt ii = 0;
121: const PetscInt tsize = ta->tablesize,tcount = ta->count;
122: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
123:
125: if (ta->tablesize == PETSC_MAX_INT/4) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->tablesize < 0");
126: ta->tablesize = 2*tsize;
127: if (ta->tablesize <= tsize) ta->tablesize = PETSC_MAX_INT/4;
128:
129: PetscMalloc(ta->tablesize*sizeof(PetscInt),&ta->table);
130: PetscMalloc(ta->tablesize*sizeof(PetscInt),&ta->keytable);
131: PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));
132:
133: ta->count = 0;
134: ta->head = 0;
135:
136: PetscTableAdd(ta,key,data,INSERT_VALUES);
137: /* rehash */
138: for (ii = 0; ii < tsize; ii++) {
139: newk = oldkt[ii];
140: if (newk) {
141: ndata = oldtab[ii];
142: PetscTableAdd(ta,newk,ndata,imode);
143: }
144: }
145: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
146:
147: PetscFree(oldtab);
148: PetscFree(oldkt);
149: return(0);
150: }
155: /* PetscTableRemoveAll() ********************************************
156: *
157: *
158: */
159: PetscErrorCode PetscTableRemoveAll(PetscTable ta)
160: {
164: ta->head = 0;
165: if (ta->count) {
166: ta->count = 0;
167: PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));
168: }
169: return(0);
170: }
176: /* PetscTableGetHeadPosition() ********************************************
177: *
178: */
179: PetscErrorCode PetscTableGetHeadPosition(PetscTable ta,PetscTablePosition *ppos)
180: {
181: PetscInt i = 0;
184: *ppos = NULL;
185: if (!ta->count) return(0);
186:
187: /* find first valid place */
188: do {
189: if (ta->keytable[i]) {
190: *ppos = (PetscTablePosition)&ta->table[i];
191: break;
192: }
193: } while (i++ < ta->tablesize);
194: if (!*ppos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"No head");
195: return(0);
196: }
200: /* PetscTableGetNext() ********************************************
201: *
202: * - iteration - PetscTablePosition is always valid (points to a data)
203: *
204: */
205: PetscErrorCode PetscTableGetNext(PetscTable ta,PetscTablePosition *rPosition,PetscInt *pkey,PetscInt *data)
206: {
207: PetscInt idex;
208: PetscTablePosition pos;
211: pos = *rPosition;
212: if (!pos) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null position");
213: *data = *pos;
214: if (!*data) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null data");
215: idex = pos - ta->table;
216: *pkey = ta->keytable[idex];
217: if (!*pkey) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Null key");
219: /* get next */
220: do {
221: pos++; idex++;
222: if (idex >= ta->tablesize) {
223: pos = 0; /* 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: }
237: PetscErrorCode PetscTableAddCountExpand(PetscTable ta,PetscInt key)
238: {
240: PetscInt ii = 0,hash = HASHT(ta,key);
241: const PetscInt tsize = ta->tablesize,tcount = ta->count;
242: PetscInt *oldtab = ta->table,*oldkt = ta->keytable,newk,ndata;
243:
245: /* before making the table larger check if key is already in table */
246: while (ii++ < ta->tablesize){
247: if (ta->keytable[hash] == key) return(0);
248: hash = (hash == (ta->tablesize-1)) ? 0 : hash+1;
249: }
250:
251: /* alloc new (bigger) table */
252: if (ta->tablesize == PETSC_MAX_INT/4) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"ta->tablesize < 0");
253: ta->tablesize = 2*tsize;
254: if (ta->tablesize <= tsize) ta->tablesize = PETSC_MAX_INT/4;
255:
256: PetscMalloc(ta->tablesize*sizeof(PetscInt),&ta->table);
257: PetscMalloc(ta->tablesize*sizeof(PetscInt),&ta->keytable);
258: PetscMemzero(ta->keytable,ta->tablesize*sizeof(PetscInt));
259:
260: ta->count = 0;
261: ta->head = 0;
262:
263: /* Build a new copy of the data */
264: for (ii = 0; ii < tsize; ii++) {
265: newk = oldkt[ii];
266: if (newk) {
267: ndata = oldtab[ii];
268: PetscTableAdd(ta,newk,ndata,INSERT_VALUES);
269: }
270: }
271: PetscTableAddCount(ta,key);
272: if (ta->count != tcount + 1) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_COR,"corrupted ta->count");
273:
274: PetscFree(oldtab);
275: PetscFree(oldkt);
276: return(0);
277: }